Bitmap Heap Scan Rechecking Excessive Rows (Lossy Bitmap)

Scenario

A product search query uses a composite index and returns about 500 rows, but runs for 8 seconds. EXPLAIN (ANALYZE, BUFFERS) shows Heap Blocks: exact=20 lossy=4800 and Rows Removed by Index Recheck: 982,000. An engineer wrongly suspects the index is corrupt. The actual cause is that work_mem is too low for the bitmap to fit in memory, causing the planner to switch to a lossy (page-granularity) bitmap.

How to Identify

Conditions:

• EXPLAIN (ANALYZE, BUFFERS) output shows Heap Blocks: exact=X lossy=Y where lossy count is high
• Rows Removed by Index Recheck: counter is very high relative to returned rows
• work_mem is set very low (64kB–1MB)
• A Bitmap Index Scan + Bitmap Heap Scan is in the plan (not a plain Index Scan)
• Table has many rows and the bitmap for matching pages exceeds work_mem

Analysis Steps

-- 1. Run EXPLAIN with BUFFERS to see exact vs lossy bitmap blocks
EXPLAIN (ANALYZE, BUFFERS, FORMAT TEXT)
SELECT * FROM products WHERE category = 'electronics' AND in_stock = true;

-- Look for in the output:
--   Bitmap Heap Scan on products
--     Recheck Cond: (...)
--     Rows Removed by Index Recheck: <high number>
--     Heap Blocks: exact=X lossy=Y    <- lossy=Y is the problem

-- 2. Check current work_mem
SHOW work_mem;

-- 3. Understand why lossy bitmaps occur:
-- Each page needs 1 bit in exact mode.
-- If total pages > (work_mem * 8), bitmap switches to lossy (1 bit per page, no row tracking)
-- In lossy mode: every row on a lossy page must be rechecked against the predicate
SELECT
    pg_size_pretty(pg_relation_size('products'))    AS table_size,
    pg_relation_size('products') / 8192             AS total_pages,
    current_setting('work_mem')                     AS current_work_mem;

-- 4. Estimate bitmap size needed for exact mode:
-- exact_bitmap_bytes = total_pages / 8
-- If exact_bitmap_bytes > work_mem → lossy

-- 5. Check effective_io_concurrency (controls prefetch for Bitmap Heap Scan)
SHOW effective_io_concurrency;

Pitfalls

• Lossy bitmaps are a work_mem problem, NOT an index problem — do not drop or rebuild the index
• Increasing work_mem affects all concurrent queries; each connection can allocate work_mem per sort/hash operation — use SET LOCAL work_mem in a transaction for targeted sessions
• A plain Index Scan is different from a Bitmap Index Scan + Bitmap Heap Scan — bitmaps combine results from multiple indexes; lossy mode only affects bitmap scans
• effective_io_concurrency should be 200 for SSDs, 1-4 for spinning disks — it controls how aggressively PostgreSQL prefetches bitmap heap blocks
• A composite index on the exact filtered columns can eliminate the bitmap scan entirely by making a plain Index Scan viable

Resolution Approach

Lossy bitmaps occur when the in-memory bitmap for matching pages exceeds work_mem. The fix is not about the index — it is about memory: