Re: [HACKERS] Merge join for GiST

On Mon, Apr 10, 2017 at 2:53 PM, Andrew Borodin <borodin@octonica.com> 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 colliding pairs (p1,p2) where p1 in s1 and p2 in s2. For 2 R-trees
of equal heights with roots R and S most straightforward[1] algorithm
look like:

SpatialJoin (R,S: Node)
{
  FOR (all E in  S)
    FOR (all ER in R with ER.rect intersecting  E.rect)
       IF (R is a leaf page)
       {
         Output ER,ES
       }
       ELSE
       {
         SpatialJoin (ER.ref, ES.ref)
       }
}

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 indexes over spoint and maximum distance (it checks not overlapping but proximity of points).  This function returns setof pairs of TIDs.

Later, Dmitry Ivanov made it a custom scan node.

https://github.com/akorotkov/pgsphere/tree/crossmatch_cnode 

You also can find some experimental evaluation here:

http://www.adass2016.inaf.it/images/presentations/10_Korotkov.pdf

Feel free to experiment with this code and/or ask any question.

------
Alexander Korotkov
Postgres Professional: http://www.postgrespro.com
The Russian Postgres Company