How PostGIS Turns PostgreSQL into a Spatial Query Engine
How PostGIS adds geometric types and R-tree indexing to Postgres so it can answer 'what's near what' queries over millions of geographic features in milliseconds.
Why ordinary indexes can't answer spatial questions
A standard B-tree index is built for one-dimensional ordering — it can find every row where a price falls between £10 and £20 efficiently because prices sort along a single line. Geographic coordinates don't sort meaningfully that way: two points can have very similar latitude values yet be on opposite sides of the planet in longitude, and a B-tree on latitude alone tells you nothing about proximity in the full two-dimensional (or three-dimensional, with elevation) sense that a question like 'find every restaurant within 500 metres of this point' actually needs. PostGIS's answer is to add both new data types that understand geometry — points, lines, polygons — and a new class of index built specifically for spatial locality.
Under the bonnet, PostGIS represents geometries using the OGC Simple Features model, storing shapes as sequences of coordinate pairs (or triples with elevation) alongside a spatial reference identifier that specifies which coordinate system and projection the numbers are expressed in — this matters enormously, because a distance calculation that's valid in a UK National Grid projection (measured in metres on a flat plane) will be wrong if applied naively to raw WGS84 latitude/longitude values, which are angular degrees on a sphere, not a flat coordinate system.
The R-tree: nesting bounding boxes
PostGIS builds its spatial index — implemented via PostgreSQL's generalised GiST index framework — as an R-tree, a structure that organises geometries by nesting rectangular bounding boxes inside larger bounding boxes, recursively, much like a filing system of folders within folders. At the leaf level, each entry stores a geometry's minimum bounding rectangle — the smallest axis-aligned box that fully contains the shape — plus a pointer to the actual geometry data. Those leaf entries are grouped into pages, and each page itself gets wrapped in a bounding box that encloses all of its children's boxes; that box becomes an entry one level up in a parent node, and the process repeats until a single root box, encompassing everything in the index, sits at the top.
A spatial query — say, 'find every point inside this polygon' — walks the tree from the root downward, and at each node it only needs to descend into children whose bounding box actually overlaps the query region, discarding entire subtrees (potentially covering millions of geometries) with a single cheap rectangle-overlap test. This is the same divide-and-conquer principle as a balanced binary search tree, just generalised from one dimension to two: instead of halving a sorted range at each step, the R-tree prunes away a fraction of two-dimensional space at each level, so a query that would otherwise need to check every one of a million polygons individually might only need a few dozen bounding-box comparisons to narrow down to the handful of candidates worth checking exactly.
Bounding box first, exact geometry second
Because checking whether two arbitrary complex polygons truly intersect is computationally expensive — it involves comparing every edge of one against every edge of the other in the worst case — PostGIS queries almost always run in two phases. The first phase uses the R-tree's bounding-box comparisons to cheaply eliminate the overwhelming majority of candidates whose boxes don't even overlap the query region; this is fast precisely because axis-aligned rectangle overlap is a handful of numeric comparisons, nothing more. The second phase then runs the exact geometric predicate — `ST_Intersects`, `ST_Contains`, `ST_DWithin` — only against the small surviving set of candidates whose bounding boxes did overlap, which is where the genuinely expensive edge-by-edge computation happens, but now on a tiny fraction of the original dataset.
This two-phase filter-then-refine pattern is why a well-indexed PostGIS query against millions of complex polygons — coastlines, administrative boundaries, building footprints — can return in milliseconds: the index does the cheap, coarse elimination, and only the geometrically-expensive exact test runs on the small remainder. Skipping the index and running the exact predicate against every row directly, as a naive query without spatial indexing would do, means paying that expensive edge-by-edge cost on the entire dataset every single time, which is the difference between a query that completes instantly and one that visibly grinds.
Operators that make 'nearby' a first-class question
PostGIS layers a rich set of geometric operators and functions on top of the R-tree that let 'nearby,' 'inside,' and 'overlapping' become ordinary parts of a SQL WHERE clause rather than something computed in application code after fetching rows. `ST_DWithin(geometry_a, geometry_b, distance)` answers 'is B within this distance of A' using the spatial index to prune candidates before the exact distance calculation runs, making it the standard way to write a 'nearby' query rather than the naive and index-unfriendly approach of computing distance for every row and filtering afterward. `ST_Contains` and `ST_Intersects` support polygon-in-polygon questions — 'which delivery zone does this address fall inside' — which is exactly the kind of query a spatial join between a points table and a polygons table performs at scale, joining not on equality of a key but on geometric relationship.
K-nearest-neighbour queries — 'find the 10 closest hospitals to this location' — use a related but distinct index traversal, the `<->` distance operator, which lets the GiST index return candidates ordered by increasing distance from a target point without having to compute and sort distances for the entire table first, walking the tree outward from the target rather than scanning every row. This operator is what makes 'nearest N' queries, one of the most common real-world spatial questions, scale to large datasets the same way the R-tree's bounding-box pruning makes containment and intersection queries scale.
Frequently Asked Questions
Why can't a normal B-tree index handle spatial queries well?
B-trees are built for one-dimensional ordering, but geographic coordinates involve two or more dimensions where proximity in the real world doesn't correspond to proximity when sorted along any single axis, so B-trees can't efficiently answer 'what's nearby' type questions.
What is an R-tree actually storing?
It stores nested minimum bounding rectangles: each geometry's bounding box at the leaf level, grouped into pages whose own bounding box wraps all its children, recursively up to a single root box, allowing large portions of space to be discarded quickly during a search.
Why does PostGIS check bounding boxes before exact geometry?
Comparing two rectangles for overlap is computationally cheap, while comparing two complex polygons edge by edge is expensive, so filtering with cheap bounding-box checks first and only running the expensive exact test on the small surviving set makes large-scale spatial queries fast.
What's the difference between ST_Intersects and ST_DWithin?
ST_Intersects tests whether two geometries share any point in common, useful for containment and overlap questions, while ST_DWithin tests whether two geometries are within a specified distance of each other, which is the standard building block for proximity or 'nearby' searches.