How did PostgreSQL find one row among millions without scanning everything?

An orders table contains hundreds of millions of rows. The API asks for one:

select id, status, total
from orders
where id = 'ord_7f42';

Reading every order would make this lookup grow with the size of the table. An index gives PostgreSQL a smaller ordered structure it can follow to find where the matching row may be stored.

The index narrows the search to a much smaller set of candidates. PostgreSQL may still need to visit the table to finish the query, and for some queries reading the table directly is still cheaper.

A B-tree narrows the search

PostgreSQL’s default index type is a B-tree. Think of it as a balanced hierarchy of pages:

root page
  ├── values below G → child page
  ├── G through P    → child page
  └── values above P → child page

Each internal page directs the search toward a smaller value range. Leaf pages contain ordered index entries and references that help PostgreSQL locate table tuples.

Because every page holds many entries, the tree stays shallow even when the table is large. Finding one key usually means reading a small number of index pages instead of examining every row.

B-trees also support ordered ranges:

where created_at >= $1 and created_at < $2
order by created_at

PostgreSQL can find the first matching leaf position and walk adjacent entries in order.

The table is still separate

A normal index entry points toward a tuple in the table’s heap storage. After finding the index match, PostgreSQL often visits the heap page to retrieve columns and confirm visibility under MVCC.

This creates two parts to the lookup: follow the index, then fetch the matching table pages. If the query matches a large part of the table, thousands of scattered heap reads may cost more than one sequential scan.

The planner compares those estimated costs before choosing. An index may exist and still be the slower option for a particular query.

Selectivity decides whether narrowing helps

An index on a nearly unique order ID is highly selective. An index on a status column containing only pending, paid, and cancelled may be much less selective.

select * from orders where status = 'paid';

If most orders are paid, the index excludes little data. A sequential scan can be cheaper. If only a tiny fraction are pending, an index on pending rows or a partial index may be valuable.

create index orders_pending_created_idx
on orders (created_at)
where status = 'pending';

This is why I design an index around a real query shape instead of adding one to every column that looks searchable.

Composite index order matters

Suppose the application frequently asks for one customer’s recent orders:

select id, status, total
from orders
where customer_id = $1
order by created_at desc
limit 20;

An index on (customer_id, created_at desc) groups entries by customer and orders each customer’s entries by creation time. PostgreSQL can locate the customer’s range and stop after 20 rows.

Reversing the columns to (created_at, customer_id) creates a different ordering. It may support time-oriented queries well but is usually less direct for locating one customer’s range.

A composite index keeps its columns in a specific left-to-right order. That order determines which query prefixes and sort orders PostgreSQL can use efficiently.

Covering can avoid some heap work

An index can include additional payload columns:

create index orders_customer_recent_idx
on orders (customer_id, created_at desc)
include (id, status, total);

If all requested values are available in the index, PostgreSQL may use an index-only scan. “Only” has a caveat: MVCC visibility normally belongs to heap tuples. PostgreSQL uses a visibility map to know when a heap page is safe to skip. Recently modified pages may still require heap checks.

A covering index can remove some heap reads, but the larger index consumes more space and adds more work to writes.

Every index charges rent on writes

An insert must add entries to the table and each relevant index. An update may modify several indexes. Deletes leave cleanup work. Larger indexes consume memory and storage, take longer to vacuum and back up, and reduce the fraction of hot pages that fit in cache.

Too many overlapping indexes slow down writes and make maintenance harder because it becomes unclear which ones the application still needs.

Before I add an index, I want to know:

1. the exact query shape;
2. how often it runs;
3. how many rows it returns;
4. the existing plan and measured bottleneck;
5. the write cost the new structure adds.

Functions can hide an indexed value

An ordinary index on email may not directly support:

where lower(email) = lower($1)

The predicate is on the result of lower(email), not the raw column ordering. An expression index can match that access pattern:

create unique index users_email_lower_idx
on users (lower(email));

The same mismatch can happen with casts, time-zone conversions, or patterns that cannot use the index ordering. What matters is the expression PostgreSQL actually has to evaluate.

Validate with observed rows and buffers

Use EXPLAIN (ANALYZE, BUFFERS) in a safe environment to compare estimates with execution and page activity.

Questions worth asking:

• Did PostgreSQL choose an index scan, bitmap scan, or sequential scan?
• How many rows did it estimate and actually process?
• How many rows were removed by a filter after the index step?
• Were pages already cached or physically read?
• Did a sort spill to disk?
• Did the query return much more data than the endpoint needed?

An index may make one query much faster while slowing down the writes that dominate the workload. I would judge it by the total cost across the requests the product actually serves, including the cost of keeping the data correct.

The index helps us find the row. The next problem begins when two transactions find that same row and both try to change it.

Sources and further reading

• PostgreSQL index types
• PostgreSQL multicolumn indexes
• PostgreSQL index-only scans