Two dimensions, one disk

This series started as a side question. I had just written an allocator for GPU memory, which packs buffers into one long line, and wondered why the line had to be one-dimensional. Two dimensions led to Morton order, Morton picked up a few ideas from image recognition, and soon I was solving Morton with bit tricks instead of packing anything. The packing can wait.

Take a table with two columns you filter on: a position on a map, or a time and a sensor id. The question is always the same: give me everything inside this rectangle. Memory, a file and an index all have one dimension, so before anything can be stored, someone has to decide in which order the cells of a two-dimensional grid go into a line. This post is about that decision. It opens a short series; the posts after it compute the orders fast and measure what they cost.

Rows

The obvious order is the one every array uses, row after row. On an 8 × 8 grid, cell (x, y) gets number y · 8 + x.

The marked square holds numbers 18 to 21, 26 to 29, 34 to 37 and 42 to 45: four contiguous stretches of the index. I will call such a stretch a run. Each run means jumping to a new place in the index and reading from there, so a run is roughly a seek. In this order a rectangle costs one run per row it covers, whatever its width, so a query one column wide and a hundred tall costs a hundred.

That is only half of the cost, though. A disk hands out pages, blocks of consecutive keys, and a database reads them whole. In rows, a page is a strip, a piece of one row. A square query cuts through as many strips as it has rows and uses only the few cells of each strip that fall inside it.

A curve

A space-filling curve is just another order: a path through the grid that visits every cell once, chosen so that cells close in the order are also close on the grid. The name sounds like geometry, but all that matters here is the numbering.

Z-order

The cheapest such order interleaves the bits of the two coordinates like a zipper: the lowest bit of x, then the lowest bit of y, then the next bit of x, and so on. The cell x = 2, y = 1 is x = 10 and y = 01 in binary; interleaved, that is 0110, so the cell gets number 6. This is Z-order, also called Morton order after G. M. Morton, who described it for a map database at IBM in 1966.

Every 2 × 2 block gets four consecutive numbers, every aligned 4 × 4 block sixteen, and so on up. That is the whole point: an aligned square of any size is one contiguous stretch of the index. The price is the jumps between blocks, the diagonal strokes of the Z, and some of them are long.

Hilbert

David Hilbert's curve, from 1891, is built from the same blocks, but each block is turned so that the path leaves it right next to where the next block starts. It never jumps: consecutive numbers are always neighbouring cells.

It is also harder to compute. Z-order is a bit shuffle, while Hilbert has to know at every level how the block it is in is turned, and that is a chain of decisions, each depending on the last. Making that cheap is the subject of the next post.

What a square costs

Here are both numbers for a setup that looks more like a database than a toy: a 256 × 256 grid, pages of 256 cells, and a 16 × 16 square query, averaged over all 58 081 positions the square can take.

Pages are where the curves win, and both win by the same margin. On a curve a page is a block close to a square, because an aligned square of the grid is a contiguous stretch of keys, and a square query cuts through only a few such blocks. Reading a quarter of the data is a real saving.

Runs are a different story. Hilbert only ties with plain rows, and Z-order needs almost twice as many: every jump between blocks starts a new run. For a square, a curve does not mean fewer seeks. Whether runs or pages decide what a query really costs, and whether something between Z-order and Hilbert does better, is what the rest of this series measures.

Try it

Below are three orders: Z-order, Hilbert, and one between them that gets a post of its own. Drag a rectangle across the grid; the curve outside it dims and the runs inside stay lit, so you can count them.

Where this lives

Geohash is Z-order: the bits of latitude and longitude, interleaved and written in base 32, so that nearby places share a prefix. Delta Lake can sort the files of a table along it, OPTIMIZE ... ZORDER BY, so that a filter on either column skips most files. Google's S2 library numbers cells on the faces of a cube along Hilbert's curve. And GPUs lay textures out in tiles much like Z-order, because a triangle reads a small square of texels, not a row.

Next

Three questions for the posts that follow:

• How to compute Hilbert almost as cheaply as Z-order: one constant, and sixty-four keys in one instruction.
• A curve between the two that takes away a third of Z-order's runs for one shift and two XORs.
• Whether fewer runs make a cheaper query. They do, by less than the count suggests.

Method

The numbers in the table come from a short script that numbers the grid in each order, collects the keys of every 16 × 16 square, sorts them, and counts runs as gaps between consecutive keys and pages as distinct values of key / 256. The same script draws the figures, so the pictures and the table cannot disagree. Hilbert is the classic construction, the same one the demo uses.