Indexes & Search
An index is a second copy of your data, sorted for one kind of question. From B-tree lookups to keyword search to "find me something like this", what each index answers, what it costs every write, and how it fails.
The whole idea
Why indexes
A table with 50 million rows answers any question you like, eventually. Without an index, WHERE email = ?
reads every row. So does “products mentioning noise cancelling”, and so does “products similar to this one”.
At a few hundred bytes a row that’s gigabytes of I/O per query, for an answer that might be one row.
An index is extra data, derived from the table, organised so that one kind of question can skip almost all of the work. Each kind of question needs a different organisation:
- Exact and range questions (
=,<,BETWEEN,ORDER BY) want the keys sorted: a B-tree. - “Which documents contain these words?” wants each word mapped to the documents that contain it: an inverted index.
- “What’s closest to this?” wants vectors arranged by proximity: a vector index, which is almost always approximate.
The price is the same in every case. An index is a second copy of part of the data that must be kept in sync, so every write pays for every index, and indexes take memory and disk. The storage-engine trade-off from the previous lesson applies again, one level up: you’re choosing which reads to make cheap at the expense of writes.
Secondary indexes
The primary key identifies a row. A secondary index is any other index you add so you can find rows by something else: email, city, created_at. Two things make secondary indexes different from a primary key:
- Values aren’t unique. Many rows share a city, so one value maps to many rows. Postgres and InnoDB both make each entry unique by treating the row reference as the last part of the key, so duplicates sit together.
- They point somewhere. An entry holds a reference to the row, either its physical location or its primary key. Which one matters a lot, as the next section shows.
An index can cover several columns. A composite index on (country, city) sorts by country, then by city
within each country, like a phone book sorted by surname, then first name. That order decides which queries it
can serve.
What a composite index can answer
Two practical rules fall out of that picture:
- Leftmost prefix. An index on
(a, b, c)serves filters ona, ona, b, and ona, b, c. A filter onbalone finds its matches scattered. Postgres 18 (September 2025) can now skip scan such an index, seeking once per distinct value ofa, which is cheap only whenahas few distinct values. - Covering indexes skip the table. If an index contains every column the query touches, the database can
answer from the index alone. Postgres lets you add non-key payload columns for this with
CREATE INDEX … (x) INCLUDE (y).
Clustered indexes
Where do the rows themselves live? There are two designs, and the difference shows up in every update.
- Heap tables. Rows sit in an unordered heap file; every index, including the primary key, is a separate structure whose entries hold the row’s physical location. This is Postgres: its docs say plainly that all of its indexes are secondary indexes.
- Clustered indexes. The table is a B-tree, ordered by primary key, with full rows stored in its leaves. Secondary indexes then store the primary key rather than a location. This is MySQL’s InnoDB, and SQL Server’s clustered indexes. If you don’t declare a primary key, InnoDB uses the first non-null unique index, or invents a hidden 6-byte row ID.
Where the row lives
Each design wins somewhere:
- Reads by primary key are fastest when clustered: the row is in the leaf you land on. Range scans by primary key read neighbouring rows from neighbouring pages.
- Reads by secondary key are cheaper on a heap: one index walk plus one fetch, versus two B-tree walks. And a wide primary key bloats every InnoDB secondary index, because each entry carries a copy of it.
- Updates favour the clustered design, because secondary entries don’t change when a row moves. In Postgres, an update creates a new row version at a new location, and unless it’s a HOT (heap-only tuple) update, every index gets a new entry, even indexes whose values didn’t change. HOT applies only when no column used by an index changed (BRIN indexes excepted) and the new version fits on the same page.
Inverted indexes
A B-tree on a description column would sort whole descriptions alphabetically, which is useless for finding
the word headphones. Search needs the index turned inside out: for each term, the list of documents that
contain it. That’s an inverted index, and its per-term lists are postings lists.
Building and querying an inverted index
The pieces:
- Analysis turns text into terms: tokenise, lowercase, drop stopwords, stem or lemmatise, maybe add synonyms. Queries go through the same analyzer, which is why “Foxes” finds “fox”. A mismatch between index and query analyzers is the most common reason a search “can’t find” something that’s plainly there.
- The term dictionary is sorted, which makes exact lookups and prefix queries fast. Lucene indexes it with a compact automaton (a finite-state transducer), so finding a term touches very little disk.
- Postings lists are sorted document IDs, stored as small deltas and bit-packed, so even a term that appears in millions of documents compresses very well. Intersecting sorted lists for AND queries, or merging them for OR, is a linear walk.
Inverted indexes aren’t only for prose. Postgres’s GIN (“generalized inverted index”) maps each element of a
composite value to the rows that contain it, so it serves full-text search over tsvector columns, JSONB
containment and array membership. Like an LSM-tree, it buffers new entries in an unsorted pending list and
merges them in later, because updating hundreds of postings lists per inserted row would be slow.
Full-text search
Finding the documents that match is half the job. The other half is ranking: which of 40,000 matches should come first?
The default answer in Lucene, and so in Elasticsearch and OpenSearch, is BM25, a refinement of TF-IDF. A document scores higher when:
- the term is rare across the collection (inverse document frequency): matching “headphones” means more than matching “the”;
- the term appears often in the document, with diminishing returns (controlled by k₁, default 1.2);
- the document is short relative to average, since a match in a title counts more than one in a manual (controlled by b, default 0.75).
Real search engines layer more on top: phrase and proximity matching, fuzzy matching for typos, field boosts,
and business signals like popularity. Substring search over code or identifiers uses n-gram indexes instead
of word terms; Postgres’s pg_trgm extension indexes trigrams so even LIKE '%foo%' can use an index.
The engine underneath is structured like a storage engine, because it is one. A Lucene index is a set of immutable segments, each a complete little inverted index.
Segments, refresh and merge
That design explains Elasticsearch’s best-known behaviour: it’s near real-time. A document becomes
searchable only after the next refresh writes a new segment, by default every second (skipped for indexes that haven’t been searched in the last 30 seconds, unless refresh_interval is set explicitly). Writing a segment to the filesystem
cache is cheap; fsyncing it (a Lucene commit) is expensive and happens less often, so Elasticsearch keeps its
own transaction log for durability in between.
Vector search
Keyword search fails when the words differ but the meaning matches: “quiet headphones for flights” should find a product described as “noise cancelling, ideal for travel”. Vector search handles that. A machine-learning model maps each item to an embedding, a vector of hundreds or thousands of numbers, trained so that similar meanings land close together. A query is embedded the same way, and search becomes geometry: find the k nearest vectors, by cosine similarity, dot product or Euclidean distance.
The exact answer is a full scan: compare the query with every vector. One million 1,536-dimensional float32 vectors is about 6 GB to read and 1.5 billion multiply-adds per query. Classic spatial indexes like k-d trees don’t rescue you: in hundreds of dimensions nearly every point is roughly the same distance away, and they degrade back to scanning.
So production systems give up exactness, which is the next idea.
Approximate nearest neighbours
An approximate nearest neighbour (ANN) index returns most of the true nearest neighbours, most of the time, for a tiny fraction of the work. Quality is measured as recall@k: of the true top k, what fraction did the index return? Every ANN index has a dial that trades recall for speed.
The simplest family is IVF (inverted file): cluster the vectors once with k-means, file each vector under its nearest centroid, and at query time scan only the few nearest clusters.
Exact search vs IVF
The family that dominates today is HNSW (hierarchical navigable small world), from Malkov and Yashunin’s 2016 paper. It’s a graph: each vector links to its near neighbours, and a random subset is promoted into sparser layers above, like an express lane.
Searching an HNSW graph
What each design costs:
- HNSW gives the best speed-recall trade-off in memory, but the graph must live in RAM, builds are slow, and deletes are awkward. Its knobs are m (maximum links per node on each layer, doubled on the bottom layer; 16 by default in pgvector and Elasticsearch), ef_construction (build-time candidate list) and ef_search (query-time candidate list).
- IVF builds fast and uses less memory, but recall depends on probing enough lists, and clusters drift as data changes, so it may need retraining.
- Quantization shrinks the vectors themselves: int8 scalar quantization is 4× smaller than float32; binary quantization stores one bit per dimension, 32× smaller. The lossier the compression, the more engines search the compressed vectors and then rescore a few extra candidates with the full-precision ones.
- Disk-based graph indexes like Microsoft’s DiskANN keep compressed vectors in RAM and the full graph on SSD, reaching billions of vectors per machine.
Filters vs approximate indexes
Real queries almost always filter (in stock, this tenant, this category), and filtering is where ANN indexes
surprise people. If the filter runs after the index returns its candidates, a selective filter starves the result.
pgvector’s README spells out the arithmetic: with a filter matching 10% of rows and the default ef_search of
40, you get about 4 rows back on average.
Choosing an index
| Index | Answers | Write cost | Watch out for |
|---|---|---|---|
| B-tree (secondary) | =, ranges, sorting, leftmost prefixes |
one entry per index per write | low-selectivity columns; non-HOT updates in Postgres |
| Clustered (PK B-tree) | PK lookups and PK ranges | row moves on PK change | random PKs split pages; wide PKs bloat secondaries |
| Hash | = only |
cheap | no ranges, no ordering |
| Inverted (Lucene, GIN) | terms, phrases, containment | many postings per document; buffered | analyzer mismatch; refresh delay; merge load |
| Vector: HNSW | approximate nearest neighbours | expensive graph inserts | RAM, deletes, filtered queries |
| Vector: IVF | approximate nearest neighbours | cheap, needs training | too few probes, cluster drift |
In the real world
- GitHub code search (2023). General-purpose search engines had been slow to index and costly to host for code (an early Elasticsearch deployment took months to index about 8 million repositories), so GitHub built Blackbird, a search engine in Rust using sparse grams, an n-gram variant tuned to avoid the false positives of plain trigrams. In its 2023 beta it covered almost 45 million repositories: 115 TB of code, deduplicated to 28 TB of unique content, in a 25 TB index, with about 100 ms p99 per shard.
- Discord (2025). Message search runs on Elasticsearch, sharded by server. Clusters of 200+ nodes became impractical to upgrade, a single node failure could fail ~40% of bulk indexing requests, and the biggest servers hit Lucene’s limit of about 2 billion documents per index. Discord moved to 40 smaller clusters grouped into “cells” on Kubernetes, with dedicated clusters for the largest servers. Median query latency fell from 500 ms to under 100 ms, p99 from 1 s to under 500 ms.
- Instacart (write-up, 2025) went the other way. Prices and availability change constantly, and keeping a denormalized
Elasticsearch copy in sync with Postgres was costly. It moved full-text search into sharded Postgres (GIN
indexes, a modified
ts_rank,pg_trgm), then replaced a separate FAISS service with pgvector for hybrid retrieval in the same database. It reported a 10× reduction in write workload from the normalized model. - pgvector added HNSW in 0.5.0 (August 2023) and iterative index scans for filtered queries in 0.8.0
(October 2024). It indexes
vectorcolumns up to 2,000 dimensions, and up to 4,000 as half-precisionhalfvec. - Elasticsearch quantizes by default: float vectors have been indexed as
int8_hnswsince 8.14, vectors of 384 or more dimensions asbbq_hnsw(binary quantization with rescoring) since 9.1, and since 9.4 the default is the disk-basedbbq_diskwhere the license allows it.
Pitfalls
- Indexing everything. Each index slows every insert and many updates, takes memory, and competes for cache. Drop indexes nothing uses; most databases can tell you which ones those are.
- Indexing low-selectivity columns. An index on a boolean that’s true for half the rows is slower than a scan. The planner knows this and ignores it, but every write still pays for it.
- Hiding the column.
WHERE lower(email) = ?can’t use an index onemail; index the expression instead. The same goes for implicit type casts and leading wildcards inLIKE '%…'. - Random primary keys in a clustered table. UUIDv4 keys scatter inserts across the whole B-tree. Time-ordered
UUIDv7 keys (RFC 9562, 2024;
uuidv7()is built into Postgres 18) keep inserts at the right edge. - Trusting ANN results without measuring recall. Recall depends on your data, your parameters and your filters. Keep a small set of exact-search ground truth and check it after every change.
- Filtering after an approximate index. Selective filters starve the result set, silently. Use iterative scans, partial indexes or filter-aware engines.
- Expecting writes to be visible immediately in a search engine. Near real-time means up to a refresh interval behind. Read-your-writes needs a refresh, or reading from the source of truth.
Recall
Go deeper
- PostgreSQL docs: Index-Only Scans and Covering Indexes: heap tables, the visibility map and
INCLUDE, in one short page. - MySQL docs: Clustered and Secondary Indexes: how InnoDB picks its clustered index and why short primary keys matter.
- Evan Klitzke, “Why Uber Engineering Switched from Postgres to MySQL” (2016): heap vs clustered storage, argued from a real write-amplification problem.
- Elastic docs: Near real-time search: segments, refresh and commits, from the source.
- Timothy Clem, “The technology behind GitHub’s new code search” (2023): building an n-gram search engine from scratch, with real numbers.
- Malkov & Yashunin, “Efficient and robust approximate nearest neighbor search using HNSW graphs” (2016): the paper behind most in-memory vector indexes in production.
- pgvector README: HNSW and IVFFlat parameters, filtering caveats and iterative scans, all in one place.
- Douze et al., “The Faiss library” (2024): a map of the whole vector-search design space, from the team behind Faiss.
Keep going
The atomic notes for this lesson live in the knowledge graph:
Next on the map: Analytics & Columnar Storage (indexes for scanning, not seeking) and Sharding (what happens to all of these indexes once the data is split across machines).