Re: [PERFORM] Slow query: bitmap scan troubles

Jeff Janes <jeff(dot)janes(at)gmail(dot)com> writes:
> [moved to hackers]
> On Wednesday, December 5, 2012, Tom Lane wrote:
>> Hm. To tell you the truth, in October I'd completely forgotten about
>> the January patch, and was thinking that the 1/10000 cost had a lot
>> of history behind it. But if we never shipped it before 9.2 then of
>> course that idea is false. Perhaps we should backpatch the log curve
>> into 9.2 --- that would reduce the amount of differential between what
>> 9.2 does and what previous branches do for large indexes.

> I think we should backpatch it for 9.2.3. I've seen another email which is
> probably due to the same issue (nested loop vs hash join). And some
> monitoring of a database I am responsible for suggests it might be heading
> in that direction as well as the size grows.

I received an off-list report of a case where not only did the 1/10000
factor cause a nestloop-vs-hashjoin decision to be made wrongly, but
even adding the ln() computation as in commit bf01e34b556 didn't fix it.
I believe the index in question was on the order of 20000 pages, so
it's not too hard to see why this might be the case:

* historical fudge factor 4 * 20000/100000 = 0.8
* 9.2 fudge factor 4 * 20000/10000 = 8.0
* with ln() correction 4 * ln(1 + 20000/10000) = 4.39 or so

At this point I'm about ready to not only revert the 100000-to-10000
change, but keep the ln() adjustment, ie make the calculation be
random_page_cost * ln(1 + index_pages/100000). This would give
essentially the pre-9.2 behavior for indexes up to some tens of
thousands of pages, and keep the fudge factor from getting out of
control even for very very large indexes.

> But I am wondering if it should be present at all in 9.3. When it was
> introduced, the argument seemed to be that smaller indexes might be easier
> to keep in cache.

No. The argument is that if we don't have some such correction, the
planner is liable to believe that different-sized indexes have *exactly
the same cost*, if a given query would fetch the same number of index
entries. This is quite easy to demonstrate when experimenting with
partial indexes, in particular - without the fudge factor the planner
sees no advantage of a partial index over a full index from which the
query would fetch the same number of entries. We do want the planner
to pick the partial index if it's usable, and a fudge factor is about
the least unprincipled way to make it do so.

> The argument for increasing the penalty by a factor of 10 was that the
> smaller one could be "swamped by noise such as page-boundary-roundoff
> behavior".

Yeah, I wrote that, but in hindsight it seems like a mistaken idea.
The noise problem is that because we round off page count and row count
estimates to integers at various places, it's fairly easy for small
changes in statistics to move a plan's estimated cost by significantly
more than this fudge factor will. However, the case that the fudge
factor is meant to fix is indexes that are otherwise identical for
the query's purposes --- and any roundoff effects will be the same.
(The fudge factor itself is *not* rounded off anywhere, it flows
directly to the bottom-line cost for the indexscan.)

> One thing which depends on the index size which, as far as I can tell, is
> not currently being counted is the cost of comparing the tuples all the way
> down the index. This would be proportional to log2(indextuples) *
> cpu_index_tuple_cost, or maybe log2(indextuples) *
> (cpu_index_tuple_cost+cpu_operator_cost), or something like that.

Yeah, I know. I've experimented repeatedly over the years with trying
to account explicitly for index descent costs. But every time, anything
that looks even remotely principled turns out to produce an overly large
correction that results in bad plan choices. I don't know exactly why
this is, but it's true.

One other point is that I think it is better for any such correction
to depend on the index's total page count, not total tuple count,
because otherwise two indexes that are identical except for bloat
effects will appear to have identical costs. So from that standpoint,
the ln() form of the fudge factor seems quite reasonable as a crude form
of index descent cost estimate. The fact that we're needing to dial
it down so much reinforces my feeling that descent costs are close to
negligible in practice.

regards, tom lane