Hilbert R-tree for spatial Index

[Vedic Chawla]

I was thinking more along the lines of an explicit in-line documentation
comments (rust withdrawal), though it makes sense if you don't want to do a
patch just for that either.

On Fri, 27 Jun, 2025, 11:16 pm Darafei "Komяpa" Praliaskouski, <
me at komzpa.net> wrote:

> Hello,
>
> GiST index on geometry in PostGIS is currently a variation of Hilbert
> R-Tree.
> A multiple level of variations actually, as "Hilbert" is a variation
> (running it on floats is going to be in any case), and "R-Tree" is a
> variation (the piece of it that fits into GiST framework).
> It is not mentioned in the docs as it is implementation detail that
> evolves with every release to handle degenerate cases brought in by the
> real world.
>
> To learn more about what we did in one of the last iterations check out
> report by Aliaksandr Kalenik: https://www.youtube.com/watch?v=TG28lRoailE
>
>
> On Fri, Jun 27, 2025 at 8:19 PM Vedic Chawla <chawlavedic8 at gmail.com>
> wrote:
>
>> I just took a look at the source code
>> <https://github.com/postgis/postgis/blob/2a4047bb383d2d94e3b4ab45a71dbe2a332d9ebe/postgis/gserialized_gist_2d.c#L1387> again
>> and it looks like we are already using packed hilbert Rtree. On my first
>> look, I was confused by the layers of abstraction and the lack of any
>> mention of the Hilbert R tree in the official documentation. Maybe we
>> should mention this in the documentation,
>>
>> Regarding Dynamic Hilbert R-trees, The trade offs are not clear to me
>> either, I don't think any of the existing systems implement this. I was
>> thinking along the lines of implementing variation of R-trees on FlatGeoBuf
>> Fork to test it out.
>>
>> I also raised this up in their discussions
>> <https://github.com/flatgeobuf/flatgeobuf/discussions/435> but they are
>> not too keen on potential breaking changes and added complexity. and I
>> agree with them just for the dynamic Hilbert rtree part as most use cases
>> allow you to reindex(repack) once in a while to squeeze any potential query
>> time optimizations out of it. More so for PostGIS as you can append nodes
>> unlike FlatGeoBuf.
>>
>> But If I do decide to go through with it, a loose plan would be to follow
>> the paper <https://www.vldb.org/conf/1994/P500.PDF>.
>>
>> Vedic
>>
>> On Thu, Jun 26, 2025 at 10:26 PM Paul Ramsey <pramsey at cleverelephant.ca>
>> wrote:
>>
>>> This would take a great deal of testing at this point, as our index
>>> implementations have been getting quite close to optimal (famous last
>>> words) so that improvments that appear to bear fruit in one use case damage
>>> performance in others.
>>>
>>> Just straight comparisons of the geos/jts strtree and a packed hilbert
>>> rtree have not shown there to be any huge wins, except to some extent for
>>> build speed, but with a penalty in query performance on the hilbert tree.
>>>
>>> The main thing is that any change to the core rtree has to not degrade
>>> query performance while also not degrading index build performance. The
>>> last time we got into this work was when the GIST pre-sort code was added,
>>> and it was a tight balancing act to avoid making query worse while
>>> improving build time.
>>>
>>> What is your plan, to try and implement a new split algorithm, or
>>> something else (also bear in mind that many potential index improvements
>>> are not available to us due to the restrictions that using the GIST API
>>> layer on top of our code).
>>>
>>> P
>>>
>>> On Jun 26, 2025, at 9:19 AM, Vedic Chawla <chawlavedic8 at gmail.com>
>>> wrote:
>>>
>>> Hi PostGIS community,
>>>
>>> I was doing a feasibility study/survey for optimal Geospatial Index when
>>> I came across this concept.
>>>
>>> Currently, POSTGIS uses R-tree on top of GiST to implement Geospatial
>>> Index. and there has been this GSOC Task[1] to implement Z sort to make
>>> this indexing faster, This should also have the effect of Increasing MSU,
>>> and making query faster as this would benefit from the same concept as
>>> Packed Hilbert R tree[2] used by FlatGeoBuf[3]. I would suggest that we use
>>> Hilbert ordering instead of Z sort, as PostGIS has since switched its sort
>>> to Hilbert and it is also used by flatgeobuf.
>>> We can probably do both too.
>>>
>>> Extending upon that we can also implement Dynamic Hilbert R-Tree[4] if
>>> we store Largest Hilbert Value for each of the Nodes.
>>>
>>> I would love to know your views on this!
>>> Regards
>>> Vedic
>>>
>>> [1] : https://trac.osgeo.org/postgis/wiki/GoogleSummerCode2021
>>> [2] :
>>> https://en.wikipedia.org/wiki/Hilbert_R-tree#Packed_Hilbert_R-trees
>>> [3] : https://github.com/flatgeobuf/flatgeobuf?tab=readme-ov-file
>>> [4] :
>>> https://en.wikipedia.org/wiki/Hilbert_R-tree#Dynamic_Hilbert_R-trees
>>>
>>>
>>>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.osgeo.org/pipermail/postgis-devel/attachments/20250627/fe41b2a2/attachment-0001.htm>