For storing permanent information about a world in Postgres, WorldQL offers the abstraction of Records.
Records have two goals:
- Offer fast lookups that leverage database indexes
- Partition the data into multiple tables to save time building indexes and allow for easier scaling
Our solution was to build an octree-inspired data structure with customizable degree and depth. This results in an n-tree, which supports dividing cubic areas into a customizable number of slices, not just 8.
As records represent permanent alterations in the world, clients will almost always want to fetch the full set of objects in a roughly defined area. Therefore, extensions like PostGIS are a bit overkill. We only need to be able to roughly grab all records in a given set of areas.
The structure of the database n-tree is decided by four configuration variables set as environment variables:
- WQL_TREE_DEGREE (must be a cubic number)
- WQL_ROOTS_PER_TABLE (must be a cubic number)
For Minecraft, we want to group changes by chunks at the smallest level. So we'd set the variables to:
- WQL_LEAF_SQUARE_SIZE = 16, each partition contains objects in a 16x16 area, which correspond to sections of a chunk.
- WQL_TREE_DEGREE = 512, further index on 8x8 chunk sets
- WQL_NUM_LEVELS = 2, only two levels including the leaf and root nodes
- WQL_ROOTS_PER_TABLE = 8, a 2x2 cube which means each 256-wide area receives its own table
This configuration would result in a scheme where:
- Each object is stored in 16 unit wide cube "buckets" which are the leaf nodes in the tree
- 512 leafs are stored in each tree root representing a 128x128x128 unit wide space.
- 8 roots per table, meaning each table represents a 256x256 cube area
In our example system, there are an arbitrary number of tables depending on how much of the world contains objects. For each table, there are eight (WQL_ROOTS_PER_TABLE) children of each table node. Each of those nodes has 512 children representing 16x16 areas which are not fully shown.
Every table has a compound index on its child key columns (teal nodes), which each refer to an n-tree child with a single integer. For our example, there are only two node child key columns, so a compound index offers good performance.
Thanks for reading, feel free to leave questions or comments in our Discord.