Indexing
When does a separate "where is it?" structure pay for itself, and what does it cost to keep it true?
Who this mechanism is for: a developer who writes code, calls APIs and knows basic SQL (SELECT, WHERE, JOIN, CREATE INDEX), but has never studied how a database finds a row, why an index is sometimes ignored, or why adding an index can slow a system down. You do not need to know B-trees, MVCC, sharding or vector search beforehand. Every technical term is explained the first time it appears, and again in the glossary at the end.
The story we will follow
Priya is a backend engineer at Parcelo, a company that tracks parcels for online shops. Customers see where their parcel is, couriers see which pickups are waiting, and support staff search for lost items. The main database holds a parcels table with 100 million rows and an events table with several billion rows (each scan, hand-over or delivery attempt is one event). Tomás is the senior engineer who owns the database and is always on call.
Over four parts, Priya will meet four problems. Each one looks like a bug: an index that exists but is not used, a query that gets slower after "fixing" it, a map search that scans everything, a search that returns stale answers. Each one is actually a consequence of how indexes work. Every article opens with her problem and ends with the solution, written in a section called "Back to Priya".
The main idea of this mechanism:
How this mechanism is organized
- 1
Why indexes exist
When is a separate index worth building, and what exactly do we trade?
CaseAn index the database ignores
- 2
Index anatomy
What is an index entry made of, and which choices (pointer, payload, columns, rows, density) matter?
CaseA partial index that works only in the console
- 3
Key domains
Why does the shape of the data (point, order, set, plane, high dimension) force the shape of the index, until exactness itself is lost?
CaseA depot finder that reads half the table
- 4
Approximation and lifecycle
What if you will not pay up front? How do indexes stay true under writes, versions and distribution?
Case16 shards, and an email search that asks every one
After that: a summary, hands-on labs, interview questions and a glossary.
One request: do not skip the arithmetic. Almost every rule people memorize about indexes ("leftmost prefix", "5% selectivity", "put the selective column first") is the result of a short calculation. If you can redo the calculation, you do not need to memorize the rule, and you will know when the rule is wrong.
A note on scope. This mechanism is about the map from a key to a location, and the cost of keeping that map true. It asks: what does an index map from and to, can a given predicate (the WHERE condition) be answered by pruning (skipping data) at all, and what does the write path pay? It does not explain the internal code of each data structure, how text is split into words or scored, or how a planner builds its statistics in detail. Where those matter we give the short version we need.
What do I do, and what does each option cost?
Design an index
Designing the indexes for a table from its queries: spend the one clustered order first, skip indexes past the selectivity crossover, then choose bitmap, covering, partial and composite indexes, and drop the unused ones.
DesignChoose an index family
A query filters by some key: does the physical order already answer it, and if not, does the predicate's shape call for a hash, an ordered index, an inverted index, a spatial index or approximate nearest-neighbour search?
Choose
Can I see it myself?
Find the crossover on your hardware
Index scan against sequential scan on 5 million PostgreSQL rows, scattered and clustered, at two random_page_cost settings.
Real systemDocker, PythonComposite order and the range column
Indexes on (a, b, c) and (a, c, b) for a = 1 AND b > 5 AND c = 3 in PostgreSQL: index condition, filter and buffers.
Real systemDocker, PythonThe partial index and the parameter
A partial index over 1,000 pending rows in 5 million: its size, and whether literal and prepared queries can use it.
Real systemDocker, PythonZone maps and clustering
50 million timestamped rows in Parquet, random and sorted: row groups a one-hour query must read.
MeasurePython with PyArrowInverted index intersection
Intersect posting lists for a common and a rare term over a million documents: query order, smallest first, and skips.
MeasurePythonChoose nlist for IVF
IVF over a million random 128-dimensional vectors: queries per second and recall@10 for nlist 100 to 16,000 and nprobe 1 to 32.
MeasurePython with FAISS
Can I reason about it under questioning?
Interview questions
Short questions on indexes, such as when they win, clustered, covering, composite and partial indexes, inverted, spatial and vector indexes, each with an answer you could give aloud and a link to the full explanation.
Scenarios
Longer problems on indexing, of the kind asked in senior interviews: each one estimated with numbers, diagnosed, and answered with its trade-offs.
The tensions this mechanism takes a position on. Each recurs across mechanisms.
Read-optimized vs. write-optimized
For example: B-tree vs. LSM, merge-on-read vs. copy-on-write.
Precompute vs. compute-on-read
For example: materialized views, ELT vs. ETL, schema-on-read.
Generality vs. specialization
For example: general engines vs. purpose-built structures.
Space vs. time
For example: compression, indexing, materialization, caching.
Exactness vs. approximation
For example: sketches, sampling, ANN.
Show all 8 trade-offsShow fewer
Ordering vs. parallelism
Global order costs serialization; parallelism costs order.
Mutability vs. immutability
In-place update vs. append-only + GC; buys reproducibility and cheap concurrency, pays in space and janitorial work.
Early binding vs. late binding
When structure is committed; determines where the failure surfaces, at write time or read time.
Ideas this mechanism meets that keep coming back, mechanism after mechanism.
Fixed cost per operation
Fixed cost per operation implies a natural batch size.
Costs are conserved
Costs are conserved, never removed.
Variance costs more than volume
Variance costs more than volume.
Immutable storage grows indirection
An immutable substrate grows an indirection layer plus a collector.
Fixed capacity meets growth
A fixed-capacity structure meeting growing cardinality breaks the design.