Seq Scan Versus Index Scan Versus Bitmap Scan Explained

Someone adds an index, runs the query and sees Seq Scan in the plan. The usual reaction is that PostgreSQL ignored the index. Usually it did the sensible thing, and the fix, if one is needed, lies elsewhere. The planner chooses among three ways to read a table, and each is best in a different range of selectivity. This article explains how each scan works, what decides between them and how to read the clues in a plan. It is part of the series that reading EXPLAIN ANALYZE output in PostgreSQL step by step opens.

Sequential scan

Seq Scan on app_order  (cost=0.00..1500.00 rows=10000 width=12)
  Filter: (status = 'paid')

The node reads every page of the table from start to end, in physical order, and applies the filter to each row. Cost is proportional to the table's size and independent of the filter. Pages are read sequentially, which operating systems and disks handle well, with read-ahead. When a filter keeps a large share of the rows (say a fifth or more), reading everything is cheaper than any alternative, because alternatives pay a per-row overhead.

A sequential scan is also the only option when no index matches the condition, when the table is small (a few pages, where the index overhead exceeds the table read) or when the query needs all rows anyway (an aggregate over the whole table). On large tables PostgreSQL can parallelize it with Parallel Seq Scan, covered in making sense of parallel query plans.

Index scan

Index Scan using app_order_customer_idx on app_order  (cost=0.43..8.45 rows=3 width=12)
  Index Cond: (customer_id = 42)

The node descends the B-tree to the first matching entry, then for each entry in range fetches the row from the heap using its location. The index returns matches in index order, so an index scan can also satisfy an ORDER BY without a sort. The cost per row is a heap page fetch which, for a table whose physical order is unrelated to the index order, is a random read. That is why index scans win for few rows and lose for many.

The planner models the effect with the column's correlation statistic (how well the index order matches the physical order). A highly correlated column, such as an increasing timestamp in an append-only table, makes index scans cheap even for larger ranges, because adjacent index entries point to adjacent pages. A uncorrelated column, such as a random UUID or a customer id on a table in insertion order, makes each match a separate random page.

Bitmap scan

Bitmap Heap Scan on app_order  (cost=120.5..2500.0 rows=8000 width=12)
  Recheck Cond: (customer_id = ANY ('{1,2,3}'::bigint[]))
  ->  Bitmap Index Scan on app_order_customer_idx  (cost=0.0..118.5 rows=8000 width=0)
        Index Cond: (customer_id = ANY ('{1,2,3}'::bigint[]))

A bitmap scan has two steps. The Bitmap Index Scan reads the index and builds an in-memory bitmap of the matching rows' locations, one bit per row or, when memory is short, one bit per page. The Bitmap Heap Scan then reads the marked pages in physical order, once each, and rechecks the condition when the bitmap is lossy. Reading pages in order turns random access into something close to sequential, so a bitmap scan beats a plain index scan when the matching rows are many but not most.

Its second strength is combining indexes. BitmapAnd and BitmapOr nodes intersect or union the bitmaps of several indexes:

Bitmap Heap Scan on app_order
  Recheck Cond: ((status = 'paid') AND (customer_id = 42))
  ->  BitmapAnd
        ->  Bitmap Index Scan on app_order_status_idx
        ->  Bitmap Index Scan on app_order_customer_idx

That lets two single-column indexes serve a two-condition query. The costs: no ordered output (a sort is needed if you want order), and Recheck Cond plus Heap Blocks: exact=... lossy=... lines in the analyzed plan. Lossy blocks mean the bitmap exceeded work_mem and degraded to page granularity, so each page must be rechecked row by row; raise work_mem if lossy counts are large.

Index only scan

Index Only Scan using app_order_customer_total_idx on app_order  (cost=0.43..4.50 rows=3 width=16)
  Index Cond: (customer_id = 42)
  Heap Fetches: 0

