Indexes

An index is a copy of some of a table's columns, kept sorted, with a pointer from each entry back to the row. That one sentence explains everything about indexes: why they make a lookup fast (sorted data can be searched in a handful of page reads), why they make writes slower (every copy must be updated), why column order matters (sorted by the first column, then the second), and why a function on the column defeats them (the sorted copy holds the value, not the function of it). This lesson is the B-tree, the composite index, and the predicates that make the engine ignore the index you built.

#The B-tree

Both PostgreSQL and MySQL's InnoDB use B-trees for ordinary indexes. A B-tree is a wide, shallow tree of pages: a root, one or two levels of internal pages holding separator keys, and leaf pages holding the indexed values in order with a pointer to each row. A table of a hundred million rows has a tree three or four levels deep, so finding one key reads three or four pages, and finding a range reads those plus the run of leaf pages that contain it. That is the whole trick: from a scan of every page to a walk of a few.

What the leaf pointer is differs between the engines, and it matters:

• PostgreSQL stores rows in a heap in no particular order. An index leaf holds the key and a tuple id (page, offset) into the heap. Every index, including the primary key's, is a separate structure pointing at the heap.
• InnoDB stores the table inside the primary key's B-tree: the leaf pages of the clustered index are the rows. A secondary index's leaf holds the key and the primary key value, so a lookup through a secondary index walks two trees: the secondary to find the PK, then the clustered to find the row. A fat primary key (a UUID string) is copied into every secondary index, and a random one scatters inserts across the clustered tree. The Schema design lesson comes back to this.

#Composite indexes and column order

An index on (customer_id, placed_at) is sorted by customer, and within each customer by date. The engine can use it for a predicate on customer_id alone, on customer_id and placed_at together, but not on placed_at alone: the dates are not in any global order, only within each customer. This is the leftmost-prefix rule, and it is the most common reason "there is an index on that column" and "the query does not use it" are both true.

SELECT * FROM orders WHERE customer_id = 42;                                   -- yes
SELECT * FROM orders WHERE customer_id = 42 AND placed_at > '2026-01-01';      -- yes, both columns
SELECT * FROM orders WHERE customer_id = 42 ORDER BY placed_at DESC LIMIT 10;  -- yes, and no sort needed
SELECT * FROM orders WHERE placed_at > '2026-01-01';                           -- no: not a prefix
SELECT * FROM orders WHERE placed_at > '2026-01-01' AND customer_id = 42;      -- yes: order in WHERE is irrelevant

The rule for choosing the order: equality columns first, then the range column, then columns used only for ordering or output. A predicate WHERE status = 'PAID' AND placed_at BETWEEN a AND b wants (status, placed_at); the other way round, the engine finds the date range and then has to check the status of every row in it. One index serves queries on its prefix, so (customer_id, placed_at) makes a separate index on customer_id alone redundant.

#Covering indexes

When every column the query touches is in the index, the engine never reads the table. PostgreSQL calls it an index-only scan; InnoDB calls it a covering index, and EXPLAIN shows Using index. It removes the random reads into the heap, which for a wide range is most of the cost.

-- PostgreSQL 11+: INCLUDE adds columns to leaf pages without making them part of the key
CREATE INDEX idx_orders_customer_placed ON orders (customer_id, placed_at) INCLUDE (total, status);
 
-- MySQL: append them to the key
CREATE INDEX idx_orders_customer_placed ON orders (customer_id, placed_at, total, status);

PostgreSQL has one more condition: an index-only scan must confirm the row is visible to this transaction, and it can skip the heap only for pages the visibility map marks all-visible. A table with heavy updates and lagging autovacuum shows Heap Fetches climbing in EXPLAIN ANALYZE, and the index-only scan quietly becomes an ordinary one. Vacuum is part of index performance there.

#Selectivity

An index earns its keep when a predicate selects a small fraction of the table. WHERE status = 'ACTIVE' on a table where 95% of rows are active is not helped by an index on status; the engine would read most of the table anyway, and reading it through the index means random reads instead of a sequential scan, which is slower. The planner knows this from statistics and will ignore such an index, and people then conclude the planner is broken.

The remedy for a skewed column is a partial index (PostgreSQL): CREATE INDEX ... ON orders (placed_at) WHERE status = 'PENDING' indexes the 2% that a queue worker polls and nothing else, small and always hot. MySQL has no partial indexes; a composite index led by the skewed column serves the same query less cheaply.

#Predicates that defeat the index

Each of these has an index on the column and does not use it:

The implicit-cast one is the sneakiest, because the query is correct, returns the right rows, and is a thousand times slower than the same query with quotes. JDBC parameter types matter here: binding an int to a VARCHAR column reproduces it.

#The cost of an index

Every index is another B-tree to update on every insert, and on every update that touches an indexed column (in PostgreSQL, on every update at all unless the HOT optimisation applies, because a new row version needs new index entries). A table with twelve indexes writes thirteen structures per insert. Indexes also take space, and a bloated one, after mass deletes, keeps its pages until reindexed. Add indexes for the queries you have, with EXPLAIN evidence, and remove the ones pg_stat_user_indexes or sys.schema_unused_indexes show are never read.

Build them without locking the table: CREATE INDEX CONCURRENTLY in PostgreSQL, ALGORITHM=INPLACE, LOCK=NONE in MySQL. A plain CREATE INDEX on a large production table blocks writes for the duration, which is the outage a migration script causes at 2 pm.

