9.3 Pre-proposal: Range Merge Join

I hope this is not an inappropriate time for 9.3 discussions. The flip
side of asking for submissions in the first couple commitfests means
that I need to submit proposals now.

What is a Range Join?

See attached SQL for example. The key difference is that the join
condition is not equality, but overlaps (&&).

Problem statement: slow. Nested loops are the only option, although they
can benefit from an inner GiST index if available. But if the join is
happening up in the plan tree somewhere, then it's impossible for any
index to be available.

Proposed solution: a modified merge join that can handle ranges.

1. Order the ranges on both sides by the lower bound, then upper bound.
Empty ranges can be excluded entirely.
2. Left := first range on left, Right := first range on right
3. If Left or Right is empty, terminate.
4. If lower(Left) > upper(Right), discard Right, goto 2
5. If lower(Right) > upper(Left), discard Left, goto 2
6. return (Left, Right) as joined tuple
7. Right := next range on right
8. goto 3

If we get step 4 or step 5 keeps getting triggered, and a btree index is
available (ordered by lower bound), we can re-probe to go to the correct
position, and consider that the new top range on that side. This is an
optimization for the case where there are large numbers of ranges with
no match on the other side.

Thanks to Nathan Boley for helping me devise this algorithm. However,
any bugs are mine alone ;)

Weaknesses: I haven't thought through the optimization, but I suspect it
will be hard to be very accurate in the costing. That might be OK,
because there aren't very many options anyway, but I'll need to think it
through.

Questions:

* Is this idea sane? -- that is, are ranges important enough that
people are willing to maintain a new operator?
* The more general problem might be "spatial joins" which can operate
in N dimensions, and I doubt this would work very well in that case.
Does someone know of a spatial join algorithm (without IP claims) that
would be as good as this one for ranges?
* Other thoughts?

Regards,
Jeff Davis