Spatial joins and discrete global grids
Why do spatial joins duplicate inputs, and what do global grids trade for using ordinary indexes?
Spatial joins
A spatial join has no equality to hash on. "Every point inside its containing polygon" relates two datasets through a continuous relation. A hash join (build a hash table on one side and probe it with the other) simply does not apply, because there is no key whose equality implies the predicate.
Three strategies exist, each recognisable from relational joins:
- Index nested loop. For each object in the smaller side, probe the other side's spatial index. It wins for the same reason it always does: when one side is small.
- Partition both sides by the same spatial decomposition, then join inside cells. This is a shuffle join where the partition function is geometric rather than a hash. It works, and it inherits the boundary problem in full. Objects that span cells go to every cell they touch, so both inputs grow, and the result needs deduplication, because a pair may match in two cells. Both the input amplification and the output deduplication are costs that a hash join does not have. They are the price of a partition function that cannot cleanly separate extended objects.
- Plane sweep. This is the sort-merge join in geometric clothing. Impose an order on one axis, sweep a line across, and keep an active set of objects whose extents currently overlap the sweep line. The trade is the usual one: a sorting cost in exchange for avoiding a build-side hash table. It fits well when the data is already ordered.
The useful compression: the three spatial join strategies are the three relational join strategies with the equality predicate replaced by a geometric one, and every difference in their behaviour traces to that substitution. The substitution costs you exact partitioning, and that is where the duplication and deduplication come from.
One more inherited problem: skew makes the shuffle variant unbalanced. The response is the same as everywhere else, namely split dense cells further and reconcile.
One line: a spatial join is a relational join whose partition function cannot cleanly separate its inputs, so it pays input duplication and output deduplication.
Discrete global grids
Geohash, S2 and H3 all do the same thing: map a location to a cell identifier (a string or an integer) with one key property: cells nested inside a parent cell share the parent's prefix. That converts a containment question into a prefix question, and prefix questions run on ordinary B-trees, ordinary string indexes and ordinary hash joins.
That is the entire point, and it should be understood as an economic and organizational mechanism rather than a geometric one: a global grid is a way to do spatial work in a system that has no spatial support. Bucketing, joining and pruning by cell id all use infrastructure you already have: clustering, ordinary indexes, hash joins. It is the cheapest answer in a general-purpose data warehouse, and it needs no spatial engine at all.
Mechanically, this is the dimensionality break: linearizing several dimensions into one must tear some neighbours apart. A space-filling curve is a rule that visits every cell of a 2-D grid in a single order, like threading one string through all the cells. Every such linearization separates some cells that are neighbours in 2-D: two adjacent cells can have completely unrelated ids if they sit across a high-order boundary of the curve. So a range query becomes a set of cell-id ranges, not one range, and the number of ranges depends on where the query sits relative to the curve's boundaries (and grows with the region's perimeter, not its area). This is the same mechanism as Z-ordering (a space-filling-curve sort order used to cluster multi-column data) in warehouse table layouts. Space-filling curves keep reappearing under different names, and that fact is itself the point.
The second and more consequential trade: a cell is a fixed-resolution approximation. A region is covered by a set of cells that either over-covers or under-covers it.
- Over-cover: you get false positives, which the refine step removes exactly. This is the safe direction.
- Under-cover: you get false negatives, which are unrecoverable.
Covering a region to a tight tolerance takes many small cells; covering it loosely takes few large cells. Resolution is a knob that trades index terms against false positives. It is the same knob as the bounding-box fill ratio in the previous section, and the same knob as nprobe in an IVF vector index (how many cells you visit). The one-sided rule is what makes over-covering the only acceptable default.
The choice among grids comes down to which distortion you accept:
| Grid design | Strength | Defect |
|---|---|---|
| Latitude/longitude based | simple | physical cell area varies enormously with latitude, so it is unsuitable for area-normalized aggregation |
| Hexagonal | uniform distance to all neighbours; good for smoothing and diffusion | a hexagon does not split exactly into smaller hexagons, so the hierarchy is approximate and containment across levels is not exact |
There is no grid without a defect. This is the sphere-to-plane theorem again, expressed discretely.
One line: a global grid converts containment into prefix matching so ordinary indexes can do spatial work. It pays the linearization tear and a resolution knob between cell count and false positives.
Two other query shapes
- Nearest-neighbour (k-NN) queries are a different traversal pattern from containment. They use expanding-radius search with a priority queue, not a filter. They link directly to vector search, where the same question has no bounding box available.
- Raster data (images and grids of values, such as satellite pictures or elevation maps) and raster-vector operations are a whole parallel family. Their cost model is array-shaped rather than index-shaped.