Re: Merge join for GiST

On Wed, Apr 12, 2017 at 10:44 PM, Andrew Borodin <borodin(at)octonica(dot)com> wrote:
>> How do you think we should proceed? Which projects do you think should
>> eventually be in core, versus which are fine as extensions?
>
> Some points in favor of Range joins via nbtree:

My patch doesn't require indexes, it can sort the input (and the 5X
improvement that I got included the effort to sort). In fact, I expect
using sort will be more common than maintaining btree indexes on a
range column.

> 1. It's more efficient than B-tree over GiST
> 2. It is already in a patch form
>
> Point against:
> 1. Particular implementation is somewhat leaked abstraction. Inside
> the planner, you check not for capabilities of operator and type, but
> for specific op and type. But I do not know how to fix this.

It's not a specific type, it's the "anyrange" type, so you can define
new range types to take advantage of range merge join.

I can drive the planner changes from the catalog rather than
hard-coded OIDs if we think range merge join is a good solution.

> So, here is my opinion: if we can inside the planner understand that
> join condition involves range specifics (for all available ranges) and
> do Range Merge Join, then this is preferred solution.

Yes, I can do that.

> Yes, Spatial Join, when available, will provide roughly the same scan
> performance. But B-trees are more well known to users new to
> PostgreSQL, and B-trees are faster.

I don't quite follow. I don't think any of these proposals uses btree,
right? Range merge join doesn't need any index, your proposal uses
gist, and PgSphere's crossmatch uses gist.

Regards,
Jeff Davis