Indexing

What an index is

A second data structure that maps values to row locations, kept sorted (or hashed) so lookups don't scan. The table is the truth; the index is a shortcut that must be maintained on every write.

That last clause is the cost, and it's the reason "just index everything" is wrong. Each index means additional writes, additional WAL, additional memory, and more work for the planner.

Clustered vs secondary

Clustered index — the table's rows are physically stored in index order. There can be only one, because the data can only be laid out one way. InnoDB clusters by primary key; looking up by PK finds the row itself with no extra hop.

Secondary index — stores the indexed value plus a pointer to the row. In InnoDB that pointer is the primary key, so a secondary lookup is two traversals: find the PK in the secondary index, then walk the clustered index to get the row.

Two practical consequences:

• Keep the primary key small. Every secondary index stores a full copy of it. A UUID PK (16 bytes) versus a bigint (8) doubles that overhead across every index.
• Random primary keys hurt inserts. A monotonic PK appends to the end of the clustered index; a random UUID inserts into the middle, splitting pages all over the tree. This is why UUIDv7 (time-ordered) exists and why it's worth preferring over UUIDv4 for keys.

Postgres differs: it stores rows in an unordered heap, and all indexes point to physical row locations. No clustered index, so no PK-size amplification — but also no free ordering.

Composite indexes and the leftmost prefix

An index on (country, city, created_at) is sorted by country first, then city within country, then time within city. It can serve:

• WHERE country = 'CH'
• WHERE country = 'CH' AND city = 'Zurich'
• WHERE country = 'CH' AND city = 'Zurich' AND created_at > …

It cannot efficiently serve WHERE city = 'Zurich' alone. Without the leading column there's no contiguous range to scan — like looking up a surname in a phone book sorted by first name.

The ordering rule that follows: equality columns first, then the range/sort column last. An index on (status, created_at) serves WHERE status='open' ORDER BY created_at perfectly, because rows for one status are already in time order. Reverse the columns and the database must sort.

Covering indexes

If an index contains every column a query needs, the database can answer from the index alone and never touch the table — an index-only scan. For a query like SELECT user_id, total FROM orders WHERE status = 'open', an index on (status, user_id, total) avoids all row lookups.

This is one of the largest wins available, especially in InnoDB where it eliminates the second traversal. The cost is a wider index.

Why the planner ignores your index

This is the hook, and the answers are:

1. Low selectivity. If status = 'active' matches 60% of the table, using the index means random-access lookups for most rows — slower than a sequential scan. The planner is right. Indexes pay off when they eliminate most of the table, roughly under 5–10% selectivity.

2. Stale statistics. The planner estimates row counts from sampled statistics. After a bulk load they can be badly wrong, producing a plan built on a fiction. Run ANALYZE.

3. A function on the column. WHERE LOWER(email) = 'x' cannot use an index on email — the index stores the original values. Fix with an expression index on LOWER(email).

4. An implicit type cast. Comparing a varchar column to a number, or an int to a bigint parameter, can silently disable the index. A frequent and invisible cause.

5. Leading wildcard. LIKE '%foo' has no prefix to seek to. LIKE 'foo%' is fine. For genuine substring search you need a trigram index or a search engine.

6. OR across different columns. WHERE a = 1 OR b = 2 often can't use either index cleanly. A UNION of two indexed queries can be dramatically faster.

Index types beyond B-tree

BRIN is worth remembering: on an append-only table of a billion timestamped rows, a BRIN index is kilobytes where a B-tree would be gigabytes, because it stores only min/max per block range. It's the right answer for time-series tables far more often than people realise.

Partial indexes are the other underused tool: CREATE INDEX … WHERE status = 'pending' indexes only the rows you actually query. On a table where 99% of rows are completed and you only ever query pending, the index is 1% of the size and stays hot in memory.

Reading a query plan

You should be able to read this much:

• Seq Scan — reading the whole table. Fine for small tables or high selectivity; alarming on a large table with a selective filter.
• Index Scan — walking the index, then fetching rows. Good for few rows.
• Bitmap Heap Scan — collect matching locations from the index, sort them, then read the table in physical order. The planner's choice for a medium number of rows.
• Index Only Scan — the covering case; no table access.
• Nested Loop / Hash Join / Merge Join — the join strategies; a nested loop over a large unindexed input is a classic disaster.

The single most useful habit: compare estimated rows to actual rows (EXPLAIN ANALYZE). A plan predicting 10 rows and getting 4 million chose the wrong strategy for a reason — bad statistics, or a correlation the planner can't see. Fix the estimate, and the plan usually fixes itself.

What to take away

• An index is a maintained shortcut — every one taxes writes.
• Secondary lookups in a clustered table cost two traversals; keep the primary key small and preferably time-ordered.
• Composite index order decides which queries it serves: equality columns first, range last.
• Covering indexes eliminate table access entirely and are often the biggest single win.
• The planner ignores an index for good reasons — usually selectivity or bad statistics.
• Partial and BRIN indexes solve specific problems at a fraction of the size.
• Read plans by comparing estimated to actual rows.