Filter-and-refine and spatial partitioning
Why is the bounding box a Bloom filter for geometry, and why must extent cross partition boundaries?
Spatial predicates and why filter-and-refine is forced
Testing whether two polygons of m and n vertices intersect is expensive: roughly O(m·n) done naively, better with sweep algorithms, but always far more than comparing four numbers. Testing their bounding boxes is four comparisons.
The key property is the direction of the implication:
- Boxes disjoint implies geometries disjoint.
- Boxes overlapping implies nothing.
So the box test is a filter with no false negatives and many false positives, and exact evaluation runs only on the survivors. It has the same structure as a Bloom filter (a small structure that can say "definitely not here" but may wrongly say "maybe here"). It has the same one-sided guarantee and the same role. It is worth counting as such, because it shows that the pattern is about the algebra of the approximation, not about the data structure that implements it.
The quality of the filter is the fill ratio: the area of the geometry divided by the area of its bounding box.
Rivers, coastlines, and countries with distant island territories behave the same way. The filter's selectivity is a property of the shapes, not of the index. This makes spatial query cost data-dependent in a way ordinary range predicates are not, and it makes cost estimation correspondingly unreliable.
The escapes are the usual ones and cost the usual things:
- Store a cheap inner approximation as well as the outer box, so you can accept as well as reject without refining. This is a two-sided filter. It saves work in the middle, at the price of extra stored geometry.
- Decompose awkward shapes into several smaller boxes. This improves the fill, at the price of more index entries per object.
- Simplify geometries for the filter stage and keep the exact one for refinement. This is a lossy materialization, paid in space.
One line: the bounding box is a Bloom filter for geometry, and its false-positive rate is one minus the fill ratio of the shape. So cost depends on what the objects look like.
Spatial partitioning: the boundary problem
Now the defining difficulty. An object with extent crosses partition boundaries. There are exactly two responses, and both cost something permanent.
Response 1: partition the space, and cut the objects. Use a fixed grid, a quadtree (a grid that splits crowded cells into four smaller ones, again and again), or any other division of space. Each cell gets the objects that overlap it. An object that appears in twelve cells is stored, or at least referenced, twelve times. The cells stay disjoint, so a query on one cell is unambiguous. But a query that spans cells returns the same object several times and must deduplicate. Storage and index size grow with object extent.
Response 2: partition the objects, and let the regions overlap. This is the R-tree style. Group nearby objects into nodes, and let each node's bounding box be whatever encloses its members. Each object is stored once, but node boxes overlap. A point query may need to descend into several subtrees. The search is no longer a single path down a tree, and with heavily overlapping nodes it degrades toward a scan.
Stated as a trade: either the objects are duplicated or the search paths are. That is the whole of spatial partitioning. It is a direct consequence of extent. Nothing like it arises when you index points.
It recurs well outside geometry:
Examples: intervals in an interval index; time ranges in bitemporal tables (tables that track both when something was true and when it was recorded); records that span a window boundary in streaming (which is why sliding windows duplicate records across windows); ranges in a range-partitioned join. Every one is the same forced choice. The tell is always the same pair of symptoms: duplication requires deduplication on read; overlap requires multi-path search.
Both structures then inherit the skew problem. Population is wildly uneven: a grid over a country has cells that contain a city and cells that contain only ocean. A uniform grid gives uniform cells and wildly non-uniform work. An adaptive structure (like a quadtree) gives balanced work and non-uniform cells, at the price of being fitted to the data. That brings in the fitted-structure rule: a structure fitted to the current distribution goes stale as the distribution moves, and an adaptive spatial partition is such a structure. Variance costs more than volume, again in its usual place.
One line: extent forces the choice between duplicating objects across disjoint cells and keeping objects whole in overlapping regions. Cut the object or cut the search.