Re: 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 <
a(dot)korotkov(at)postgrespro(dot)ru> wrote:

> 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
>

--
--Regards, Sergey Mirvoda