Indexes: Why a Query Is Fast or Slow

Without an index

Start with a table of ten million users and a query: find the user with this email. Without an index, the database has no idea where that row is. It reads every row, checks the email, and keeps the one match. That's a full table scan: ten million checks to return one row.

An index fixes this the way the index at the back of a book does. Instead of reading every page for one word, you look the word up in a sorted list that tells you the page. A database index is a sorted structure that maps a column's values to the rows that hold them.

One line creates it. Now the same query checks about three entries instead of ten million, and returns in four milliseconds. That's the single biggest performance tool you have, and the first thing to say in an interview when a query is slow.

SELECT * FROM users
WHERE email = 'priya@x.com';

rows checked: 10,000,000
rows returned: 1

time: ~4 s

CREATE INDEX users_email_idx
  ON users (email);

rows checked: ~3
rows returned: 1

time: ~4 ms

B-tree

Inside, most indexes are B-trees. Think of a sorted tree that is very wide and very shallow: each node holds hundreds of keys, so ten million entries fit in a tree only three or four levels deep. A lookup walks down one path from the root to a leaf, and the leaf points at the row on disk.

That's why it's fast: the work grows with the logarithm of the table size, not the size itself. Doubling the table adds at most one level. And because the tree is sorted, it answers ranges too: everyone with an email starting with p, or every order between two dates.

10,000,000 rows
B-tree with ~500 keys per node

levels = log₅₀₀(10,000,000) ≈ 3

full scan: 10,000,000 reads
index:     3 or 4 reads

What it can do

An index on a column speeds up equality, ranges, sorting by that column, and joins on it. It does not help when you wrap the column in a function, or search with a wildcard at the start, because the sorted order no longer matches what you're asking.

✓ WHERE email = ?        equality
✓ WHERE created_at > ?   range
✓ ORDER BY created_at    sorting
✓ JOIN … ON user_id      join keys

✗ WHERE LOWER(email) = ? function
✗ WHERE email LIKE '%x'  wildcard

Composite indexes

You can index several columns together. A composite index on (user_id, created_at) is sorted by user first, then by date within each user. It serves queries that filter on user id, or user id and date. But it does not serve a query on date alone, because date isn't the first column. Put the equality column first, the range column second.

One more trick: a covering index. If every column the query needs is inside the index, the database answers from the index and never touches the table at all. Postgres lets you include extra columns for exactly this.

CREATE INDEX orders_user_date_idx
  ON orders (user_id, created_at);
sorted by user_id, then created_at

✓ user_id = 7
✓ user_id = 7 AND created_at > ?
✗ created_at > ?  (not the first
                    column)

SELECT email FROM users
WHERE email LIKE 'p%';

the index already holds email
→ answer from the index alone,
  never touch the table

INCLUDE (name) adds extra columns

The cost

Indexes are not free. Every insert, update and delete has to update every index on the table. Five indexes means each write is really six writes. They take disk space and memory too. So index what you query, and drop what you don't. A write-heavy table with ten indexes is a classic interview trap.

EXPLAIN

How do you know which query needs an index? Ask the database. EXPLAIN ANALYZE prints the plan it used. Seq Scan means it read the whole table. Index Scan means it used the index. In practice you log slow queries, run EXPLAIN on them, and add the index the plan is missing.

EXPLAIN ANALYZE
SELECT * FROM users WHERE email = ?;

Seq Scan on users      ← full scan: bad
  rows=10000000

Index Scan using users_email_idx
  rows=1               ← good

Rules

Rules of thumb. Index the columns you filter, join and sort by. Primary keys are indexed automatically; foreign keys usually should be. Equality column first, range second. Keep the number small, and let EXPLAIN, not guesses, tell you what's slow.

In the interview

In the interview, say it like this. Looking up a user by email is the hot path, so I'd put a B-tree index on email. Orders are fetched per user by date, so a composite index on (user_id, created_at). On the write-heavy events table I'd keep indexes minimal. Hot query, index, trade-off. That's the whole answer.