Hilbert R-tree for spatial Index

Fri Jun 27 10:46:32 PDT 2025

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/1379afc5/attachment.htm>