If every column the query needs is in the index (as key columns or INCLUDE columns), the node can return values from the index without visiting the heap. PostgreSQL still needs to know that each row is visible to the current transaction, and that information lives in the heap; the visibility map records pages where all rows are visible to everyone. For such pages the scan skips the heap. For others it visits the heap, counted as Heap Fetches. A high Heap Fetches means the visibility map is stale because VACUUM has not run recently; autovacuum updates it, and a manual VACUUM on the table fixes a sudden slowdown of an index-only scan. The technique of adding columns to an index is covered in covering indexes with INCLUDE.

How the planner chooses

For each table access, the planner estimates the cost of each path from statistics and picks the cheapest. The inputs:

• Selectivity: the estimated fraction of rows that match the condition.

• Table and index size: pages and tuples.

• **random_page_cost and seq_page_cost**: the relative cost of a random page and a sequential page (defaults 4.0 and 1.0).

• Correlation: physical ordering versus the index.

• **effective_cache_size**: how much of the data is likely cached, lowering the effective random-read cost.

Typical switch points on default settings with uncorrelated data: an index scan for up to about 1 percent of rows, a bitmap scan from there up to perhaps 10 to 20 percent, a sequential scan above. Those numbers move: on SSD storage with random_page_cost near 1.1, index and bitmap scans stay competitive to higher fractions, which is the subject of tuning PostgreSQL for SSDs with random_page_cost.

When a seq scan is the right answer

Read the estimate and the filter. If Rows Removed by Filter is small compared with the rows returned, the scan is efficient: it read what it needed. Only when the scan discards nearly everything is an index likely to help. On a table of 100,000 rows where the query returns 30,000, a sequential scan is correct and an index would slow it. A small table fits in a few pages, and any index lookup costs as much as reading the table.

The plans that do indicate a problem: a sequential scan on a large table returning a handful of rows (a missing or unusable index), a sequential scan inside a nested loop executed thousands of times (the inner side needs an index) and a scan whose estimate of selectivity is wrong, so the planner thinks the filter keeps half the table when it keeps 0.01 percent.

Why an existing index is not used

If a selective query still scans the table, check in this order:

1. The condition wraps the column in a function or cast, such as WHERE lower(email) = ... or WHERE created_at::date = ..., which needs an expression index or a rewritten condition.

2. The types differ, as with comparing a bigint column to a numeric parameter, causing a cast on the column.

3. A leading wildcard, as LIKE '%term', needs a trigram index.

4. The index has the wrong column order for the condition; a composite index on (a, b) does not serve a filter on b alone.

5. Statistics are stale after a big load. Run ANALYZE.

6. The planner thinks the table is small because the statistics say so.

7. The index is invalid after a failed CREATE INDEX CONCURRENTLY.

8. The query returns a large fraction of the table, and the scan is right.

Testing with enable_ settings

You can discourage a scan type for a session to see what the planner would otherwise do:

SET enable_seqscan = off;
EXPLAIN (ANALYZE, BUFFERS) SELECT * FROM app_order WHERE customer_id = 42;
RESET enable_seqscan;

This does not forbid sequential scans; it adds a large cost penalty. If the index plan is faster, the planner's costs or estimates were wrong, and the fix is to correct them: statistics, random_page_cost, an extended statistic. If the index plan is not faster, the planner was right. The enable_* settings are for diagnosis. A setting left off in a deployment makes plans brittle.

When forcing a scan type is justified

Rarely. Reasonable cases: a one-off maintenance query where you know the data better than the statistics; a session-level override for a known-bad estimate while a proper fix is prepared; and a SET LOCAL inside a transaction for a specific batch job whose behavior has been measured. Never leave a global enable_seqscan = off in postgresql.conf as a fix, because it will punish every query that legitimately needs a scan. Prefer to fix the cause, as described in why the planner estimates the wrong number of rows.

What to do next

Look at your three slowest queries and classify the scan on each big table as correct, avoidable or wrong, using the questions above. The manual describes the scan types in using EXPLAIN and the index types in index types. For choosing the join that follows a scan, read nested loop, hash join and merge join compared.