Database Indexing – Part 5: Sequential Scan vs. Index Scan vs. Bitmap Index Scan in PostgreSQL

In my previous articles, we explored different types of indexes in PostgreSQL.

But creating an index doesn't mean PostgreSQL will always use it.

Depending on the query and the number of matching records, PostgreSQL may choose a Sequential Scan, an Index Scan, or a Bitmap Index Scan.

In this article, we'll understand how these scan methods work using practical examples and PostgreSQL execution plans.

Understanding Scan Methods with an Example

Let's use a students table to understand when PostgreSQL chooses a Sequential Scan, Index Scan, or Bitmap Index Scan.

1. Creating the Table

CREATE TABLE students (
    id BIGSERIAL PRIMARY KEY,
    name TEXT,
    grades INTEGER
);

Since id is the primary key, PostgreSQL automatically creates an index on it.

2. Inserting Records

Let's insert 1 million student records.

INSERT INTO students (name, grades)
SELECT
    'Student_' || g,
    (g % 100) + 1
FROM generate_series(1, 1000000) AS g;

The grades column contains values from 1 to 100.

3. Creating an Index on Grades

CREATE INDEX idx_students_grades
ON students (grades);

Now, we have two indexes:

• Primary key index: On id
• Separate index: On grades

4. Updating Table Statistics

Before running our experiments, let's understand why updating table statistics is important.

PostgreSQL uses statistics to estimate how many records a query might return. Based on these estimates, it decides whether scanning the table or using an index would be more efficient.

We can check the statistics using:

SELECT
    relname,
    n_live_tup,
    n_mod_since_analyze,
    last_analyze,
    last_autoanalyze
FROM pg_stat_user_tables
WHERE relname = 'students';

Here:

• n_live_tup: Estimated number of live records.
• n_mod_since_analyze: Estimated number of records modified since the last analysis.
• last_analyze: Last time statistics were updated manually.
• last_autoanalyze: Last time statistics were updated automatically.

Before ANALYZE:

We can see that n_mod_since_analyze is 1,000,000, meaning PostgreSQL has recorded approximately 1 million modifications since the last analysis.

Now, let's update the statistics manually.

ANALYZE students;

After ANALYZE:

After running ANALYZE, we can observe that:

• n_mod_since_analyze changed from 1,000,000 to 0.
• last_analyze was updated with the execution time.
• PostgreSQL refreshed the statistics used for estimating query costs.

PostgreSQL also performs this automatically through auto-analyze. We ran it manually here to understand how the statistics change.

Refer more here

Now that our table and indexes are ready, let's run a few queries and observe which scan methods PostgreSQL chooses.

1. Index Scan

Let's start with a query that retrieves a small number of records from our students table.

EXPLAIN (ANALYZE, BUFFERS)
SELECT name
FROM students
WHERE id < 100;

Execution Plan:

PostgreSQL chose an Index Scan using students_pkey, the primary key index on id.

How Does an Index Scan Work?

1. PostgreSQL searches the index to find entries where id < 100.
2. Each matching index entry contains a reference to the corresponding row in the table (heap).
3. PostgreSQL uses these references to fetch the rows from the heap and retrieve the name values.
4. This process continues until all matching records are retrieved.

Since we're selecting name, which is not stored in the primary key index, PostgreSQL needs to visit the heap to retrieve it.

Why Did PostgreSQL Choose an Index Scan?

Our table contains 1 million records, but this query needs only 99.

Instead of scanning the entire table, PostgreSQL uses the primary key index to locate the matching records.

An Index Scan is generally useful when a query retrieves a small number of records, especially when the required rows can be found through an index without scanning most of the table.

2. Sequential Scan

Now, let's change the condition to retrieve most of the records from our students table.

EXPLAIN (ANALYZE, BUFFERS)
SELECT name
FROM students
WHERE id > 100;

Execution Plan:

This time, PostgreSQL chose a Sequential Scan (Seq Scan), even though we already have an index on id.

How Does a Sequential Scan Work?

1. PostgreSQL reads the table pages sequentially.
2. It checks each row against the condition id > 100.
3. If the row matches, PostgreSQL retrieves its name.
4. This continues until the entire table has been scanned.

Why Didn't PostgreSQL Use the Index?

Our table contains 1 million records, and this query returns almost all of them.

