Re: More thoughts about planner's cost estimates

Tom Lane wrote:

> Another thing that's bothering me is that the index access cost computation
> (in genericcostestimate) is looking sillier and sillier:
>
> /*
> * Estimate the number of index pages that will be retrieved.
> *
> * For all currently-supported index types, the first page of the index is
> * a metadata page, and we should figure on fetching that plus a pro-rated
> * fraction of the remaining pages.
> */
> if (index->pages > 1 && index->tuples > 0)
> {
> numIndexPages = (numIndexTuples / index->tuples) * (index->pages - 1);
> numIndexPages += 1; /* count the metapage too */
> numIndexPages = ceil(numIndexPages);
> }
> else
> numIndexPages = 1.0;
>
> /*
> * Compute the index access cost.
> *
> * Disk cost: our generic assumption is that the index pages will be read
> * sequentially, so they have cost 1.0 each, not random_page_cost.
> */
> *indexTotalCost = numIndexPages;
>
> There are several things wrong with this, at least in its application to
> btrees. It's not counting descent of the btree (ie, touches of the root
> page and intermediate-level pages). On the other hand it's surely
> overcharging for metapage touches. As of CVS tip we cache the metapage in
> the relcache, so it's probably fair to disregard that cost altogether.
> And on the third hand, when we need to retrieve multiple leaf pages it's
> over-optimistic to assume that those'll be purely sequential fetches.
> (That would be approximately true in a freshly-built btree, but not in one
> that's suffered any amount of page splitting or recycling.)
>
>
> I am inclined to think that a reasonable model is to continue to estimate
> the number of index leaf pages touched as above (pro-rating against the
> total number of index entries), to charge random_page_cost per leaf page
> touched, and not to count anything for metapage or tree descent. I
> justify the latter on the grounds that upper tree levels will tend to stay
> in cache because they're touched so often. random_page_cost per leaf page
> may be an overestimate, since sometimes logically adjacent leaf pages will
> be physically adjacent too, but not charging for tree descent should help
> to cancel that out. With this model, the disk cost to fetch a single
> index entry will be estimated as random_page_cost (default 4.0) rather
> than the current fixed 2.0. This shouldn't hurt things too much for
> simple indexscans --- especially since anyone running with a reduced
> random_page_cost won't see as much change. And it will increase the costs
> for bitmap scans that cross many index pages, which is what we need in
> light of Philippe's numbers.
>

This sounds good to me, although the 2.0 -> 4.0 cost jump may cause
(more) cases of people seeing their index scans in pre-8.2 versions
becoming some other type of access in 8.2. I guess a comment about
testing existing applications could be placed in the 8.2 release notes?

> Now we have seen a lot of cases in which indexscans were being drastically
> overestimated, so increasing the cost estimate even more may seem like a
> horrid idea. But I believe that most or all of these cases were ones
> where the same index was being visited many times, and so the real
> estimation failure is not accounting for cache effects across multiple
> indexscans. Rather than being afraid to raise the cost estimate for an
> indexscan in isolation, I think it's time to bite the bullet and do
> something about that.
>
> The big difficulty in modeling cache effects from multiple scans is that
> we usually don't know how many times the index will be scanned. If we did
> have that number, I think it'd be reasonable to use the Mackert and Lohman
> approximation already used in cost_index to estimate the total number of
> index leaf pages fetched over N scans, and then divide by N to get our
> per-scan estimated cost. But because the planner builds cost estimates
> bottom-up, in most scenarios we don't have any idea whether an indexscan
> plan node will be iterated once or many times in the finished plan.
> However there is one case where we do have some information: when
> computing a best_inner_indexscan() for a nestloop join, it'd be reasonable
> to use the estimated size of the outer relation as the loop count.
> And this is exactly the case where we are falling down in practice:
> the complaints we've seen are mostly about overestimating the cost of a
> nestloop-with-inner-index-scan. So I think handling just this case would
> be a big step forward, even if it's not a theoretically pure general
> solution.
>
>

If I understand correctly, this is the case were we normally see folks
needing add several 'set enable_xxx=off' statements to get the nested
loop plan that *actually* works best :-). So, also looks good!

Cheers

Mark