Skip to content

A delayed controller oscillates Admitting traffic to a cold cache Asserted metadata decays Automatic or manual failover Balls in bins: the fullest partition Block nested loop I/O Bloom filter false positives Broadcast or shuffle a join Brute-force vector search is memory-bound Buffer survival under overload Cache leverage Catching up after an outage Cells: smaller, more frequent outages Commit wait under bounded clock uncertainty Compaction debt Compression on the wire Conflict grows with the square of throughput Copysets: frequency against blast radius Count-min sketch guarantee Cyclic access: LRU against random replacement Deduplication window Delay scheduling for locality Dictionary encoding: when it pays Differential-privacy noise and budget Effective price Elastic or provisioned Elias–Fano: space of a sorted sequence Exponential backoff with full jitter External sort: passes and fan-in Fanout and tree depth Finding the rows that differ Fixed cost per operation Garbage-collection overhead and headroom Graph traversal is exponential in depth Hedged requests How a type 2 dimension grows How wide a block's min–max range is How wide a shuffle can be Hybrid hash: a ramp, not a cliff Incremental or full recompute Jitter spreads a herd Join size estimate Keys moved by a membership change Kingman's approximation Linear probing: probes by load factor Loop gain Losing every replica LSH banding: the S-curve LSM compaction: leveled against tiered Merge-on-read against copy-on-write Naive retry on one pointer Nulls: bitmap or positions Optimistic against pessimistic Order predicates by rows removed per unit of cost Pages a range query reads Patched frame of reference Pattern matching state explodes Query cost across index segments Recovery time from the checkpoint interval Request charges per gigabyte Restart interval of front coding Restarting the whole query Retry amplification across layers Retrying tasks, not jobs Role explosion Rows a sample needs to see a rare defect Run-length encoding and row order Scan time with per-file overhead Scrubbing: bandwidth and the detection window Selectivity under independence Share a subexpression or recompute it Shuffle sharding Slow-start ramp Space of an approximate membership filter Statistical multiplexing Synchronous commit latency Tail at scale The barrier waits for the maximum The composite-key rule The five-minute rule The metastable band The misses own the mean The queueing wall (M/M/1)The roofline model The square-root rule The watermark The Z-order floor Unanimity multiplies unavailability Universal Scalability Law What a commitment really saves What a defect costs What a majority quorum buys What a structural change touches What clustering can pay What columnar storage buys a scan What keeping versions costs in hit rate What partial aggregation saves What retained snapshots cost What spilling costs What variance costs in money When a cache entry pays When an index beats a scan When cold storage pays When compression speeds up a read When prefetching pays When scaling out mid-query pays Why removing names does not remove identity Write amplification of garbage collection Zipf caps data-parallel speedup Zipf: what the hottest items carry

The Data EngineeringBeta

Main content

Relationships
The composite-key rule

Relationships

Model

The composite-key rule

The cardinality of the leading column must not be larger than the number of units. Otherwise the second column gives no skipping at all.

\frac{N}{C _{a}} \geq G ⟺ C_{a} \leq U

$C_{a}$: Leading cardinality; the number of distinct values of a
$U$: Units; number of units
$G$: Unit size; rows per unit

Worked examples, recomputed

Every number the mechanisms quote for this relationship is recomputed from it, so none of them disagrees with it.

2 billion ÷ 12 parcels against 3,125 files → about 50,000×

Where it appears

Each mechanism states it in its own names. The general symbol each name stands for is shown with it.

Storage: Physical Organization
What should sit next to what, given that I must decide at write time and find out at read time?
$C_{a} \leq U$
Read it in place →

The barrier waits for the maximum

Previous Page

The five-minute rule

Next Page

The Data Engineering

Learn

Mechanisms
Symptoms
Routes

Practice

Labs
Playbooks
Interview

Reference

Trade-offs
Relationships
Glossary

The project

About
Privacy

Text CC BY-NC 4.0 · Lab code MIT

Written by Aayush Sharma