Re: [HACKERS] Merge join for GiST - Mailing list pgsql-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 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)
       }
}