How database indexes work (and why yours might be useless)

You added an index on customer_id. The query still does a sequential scan. You added another index on status. Same thing. You now have five indexes on a table, writes are slower, and the planner hasn't touched a single one of them.

Why?

Because an index isn't magic. It's a trade. And if you don't understand what you're trading — or when the database decides the trade isn't worth it — you'll keep throwing indexes at problems they can't solve.

🧠 What an index actually stores

Forget the "it makes queries faster" hand-wave. An index is a separate data structure, sorted by your chosen column, where each entry holds two things: the column value (the key) and a row locator that tells the database where the full row lives.

That row locator is where Postgres and MySQL diverge in a way that matters.

In Postgres, tables are heap-organized. Rows sit in an unordered pile. The locator is a ctid, basically a (page number, slot offset) pair. A physical address. The index says "the row with customer_id = 42 is at page 87, slot 3." Direct jump.

InnoDB does it differently. The table itself is a B-tree, organized by primary key. They call this a clustered index. Secondary indexes don't store a physical address. They store the primary key value. So when you look up customer_id = 42 through a secondary index, InnoDB finds the PK in the index leaf, then descends the clustered index B-tree a second time to reach the actual row.

Two lookups instead of one. That second descent is cheap for a single row. It gets expensive in bulk.

🔑 The two-step lookup and when sequential scan wins

Here's the thing people miss. Every index lookup that returns a full row is a two-step process:

Walk the index structure to find the matching entries.
For each entry, follow the locator to fetch the full row from the table.

Step 1 is fast. Sorted structure, logarithmic depth. Step 2 is the problem. Each row fetch is a random I/O to a potentially different page on disk. Fetch 10 rows, you might hit 10 different pages. Fetch 10,000 rows, that's potentially 10,000 random page reads scattered across the table.

A sequential scan, by contrast, reads pages in order. One continuous stream. Sequential I/O is dramatically faster than random I/O, even on SSDs.

So the database planner does math. If your query returns a small fraction of the table, say 50 rows out of a million, the index wins easily. But as that fraction grows, random I/O piles up until a single sequential pass through the whole table is genuinely cheaper.

Where's the crossover? Roughly 5-15% of the table, depending on row width, storage speed, and planner settings like random_page_cost. Not a fixed number. A rule of thumb. But it means an index on a column where most queries match 20% of rows is dead weight.

-- This query returns ~30% of a million-row table.
-- The planner will almost certainly ignore your index on status.
SELECT * FROM orders WHERE status = 'completed';

⚡ Selectivity, cardinality, and the column that never gets indexed

Selectivity is the fraction of rows a predicate matches. Low selectivity (few rows match) means the index pays off. High selectivity (many rows match) means it doesn't.

Cardinality is how many distinct values a column has. A boolean column has cardinality 2. An email column might have cardinality in the millions.

Low cardinality columns are the classic trap. You index is_active (true/false). Half the table is true. The planner won't use that index for WHERE is_active = true because fetching 500,000 rows via random I/O is worse than scanning the whole million-row table sequentially.

Same story with a status column holding three values. Each value matches roughly 33% of rows. The index exists, takes up space, slows every write, and the planner ignores it.

But here's a trick. If you only ever query the rare value:

-- Partial index: only indexes rows where status = 'pending'
-- (maybe 2% of the table)
CREATE INDEX idx_orders_pending ON orders (created_at)
WHERE status = 'pending';

-- The planner will happily use this for:
SELECT * FROM orders
WHERE status = 'pending' AND created_at > NOW() - INTERVAL '7 days';

Smaller index, higher selectivity, actually gets used. And cheaper to maintain because it only tracks the rows that match the predicate.

Things that silently prevent index usage

Even with good selectivity, the planner might still ignore your index. Common blockers:

Function wrapping the column. WHERE LOWER(email) = 'bob@test.com' can't use a plain index on email. The index is sorted by raw values, not lowercased ones. Fix: expression index. CREATE INDEX ON users (LOWER(email)).

Type mismatch. WHERE int_column = '42' forces a cast. The planner can't match the index. Fix: use the right literal type.

Leading wildcard. WHERE name LIKE '%smith' needs to scan every entry because the prefix is unknown. Fix: a trigram index with pg_trgm.

OR across different columns. WHERE a = 1 OR b = 2 can't walk a single index cleanly. Fix: separate indexes on each column (Postgres can bitmap-OR them), or restructure as a UNION.

The write cost nobody talks about

Every index you add is a promise: "I will maintain this sorted structure on every single write."

INSERT a row? The database updates every index on that table. UPDATE an indexed column? Old entry removed, new entry inserted. DELETE a row? Every index gets cleaned.

That's per-write, per-index overhead. A table with 8 indexes means every INSERT does 8 additional B-tree modifications. And if you have expression indexes, the database recomputes the expression on each write too.

Then there's bloat. Postgres uses MVCC, so old row versions stick around until VACUUM cleans them up. But those dead tuples also exist in the index. On a heavily-updated table, indexes can bloat to 2-5x their ideal size. VACUUM reclaims the space inside the index, but the file on disk doesn't shrink. You end up with a 4GB index that's half dead entries, slowing scans through the index structure itself.

So every index is a bet. You're betting that the read performance gain outweighs the write cost and the maintenance burden. For a read-heavy table with highly selective queries, that bet pays off. For a write-heavy table where the indexed column has low cardinality? You're paying the cost with zero benefit.

-- Check index usage: are your indexes actually being used?
SELECT indexrelname, idx_scan, idx_tup_read
FROM pg_stat_user_indexes
WHERE schemaname = 'public'
ORDER BY idx_scan ASC;
-- Indexes with idx_scan = 0 are candidates for removal.

What this post doesn't cover

The internal node layout of B+ trees (fanout, splits, how height stays low) gets its own post. Same for multi-column index ordering strategy and index-only scans where the database never touches the table at all. Those are different problems with different mental models.

If you're building systems that route traffic between services, the trade-off thinking here is similar to decisions you'd make at the API gateway layer. And if you want another example of hidden costs in layered systems, the write amplification story in Docker image layers rhymes with index bloat more than you'd expect.

📌 Key takeaways

An index stores the key plus a row locator. In Postgres that's a ctid (physical address). In InnoDB it's the primary key, requiring a second tree descent.
The second fetch (random I/O per row) is why the planner ignores your index past roughly 5-15% of the table. Not a fixed threshold, but a useful mental benchmark.
Low-cardinality columns (booleans, status fields) produce indexes the planner will never use. Partial indexes targeting the rare value are the fix.
Every index costs you on writes: maintenance overhead, expression recomputation, and MVCC-driven bloat in Postgres.
Functions on columns, type mismatches, leading wildcards, and OR across columns all silently block index usage. Each has a specific fix.