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 < a.korot...@postgrespro.ru> wrote: > On Mon, Apr 10, 2017 at 2:53 PM, Andrew Borodin <boro...@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 > -- --Regards, Sergey Mirvoda