Read-optimised 3D n-tree lookups for storing persistent worlds in PostgreSQL

A simple approach for partitioning a world

Published Tuesday, September 14, 2021
Posted by Jackson Roberts

For storing permanent information about a world in Postgres, WorldQL offers the abstraction of Records.

Records have two goals:

  1. Offer fast lookups that leverage database indexes
  2. 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:

For Minecraft, we want to group changes by chunks at the smallest level. So we'd set the variables to:

This configuration would result in a scheme where:

Orange nodes represent tables, while teal ones represent column values.

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.