Re: [HACKERS] Merge join for GiST

Hi, hackers! I've adapted crossmatch join from pgSphere to cube for performance tests. I've placed spatial join code here https://github.com/Octonica/postgres/blob/spatialjoin/contrib/cube/spatialjoin.c and node code here

Re: [HACKERS] Merge join for GiST

2017-04-13 11:30 GMT+05:00 Jeff Davis : > 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. Merge join will use presorted data, B-tree provides

Re: [HACKERS] Merge join for GiST

On Wed, Apr 12, 2017 at 10:44 PM, Andrew Borodin 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

Re: [HACKERS] Merge join for GiST

2017-04-13 7:01 GMT+05:00 Jeff Davis : > On Tue, Apr 11, 2017 at 8:35 AM, Alexander Korotkov > wrote: >> On Tue, Apr 11, 2017 at 5:46 PM, Jeff Davis wrote: >>> Do you have a sense of how this might compare with range merge join? >>

Re: [HACKERS] Merge join for GiST

On Tue, Apr 11, 2017 at 8:35 AM, Alexander Korotkov wrote: > On Tue, Apr 11, 2017 at 5:46 PM, Jeff Davis wrote: >> Do you have a sense of how this might compare with range merge join? > > > If you have GiST indexes over ranges for both sides of join,

Re: [HACKERS] Merge join for GiST

Thank you, Alexander! This is definitely the example we are looking for! Hat tip to Dmitry especially for this commit https://github.com/akorotkov/pgsphere/commit/971d2c5d61f17774a6d8d137ca3ad87e2883048f Regards, Sergey Mirvoda On Tue, Apr 11, 2017 at 2:17 PM, Alexander Korotkov <

Re: [HACKERS] Merge join for GiST

2017-04-11 14:17 GMT+05:00 Alexander Korotkov : > FYI, I've implemented this algorithm for pgsphere. See following branch. > https://github.com/akorotkov/pgsphere/tree/experimental > It's implemented as crossmatch() function which takes as arguments names of > two

Re: [HACKERS] Merge join for GiST

On Tue, Apr 11, 2017 at 5:46 PM, Jeff Davis wrote: > On Tue, Apr 11, 2017 at 2:17 AM, Alexander Korotkov > wrote: > > FYI, I've implemented this algorithm for pgsphere. See following branch. > >

Re: [HACKERS] Merge join for GiST

On Tue, Apr 11, 2017 at 2:17 AM, Alexander Korotkov wrote: > FYI, I've implemented this algorithm for pgsphere. See following branch. > https://github.com/akorotkov/pgsphere/tree/experimental > It's implemented as crossmatch() function which takes as arguments names of

Re: [HACKERS] Merge join for GiST

On Mon, Apr 10, 2017 at 2:53 PM, Andrew Borodin wrote: > ==Spatial joins== > Scientific papers from the dawn of R-trees and multidimensional > indexes feature a lot of algorithms for spatial joins. > I.e. you have two sets of geometries s1 and s2, you need to produce > all

Re: [HACKERS] Merge join for GiST

2017-04-10 20:38 GMT+05:00 Robert Haas : > On Mon, Apr 10, 2017 at 7:53 AM, Andrew Borodin wrote: >> I think this idea is somewhat related to this patch [2], but as for >> now cannot describe how exactly GiST merge and Range Merge features >> relate. >

Re: [HACKERS] Merge join for GiST

On Mon, Apr 10, 2017 at 7:53 AM, Andrew Borodin wrote: > I think this idea is somewhat related to this patch [2], but as for > now cannot describe how exactly GiST merge and Range Merge features > relate. It also seems somewhat related to Peter Moser's work on ALIGN and

[HACKERS] Merge join for GiST

Hello, hackers! ==Spatial joins== Scientific papers from the dawn of R-trees and multidimensional indexes feature a lot of algorithms for spatial joins. I.e. you have two sets of geometries s1 and s2, you need to produce all colliding pairs (p1,p2) where p1 in s1 and p2 in s2. For 2 R-trees of