How Database Indexes Work and Why Queries Get Slow
An index is a sorted structure that lets the database find rows without reading the whole table — the same trade as a prefix sum array, at a much larger scale. Knowing when an index helps, and the everyday mistakes that make the planner ignore one, is what separates a query that returns in 2 ms from the same query at 2 s.
What an index actually is
Most relational indexes are B-trees: a balanced tree kept sorted by the indexed column, whose leaves point at the rows. Depth grows logarithmically, so even a table of a hundred million rows is only a handful of levels deep.
| Access path | Rows examined | Typical cost |
|---|---|---|
| Full table scan | 10,000,000 | Seconds |
| B-tree index lookup | ~24 nodes | Under a millisecond |
Indexes are not free. Every INSERT, UPDATE and DELETE must also maintain them, and each one occupies disk. That is the real trade: faster reads, slower writes, more storage.
Composite indexes and the leftmost prefix rule
An index on (a, b, c) is sorted by a, then by b within equal a, then by c. It can therefore serve queries filtering on a, on (a, b), or on (a, b, c) — but not on b alone, exactly as a phone book sorted by surname cannot find people by first name.
CREATE INDEX idx_orders ON orders (customer_id, status, created_at);
-- Uses the index
SELECT * FROM orders WHERE customer_id = 42;
SELECT * FROM orders WHERE customer_id = 42 AND status = 'PAID';
SELECT * FROM orders WHERE customer_id = 42 AND status = 'PAID'
ORDER BY created_at DESC;
-- Cannot use it: no leftmost column in the predicate
SELECT * FROM orders WHERE status = 'PAID';Ordering the columns
Put equality predicates first, then the range or sort column last. Among the equality columns, the most selective one (the one that eliminates the most rows) generally goes first.
What stops an index from being used
Wrapping the column in a function
WHERE YEAR(created_at) = 2026 forces a scan, because the index stores created_at, not YEAR(created_at). Rewrite it as a range: WHERE created_at >= '2026-01-01' AND created_at < '2027-01-01'.
A leading wildcard in LIKE
LIKE '%phone' cannot use a B-tree, because the tree is sorted by the start of the value. LIKE 'phone%' can. Leading-wildcard search needs a full-text or trigram index instead.
Comparing across types
Comparing a VARCHAR column to a number makes the database coerce every row before comparing, which discards the index. Match the literal's type to the column's.
The planner may also skip an index on purpose: if a query will return a large fraction of the table, a sequential scan is genuinely cheaper than millions of index lookups plus row fetches. That is the optimiser being right, not broken.
Reading the plan
Never guess — ask. EXPLAIN shows the plan the database intends; EXPLAIN ANALYZE runs it and reports what actually happened.
EXPLAIN ANALYZE
SELECT id, total_paise
FROM orders
WHERE customer_id = 42
AND status = 'PAID'
ORDER BY created_at DESC
LIMIT 20;- Seq Scan / full table scan on a large table with a selective filter — an index is probably missing.
- Index Scan or Index Only Scan — the index is being used; "only" means the row itself never had to be read.
- Rows removed by filter is large — the index matched far more rows than the query kept; consider adding the filtered column to it.
- Estimated rows far from actual rows — the planner's statistics are stale; refresh them (
ANALYZE).
Key takeaways
- A B-tree index turns a linear scan into a logarithmic lookup, at the cost of slower writes.
- A composite index is usable only from its leftmost column onwards.
- Functions on the column, leading wildcards and type mismatches all disable an index.
- EXPLAIN ANALYZE tells you what actually happened — read it before adding an index.
Practice
| Problem | Pattern | Level |
|---|---|---|
| Normalise a flat spreadsheet export to 3NF | Schema design | Easy |
| Write the index for a filter plus sort query | Composite index | Medium |
| Rewrite a WHERE YEAR(col) predicate as a range | Sargable predicates | Medium |
| Find the second highest salary | Subquery or window function | Medium |
Frequently asked questions
How does a database index make queries faster?
It keeps a sorted B-tree of the indexed column with pointers to the rows, so the database can navigate to matching rows in logarithmic time instead of scanning every row.
Why is my query not using the index?
Most often the column is wrapped in a function, the LIKE pattern starts with a wildcard, the types on either side of the comparison do not match, the predicate skips the index's leftmost column, or the query would return so many rows that a scan is genuinely cheaper.
What is the leftmost prefix rule?
A composite index on (a, b, c) can serve predicates on a, on a and b, or on all three — but not on b or c alone, because the index is sorted by a first.
Test yourself on DBMS & SQL
Reading is not recall. Take a timed quiz on this topic solo, or share a room code and battle friends on it.
⚡ Start the DBMS & SQL quiz