Re: Merge join for GiST

On Mon, Apr 10, 2017 at 2:53 PM, Andrew Borodin <borodin(at)octonica(dot)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