What a record is

Both changes are about the records that make up a chunk, so a short recap. A chunk is a square patch of the world. The compressor looks at which places overlap the patch, and if a boundary runs through it, cuts it into four and asks again for every part, down to a maximum depth. Every leaf cell becomes one record: a depth (how many times the patch was cut to get to this cell) and a palette index (which place the cell belongs to). The records are sorted by their Morton code and stored as two parallel arrays, all depths first and all palette indices after that.

Merging the children back into their parent

The first fix is a recent change; I realised something important while writing the first post. Initially, once a cell had been split, its children were never merged back. Four siblings that all resolved to the same place stayed four records, even though the parent cell covers exactly the same ground and gives exactly the same answer.

I talked with Claude Opus about this, Opus didn’t think it would be a significant improvement, because zlib’s repeating value compression would see the pattern. My gut feeling was different. I hadn’t thought about zlib, and merging four siblings into one record saves 75% of their records. After testing, on the worldwide file as it then stood, a single bottom-up merge pass would have removed 45,954,924 of 166,081,761 records.

After the merge cascades build finished, I realised that both Claude and I were wrong, because a merged parent can itself become one of four mergeable siblings, so even though the numbers didn’t look great initially, the real reduction is 36.0% of the records, 166,081,761 down to 106,377,942. And the file:

zlib’s loss on the shortened runs is real but small next to the win from dropping a third of the varint deltas: 5,748 chunks got smaller, 15 got bigger. Lookups got faster too: a cold query in the densest chunk went from 17.9 ms to 9.5 ms, because there is a third less to decode.

The subtle part is the condition. It is not enough that four children each came back as a single record for the same place; they must each be a record at the child depth. A child that only one place touches a corner of also comes back as exactly one record, but a smaller and deeper one, and merging four of those hands the place all the empty cells in between. On the first worldwide build that invented 88,542 records of ocean, caught only because the output disagreed with an independent simulation by exactly that count.

Do we actually need to store the Morton codes?

The example chunk from the first post, the patch of the world around Amsterdam (palette index 1) and Diemen (palette index 2), written out as two parallel arrays. The numbers on top are the Morton codes of the records:

As I was reviewing the Claude-drafted SVG of the quadtree, I realised another aspect. Looking at the “array” section, the depth and the codes have a relationship. If depth is 1, the next code is 16. If depth is 2, it is 4. If depth is 3, it is 1. The only thing that ever broke the pattern was a gap, a stretch of unplaced cells between two records. Make the gap an explicit record instead of a silent skip, and there is nothing left for the codes array to say that the depths array does not already say: a reader can get a cell’s code by walking the chunk and adding up depths as it goes.

That became CGEODATA version 1: the codes array is gone, and an empty stretch of cells is now an explicit “no place” record instead of a silent skip. Measured on the real rebuilt file, not a prototype:

The extra 3,770,703 records are the gaps, which used to cost nothing and now cost one record each. They are cheap anyway: a long run of identical depths and index-0 palette indices is exactly what zlib likes. Losing the codes array outright pays for them several times over.

I asked Claude to write a WebAssembly decoder for version 1 chunks, matching the one version 0 already had, then reverted it a day later. Measured across the whole file, deriving codes in WebAssembly instead of plain JavaScript saved about 16 microseconds per chunk, not enough to justify a second compiled decoder and its own fuzz tests. Version 0 files still decode through WebAssembly; version 1 does not. The honest cost of that shows up in a cold lookup: Paris, which used to resolve in 9.5 ms, now takes about 11 ms, because the arithmetic a compiled module used to do now runs as plain JavaScript on every chunk a query happens to land in. The file got smaller and a cold query got slower, in the same release. Even then, 13 ms is fast, considering how often geocoding happens.