Scan types
Sequential, index, bitmap and index-only scans, and how the planner chooses between them.
Draft. This page is new and has not yet been reviewed by a second person. Every query output on it was produced by a real run on PostgreSQL 18.6 (PGlite 0.5.9). If something looks wrong, report it.
On this page
"Is there an index?" is the wrong question. The planner can reach the same rows in several ways, and it picks by estimating how much each one would cost. Knowing the options, and what makes each one expensive, is what lets you read a plan and predict what a change will do.
The four ways to read a table#
- Sequential scan. Read every page in order and test every row. It reads more than it needs, but reading pages in order is the cheapest kind of reading there is, and it is the best plan when a large share of rows match.
- Index scan. Walk the index and fetch each matching row as its entry comes up. Ideal for a few rows, or when the rows must come out in index order. It gets expensive when many rows match and they are spread across the table, because each fetch can land on a different page.
- Bitmap scan. Walk the index first and only note where the matching rows live, then sort those locations by page and read each page once. It is the middle ground for "more than a few, less than most" rows. In a plan it appears as a
Bitmap Index Scanfeeding aBitmap Heap Scan. - Index-only scan. Answer from the index alone, when it contains every column the query needs and the table pages are known to be all-visible.
How the planner chooses#
The planner estimates two things: how many rows will match (from statistics gathered by ANALYZE) and what reading them will cost. Costs are in abstract units where reading one page in sequence costs seq_page_cost (1.0 by default) and reading one page out of order costs random_page_cost (4.0 by default). An index scan over many scattered rows adds up random reads quickly; a sequential scan pays a fixed price whatever matches.
One statistic decides a lot: the correlation between a column's order and the physical order of rows. Orders were inserted over time, so created_at follows the table's order almost perfectly, while user_id does not:
select attname as column_name, round(correlation::numeric, 3) as correlation
from pg_stats
where tablename = 'orders' and attname in ('id', 'created_at', 'user_id', 'total')
order by attname;| column_name | correlation |
|---|---|
| created_at | 1.000 |
| id | 1.000 |
| total | 0.000 |
| user_id | -0.003 |
create index orders_created_at_idx on orders (created_at);
create index orders_user_id_idx on orders (user_id);A range on the well-correlated column touches neighbouring rows, so a plain index scan reads few pages:
select id, created_at from orders where created_at >= '2024-12-01';Index Scan using orders_created_at_idx on orders (cost=0.29..154.31 rows=4001 width=12) (actual time=0.030..2.599 rows=4001.00 loops=1) Index Cond: (created_at >= '2024-12-01 00:00:00+00'::timestamp with time zone) Index Searches: 1 Buffers: shared hit=34 read=13 Planning: Buffers: shared hit=8 read=2 Planning Time: 0.316 ms Execution Time: 4.005 ms
A range on the uncorrelated column matches rows scattered across the whole table. Fetching them in index order would jump around, so the planner builds a bitmap and reads each page once:
select id, user_id from orders where user_id between 100 and 300;Bitmap Heap Scan on orders (cost=85.97..974.53 rows=5237 width=8) (actual time=0.547..4.102 rows=5213.00 loops=1)
Recheck Cond: ((user_id >= 100) AND (user_id <= 300))
Heap Blocks: exact=809
Buffers: shared hit=810 read=6
-> Bitmap Index Scan on orders_user_id_idx (cost=0.00..84.66 rows=5237 width=0) (actual time=0.434..0.434 rows=5213.00 loops=1)
Index Cond: ((user_id >= 100) AND (user_id <= 300))
Index Searches: 1
Buffers: shared hit=1 read=6
Planning:
Buffers: shared hit=4 read=2
Planning Time: 0.228 ms
Execution Time: 5.714 msLook at Heap Blocks: about 5% of the rows match, yet they sit on almost every page of the table, so even the bitmap scan reads nearly all of it. The fraction of pages touched matters more than the fraction of rows. A little wider and a sequential scan would win.
When the index holds every column the query needs, the table hardly has to be visited. Heap Fetches counts the rows that still had to be checked in the table, because their page was not yet marked all-visible by VACUUM; on a settled table it stays near zero:
select count(*) from orders where user_id between 100 and 300;Aggregate (cost=154.12..154.13 rows=1 width=8) (actual time=3.262..3.264 rows=1.00 loops=1)
Buffers: shared hit=9
-> Index Only Scan using orders_user_id_idx on orders (cost=0.29..141.03 rows=5237 width=0) (actual time=0.013..1.863 rows=5213.00 loops=1)
Index Cond: ((user_id >= 100) AND (user_id <= 300))
Heap Fetches: 1
Index Searches: 1
Buffers: shared hit=9
Planning:
Buffers: shared hit=6
Planning Time: 0.224 ms
Execution Time: 3.296 msAnd when most of the table matches, none of the index paths is worth it:
select count(*) from orders where created_at >= '2023-03-01';Aggregate (cost=2289.78..2289.79 rows=1 width=8) (actual time=49.356..49.358 rows=1.00 loops=1)
Buffers: shared hit=810
-> Seq Scan on orders (cost=0.00..2060.00 rows=91910 width=0) (actual time=0.694..27.997 rows=91910.00 loops=1)
Filter: (created_at >= '2023-03-01 00:00:00+00'::timestamp with time zone)
Rows Removed by Filter: 8090
Buffers: shared hit=810
Planning Time: 0.135 ms
Execution Time: 49.397 msWhat to take from it#
- A sequential scan is not a bug. On a small table, or when most rows match, it is the right plan.
- The same index can lead to an index scan, a bitmap scan or no use at all, depending on how many rows match and where they live.
- The planner works from estimates. When a plan looks wrong, compare its estimated rows with the actual rows before anything else; that is the first step in reading a plan.
Try it yourself#
Each exercise runs on the same sample database. Your changes are made inside a transaction and undone after every check, so you cannot break anything.
In MySQL#
Not run here; from the MySQL reference manual. InnoDB's equivalents are a full table scan (type: ALL in EXPLAIN), range and ref lookups through an index, and covering index reads (Using index). Because rows are stored in primary key order, a range on the primary key is naturally a sequential read. MySQL has no bitmap heap scan; Multi-Range Read (Using MRR) plays a similar role by sorting row lookups before reading them.
Sources#
- PostgreSQL documentation: Using EXPLAIN, Planner Cost Constants (
seq_page_cost,random_page_cost), Statistics Used by the Planner, pg_stats (correlation), Index-Only Scans and Covering Indexes. - MySQL reference manual: EXPLAIN Output Format, Multi-Range Read Optimization.