A query is a disc, and a disc is not a cell

The cells ladder has been careful to keep away from pictures. A discrete global grid is an addressing scheme, not a map: its purpose is joining, aggregating and indexing data that may never be drawn, and the separating test an address is an area sets is whether the object has to be rendered for the argument to exist.

There is one thing a cell system does that is unavoidably geometric, and it is the thing it is mostly asked to do. Find everything within five kilometres of here is a disc. It is not a cell, it does not respect the addressing hierarchy, and answering it means fetching every cell the disc meets.

That count is the cost of the query, and it has an obvious estimate which is wrong by a factor of several in the regime that matters.

The estimate, and the term it leaves out #

The area ratio is the estimate a capacity plan uses: divide the disc’s area by a cell’s and round up. It is what a cell system’s own documentation quotes, and it is exactly right in the limit of a query many cells across.

The plane’s own counting gives the whole answer. For a grid of square cells of side s, the number of cells a disc of radius r meets is about

$$\frac{\pi r^2 + 2\pi r s + s^2}{s^2}$$

— an area term, a perimeter term, and a constant. The perimeter term counts the cells the boundary crosses, and it exceeds the area term whenever the disc is narrower than about six cells across.

Six cells is not a small query. It is a five-kilometre radius on a grid whose cells are a kilometre, which is an ordinary thing to ask.

The number a plan is written against is the worst one #

A mean is the wrong statistic for the same reason it usually is: a service is sized by its slow queries, not its typical ones.

The same query asked in different places against the same scheme costs different amounts, because the cells are not identical and because a disc can land badly. On a cube scheme the expensive place is a corner, where three faces meet and a disc crosses all three.

The spread is worse at coarse levels and on schemes whose cells vary in area, and it is the quantity the previous rung’s aspect ratio was standing in for. A cell whose shape is far from square meets a disc’s boundary along more of its perimeter; a scheme whose cells vary in area has places where a disc lands on many small cells at once. The aspect ratio predicts both effects qualitatively and neither of them numerically, which is what the recorded shortfall said.

The four schemes, on the question they are for #

The ordering is not the one the previous rung’s table would predict, and that is the finding. On area spread and aspect ratio the equal-area cube is the outlier: it holds area to a part in a thousand and has the most elongated cells. On query cost it is unremarkable, because a query’s cost depends on the cells’ perimeter in units of their own size, and an elongated cell of the right area has only slightly more perimeter than a square one — the isoperimetric penalty for a 1.29 aspect ratio is under two per cent.

What does move the query cost is variation in cell size, because a disc that lands on a patch of small cells fetches many of them. That is the lon/lat quadtree’s failure and it is the same failure an address is an area measures as a precision problem.

How the cost grows, and why that is the useful form #

The two terms scale differently, and separating them is what turns a table into something a plan can use.

The area term grows as the square of the radius and the perimeter term as the first power, so at a radius of r cells the ratio of the two is about r/2. Doubling the query radius roughly quadruples the area term and doubles the perimeter one; halving the cell size at a fixed query radius does the same. Both of those are the ordinary quadratic growth a spatial index has, and neither is the surprise.

The surprise is the constant. At r = 1 cell the perimeter term is 2π ≈ 6.3 cells and the area term is π ≈ 3.1, so a query the size of one cell fetches about ten. There is no radius at which a query fetches one cell, and a system whose users mostly ask for small neighbourhoods spends nearly all of its fetching on boundary cells.

That is the practical content of the whole measurement: for small queries the cost is set by the perimeter of what is asked for, so a system’s throughput is governed by the total length of its users’ query boundaries rather than by the total area they ask about.

Where the two terms cross, exactly #

The crossover is worth pinning down, because it is one division and it turns the essay’s rule of thumb into a design number.

The area term is πr²/s² and the perimeter term is 2πr/s, so they are equal when r = 2s — a disc of radius two cells, which is four cells across, not six. Including the constant s² on the area side moves the crossing slightly below that, to about 1.9 cells of radius. Either way the boundary work dominates for any query under about four cells wide and the area estimate is the larger term above it.

