Databases
Database indexing: interview questions and how to answer them
An index is a separate ordered structure that lets the database find rows without scanning the table — paid for with storage and slower writes.
Written and reviewed by Sahil Srivastav
What it actually is
An index is a second data structure, stored separately from the table, that maps column values to row locations in sorted order. The default in PostgreSQL, MySQL and most relational engines is a B-tree: a balanced structure where each lookup descends a handful of levels regardless of table size, which is what turns a linear scan into something closer to constant cost.
The ordering is the whole point, and it is what people miss when they treat an index as "making the column fast". Because the entries are sorted, a B-tree serves three distinct things: equality lookups, range scans, and ordered retrieval without a sort. An index that cannot be used for your particular access pattern is not a partial win — it is dead weight you are paying for on every write.
It is worth being precise that an index does not store rows (with the exception of clustered indexes, where the table is the index, as in InnoDB’s primary key). It stores keys plus a pointer. So after finding the key, the database usually still has to fetch the row itself, and that second step is often where the real cost lives.
Why it matters in production
Because the difference between an indexed and unindexed access path is not a percentage, it is an order of magnitude that grows with your data. A query scanning 40,000 rows to return 20 is fine in development seed data and an outage for the customer with four million. The query did not change and the code did not change — only the data did, which is why these failures arrive without a deploy to blame.
The counterweight is that indexes are not free, and interviews probe whether you know the cost. Every index must be updated on every insert, update and delete touching its columns, so a table with eight indexes does roughly eight times the index maintenance work per write. Indexes also consume storage and memory, competing with the data itself for the buffer cache. Teams that add an index per slow query eventually produce a write-throughput problem they cannot locate.
How it works
What the B-tree descent actually does
The root and internal pages hold separator keys that narrow the search; the leaf pages hold the indexed values in sorted order along with a pointer to the row. A lookup reads one page per level, and because the fan-out is high — hundreds of keys per page — even a very large table is three or four levels deep. This is why index lookup cost grows logarithmically and why "the table got ten times bigger" barely changes it.
Selectivity decides whether the planner uses it
An index is only worth using if it eliminates most rows. If a predicate matches 40% of the table, following index pointers to 40% of the rows in index order means effectively random access across the whole table, which is slower than reading it sequentially. The planner estimates selectivity from statistics and picks the scan. That is why an index on a boolean or a low-cardinality status column is frequently ignored — and why the planner is usually right.
The second fetch, and how a covering index removes it
After locating the key, the database normally fetches the row to get the other columns — a random read per match. If every column the query needs is already in the index, it can skip that step entirely. PostgreSQL calls this an index-only scan (and needs the visibility map to be current, which is why vacuum matters here); other engines call it a covering index. Adding a column with INCLUDE is often a bigger win than adding another index.
Why your index gets ignored
Three common reasons, all fixable. The predicate wraps the column in a function or a cast, so the stored values no longer match what is being compared — WHERE lower(email) = $1 cannot use an index on email, but can use one on lower(email). The pattern has a leading wildcard, so there is no prefix to seek on. Or the statistics are stale after a bulk load and the planner believes the predicate is far less selective than it is.
Write amplification
Each index is an additional structure to maintain. An insert writes the row plus one entry per index; an update writes new index entries for every index whose columns changed, and in PostgreSQL may write all of them unless the update qualifies as HOT. This is the cost that makes "add an index for every slow query" a bad strategy, and the reason unused indexes should be dropped rather than left alone.
Implementing it
Index for an access pattern, not for a column. Look at the actual WHERE, JOIN and ORDER BY clauses of the queries that matter, and build the smallest set of indexes that serves them — then verify with EXPLAIN that the plan uses what you created. An index the planner ignores is pure write cost.
Prefer one well-ordered composite index over several single-column indexes for the same query. The engine can combine separate indexes, but it is usually slower than a single index that matches the predicate and the ordering together.
Find and drop unused indexes periodically. PostgreSQL exposes scan counts per index in pg_stat_user_indexes; an index with zero scans after a full business cycle is costing writes and buying nothing.
Use partial indexes when queries only ever touch a subset — WHERE deleted_at IS NULL or WHERE status = 'ACTIVE'. The index is smaller, fits in cache better, and skips maintenance for rows outside the predicate.
-- Cannot use an index on email: the column is wrapped in a function
SELECT * FROM users WHERE lower(email) = $1;
-- Either index the expression...
CREATE INDEX users_lower_email_idx ON users (lower(email));
-- ...or store it normalised and index the column directly.
-- Find indexes that are costing writes and returning nothing
SELECT relname, indexrelname, idx_scan, pg_size_pretty(pg_relation_size(indexrelid))
FROM pg_stat_user_indexes
WHERE idx_scan = 0
ORDER BY pg_relation_size(indexrelid) DESC;Interview questions and how to answer them
You added an index and the query is still slow. What are the possibilities?
Either the planner is not using it, or it is using it and that is not where the time goes. For the first: a function or cast around the column, a leading wildcard, a type mismatch, or stale statistics making the predicate look unselective. For the second: the index found the rows quickly but the query then fetched thousands of them, or sorted them, or the real cost is a join further up. EXPLAIN (ANALYZE, BUFFERS) distinguishes these in one run.
When is a sequential scan the right plan?
When the predicate matches a large fraction of the table. Following index pointers to 40% of rows means random I/O across most of the table, while a sequential scan reads pages in order and is dramatically faster per row. The crossover is lower than people expect — often in single-digit percentages — which is why an index on a low-cardinality column is frequently useless.
What is the cost of adding an index?
Storage, memory pressure in the buffer cache, and write amplification: every insert and every update touching the indexed columns must maintain it. There is also a lock consideration — building one without CONCURRENTLY blocks writes for the duration of the build, which on a large table is an outage.
What is an index-only scan and what does it require?
A plan where every column the query needs is present in the index, so the database never fetches the row. In PostgreSQL it additionally needs the visibility map to show the page as all-visible, otherwise it must check the heap for tuple visibility anyway — which is a concrete reason table bloat and under-vacuuming degrade query plans, not just storage.
How would you decide which indexes a table needs?
From the workload, not the schema. Rank queries by total time in pg_stat_statements, look at the predicates and ordering of the top few, and design the smallest set of composite indexes covering them. Then check for redundancy — an index on (a) is redundant if one on (a, b) exists — and drop anything with no scans.
Answers that lose the round
- Treating an index as "making a column fast" rather than serving a specific access pattern
- Adding an index per slow query until write throughput collapses, with no one able to say which index caused it
- Claiming the planner is wrong when it skips an index on a low-selectivity predicate — it is usually right
- Not knowing that a function or cast around the column disables the index
- Forgetting that every index is maintained on every write to its columns
- Never checking
EXPLAINto confirm the new index is actually used - Leaving zero-scan indexes in place because dropping them feels risky
FAQ
Does an index on (a, b) also serve queries on b alone?
No — this is the most important practical rule about composite indexes. The B-tree is sorted by a first, so entries for a given b are scattered throughout. A query filtering only on b has no contiguous range to seek. It can serve a alone, and a plus b, but not b alone.
Should I index foreign key columns?
Usually yes, and PostgreSQL does not create them automatically — only the referenced primary key is indexed. Without an index on the referencing column, deleting a parent row requires scanning the child table to check the constraint, which is a surprisingly common source of slow deletes.
Hash index or B-tree?
B-tree in nearly all cases. A hash index serves only equality, cannot help with ordering or ranges, and the B-tree is fast enough at equality that the specialisation rarely pays. Reach for other index types when the data shape demands it — GIN for containment and full-text, GiST for geometric and range types, BRIN for naturally-ordered large tables.
How many indexes is too many?
There is no fixed number — it is a write-throughput judgement. The practical test is whether each index has non-zero scans and serves a query that matters. Tables with more than a handful usually contain redundancy, such as a single-column index already covered by the leading column of a composite one.