#Under the hood: pages, fill factor, and the two ways to point at a row

A B-tree page is 8 KB in PostgreSQL and 16 KB in InnoDB, and it holds as many (key, pointer) entries as fit: a few hundred for an integer key, fewer for a UUID or a long string. Fan-out that wide is why a hundred million keys need only three or four levels, and why the upper levels, a few hundred pages in total, are always in memory: an index lookup is effectively one or two disk reads for the leaf plus the heap read. Leaf pages are linked to their neighbours, so a range scan reads the first leaf by descending the tree and then walks the chain without going back up. A page that fills splits in two, each half full, and a monotonically increasing key (an identity column, a v7 UUID) always splits the rightmost page, which both engines optimise into an append; a random key splits pages all over the tree, leaving them half empty and the index twice the size it needs to be. fillfactor (PostgreSQL, default 90 for B-trees) and innodb_fill_factor leave slack on purpose so updates fit without splitting.

The planner treats an index as a cost model, not a rule. For a predicate it estimates the selectivity from statistics, multiplies by the table's row count, and compares the cost of rows × (index descent + random heap read) against a sequential scan of every page; random_page_cost (4.0 by default in PostgreSQL, tuned down to 1.1 on SSDs) is the knob that decides where the crossover sits, and a wrong value is why a healthy index goes unused on a fast disk. Bitmap scans are the middle path: collect the matching tuple ids from one or more indexes into a bitmap, sort by page, then read the heap in page order, converting random reads into near-sequential ones; that is the plan for medium selectivity and for OR across indexes. PostgreSQL's index-only scan has the extra visibility cost from the section above: the heap holds visibility, not the index, so the visibility map is consulted per page, and a page not marked all-visible costs a heap fetch anyway.

Writes are where an index's cost is paid. In PostgreSQL an UPDATE creates a new row version, and every index needs an entry for it unless the new version fits in the same heap page and no indexed column changed (a HOT update, which the fill factor exists to make likely). In InnoDB a secondary-index change goes through the change buffer when the leaf page is not in memory, deferring the write; the primary key, being the row, is updated in place. Either way a table with twelve indexes writes thirteen structures per insert, and the write amplification shows in pg_stat_user_tables as n_tup_upd versus n_tup_hot_upd.

#Walkthrough: the index that was there and not used

An orders API had a slow endpoint despite an index orders(customer_id, status, placed_at).

SELECT * FROM orders
WHERE customer_id = $1 AND status IN ('PAID', 'SHIPPED')
  AND placed_at > now() - interval '90 days'
ORDER BY placed_at DESC LIMIT 20;
-- Index Scan using orders_customer_status_placed ... rows=48000 ... Sort ... Limit

1. The index was used, but EXPLAIN ANALYZE showed it delivering 48,000 rows to a sort and then a limit of 20. The customer was a marketplace seller with 200,000 orders; the index found the prefix customer_id = $1 and then, because status IN (...) is two values, scanned two ranges of (status, placed_at) and had to merge them by placed_at with a sort.
2. The ORDER BY placed_at DESC LIMIT 20 could not stop early: with the status column between the customer and the date, the index order is placed_at within each status, not overall, so the engine had to read every row in the 90-day window for both statuses before it knew the top twenty.
3. The team had built the index from the WHERE clause left to right, which is the rule of thumb and wrong here: the range and the order are both on placed_at, and the IN is a two-value "equality" that breaks the ordering guarantee.
4. Two options. orders(customer_id, placed_at DESC) with status checked as a filter reads the newest rows for the customer and stops after twenty that match, typically a few dozen page reads. Or, on PostgreSQL, a partial index WHERE status IN ('PAID','SHIPPED') on (customer_id, placed_at DESC) keeps both the selectivity and the order. The second went in: 48,000 rows became 23, and the endpoint went from 800 ms to 2 ms.
5. pg_stat_user_indexes a week later showed the old three-column index with zero scans; it was dropped, and inserts on orders got measurably cheaper.

The rule "equality columns first, then the range" needs one clarification the incident supplied: an IN list is several equalities, and a column after it loses its global order. When a query wants the top N by a column, that column should come right after the true equality columns.

#Try it yourself

#Misconceptions

• "An index on a column means queries on it are fast." Only if the predicate is a leftmost prefix, sargable, and selective enough for the cost model to prefer it.
• "Column order in a composite index does not matter much." It decides which prefixes are usable and whether an ORDER BY ... LIMIT can stop early; an IN in the middle breaks the order of everything after it.
• "More indexes never hurt reads." They hurt every write, bloat the cache with pages nobody reads, and give the planner more wrong choices to make.
• "Index-only scans need only the index." In PostgreSQL they also need the visibility map to be fresh; Heap Fetches says whether it is.
• "The planner ignoring my index is a bug." It compared costs; check selectivity, statistics and random_page_cost before overriding it.

#Going deeper

• PostgreSQL manual, chapter "Indexes", especially "Multicolumn Indexes", "Index-Only Scans and Covering Indexes" and "Examining Index Usage".
• MySQL reference, "InnoDB Index Types", "Clustered and Secondary Indexes" and "Change Buffer".
• Markus Winand, SQL Performance Explained (use-the-index-luke.com): the whole book is this lesson.
• PostgreSQL manual, "Heap-Only Tuples" (README.HOT in the source) and the fillfactor storage parameter.
• Egor Rogov, PostgreSQL 14 Internals, part III on indexes.