More useful than the crossing is the ratio, which is simply

$$\frac{\text{perimeter term}}{\text{area term}} = \frac{2s}{r},$$

so the share of a fetch that is boundary work is decided by the query’s radius in cells and by nothing else — not the scheme, not the cell shape, not the latitude:

Read the last column as a design rule and it says something sharper than the area ratio is wrong for small queries. To get the boundary work below a tenth of the fetch, a query has to be forty cells across. A system whose users ask for five-kilometre neighbourhoods and whose cells are a kilometre is running at 29 per cent boundary work permanently, and the only way to move it is to make the cells smaller — which multiplies the area term by the square of the same factor and makes the absolute cost far worse.

That is the trade the essay’s two terms actually offer, and it has no comfortable end. Coarse cells make the fetch small and mostly boundary; fine cells make it mostly interior and enormous. The cell size that minimises total work depends on what the boundary cells cost relative to the interior ones — a boundary cell has to be filtered row by row and an interior cell does not — so the optimum is set by the occupancy of the data rather than by any property of the sphere.

Which is why the interface returns two sets rather than one. A library that handed back a single set would be forcing the caller to filter cells that need no filtering, and the ratio above says how much of the answer that would be: two thirds of it, at the radius a user most often asks for.

What was computed, and how #

A cell is fetched if any point of it lies within the query radius. The test is the cell’s own densified boundary — six samples per edge — plus the case of a disc entirely inside one cell, which a boundary test alone gets wrong and which is handled by falling back to the nearest cell centre.

Cells are rejected early by their circumradius. A cell whose centre is further from the query than the radius plus the cell’s own circumradius cannot be met, and skipping those is what makes a sweep over six thousand cells affordable inside a build.

Query positions are a Fibonacci spiral, not a random sample: a build must give the same figure twice, and a spiral covers the faces and their corners evenly rather than favouring the middle of a face.

The cell size compared against is √(4π/N) — the side of a square of the mean cell area — so the comparison with the plane’s formula is on the same footing for every scheme, including the ones whose cells are not square.

What the same question looks like on a graticule scheme #

The lon/lat quadtree is the scheme everybody has, because it is what a table of coordinates already is: split the range of longitude, split the range of latitude, and the address is the pair of indices. Its cells’ areas vary without bound towards the poles, and a query’s cost inherits that directly.

The cube schemes exist to remove that variation, and they do: their worst-to-best area ratio is 2.48 for the raw cube, 1.20 for the tangent-warped one and 1.003 for the equal-area one, against a lon/lat quadtree’s unbounded growth. What the query measurement adds is that the query cost tracks that ordering rather than the shape ordering, which is the reverse of the emphasis the trade-off figure invites.

Two refusals #

The measurement is only worth having if it can fail, and it is asked to fail in two directions.

The area ratio must be recovered at large radii. If the measured cost stayed several times the area ratio at every radius, the perimeter term would not be the explanation — something else would be, and the model would be wrong. At 32° the ratio is 1.07, which is the term dying away as it should.

The plane’s fuller estimate must not be beaten by much. The measured cost is required to sit within a factor of two of (πr² + 2πrs + s²)/s², and it does at every radius tested. A sphere’s cells are not plane squares and the agreement says the difference is second-order — which is the same statement, at the level of a query, that how small is flat enough makes about surveying.

What a system actually does about it #

Nothing here is news to the people who build these systems, and what they do about it is worth recording because it explains a piece of every such library’s interface.

A cell library asked for a disc query does not return a set of cells. It returns two sets: the cells entirely inside the disc, which need no further checking, and the cells the boundary crosses, whose contents must be tested individually. The first set is the area term and the second is the perimeter term, and the reason the interface is shaped that way is exactly that the second set is not negligible.

