What lookup structures forbid

What this article forbids

No structure gives all of these at once: constant-time point lookup, ordered range scan, cheap random update, and space near the entropy bound. The RUM triangle is the binding form of this. The order/no-order split is a second, harder constraint: order cannot be bought afterwards for less than the cost of a sort, and a hash can never serve a range predicate at any price.

More sharply: you cannot build a structure that is good for an access distribution you do not know. Every structure here encodes a bet, and the loss when the bet is wrong is not proportional. It is a cliff. Spilling, full scans, degenerate range joins and useless zone maps are all the same failure: the structure's assumption about the workload was violated and there was no graceful middle.

The escapes, and what each costs

Escape	What it costs
Keep more than one structure (a primary index plus secondary indexes; a B-tree plus an inverted index)	Write amplification multiplies by the number of structures, and you get a consistency problem between them, which is how index maintenance becomes a transaction problem. In a distributed system you also choose between local secondary indexes (cheap writes, reads must ask every partition) and global ones (the exact opposite)
Rebuild instead of update (segments, SSTables, immutable files)	A collector, staleness, and read amplification against the set of unmerged pieces. It buys the compact static structures of perfect hashing almost free
Approximate	Correctness: a false-positive rate you must design around. This is Probabilistic structures
Restrict the workload (static key sets, monotonic keys, append-only)	Flexibility, and a brittle coupling to an assumption that will eventually be broken by a product decision nobody told you about
Adapt at runtime (database cracking, adaptive indexes, self-tuning layouts)	Unpredictability, and a performance profile that depends on query history, which makes incidents hard to reproduce

Case, resolvedConstructed case · Arjun at Parcelo

An index 45% larger than its data

Launch week brought three symptoms: an index on random UUIDs about 45% larger than its data with fast SSD wear, a nightly hash aggregation that went from 6 to 70 minutes when the data doubled, and a contract-validity join that turned into a cross product. Where it started: Lookup structures →

Symptom 1 (index 45% too big, SSD wearing). Random UUIDv4 keys split pages everywhere, leave them about 69% full, and turn each insert into a random 16 KB page write for a 200-byte row (80× amplification, and about 240× at the flash with the FTL on top). Arjun switches the primary key to UUIDv7 (timestamp first). Inserts now append at the right edge, pages fill up, and the 45% overhead disappears. He accepts one hot page and watches the latch contention. Then he runs Lena's question: the rows are 200 bytes and writes are heavy, so an LSM (write amplification about 30) beats the B+tree (about 80) for the raw events, while the B+tree stays for small, read-mostly lookup tables.

Symptom 2 (hash aggregation 6 to 70 minutes). The hash table per partition no longer fitted in memory after the data doubled, so the operator spilled to disk. That is the discontinuity: not 2× slower but about 12× slower. He cuts the footprint per distinct key and checks the distribution of keys per depot. One huge depot had received most of the rows (skew), so one task did most of the work. He salts the hot key (splits it into several sub-keys, aggregates, then combines).

Symptom 3 (report becomes a cross product). Contract validity ranges are intervals, and the join "which contract was live at scan time?" is a stabbing query. He bins time into 5-day bins and replicates each contract into every bin it touches (replication about mean length/bin width + 1). The join becomes a hash join on the bin, followed by a filter. Hours become minutes.

He also adds a sparse index, one entry per 8,192 rows, to the sorted event files, because the whole index now fits in memory.