When the map gets built: paying later, or paying less

How can the cost of building an index be deferred or shrunk?

CaseConstructed case · Priya at Parcelo

16 shards, and an email search that asks every one

Parcelo grows. The parcels table is now split across 16 shards (separate database servers), by parcel_id. Two new problems appear.

Support staff search parcels by recipient_email. The query now takes 16 times more work than before and its p99 latency (the time under which 99% of requests finish) has become poor: the database must ask every shard.
To fix it, a teammate builds a separate lookup table "email to parcel id", written together with each parcel. Now a different complaint arrives: a customer creates a parcel, immediately searches for it, and it is not found. A few seconds later it appears. In another incident, deleting parcels left ghost results in vector search for days.

Nothing is broken. Index maintenance has to be placed somewhere, and every placement has a visible cost.

How it ends →

So far every index was built up front and paid for in full. Three ideas relax that.

Sparse indexing (Index anatomy): index every Nth key and pay a bounded scan inside the block. Quantization (Key domains): index a lossy copy of the data and accept some recall loss. Two more ideas change when the map is built rather than what it maps.

Cracking (adaptive indexing). The index is built as a side effect of querying. The first query that filters a column splits the data into "below the boundary" and "above the boundary". Each later query splits the pieces further. Frequently queried regions become finely ordered, and untouched regions stay unordered. You pay nothing up front, and the index follows the workload.

Learned indexes. An index is a function from key to position. A sorted array's position function is the cumulative distribution of the keys, so one can fit a model to it (a line, a small neural network) and keep a small error bound for a final local search. The idea is worth understanding because it reframes what an index is. But it is research, not current engineering practice: the update problem (what happens to the fit when keys are inserted) is unsolved enough that no major production system relies on one. Treat it as an interesting direction, not as a live option.

The common point: the data's own distribution is information. Sparse indexes, zone maps, cracking and learned indexes all exploit it; the difference is when and how the exploitation is paid for.