I've been working on a custom tree index that runs up to 7x faster than LTREE
Hi All
I’ve been working on a custom data structure and algorithm for hierarchical indexing.
while I designed the algorithm myself, I wouldn't claim to be a definitive master of hierarchy trees, nor postgres. Its actually a Rust project I've turned into an extension. I'm mainly sharing these early numbers in hopes of connecting with the right people to see if there's genuine value.
I'm not sure if I'm violating rule 5; I'd appreciate any guidance on 3rd party benchmarks for this kind of algo compare to ltree.
I ran benchmarks against 500k, 1M, 2M and 20M node recursive trees. The baseline comparisons against ltree are looking solid:
- Huge I/O Drop: For descendant queries, B-tree range scans touch up to 74x fewer buffer pages.
- Query Speed: Subtree queries run 2.5x to 6x faster (500k). up to 16x for 20M nodes. Ancestor lookups (via SP-GiST) execute up to 7.3x faster.
- Storage Density: A custom compact encoding shrank the on disk value size by 42.7%. This translates to a ~23% smaller B-tree index footprint.
- Write Performance: Appending 50,000 leaf nodes is roughly 2x faster. Reparenting large subtrees is 1.2x to 2.7x faster
I have some thoughts where this may be beneficial but lacking some subject matter expertise when it comes to practical application of hierarchy data (and these types of ops), this is the main point of my post, to ask for some insight:
- Could it make servers run more efficiently?
- Do other more efficient extensions/algos beat these benchmarks? Is LTREE just a default?
- What kinds of large scale operations would this benefit? Domains/applications?
- What should my benchmark tests look like?
Eager to get some expert opinions and either validate my thoughts or give me some reality - cheers!