How do database indexes work, and when do they hurt?
What interviewers are testing
Interviewers use indexes to test whether you connect query performance to physical storage instead of just syntax. Strong candidates explain page I/O, the leftmost-prefix rule for composite keys, and why the planner might ignore an index. It also probes judgment: knowing when not to add an index is as valuable as knowing how to add one.
Mental model
An index is a sorted B+Tree keyed by column values whose leaves point at rows. Lookups descend O(log n) pages instead of scanning O(n) pages, but every INSERT/UPDATE/DELETE must maintain the tree. Indexes accelerate reads for selective predicates — the first columns of a composite key and covering queries especially — and can slow writes and even reads when selectivity is poor.
Step-by-step solution
Step 1 of 5
Full scans read every page
Without an index, SELECT * FROM users WHERE email = ? forces the planner into a sequential scan: read every heap page, test every row, and stop only when the relation ends. Cost scales with table size and row width — ten million rows at roughly one hundred rows per page is about one hundred thousand page reads, and if the table does not fit in the buffer cache, many of those are physical disk I/Os. Watch the animation: the query touches heap page after heap page, and the rows-tested node grows without any bound tied to the predicate. The work is O(n) in pages regardless of how selective the filter is, because the heap has no ordering that helps. An index changes the shape of that work from linear scanning into logarithmic descent, which is the entire reason databases maintain a second copy of the keys.
Animation — Full scans read every page
email = ?
The query arrives with an equality filter on an unindexed column.
Edge cases & traps
- Leading wildcards (LIKE '%foo') cannot use a B+Tree: rewrite as a prefix LIKE 'foo%' or add a trigram/GIN index.
- Wrapping the indexed column in a function (WHERE lower(email) = ?) disables the index: index the expression or normalize on write.
- Adding an index for every foreign key without checking usage taxes every write — keep only the indexes that queries actually exercise.
- Forgetting that a non-covering index adds a random row fetch per match: extend the index to cover selected columns or accept the scan.
- Assuming an index is always faster: for low-selectivity predicates such as status = 'active', a sequential scan is often cheaper.