When is an index possible at all?

Which single criterion decides whether a predicate can be pruned, and how does each key domain fare against it?

CaseConstructed case · Priya at Parcelo

A depot finder that reads half the table

Parcelo launches three new features in a month, and one older feature starts to misbehave.

Depot finder: "show pickup depots within 2 km of this point." An index on (latitude, longitude) exists, but the query still reads a huge part of the 2-million-row depots table.
Support search: staff type words such as "red bicycle damaged" and want matching parcel descriptions. LIKE '%bicycle%' takes minutes on 100 million rows.
Similar items: for the lost-and-found feature, each item description becomes an embedding (a list of 768 numbers produced by a machine-learning model, where similar items give nearby lists). "Find the 10 nearest items" must be answered in milliseconds. An exact nearest-neighbor search over 100 million vectors is hopeless.
Late events: the events table is fast for "last hour" queries, until a courier app syncs a batch of offline scans from three days ago. After that, time-range queries on recent data read far more than before.

Four different shapes of key, four different behaviors. One principle explains all of them.

Index anatomy took the index apart. This article asks a prior question: when is an index possible at all?

Not every predicate can be accelerated. An index helps only by not reading things, and it can only avoid reading things it can prove do not qualify. So there is a single criterion underneath every family:

(A run is a stretch of neighboring entries that can be read in one go.) One run is ideal. A handful is fine. When the number of runs approaches the number of entries, the index has become a scan with extra steps and a maintenance bill.

Everything below is that criterion meeting different key spaces.

A point predicate produces one run trivially.
A range produces one run if the order is preserved.
Set membership produces one run after you invert the relation.
Two dimensions produce many runs, and you get to choose how they fragment.
High dimensions produce runs that cover everything, which is where exactness stops being purchasable.

The categorical shift is at the last step. Every earlier family trades space and write cost for read cost. The high-dimensional family trades correctness: not by accident or sloppiness, but because the alternative is a full scan.

The lattice

Key domain	Predicate	What must be preserved	Runs produced	Surrendered
Any	equality	nothing but a stable hash	1	order, ranges
Totally ordered (1-D)	range, prefix, top-N	order	1	one order per index
Set-valued (document contains terms)	membership + conjunction	membership, per term	1 per term; cost is the intersection	in-place update granularity
Ordered, insert-correlated (time)	recency, range	order (free: the layout already has it)	1	nothing; this is the easy case
2-3 dimensions, bounded	containment, overlap, k-nearest-neighbor	proximity	perimeter-many (linearized) or subtree-many (partitioned)	disjointness or locality
High dimension (d much larger than 10)	k-nearest-neighbor	proximity	approaches N	exactness

Read the "Runs produced" column from top to bottom. That is the argument of the part.