Bitmap Heap Scans and Rechecks

In this lesson, you will learn how PostgreSQL uses bitmap scans to bridge the gap between index metadata and raw heap data storage.

The Problem: Random I/O

When you run a query like SELECT * FROM sales WHERE category = 'electronics', the planner often uses an index. If the index returns thousands of matching rows, a standard "Index Scan" would jump back and forth between the index and the heap (the actual table storage) for every single match. If those rows are scattered across different pages of the heap, this leads to expensive random I/O.

The Bitmap Solution

To solve this, PostgreSQL performs a Bitmap Heap Scan. It splits the process into two phases:

1. Bitmap Index Scan: The engine scans the index and builds a "bitmap" in memory. This bitmap is a compact bitmask where each bit represents a page in the heap. If a bit is set to 1, it means that page contains at least one matching row.
2. Bitmap Heap Scan: Once the bitmap is fully populated, the engine sorts the bits by page number and visits the heap pages in physical order. By visiting pages in order, the engine transforms random I/O into sequential I/O, which is significantly faster.

The Necessity of Rechecks

Because the bitmap tracks pages rather than individual rows, we lose some precision. A bitmap might indicate that page #42 contains a match, but it doesn't store exactly which row inside that page qualified.

If the bitmap is small enough to fit in memory (defined by work_mem), it is highly accurate. However, if the result set is massive, the bitmap may become "lossy," meaning it flags an entire page as a match even if only one row technically qualifies. Consequently, after fetching the page, the engine must perform a Recheck.

-- Example EXPLAIN plan indicator
->  Bitmap Heap Scan on sales
      Recheck Cond: (category = 'electronics')  -- The recheck phase
      ->  Bitmap Index Scan on idx_sales_cat

The "Recheck" step re-evaluates the WHERE clause filter against the actual data in the heap page to ensure the results are accurate, discarding any false positives picked up by the lossy bitmap.

Key Takeaway: Bitmap Heap Scans optimize disk access by converting scattered random lookups into efficient, page-ordered sequential reads, using a recheck phase to ensure data integrity when memory constraints force the bitmap to be lossy.