Hi,
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. As an example, let's say we are doing equi merge join between two tables with the following data:
(3, 4, 5, 9, 10, 11)
(0, 1, 2, 6, 7, 8)
Currently, even though no tuples would be returned from the merge join, all of the data will be read from both tables. If there are indexes on both tables, pg should be able to execute as follows. Get the tuple with value 3 from the first table and then look up the first value greater than 3 in the second table using the index. In this case, that value would be 6. Since 3 != 6, pg would then look up the lowest value greater than 6 in the first table. This process repeats, and tuples are output whenever the values are equal. This can be thought of as an alternating nested loop join, where the positions in the indexes are maintained. In the case where only one of the tables has an index, this can be thought of as a nested loop join where the inner relation is the table with the index, and the position in that index is maintained while iterating over the outer relation (the outer relation would need to be sorted for this to work).
I can't demonstrate in any benchmarks, but I imagine this would dramatically speed up cases of a merge join between two tables where the number of tuples that satisfy the join condition is small. I don't know the Postgres internals well enough to know if there is anything obvious that would prevent this optimization.
Thanks,
Michael