The ratio between them is the quantity this essay measures. At six cells across it is about one to one; at a hundred cells across it is one to twenty-five, and the boundary work disappears into rounding.

The ratio also settles why the position spread measured above is what it is. A disc’s boundary meets a number of cells proportional to its own length, so the variation between query positions is a variation in how the boundary happens to fall across cell edges — a boundary of a given length can cross anywhere from L/s to about 2L/s cells depending on its alignment. That factor of two on the boundary term becomes a factor of 1.47 on the total at eight degrees, because the interior term does not vary at all. The whole of a query’s positional spread lives in the term the area estimate omits, which is one more reason the estimate cannot be repaired by a safety factor.

Where the model stops #

A disc, not a rectangle. Bounding-box queries are at least as common in practice and their cost has a different shape, because a box aligned to the grid meets far fewer cells than one at 45° to it. Nothing here measures that anisotropy, and on a cube scheme it would be a function of which face the query lands on.

One level at a time. Real systems answer a disc query at a mixture of levels — coarse cells in the middle where a whole cell is inside, fine cells at the rim — which is the covering the hierarchy exists to provide. The cost of that is a different and better number than anything here, and computing it needs the hierarchy rather than a single grid.

No data. The cost measured is cells fetched, not rows read. A cell holding no data costs almost nothing and a cell holding a million rows costs a great deal, so the real cost is this count weighted by an occupancy distribution — which is a property of the data and not of the sphere.

The schemes are the ladder’s four. H3’s icosahedral hexagons and S2’s exact library are not implemented here; the tangent-warped cube is S2’s construction and the comparison is with the site’s own three others. A hexagonal scheme would be expected to do slightly better on this measure, because a hexagon is the plane’s most efficient shape by perimeter for its area and the twelve pentagons are too few to matter — but slightly is the operative word, since the isoperimetric gap between a square and a hexagon is under eight per cent.

The disc is a metric object and the metric is the sphere’s. A query for everything within five kilometres is a spherical cap only if distance means great-circle distance, which is the assumption nearest is a question about the metric exists to question. A query answered in a projected plane asks for a different region, and on a badly chosen projection that region is not even close to a disc.

Who found it, and when #

The perimeter term is the discrete geometry of the Gauss circle problem, which asks how many lattice points lie inside a circle and has been studied since Gauss; the count of cells a disc meets is its close relative and has the same area-plus-perimeter shape.

In the database literature the quantity appears as selectivity estimation for spatial predicates, and the practical form — inner cells and boundary cells returned separately — is in S2 from the beginning, at Google in 2005 onwards, and in H3 from 2018. Uber’s H3 documentation is unusually direct about it, warning that a disc query returns cells that must be filtered afterwards.

What none of those sources gives is a measurement over query positions, and the spread over positions is the part a plan needs.

The shortfall this settles, and what it replaces #

A cell system trades area for shape ends by recording that the aspect ratio only approximates the measurement a working cell system wants. It does, and the approximation is worse than only approximates suggests: the two quantities do not even order the schemes the same way.

The aspect ratio is a statement about one cell. The query cost is a statement about a scheme’s area variation and about the query’s own size, and a cell’s shape enters only through an isoperimetric factor that is within a few per cent of one for every shape a scheme actually uses. So the shortfall is not paid by refining the aspect ratio; it is paid by measuring the other thing, which is what this essay does.

Both numbers remain worth having. Shape decides whether a cell is a sensible unit to aggregate over — a long thin cell mixes places that have nothing to do with each other — and size decides what a query costs. They are different questions and the ladder now has one measurement for each.

Where the ladder goes next #

The count of cells is half the cost of a query. The other half is how those cells sit in identifier order, because a database does not fetch a set — it reads ranges.

Twenty-nine cells scattered through the index cost twenty-nine reads; the same twenty-nine in three contiguous runs cost three. Which happens is decided by the curve the identifiers are laid along, and the usual argument for choosing that curve turns out to be measured on the wrong statistic.