Re: index prefetching

Hi,

Attached is an updated version of this patch series. The first couple
parts (adding batching + updating built-in index AMs) remain the same,
the new part is 0007 which switches index scans to read stream API.

We tried to use read stream API for index prefetching before, and it
didn't seem to be a good fit with that design of the patch. It wasn't
clear what to do about kill tuples, the index AM and read stream had no
way to communicate, etc.

I speculated that with the batching concept it might work better, and I
think that turned out to be the case. The batching is still the core
idea, giving the index AM enough control to make kill tuples work (by
not generating batches spanning multiple leaf pages, or doing something
smarter). And the read stream leverages that too - the next_block
callback returns items from the current batch, and the stream is reset
between batches. This is the same prefetch restriction as with the
explicit prefetching (done using posix_fadvise), except that the
prefetching is done by the read stream.

As I said before, I think this is an acceptable restriction for v1. It
can be relaxed in the future if needed, allowing either cross-leaf
batches and/or multiple in-flight batches. But the patch is complex
enough, and even this simpler patch gives significant benefit.

The main open questions are about how to structure the patch - in which
order to introduce the changes. Right now the patch adds batching, and
then bases the read stream on that.

The batching part now includes explicit prefetching, which is later
removed by 0007. That's mostly to allow comparisons with the read
stream, because that's interesting. Ultimately the explicit prefetch
should be removed, and it'd be just basic batching + read stream.

But then in which order we should introduce the parts? Now the batching
is introduced first, followed by read stream. But I can imagine doing it
the other way too - introducing read stream, and then batching.

Of course, without batching the read stream can't do any prefetching
(for index scans). It'd only simply read the heap pages 1 by 1, just
like now. Only with the batching part it'd be able to prefetch.

I don't see either of those options as obviously superior, but maybe
there are good reasons to pick one? Opinions?

A related question is whether all index scans should use ther read
stream API, or whether there should be a fallback to "regular" read
through ReadBuffer. Right now the read stream is an optional field in
IndexFetchHeapData, initialized only for index AMs supporting batching,
with a couple exceptions for cases where we don't expect batching (and
prefetch) to be very effective (e.g. for systables).

All built-in AMs do support batching, but my plan was to keep the
optional, and I can't  predict if all index AMs can do batching (easily
or even at all).

I've thought maybe we could simulate batching for those AMs by simply
treating individual items (returned by amgettuple) as tiny single-item
batches, and just do everything through the read stream.

But the annoying consequence is that we'd have to reset the stream after
every item, because there's no way to "pause" the stream once it runs
out of the current batch. I haven't measured how expensive that is,
maybe not much, but it seems a bit inconvenient.

I wonder if there's a more natural / convenient way to handle this, when
we really can't look further ahead than at the very next item.

If this "single-item" batch idea is not usable, that means we can't
introduce read stream first. We have to introduce batching first, and
only then do the read stream change.


Opinions? I hope this wasn't too confusing :-(



regards

-- 
Tomas Vondra