Re: 9.3 Pre-proposal: Range Merge Join

On Mon, Apr 16, 2012 at 10:29 AM, Heikki Linnakangas <
heikki(dot)linnakangas(at)enterprisedb(dot)com> wrote:

> On 16.04.2012 08:40, Jeff Davis wrote:
>
>> Does someone know of a spatial join algorithm (without IP claims) that
>> would be as good as this one for ranges?
>>
>
> I'd be happy with an algorithm that's specific to ranges, too, but my gut
> geeling is that there has to be a lot of research on spatial join
> algorithms out there. Implementing one of them would be more widely
> applicable, so I think we should look into spatial join algorithms first
> and see how far that gets us, before we write something specific to ranges.

There is a good overview article about spatial joins.
http://www.cs.umd.edu/users/hjs/pubs/jacoxtods07.pdf
It shows that there is a lot of methods based on building temporaty
indexes. It might mean that building of temporary GiST index is not a bad
idea.
Also there are methods which looks like extension of Jeff Davis proposal to
the multidimensional case. It is Plane Sweep and External Plane Sweep
methods. However, it might use sophisticated data structures for the
"sweep". And I believe it should use it for good performance.

------
With best regards,
Alexander Korotkov.