Re: Merge Join with an Index Optimization

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.

regards, tom lane