PostGIS: A Seventh of a Millisecond, and the Query That Never Ends

Twenty-Four Out of a Hundred and Thirteen

You ran a query against the real permit corpus last week. Find every mining exploration permit whose shape overlaps this cluster, and whose dates are still live. Out of a hundred and thirteen permits, twenty-four came back. The interesting number is not twenty-four. The interesting number is how long it took. You asked the database to explain itself, and it reported a plan that ran in roughly a seventh of a millisecond. Not a seventh of a second. A seventh of a thousandth of a second. That is fast enough to feel like the database already knew the answer before you asked. It did not cheat. It used two old, clever tricks, and most people who lean on those tricks every day could not tell you how either one works.

The Trouble With Shapes

Start with what should have been slow. A permit is not a number, it is a shape, a polygon, sometimes a complicated one with holes and islands and hundreds of corner points. Asking whether two shapes overlap is genuinely hard arithmetic. To do it honestly you have to walk the edges of both shapes and check, edge against edge, whether they cross. For one pair that is fine. For a hundred and thirteen permits checked against your search area, doing the honest geometry every single time would mean a storm of floating point math. The naive version of this query is not a seventh of a millisecond. It is a coffee break.

So the database refuses to do the honest version first. Instead it does something lazy and brilliant. Around every messy polygon it draws a single rectangle, the smallest upright box that still contains the whole shape. Engineers call it the bounding box. A box is trivial to compare. Two rectangles either overlap or they do not, and finding out takes four comparisons of plain numbers. If the boxes do not even touch, the real shapes cannot possibly touch, so the permit is thrown out instantly without anyone walking a single edge. Only the handful of permits whose boxes do overlap get the expensive, honest geometry test. Cheap filter first, expensive truth second.

The Tree That Holds the Boxes

That trick alone is not enough, because you would still have to look at all hundred and thirteen boxes. The second trick is how the boxes are organized. They live in an index, and the index is a kind of tree. Picture nesting boxes inside bigger boxes. A few permits in the same valley get wrapped in one regional box. Several regional boxes get wrapped in one bigger box, and so on up to a single box over the whole country. When you search, the database starts at the top and only opens the boxes that overlap your search area. Whole branches, hundreds of permits, get skipped because their parent box was nowhere near you. You never even consider them.

This structure has a wonderfully bland name, the generalized search tree, which everyone shortens to gist. It came out of Berkeley in the nineteen nineties as a single framework that could hold many kinds of data, and the spatial world built its bounding-box trees on top of it. Then your date filter rode along on a second, different kind of index, the plain balanced tree that databases have used for decades to keep sorted things findable. So your seventh of a millisecond is two indexes working together. The spatial tree throws away every permit in the wrong place, the date tree throws away every permit in the wrong time, and only two dozen survivors ever get the honest treatment. That is the whole secret. Most of the speed is just refusing to look at things.

The Same Geometry, Run Off a Cliff

Now the other side of the coin, from the same week, the same kind of shapes, and a completely different ending. You needed one nationwide map of water. To build it you had to take hundreds of thousands of separate water polygons, Swedish lakes and Norwegian fjords and every river segment, and melt them into one combined shape where the seams disappear. The operation that melts shapes together is called union. And union, done all at once over enormous inputs, does not run in a seventh of a millisecond. It hangs. It sits there spinning, consuming memory, never finishing.

Here is why, and it is the dark mirror of the fast query. The overlap test only had to answer yes or no. Union has to produce a brand new, perfectly clean shape, which means it must figure out the exact arrangement of every edge against every other edge, all at the same time, and then stitch a flawless boundary through the whole mess. With sixty-seven huge multi-part shapes feeding in, the geometry engine tries to reason about the entire planar puzzle in one pass. The math underneath is fragile too. Two points that are supposed to be in exactly the same place are, thanks to floating point, a hair apart, and the engine ties itself in knots trying to decide what is really touching what. The honest geometry you were allowed to skip in the fast query is now the entire job, at national scale, and it buries you.

Don't Boil the Ocean

Your fix was not cleverer math. It was refusing to ask for the impossible thing. Instead of one grand union over everything, you melted the shapes in chunks, and then simply stacked the chunk results next to each other without forcing one final all-consuming merge. The seams between chunks stay as seams, and for a map that is completely fine. Six hundred and twenty-six megabytes of water, hundreds of thousands of parts, produced without ever asking the engine to solve the whole planar puzzle in a single breath. The same instinct that makes the fast query fast, do the cheap thing and avoid the expensive thing, is exactly what rescued the slow one.

So carry two pictures out of this. The first is the bounding box and the tree of boxes, the reason a search over shapes can feel instant. It is fast because it spends almost all its effort deciding what not to look at. The second is the union that hangs, the reminder that the honest geometry you keep skipping is genuinely expensive, and that scale turns it from a coffee break into a brick wall. When a spatial query returns before you blink, that is the tree doing its quiet work. When one never returns at all, you have asked the engine to hold the entire country in its head at once. Both behaviors come from the same place, and now you can see it.