The address is a curve through the sphere

A cell’s identifier looks like a label and behaves like a position. Every scheme numbers its cells somehow, and the numbering decides where a cell’s data physically sits: a database stores rows in identifier order and answers a query by reading ranges of identifiers.

So the count of cells a query touches — the whole of the previous rung — is only half its cost. The other half is how those cells sit in the ordering. Twenty-nine cells scattered through the index are twenty-nine reads; the same twenty-nine in three contiguous runs are three.

The numbering is therefore a curve through the cells, and which curve is a design decision with a measurable price.

Three orderings, and what each is for #

Row-major is the obvious one: number along a row, then the next row. It is what a two-dimensional array already is.

Morton order, or Z-order, interleaves the bits of the two coordinates. Its defining property is not locality but hierarchy: the first bits of a Morton key are the parent cell’s key, so a prefix is an ancestor. That is exactly the quadkey a screen map’s tile pyramid uses, and it is the reason a screen map is a pyramid of tiles can address a tile at any zoom with one string.

Hilbert order is the space-filling curve: it visits every cell exactly once and never jumps. It is what S2 uses, and it also has the prefix property — a Hilbert key’s leading bits identify an ancestor cell — which is why it is a serious competitor to Morton rather than a curiosity.

The statistic usually quoted, which prefers the wrong answer #

The standard argument for a space-filling curve is locality: nearby cells get nearby identifiers. It is usually supported by measuring the mean difference in identifier between cells that share an edge.

Measured, that statistic prefers row-major order.

The reason is arithmetic. In row-major order half of all neighbouring pairs — the horizontal ones — differ by exactly 1, and the other half by exactly the row length, so the mean is about half the row length and the worst case is the row length. A Hilbert curve has no pairs differing by the row length and no pairs differing by 1 in a predictable way; it has a distribution with a long tail, and its worst pair is a large fraction of the whole grid, because the curve’s own recursion puts some adjacent cells at opposite ends of it.

That is a real property of the curve and not a defect of the measurement. What is wrong is the inference.

The statistic a database pays #

A query is not a pair of neighbouring cells. It is a two-dimensional region containing dozens of them, and what it costs is the number of contiguous identifier runs those cells form.

Two things in that figure are worth separating.

Hilbert beats Morton on the mean, by 36 per cent, and that is the ordinary expected result: Morton’s jumps break runs.

Hilbert beats row-major on the worst case by 43 per cent while beating it on the mean by only 18. Row-major’s cost is highly variable — a query aligned with a row is cheap and one spanning many rows is expensive — and the tail is where a space-filling curve earns its place.

So the usual claim survives, and the usual argument for it does not. A curve with good query behaviour need not have good pairwise locality, and the site’s own rule about measuring rather than naming applies to a data structure exactly as it does to a projection.

One query is not a measurement #

The tail matters enough to show what a single query looks like, and the single query chosen here loses.

Showing the counterexample is cheap and it is the honest form of the argument. A figure showing only a query where Hilbert wins would be a figure chosen to agree with the conclusion.

The over-fetch, and why a range scan is not free #

A client that wants to avoid many round trips can ask for one range covering everything from the lowest identifier to the highest, and filter afterwards. That trades reads for bytes, and the exchange rate is the span: the number of cells in that range against the number wanted.

For the query above the span is about 4,300 identifiers for 66 cells wanted — a factor of 65 — in every one of the three orderings. That number is large because a 10° query at level 5 spans several faces of the cube, and identifiers on different faces are as far apart as the numbering permits.

The lesson is that the choice of curve controls the number of runs and barely touches the span. A system that merges its ranges is choosing to be dominated by a quantity the curve cannot help with, and a system that does not merge is choosing to pay per run — which is what makes the run count the quantity worth optimising.

The cells a query fetches, seen on the map again #

It is worth putting the two halves of a query’s cost in one picture, because they are usually discussed apart.

The shaded region is the same whichever ordering is used. Everything this essay measures is a property of the numbering laid over that region, and none of it can be seen by looking at the map — which is a good argument for the ladder’s rule that a cell scheme is not a picture, made by the one essay in it that draws one.

What was computed, and how #

One sweep of queries, answered three ways. The cells fetched are computed once, by the previous rung’s disc query, and then looked up under each ordering. Nothing about the geometry differs between the three columns; only the numbering does.

Runs are counted after sorting the identifiers: a run ends wherever the next identifier is not one more than the last. That is exactly what a database’s range-scan planner does.

The Hilbert index is the standard bit-manipulation algorithm, and it is checked rather than trusted: at every level it must be a permutation of the cells, and consecutive identifiers must differ by one step in the grid. Morton’s must be a permutation and must not have that property, which is the refusal — a bug that made Morton continuous would make the whole comparison meaningless.

Faces are numbered before cells within them, so an identifier is face × n² + curve index. That is the simplest scheme and it is why the span above is dominated by face boundaries; S2 threads its Hilbert curve through the six faces in a chosen order so that the curve is continuous across face boundaries too, which reduces exactly this effect and is not implemented here.

What the hierarchy costs, and why both curves keep it #

The prefix property is worth more than any of the above, and it is worth saying why.

If a cell’s identifier begins with its parent’s identifier, then a query at a coarse level is a prefix range — a single contiguous scan — and aggregating fine cells into coarse ones is a truncation rather than a lookup. Every hierarchical cell system is built on that, and it is the reason the address of a tile is a quadkey rather than a pair of coordinates.

Both Morton and Hilbert have it. Row-major does not: the cells of a coarse cell are scattered across many rows, so a coarse query is many ranges however few cells it wants. That is the property row-major gives up in exchange for its excellent pairwise locality, and it is why nobody uses row-major for a global grid despite its winning the statistic in the third figure.

Why the run count and not the cell count #

