0

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: enter image description here

enter image description 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:

enter image description here

  • 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?
3
  • Imagine a 100k value IN() query..., you can insert those rows into a temporary table and join with that – Lennart Feb 7 at 16:28
  • This is true. I'd have to test the performance since I'm aiming for <=100ms, but that does sound like a reasonable and obvious approach. – Douglas Gaskell Feb 7 at 17:26
  • Dumb question - it's relatively simple (and doesn't require a large amount of storage) to store lat/long and place a geospatial index on top of that. Why use this system? – bbaird Feb 7 at 19:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.