Re: Merge Join with an Index Optimization

On Sun, Sep 11, 2016 at 1:20 PM, Tom Lane <tgl(at)sss(dot)pgh(dot)pa(dot)us> wrote:
> Michael Malis <michaelmalis2(at)gmail(dot)com> writes:
>> As I understand it, a merge join will currently read all tuples from both
>> subqueries (besides early termination). I believe it should be possible to
>> take advantages of the indexes on one or both of the tables being read from
>> to skip a large number of tuples that would currently be read.
>
> IIUC, what you're proposing is to replace "read past some tuples in the
> index" with "re-descend the index btree". Yes, that would win if it
> allows skipping over a large number of index entries, but it could lose
> big-time if not. The difficulty is that I don't see how the merge join
> level could predict whether it would win for any particular advance step.
> You'd really need most of the smarts to be in the index AM.
>
> You might want to troll the archives for past discussions of index skip
> scan, which is more or less the same idea (could possibly be exactly the
> same idea, depending on how it's implemented). I think we had arrived
> at the conclusion that re-descent from the root might be appropriate
> when transitioning to another index page, but not intra-page. Anyway
> no one's produced a concrete patch yet.

Interesting it should be brought up.

I was considering the index skip optimization for vacuum at some
point, might as well consider it for regular scans too if I get to
that.

Basically, instead of a simple get next, I was considering adding a
"get next skip until". The caller would be the one responsible for
sending the hint, and the index am would be free to implement the skip
in a smart way if possible.

The interface for vacuum is a bit different in practice, but
conceptually the same.