A reader might reasonably ask why a system does not simply fetch the cells one at a time and forget about runs, in which case the ordering would not matter at all.

Because a fetch has a fixed cost and a scan does not. Reading sixty-six individual keys from a distributed store is sixty-six round trips; reading eight ranges is eight, and each returns a few hundred bytes more than was asked for. At any realistic latency the second is faster by an order of magnitude, which is why every spatial library builds ranges rather than key lists.

The consequence is that the quantity to design against is the run count, and the run count is a property of the curve. That is the whole chain: a query is a region, a region is a set of cells, the cells are positions on a curve, and the curve decides how many pieces the set breaks into. Four steps, each one a different kind of object, and the last is the only one a schema designer chooses.

Where the model stops #

One face at a time. The curve here is continuous within a face and not across face boundaries, so a query straddling two faces pays for the discontinuity. Making the curve continuous over the whole sphere is a matter of choosing the face order and the orientation of each face’s curve, which S2 does and this ladder does not.

Level 5, and the effect grows with level. At level 3 the queries are so small that all three orderings are nearly equal; at level 5 the ordering matters as the figures show; at level 12, which is what a real system uses, the runs are longer and the differences larger. Nothing here extrapolates, and the direction is stated rather than measured.

A run is not a read. A database reads pages, not identifiers, so several short runs falling on one page cost one read and one long run spanning many pages costs many. The run count is the right abstraction for comparing curves and it is not the physical cost.

No hexagons. H3 numbers its cells by a different scheme entirely, since a hexagonal hierarchy is not exact — hexagons cannot tile the sphere is the reason, and the same argument forbids a hexagon from being subdivided into hexagons.

The measurement this replaces #

The claim that a space-filling curve improves spatial locality is true, useful and almost always supported with the wrong evidence. That pattern is familiar from the rest of this site: a projection is called conformal because of its name, a cell scheme is judged by its aspect ratio, an atlas is sized with the plane’s covering density. In each case a quantity that is easy to compute stands in for one that is not, and in each case the substitution survives because nobody measures both.

Here both are measured on the same cells, in the same run, and they disagree about which ordering is better. The resolution is not that one number is wrong — row-major genuinely does keep neighbouring cells nearer in identifier — but that the number answers a question nobody asked. A database is never handed two adjacent cells; it is handed a region.

The general form of the lesson is the one measuring instead of naming states for projections: a property has to be measured on the thing that is actually done with the object, and a proxy is worth exactly as much as the correlation nobody has checked.

Who found it, and when #

Peano gave the first space-filling curve in 1890 and Hilbert the one that carries his name in 1891, as answers to a question in analysis — whether a continuous map from an interval onto a square could exist — with no thought of storage. Morton’s paper is from 1966 and is explicitly about computing: a file sequencing technique for a geodetic database, at IBM Canada, which is the earliest use of an interleaved key for spatial data.

The measurement that space-filling curves help spatial queries dates from the 1980s database literature and the comparisons there are mostly done on range queries in a plane. Google’s S2, from around 2005, is the first widely used global cell system built on a Hilbert curve, and Uber’s H3 from 2018 is the widely used one that is not — because its hexagons make a different trade.

The pairwise-locality statistic is the one that appears in the popular explanations, and the fact that it prefers row-major numbering is not usually mentioned.

The right curve depends on what a seek costs #

The run count is the statistic a database pays, and it is worth following the reasoning one step further, because the cost it stands in for is not a constant and has changed by three orders of magnitude within the lifetime of the systems using these curves.

A range scan’s real cost is roughly $n_{\text{runs}} \times c_{\text{seek}} + n_{\text{cells}} \times c_{\text{read}}$: a fixed price per contiguous range fetched, plus a price per unit of data. The run count matters in proportion to the ratio of those two, and the ratio is a property of the storage rather than of the geometry.

On a spinning disk the seek dominates absolutely. A head movement is milliseconds and a sequential read is microseconds per kilobyte, so the run count is nearly the whole cost and minimising it is nearly the whole optimisation. That is the regime the 1980s database literature measured in, and it is the regime in which the Hilbert curve’s advantage over Morton order is worth what it costs to compute.

On a local solid-state device the ratio narrows sharply. A random read is tens of microseconds and a sequential one is not enormously cheaper per byte, so runs and cells move towards comparable weight and the choice of curve matters less than the over-fetch does.

On a network object store the ratio inverts in effect. A request is tens of milliseconds of latency whatever it asks for, and bandwidth is plentiful, so the optimum is to issue few requests even at the cost of fetching a great deal that will be discarded. The correct move there is deliberately to truncate the key — query at a coarser level than the question needs, accept a much larger over-fetch, and read one long range instead of forty short ones.

So the same query, over the same cells, on the same curve, has three different optimal decompositions, and the parameter that selects between them is in the hardware. That is not a criticism of the run count; it is the reason the run count is the right thing to have measured. A cell count would have been a statistic about the geometry alone and would have had nothing to be traded against.

The ratio is also the one number a system can measure for itself, in a few lines, rather than inherit from a paper written on different hardware.

It also explains an otherwise puzzling pattern in practice. Systems built for object storage tend to use coarse cells and simple orderings, and systems built for local indexes use fine cells and clever curves — which reads as fashion or as one community not having heard of the other, and is a rational response to a cost ratio that differs between them by a factor of a thousand.

Where the ladder goes next #

The cells ladder now covers what a cell is, what shape it can be, what it costs to query and how its identifier should be ordered. All of it is about counting things in cells.

The other half of this field is about pictures — a raster, resampled from one projection into another — and it has a recorded gap of its own. The site measured three interpolation kernels on a smooth field and reported their orders of convergence, and real imagery is not smooth: it has edges, and an edge is where those orders stop meaning anything.