Hilbert R-tree for spatial Index

[Vedic Chawla]

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/212eb89e/attachment.htm>