Skip to content
The Data EngineeringThe Data EngineeringBeta
About
Main content

The one assumption behind every ordinary index

In which three ways does the reduction to a range fail, and which five families does that create?

Almost everything built for ordinary databases rests on one assumption:

  • B-trees need ordered keys.
  • need min/max to bound a set of rows.
  • needs the partition key to be comparable.
  • Hash joins need equality to be exact and cheap.

Together these make up an elaborate industry built on one reduction: "turn the question into a range, then read only that range".

This mechanism is about the workloads where that reduction fails. It is not a chapter about "other databases". It is about that cannot be turned into a range, and the families of mechanisms that grow in the gap.

Three ways the reduction breaks

There are three distinct ways, and they are not variations of each other.

1. Dimensionality. Vectors (lists of numbers that describe an item) and geometry live in spaces with more than one dimension. No preserves proximity in more than one dimension. Try it: lay out the 2-D points of a city map along a single line. Two points that are neighbours on the map will sometimes end up far apart on the line, however you fold the line. This is a mathematical fact, not an engineering shortfall. Any scheme that turns 2-D positions into a 1-D key (called linearization; examples are Z-order, and S2, explained in Geospatial) must choose which neighbours to tear apart.

2. Structure. In graph traversal ("who is within three hops of this person?") and in transitive closure (everything reachable by following links), the answer set is defined by following data, not by comparing values. You cannot know which record you need next until you have read the current one. That one property invalidates:

  • prefetch (loading data before it is asked for),
  • scan and vectorization (processing many values per instruction),
  • every pushdown (sending a filter to where the data lives) that assumes the access pattern is a function of the query rather than of the data.

3. Relevance. Text and vector search have no exact answer to be right about. A hundred thousand documents may contain your words; which ten are "best" is a judgement that lives in a human head. Correctness stops being a property the system can check. It becomes a ranking judgement made outside the system.

One more family, included for another reason

Time series is not a predicate break at all, because time is perfectly orderable. It is a distribution break: the data is so redundant and so append-shaped that general-purpose encodings waste an order of magnitude of space, and the number of distinct , not the number of points, is what breaks systems.

So this mechanism has five families: text, vector, graph, geospatial and time series, taken in turn.