Database Indexes and Query Performance
Why one query returns in 2 ms and an identical-looking one takes 40 seconds. Indexes from first principles, and the storage-engine choice that decides whether your database prefers reads or writes.
Covers: B-trees vs LSM trees, composite indexes, covering indexes, selectivity, EXPLAIN, write amplification
Almost every 'the database is slow' incident is a missing or unusable index. And almost every 'why is our write throughput so bad' incident is too many indexes. Understanding the mechanism - not just the advice - is what lets you reason about a schema you have never seen.
30-second answer
An index is a separate sorted data structure - usually a B+ tree - mapping column values to row locations. It turns an O(n) table scan into an O(log n) tree descent, typically three or four disk pages instead of millions. Writes slow down because every insert, update or delete must also update every index on that table, each of which is an additional random write plus possible page splits. So indexes trade write throughput and disk space for read speed, and a table with twelve indexes can be several times slower to write than the same table with two.
The structure
A B+ tree keeps keys sorted and balanced, with all actual data in the leaf nodes and internal nodes holding only routing keys. Because the fan-out is huge - a 4 KB page can hold hundreds of keys - depth stays tiny. A B+ tree over 100 million rows is typically only 4 levels deep, so a lookup is 4 page reads, and the top levels are almost always cached in memory.
With f = 200, one billion rows fits in four levels. This is why indexed lookups feel instant regardless of table size.
| Access path | Rows examined | Typical cost at 100 M rows |
|---|---|---|
| Full table scan | 100,000,000 | Seconds to minutes |
| Index range scan + lookup | ~matching rows | Milliseconds |
| Index unique lookup | 1 | < 1 ms, mostly from cache |
| Covering index scan | ~matching rows, no table access | Fastest non-trivial path |
Why writes get slower
- Every index is a second write. One
INSERTinto a table with six indexes is seven structures to update, each potentially a random I/O to a different part of the disk. - Page splits. Inserting into the middle of a full B+ tree page splits it in two, rewriting both and updating the parent. Random-UUID primary keys cause this constantly; monotonic keys append to the rightmost page and rarely split.
- Write amplification. Updating one indexed column can rewrite an index entry, the row, and the write-ahead log. A 200-byte logical update can become several kilobytes of physical I/O.
Composite indexes and the leftmost-prefix rule
CREATE INDEX idx ON orders (customer_id, status, created_at);
-- ✅ Uses all three columns
WHERE customer_id = 42 AND status = 'shipped' AND created_at > '2026-01-01';
-- ✅ Uses the first two (leftmost prefix)
WHERE customer_id = 42 AND status = 'shipped';
-- ⚠️ Uses only customer_id - the range on status stops further column use
WHERE customer_id = 42 AND status > 'a' AND created_at > '2026-01-01';
-- ❌ Cannot use the index at all: no leftmost column
WHERE status = 'shipped';
-- ❌ Function on the column makes it unusable (unless you index the expression)
WHERE LOWER(email) = 'a@b.com';Covering indexes
If the index contains every column the query needs, the engine never touches the table at all - an index-only scan. On a wide table this can be an order of magnitude faster, because you read a fraction of the bytes.
-- Query needs: total, and filters on customer_id + created_at
SELECT total FROM orders WHERE customer_id = 42 AND created_at > '2026-01-01';
-- Without covering: index seek -> then a heap fetch per matching row
CREATE INDEX idx_a ON orders (customer_id, created_at);
-- With covering: everything the query needs lives in the index
CREATE INDEX idx_b ON orders (customer_id, created_at) INCLUDE (total); -- Postgres
-- MySQL/InnoDB: just append it to the key
CREATE INDEX idx_b ON orders (customer_id, created_at, total);Say these points
- B+ tree indexes turn O(n) scans into ~4 page reads regardless of table size.
- Every index multiplies write cost; page splits and write amplification make it worse.
- Sequential primary keys avoid random page splits - UUIDv4 is a real throughput tax.
- Composite indexes obey the leftmost-prefix rule; put equality columns before range columns.
- Covering indexes avoid the table entirely; low-selectivity indexes get ignored.
Avoid these mistakes
- Adding an index per column instead of one well-ordered composite index.
- Wrapping an indexed column in a function and silently disabling the index.
- Indexing low-cardinality columns without making the index partial.
- Forgetting that indexes must be maintained on every write, including deletes.
Expect these follow-ups
- How would you find unused indexes in production, and is it safe to drop them?
- Why might the planner ignore a perfectly good index?
- How do you add an index to a 500 GB table without locking it?
30-second answer
A B-tree updates data in place: writes are random I/O but reads are a single predictable tree descent. An LSM-tree buffers writes in memory, flushes them as sorted immutable files, and merges those files in the background - so writes are sequential and fast, but a read may have to check several files, making reads slower and less predictable. B-trees power Postgres, MySQL InnoDB and most relational systems and suit read-heavy or read-modify-write workloads. LSM-trees power Cassandra, RocksDB, LevelDB, ScyllaDB and HBase and suit write-heavy, append-oriented workloads such as time series, event logs and metrics.
| B-tree | LSM-tree | |
|---|---|---|
| Write path | In-place update, random I/O | Append to memtable → flush sorted file |
| Write amplification | Moderate, from page rewrites and WAL | Higher, from repeated compaction |
| Read path | One tree descent, predictable | Memtable + several SSTables, plus Bloom filters |
| Read amplification | Low | Higher, grows with un-compacted files |
| Space amplification | Fragmentation from partial pages | Obsolete versions until compaction |
| Compression | Page-level, moderate | Excellent - large sorted immutable blocks |
| Range scans | Very good | Good, merged across files |
| Used by | Postgres, InnoDB, SQL Server | Cassandra, RocksDB, ScyllaDB, HBase |
How an LSM write actually flows
1 · Write-ahead log
The write is appended to a sequential log for durability. Sequential appends are the fastest thing a disk does - this is the whole performance idea.2 · Memtable
The value goes into an in-memory sorted structure. The write is acknowledged here, so latency is memory-speed.3 · Flush to SSTable
When the memtable is full it is written out as an immutable, sorted file. Immutability is why there are no in-place updates and no page splits.4 · Compaction
Background merges combine SSTables, discard overwritten versions and drop tombstoned deletes. This reclaims space and limits how many files a read must consult - and it is where all the operational pain lives.
Choosing in an interview
- Write-heavy, append-mostly - metrics, events, logs, IoT, chat messages → LSM (Cassandra, ScyllaDB, RocksDB-backed stores).
- Read-heavy with updates and joins - user profiles, orders, inventory → B-tree (Postgres, MySQL).
- Read-modify-write on the same rows - LSM is a poor fit; every update creates a new version and compaction has to clean it up.
- Heavy deletes - LSM tombstones are a known operational hazard; a workload that deletes as much as it writes will fight compaction forever.
Say these points
- B-tree: in-place, random writes, predictable single-descent reads.
- LSM: sequential writes via memtable and immutable SSTables, reads merge several files.
- Bloom filters make LSM reads practical by skipping files that cannot contain the key.
- Write-heavy/append → LSM; read-heavy with updates → B-tree.
- Compaction causes tail-latency spikes and is the main operational cost of LSM.
Avoid these mistakes
- Choosing Cassandra for a workload dominated by updates and deletes.
- Forgetting that LSM reads are slower and more variable than B-tree reads.
- Ignoring compaction's disk-space and I/O headroom requirements.
- Treating storage engine choice as equivalent to SQL vs NoSQL - they are independent axes.
Expect these follow-ups
- Why do LSM deletes create tombstones instead of removing data immediately?
- How does levelled compaction differ from size-tiered, and when do you pick each?
- Could you run a write-heavy workload on Postgres, and what would you change?
30-second answer
Start with EXPLAIN ANALYZE and compare the planner's estimated rows with the actual rows - a large divergence means stale statistics and a bad plan. Then check the four usual causes: data growth crossing a threshold that flipped the plan from index scan to sequential scan, stale or missing statistics after a bulk load, lock contention or long-running transactions blocking progress, and a change in parameter values causing parameter-sniffing to reuse a plan that suits a different value. Confirm with the plan, not with intuition.
1 · Get the actual plan, not the estimate
EXPLAIN (ANALYZE, BUFFERS)in Postgres,EXPLAIN ANALYZEin MySQL 8. The single most informative number is estimated rows vs actual rows. If the planner expected 10 and got 2,000,000, everything downstream is wrong for that reason.2 · Look for the plan flip
Index Scan → Seq Scan, or Nested Loop → Hash Join, is the classic signature. A nested loop over 50 rows is optimal; the same plan over 500,000 rows is a disaster, and the planner switches based on statistics that may now be stale.3 · Refresh statistics
ANALYZE table;. After a bulk import or a partition swap, the optimiser may believe the table still holds yesterday's row counts and distribution. This alone fixes a surprising share of incidents.4 · Check for blocking
Querypg_stat_activity/performance_schemafor long-running transactions and lock waits. An idle-in-transaction session holding a lock - or preventing vacuum - degrades everything around it without changing any query text.5 · Check for bloat and vacuum
In MVCC systems, dead tuples accumulate. If autovacuum is behind, a logically small table can be physically enormous and every scan reads mostly garbage.
EXPLAIN (ANALYZE, BUFFERS)
SELECT o.id, o.total
FROM orders o
WHERE o.customer_id = 42 AND o.created_at > now() - interval '30 days';
-- Healthy:
-- Index Scan using idx_orders_cust_created on orders
-- (cost=0.43..8.45 rows=12 width=16) (actual time=0.02..0.09 rows=14 loops=1)
-- Buffers: shared hit=5
--
-- Unhealthy - note rows=1 estimated vs rows=1,240,000 actual:
-- Seq Scan on orders
-- (cost=0.00..982431.00 rows=1 width=16) (actual time=0.3..7980 rows=1240000 loops=1)
-- Filter: (customer_id = 42 AND created_at > ...)
-- Rows Removed by Filter: 48,712,004
-- Buffers: shared hit=112 read=982319 <- reading a million pages from diskThe four causes, and their fixes
| Cause | Signature | Fix |
|---|---|---|
| Stale statistics | Estimated rows wildly wrong | ANALYZE; increase statistics target on skewed columns |
| Data growth crossed a threshold | Plan flipped to Seq Scan; table much larger than before | Better index, partitioning, or raise the planner's cost awareness |
| Lock contention | Query is waiting, not working; low CPU, high wait time | Kill the blocking transaction; add statement timeouts; shorten transactions |
| Parameter sniffing / plan cache | Fast for most values, catastrophic for one | Re-prepare, use a generic plan, or split the query path per value class |
| Bloat / vacuum backlog | Huge physical size vs logical rows | Tune autovacuum; VACUUM; consider partitioning by time |
Say these points
- EXPLAIN ANALYZE first; compare estimated to actual rows.
- Plan flips (index → sequential scan) are the classic overnight regression.
- Stale statistics after a bulk load cause bad plans with no code change.
- Check lock waits and vacuum backlog before blaming the query.
- Close with prevention: timeouts, slow-query capture, latency alerting.
Avoid these mistakes
- Adding an index before reading the plan.
- Assuming slow means CPU-bound when the query is actually waiting on a lock.
- Running EXPLAIN without ANALYZE and only seeing estimates.
- Restarting the database as a first response - it hides the evidence.
Expect these follow-ups
- How do you safely add an index to a hot 500 GB table?
- What is parameter sniffing and how do you defend against it?
- How would you catch this class of regression before users do?
Showing 3 of 3 questions for database-indexes-and-query-performance.
Check your understanding
4 questions · no sign-up, nothing stored
Hands-on challenge
Build it - this is what you talk about in a deep-dive round.
Index a real schema and prove the improvement
Take a table with at least a million rows (generate one if needed) and optimise a genuinely slow query end to end.
Requirements
- Write a query that takes over one second without an index and capture its EXPLAIN ANALYZE.
- Design one composite index that serves it, and justify the column order.
- Re-run and record the new plan, noting the change in rows examined and buffers read.
- Measure the insert-throughput cost of the new index with a bulk-insert benchmark.
- State the read/write trade-off you just made, with numbers.
Stretch goals
- Convert it to a covering index and measure the further gain.
- Add a partial index for a low-selectivity filter and compare index size.