Re: limit clause breaks query planner? - Mailing list pgsql-performance

As a user, I prefer this solution.  For one, statistics get out of date.  A few updates/ inserts (maybe 3% of the table) can greatly
affect an individual value in the histogram, breaking the location assumptions and create a worst case result.
But when 3% of rows change, the correlation cannot change as drastically as the histogram in the worst case.  When deciding how to go about using the statistics for a query plan, its best to assume that they are not perfect, and that there has been some change since they were last gathered.  This is but one thing that makes the universe perverse :)
The safe assumption is that if the distribution is not random, the expected average number of rows to scan goes up -- this is statistically correct.  With perfect correlation and unknown locations the average expected value number of scanned rows would be ~ half the table.  Equal likelihood of the first 15 rows as the last 15.  Thus, for perfect correlation the average penalty would be half the table scanned, and worst case would be the whole table.  In this case, if the statistics are out of date somewhat, the cost estimate is not likely to be more than a factor of 2 off.  If one were to use the histogram, the cost estimate could be many orders of magnitude off. 
I'm fairly sure the penalty function to use for correlation values can be derived statistically -- or at least approximated well enough for a look up table.
If the histogram is used, the odds of it being wrong or out of date have to be taken into account since the penalty for being incorrect is potentially very large -- its not a gradual increase in cost for a small error, it is a big and uncertain increase.  I see the query planner's main goal is to avoid the worst outcomes more than finding the absolute best one.  Better to produce 90% optimized queries 100% of the time than make 100%  perfect plans  90% of the time and then 10% of the time produce very bad plans.  Your suggestion above would do the best job avoiding bad plans but could miss squeezing out that last few % in rare cases that probably don't matter that much.

Because the full scan is compared against more than just index scans (potentially), it makes sense to adjust each accordingly and independently.  Additionally, the index scan cost reduction function and the full table scan cost increase function as correlation changes may have very different, nonlinear 'shapes' between 0 and 1.