If PostgreSQL used an Index Scan, it would need to find the matching entries in the index and then visit the corresponding heap rows to retrieve their names.

Since almost every row matches, repeatedly accessing the table through index entries would involve unnecessary work.

Instead, PostgreSQL chose to scan the table directly.

A Sequential Scan can be more efficient than an Index Scan when a query needs to retrieve a large portion of the table.

3. Bitmap Index Scan

Now, let's filter students whose grades are greater than 95.

EXPLAIN (ANALYZE, BUFFERS)
SELECT name
FROM students
WHERE grades > 95;

Execution Plan:

PostgreSQL used a Bitmap Index Scan on idx_students_grades, followed by a Bitmap Heap Scan.

How Does a Bitmap Index Scan Work?

In a regular Index Scan, PostgreSQL uses the index to locate matching rows and fetches them from the heap.

In a Bitmap Index Scan, PostgreSQL first collects the locations of all matching rows into a bitmap. The Bitmap Heap Scan then uses this information to fetch the required heap pages.

Let's take a small example.

Each index entry contains a TID (Tuple Identifier), which identifies a row using its heap page number and tuple offset.

Suppose the index finds these matching locations:

Page 10 → Tuples [2, 5, 8]
Page 20 → Tuples [3, 7]
Page 30 → Tuple [4]

PostgreSQL stores these locations in a bitmap and processes the heap pages in page order.

When Page 10 is fetched into memory, the entire page (usually 8 KB) is loaded, including all the tuples stored on it.

However, PostgreSQL already knows that only tuples 2, 5, and 8 matched the index condition. So it directly accesses those tuples, checks their visibility, and retrieves the required values.

This is called an exact bitmap.

PostgreSQL can also combine multiple indexes using BitmapAnd and BitmapOr when queries have multiple filtering conditions.

I've explained both methods with practical examples in my previous article: Database Indexing – Part 3: Understanding Composite Indexes in PostgreSQL.

Why Did PostgreSQL Choose a Bitmap Index Scan?

Our table contains 1 million records, and this query returns 50,000 records.

Using a regular Index Scan could involve repeatedly accessing heap pages for individual matching rows.

A Sequential Scan would need to scan the entire table.

A Bitmap Index Scan allows PostgreSQL to collect the matching row locations first and then access the required heap pages in page order, reducing unnecessary page accesses.

Understanding Recheck Cond and Lossy Bitmap Pages

If we look at our execution plan, we can see:

Recheck Cond: (grades > 95)
Heap Blocks: exact=7352

Here, exact=7352 means PostgreSQL had the exact matching tuple locations for all 7,352 heap pages.

But storing all these tuple locations requires memory.

When there isn't enough memory, PostgreSQL can convert some exact bitmap entries into lossy entries.

Instead of remembering the matching tuple offsets:

Page 10 → Tuples [2, 5, 8]

It remembers only the page:

Page 10 → May contain matching tuples

When PostgreSQL fetches this page, it has to examine the candidate tuples and check the condition grades > 95 again, since the bitmap no longer contains the exact matching offsets.

This is where Recheck Cond is used.

Let's try this practically by reducing work_mem to 64 KB.

BEGIN;

SET LOCAL work_mem = '64kB';

EXPLAIN (ANALYZE, BUFFERS)
SELECT name
FROM students
WHERE grades > 95;

ROLLBACK;

Execution Plan:

This time, PostgreSQL used a Parallel Bitmap Heap Scan.

Recheck Cond: (grades > 95)
Rows Removed by Index Recheck: 288507
Heap Blocks: exact=209 lossy=1660

Here:

• exact=209: Heap-block accesses with exact tuple-location information.
• lossy=1660: Heap-block accesses where only page-level information was available.
• Rows Removed by Index Recheck: 288507: Candidate rows that PostgreSQL rejected after evaluating the condition again.

Since this was a parallel scan, the heap-block counts shown are not necessarily the total number of distinct pages processed by all workers.

With sufficient memory, PostgreSQL can remember the exact matching tuple locations. When memory is limited, it may retain only page locations and recheck the filtering condition while scanning the heap.

PostgreSQL doesn't always use an index just because one is available. It chooses a scan method based on what it estimates will be most efficient for the query.

In the next article, we'll explore how PostgreSQL's query optimizer makes these decisions.

Thanks for reading! I hope this article helped you understand how different scan methods work in PostgreSQL.