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.

Before thisB-tree indexes
On this page
  1. The four ways to read a table
  2. How the planner chooses
  3. What to take from it
  4. Try it yourself
  5. In MySQL
  6. Sources

"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 Scan feeding a Bitmap 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:

sql
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;
Result 4 rows; real output from PostgreSQL 18.6 (PGlite 0.5.9)
column_namecorrelation
created_at1.000
id1.000
total0.000
user_id-0.003
sql
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:

sql
select id, created_at from orders where created_at >= '2024-12-01';
Plan, executed real output from PostgreSQL 18.6 (PGlite 0.5.9). Timings depend on the machine; the shape and the row counts do not
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:

sql
select id, user_id from orders where user_id between 100 and 300;
Plan, executed real output from PostgreSQL 18.6 (PGlite 0.5.9). Timings depend on the machine; the shape and the row counts do not
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 ms

Look 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:

sql
select count(*) from orders where user_id between 100 and 300;
Plan, executed real output from PostgreSQL 18.6 (PGlite 0.5.9). Timings depend on the machine; the shape and the row counts do not
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 ms

And when most of the table matches, none of the index paths is worth it:

sql
select count(*) from orders where created_at >= '2023-03-01';
Plan, executed real output from PostgreSQL 18.6 (PGlite 0.5.9). Timings depend on the machine; the shape and the row counts do not
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 ms

What 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.

Exercise

Who bought this product?

The product page lists the orders that included it. order_items has a foreign key to products, so it seems as if it ought to be indexed, but the query reads well over a thousand pages.

Your task. Cut the pages read to a few hundred.

select o.id, o.created_at
from order_items oi
join orders o on o.id = oi.order_id
where oi.product_id = 77

This exercise runs a real database in your browser and needs JavaScript.

Exercise

Page 2,501 of the order list

An admin list shows orders newest first, 20 per page, using OFFSET. Page 2,501 is painfully slow: to skip 50,000 rows the database has to produce them first. The previous page ended with the order created at 2023-12-31 14:10:51+00 (created_at is unique in this table).

Your task. Fetch the same 20 rows by starting after the last row you already have, instead of skipping 50,000.

select id, created_at, total
from orders
order by created_at desc
offset 50000
limit 20

This exercise runs a real database in your browser and needs JavaScript.

Exercise

One month of events

The events table is partitioned by month, so a query for one month should only touch that month's partition. This one reads all twelve.

Your task. Make the query read only November's partition.

select count(*) from events where date_trunc('month', at) = '2024-11-01'

This exercise runs a real database in your browser and needs JavaScript.

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#

Esc
↑ ↓ to move↵ to open