Creating a specific index tree structure from keys that have the tree-structure baked in? Indexing H3 Hexes

Question

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 Index:

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 Example:

• Index Hex: 8d299d10145543f
• Index Binary: 0000100011010010100110011101000100000001010001010101010000111111
• Index Hierarchy: 0010100 -> 110 -> 011 -> 101 -> 000 -> 100 -> 000 -> 001 -> 010 -> 001 -> 010 -> 101 -> 010 -> 000

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

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

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 0010100 -> 110 -> 011 -> 101 -> 000 -> 100 node.

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:

1. Are my performance expectations reasonable?
2. How can I create an index that can efficiently retrieve data following the structure that already exists in the H3 index?
3. How do I target specific tree-levels to retrieve all rows that fall under that node in a query?
4. How do I handle queries that need to reference tens of thousands of keys?

Answer 1

I would consider these two options if it was me:

Option 1: depend on your data can aggregate or not, let say it can sum (or count). Take a look at this image Let say each of these 7 children cells (inside a red one) have a count value as follow

then you can also write the parent cell (red) with the sum values of all of its children Then you would also continue pre aggregate up to the biggest cells. So on query time you can query the biggest cell instead of get all of its children. With this approach you have to write a lot in write time but you can just query parents. Remember to do idempotent add otherwise the sum will not correct (duplicate).

Option 2 Write multiple resolution in the same row

Then to query instead of your long nasty WHERE IN. You can do smaller WHERE IN with higher resolution Example SELECT * FROM MYTABLE WHERE CellRes0 IN ("8029fffffffffff") will return every child and grandchild and everything...

Answer 2

A custom index is quite hard to implement but postgres has your back covered with GiST and SP-GiST. Those are "high level" index frameworks to build your index for your custom type (h3 in this case). There's an ongoing implementation in https://github.com/zachasme/h3-pg/pull/42 which is not ready yet (at the time of this comment) but can give you an idea of what to do to implement your own.

Nevertheless,another solutionish (but quite heavy) is to index the relations between cells and parents at a larger resolution (the resolution you will use to query the database). Like if you query your data normally with something in the line of

select h3index, value from h3_table
    where cellToParent(h3index, 3) = parent_id

you can build an index for this specific operation

create index parent_idx
    on h3_table (h3_cell_to_parent(h3index, 3))

This will create huge b-tree if your dataset is large so be aware.