Re: kill_prior_tuple and index scan costing

Hi,

reply largely based on a quick IM conversation between Peter and me.

On 2020-03-04 17:13:33 -0800, Peter Geoghegan wrote:
> Both plans are very similar, really. The number of heap accesses and
> B-Tree index page accesses is exactly the same in each case.

Note that bitmap heap scans, currently, have the huge advantage of being
able to efficiently prefetch heap data. That can be a *huge* performance
boon (I've seen several orders of magnitude on SSDs).

There's also some benefits of bitmap heap scans in other ways. For heap
the "single tid" path index->heap lookup locks the page once for each
tid, whereas bitmap heap scans only do that once - adding more lock
cycles obvious can have a noticable performance impact. Not having
interspersed io between index and heap can be beneficial too.

I thought we had optimized the non-lossy bitmap path for heap
(i.e. heapam_scan_bitmap_next_block()) to perform visibility checks more
efficiently than single tid fetches
(i.e. heapam_index_fetch_tuple()). But both use
heap_hot_search_buffer(), even though the number of page locks differs.

I'm a bit surprised that neither heap_hot_search_buffer() nor the "lossy
path" in heapam_scan_bitmap_next_blocks()'s take advantage of the page's
all-visible? I don't really see a good reason for that. The HTSV calls
do show up noticably in profiles, in my experience.

While your recent btree work ensures that we get the heap tids for an
equality lookup in heap order (right?), I don't think we currently have
the planner infrastructure to know that that's the case (since other
index types don't guarantee that) / take it into account for planning?

> But the index scan plan has one non-obvious advantage, that might
> matter a lot in the real world: it can apply the kill_prior_tuple
> optimization. (It is never possible to use the kill_prior_tuple
> optimization during a bitmap index scan.)

Indeed. I've seen this cause very significant issues a couple
times. Basically whenever the handful of very common queries that
touched most of the data switched to bitmap heap scans, the indexes
would explode in size. Due to the index sizes involved there was no way
normal vacuum could clean up dead tuples quickly enough to prevent
bloat, but with kill_prior_tuple that wasn't a problem.

I have wondered whether we could "just" add some support for
kill_prior_tuple to the bitmap index scan infrastructure. Obviously
that'd require some way of calling "back" into the index code once
(several?) tuples on a page are found to be dead during a bitmap heap
scan. Which would require keeping track of additional metadata for each
tuple in the tid bitmap, which is obviously not free and would have to
be conditional.

I don't really like the kill_prior_tuple interface much. But I don't
immediately see how to do better, without increasing the overhead.

> It makes sense that the planner determines that a bitmap index scan is
> faster -- or it used to make sense. Before commit dd299df8, which made
> heap TID a tiebreaker nbtree index column, we might find ourselves
> accessing the same heap page multiple times, pinning it a second or a
> third time within the executor (it depended on very unstable
> implementation details in the nbtree code). These days we should
> *reliably* access the same number of heap pages (and index pages) with
> either plan. (There are a couple of caveats that I'm glossing over for
> now, like pg_upgrade'd indexes.)

Leaving the locking difference pointed out above aside, there still is a
significant difference in how many times we indirectly call into the
index AM, and how much setup work has to be done though?

There's at least one index_getnext_tid() call for each result tuple,
which each time indirectly has to call btgettuple(). And each
btgettuple() has to do checks (do array keys need to be advanced, has
_bt_first() been called). Whereas btgetbitmap() can amortize across
all tuples.

And that's without considering the fact that, to me, btgetbitmap() could
be significantly optimized by adding multiple tuples to the bitmap at
once, rather than doing so one-by-one.

Greetings,

Andres Freund