<div dir="ltr">I just took a look at the <a href="https://github.com/postgis/postgis/blob/2a4047bb383d2d94e3b4ab45a71dbe2a332d9ebe/postgis/gserialized_gist_2d.c#L1387">source code</a> 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,<div><br></div><div>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.</div><div><br>I also raised this up in their <a href="https://github.com/flatgeobuf/flatgeobuf/discussions/435">discussions</a> 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.</div><div><br></div><div>But If I do decide to go through with it, a loose plan would be to follow the <a href="https://www.vldb.org/conf/1994/P500.PDF">paper</a>.</div><div><br></div><div>Vedic</div></div><br><div class="gmail_quote gmail_quote_container"><div dir="ltr" class="gmail_attr">On Thu, Jun 26, 2025 at 10:26 PM Paul Ramsey <<a href="mailto:pramsey@cleverelephant.ca">pramsey@cleverelephant.ca</a>> wrote:<br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><div>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. <div><br></div><div>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.</div><div><br></div><div>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.</div><div><br></div><div>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).</div><div><br></div><div>P<br id="m_-6696818373159847597lineBreakAtBeginningOfMessage"><div><br><blockquote type="cite"><div>On Jun 26, 2025, at 9:19 AM, Vedic Chawla <<a href="mailto:chawlavedic8@gmail.com" target="_blank">chawlavedic8@gmail.com</a>> wrote:</div><br><div><div dir="ltr">Hi PostGIS community,<div><br><div>I was doing a feasibility study/survey for optimal Geospatial Index when I came across this concept. </div><div><br></div><div>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.</div><div>We can probably do both too.</div></div><div><br></div><div>Extending upon that we can also implement Dynamic Hilbert R-Tree[4] if we store Largest Hilbert Value for each of the Nodes. </div><div><br></div><div>I would love to know your views on this!</div><div>Regards</div><div>Vedic</div><div><br></div><div>[1] : <a href="https://trac.osgeo.org/postgis/wiki/GoogleSummerCode2021" target="_blank">https://trac.osgeo.org/postgis/wiki/GoogleSummerCode2021</a></div><div>[2] : <a href="https://en.wikipedia.org/wiki/Hilbert_R-tree#Packed_Hilbert_R-trees" target="_blank">https://en.wikipedia.org/wiki/Hilbert_R-tree#Packed_Hilbert_R-trees</a></div><div>[3] : <a href="https://github.com/flatgeobuf/flatgeobuf?tab=readme-ov-file" target="_blank">https://github.com/flatgeobuf/flatgeobuf?tab=readme-ov-file</a></div><div>[4] : <a href="https://en.wikipedia.org/wiki/Hilbert_R-tree#Dynamic_Hilbert_R-trees" target="_blank">https://en.wikipedia.org/wiki/Hilbert_R-tree#Dynamic_Hilbert_R-trees</a></div></div>
</div></blockquote></div><br></div></div></blockquote></div>