Preface: I am NOT a DBA, please be gentle on my terminology and explanations.
I have data that already has a structure baked into it and need to create an index in my DB that represents the hierarchical relationships in this data. These are actually indexes from Uber H3 (https://h3geo.org/docs/core-library/h3indexing). Each index is a 64-bit value, and a hierarchical relationship already exists within this index, something I wish to take advantage of.
This data describes individual hexagons in the H3 Hierarchal Geospatial Indexing System. Each hexagon has a unique index that describes itself and all 'parent' hexagons up to the base-cells. Since each hexagon is subdivided into 7 more, and each of those into 7 more, this 64-bit index already has a tree-structure baked into it.
The H3 index (described here) describes a hierarchical relationship between hexagons starting with the 122 base cells that can then be recursively subdivided into 7 children as visualized here:
This data pretty much has a tree structure baked into it. The index (
8d299d10145543f for example) describes the base-cell index, and the index of each hexagon down to itself. There are 15 resolutions (I'm only using 13), each resolution is the subdivision of the resolution above.
This exists as bit
20 -> 64, with each resolution having 3-bits with values between
0 -> 6 in the 64-bit index. Bit
13 -> 19 representing the 122 base cells.
- Index Hex:
- Index Binary:
- Index Hierarchy:
As you can see that the 64-bit index already has a tree-structure in it. I wish to utilize this in the DB index.
I will use this how?
I have a need to store lots (billions) of cells at a specific resolution (13). The primary key being the 64-bit H3 index. This will be read-heavy, write speed isn't a concern. I imagine that I'll have partitions for each of the 122 base cells, though that is a best guess on my part...
Writing would just be adding a few hundred thousand rows at a time. I'm not to concerned with write speed, for my read-heavy use case I could even do a once-a-day bulk write.
Reading is where things get bit trickier. I will have all the keys I need beforehand, say 100k of them, and just need to retrieve those 100k rows. This gets somewhat messy (Imagine a 100k value IN() query...). Thankfully
H3 provides a way for me to 'compress' this mass of individual indexes into their ideal parents (So I get an array of indexes at various resolutions that when unpacked at my specific resolution (13) I get the same 100k indexes back). This would leave me ~10k indexes at varying resolution levels to retrieve.
I would then want to retrieve all rows that have these specific parents (regardless of res), which is already represented by the 3-bit res levels as shown in the examples above. For instance retrieving every row that falls under the
My objective is to get this data for these indexes back as fast as possible, ideally several times faster than it would take me to re-generate it from scratch (~600ms to generate ~150k cells and their data)
As for DBMS, it will probably be PostgresSQL. I'm familiar with MySQL & MS SQL Server, but the later has prohibitive licensing costs and the former seems like a poor fit vs postgres. Please formulate answers with that in mind, though if you have opinions on a more appropriate technology, I'm all ears.
I do understand that the memory requirements for this will get quite steep... However, I'm willing to chew hundreds of gigs of RAM to get the read speeds I need. Right now I compute all the data on-demand, and my computational needs are way too high, my aim is to reduce that by storing the computed data in a DB and retrieving it instead.
My Questions in order of importance:
- Are my performance expectations reasonable?
- How can I create an index that can efficiently retrieve data following the structure that already exists in the
- How do I target specific tree-levels to retrieve all rows that fall under that node in a query?
- How do I handle queries that need to reference tens of thousands of keys?