Filter vs Recheck Conditions: Diagnosing Bitmap Scan Overhead #

When EXPLAIN (ANALYZE, BUFFERS) output shows both a Filter node and a Recheck Cond node on the same query, PostgreSQL is telling you two different things about predicate evaluation — and confusing them leads to the wrong tuning action. This page isolates that decision point: what each node means mechanically, what the Heap Blocks: exact=N lossy=M line exposes, and the exact steps to drive unnecessary rechecks to zero.

The Triggering Condition: When Bitmap Memory Runs Out #

The distinction between Filter and Recheck Cond is rooted in the filter pushdown mechanics that govern how early or late a predicate is evaluated in the execution tree.

A Filter is applied row-by-row as rows emerge from the scan node. On a Seq Scan, every row from the heap is tested immediately; on an Index Scan, rows fetched from the heap are tested against any predicate that the index could not satisfy. Either way, the engine works with individual rows, not pages.

A Recheck Cond exists exclusively on Bitmap Heap Scan nodes and has a specific trigger: the bitmap that maps candidate rows ran out of work_mem. The two-phase bitmap scan works like this:

  1. Bitmap Index Scan phase — the index is walked and matching row TIDs (tuple identifiers) are stored in a bitmap in memory, sorted by physical heap location to enable sequential I/O.
  2. Bitmap Heap Scan phase — the engine reads only the heap pages that the bitmap references, re-evaluating the original index predicate if necessary.

When work_mem is sufficient, the bitmap stores exact TIDs. The Recheck Cond is present in the plan (it is always emitted for bitmap scans), but the engine skips re-evaluation for individual rows because the bitmap already guarantees they match. When work_mem is exhausted, the bitmap degrades to page-level tracking: instead of recording “row 42 on page 7,” it records only “page 7.” Every row on every marked page must now be re-tested — that is the lossy recheck.

The plan line that reveals which mode you are in is:

Heap Blocks: exact=1240 lossy=0

vs.

Heap Blocks: exact=0 lossy=2380

The second output means the entire result was processed in lossy mode and every qualifying page had every row re-evaluated.

Annotated EXPLAIN Evidence #

The two plan fragments below show the same query run first with a small work_mem (lossy) and then with adequate work_mem (exact).

Lossy bitmap scan (insufficient work_mem):

SET LOCAL work_mem = '512kB';

EXPLAIN (ANALYZE, BUFFERS)
SELECT id, payload
FROM events
WHERE severity = 'ERROR' AND source = 'auth-service';
Bitmap Heap Scan on events  (cost=284.12..6821.44 rows=1803 width=48)
                            (actual time=4.3..312.6 rows=1803 loops=1)
  Recheck Cond: ((severity = 'ERROR') AND (source = 'auth-service'))
  Rows Removed by Index Recheck: 74912          -- <-- lossy overhead: 74k wasted row tests
  Heap Blocks: exact=0 lossy=2380               -- <-- all blocks tracked at page level only
  Buffers: shared hit=148 read=2380
  ->  Bitmap Index Scan on events_severity_idx  (cost=0.00..283.67 rows=1803 width=0)
                                                (actual time=3.8..3.8 rows=1803 loops=1)
        Index Cond: (severity = 'ERROR')
        Buffers: shared hit=148
Planning Time: 0.9 ms
Execution Time: 313.2 ms

Key signals to read:

Exact bitmap scan (adequate work_mem):

SET LOCAL work_mem = '32MB';

EXPLAIN (ANALYZE, BUFFERS)
SELECT id, payload
FROM events
WHERE severity = 'ERROR' AND source = 'auth-service';
Bitmap Heap Scan on events  (cost=284.12..6821.44 rows=1803 width=48)
                            (actual time=4.1..18.7 rows=1803 loops=1)
  Recheck Cond: ((severity = 'ERROR') AND (source = 'auth-service'))
  Rows Removed by Index Recheck: 0              -- <-- no wasted row tests
  Heap Blocks: exact=1240 lossy=0               -- <-- exact TID tracking restored
  Buffers: shared hit=1388
  ->  Bitmap Index Scan on events_severity_idx  (cost=0.00..283.67 rows=1803 width=0)
                                                (actual time=3.9..3.9 rows=1803 loops=1)
        Index Cond: (severity = 'ERROR')
        Buffers: shared hit=148
Planning Time: 0.9 ms
Execution Time: 18.9 ms

Execution time dropped from 313 ms to 19 ms purely by eliminating lossy rechecks. The Recheck Cond line is still present — it always is for bitmap scans — but Rows Removed by Index Recheck: 0 confirms it did no real work.

The Bitmap Scan Memory Transition #

The diagram below shows the two execution paths — exact TID mode and lossy page mode — and where the memory boundary sits.

Bitmap Scan Memory Modes Two side-by-side diagrams showing how the bitmap index scan stores results in exact TID mode when work_mem is sufficient versus lossy page mode when work_mem is exhausted, and the downstream effect on the Recheck Cond in the Bitmap Heap Scan. work_mem sufficient — exact mode Bitmap Index Scan walks index → collects TIDs Bitmap (exact TIDs) TID (page 7, row 42) ✓ TID (page 7, row 91) ✓ Bitmap Heap Scan fetches exact rows only Heap Blocks: exact=N lossy=0 Rows Removed by Recheck: 0 work_mem exhausted — lossy mode Bitmap Index Scan walks index → TIDs overflow Bitmap (page-level only) page 7 marked — all rows TID precision lost Bitmap Heap Scan + Recheck scans every row on every page Heap Blocks: exact=0 lossy=M Rows Removed by Recheck: large

Step-by-Step Resolution Workflow #

Step 1 — Capture the baseline.

Run EXPLAIN (ANALYZE, BUFFERS) and record the Bitmap Heap Scan node’s Heap Blocks line and Rows Removed by Index Recheck. If lossy=0 already, there is no problem to fix.

EXPLAIN (ANALYZE, BUFFERS)
SELECT id, payload
FROM events
WHERE severity = 'ERROR' AND source = 'auth-service';
-- Note: Heap Blocks: exact=X lossy=Y

Step 2 — Check current work_mem.

SHOW work_mem;
-- Default is often 4MB — insufficient for large bitmap index scans

Step 3 — Test with higher work_mem in session scope.

SET LOCAL limits the change to the current transaction; it will not affect other sessions or persist after the transaction ends. Use it to test the effect before committing to a global change.

BEGIN;
SET LOCAL work_mem = '64MB';

EXPLAIN (ANALYZE, BUFFERS)
SELECT id, payload
FROM events
WHERE severity = 'ERROR' AND source = 'auth-service';
-- Check: Heap Blocks: exact=N lossy=0
-- Check: Rows Removed by Index Recheck: 0
ROLLBACK;

Step 4 — Quantify the row volume driving the bitmap.

A bitmap degrades to lossy when the number of candidate TIDs exceeds roughly work_mem / 6 bytes. To see how many rows the index condition matches:

SELECT COUNT(*)
FROM events
WHERE severity = 'ERROR';
-- If this is > (work_mem_bytes / 6), the bitmap will go lossy at current work_mem

Step 5 — If work_mem increase is not viable, add a composite index.

Adding source alongside severity in the index allows the Bitmap Index Scan to return fewer TIDs because both predicates are evaluated at index time, reducing bitmap memory pressure:

CREATE INDEX CONCURRENTLY idx_events_severity_source
ON events (severity, source);

EXPLAIN (ANALYZE, BUFFERS)
SELECT id, payload
FROM events
WHERE severity = 'ERROR' AND source = 'auth-service';
-- Expect: far fewer TIDs in the bitmap → lossy=0

Step 6 — Evaluate a covering index for Index Only Scan.

When the query only needs id and payload, a covering index that includes those columns eliminates the heap scan phase entirely — no bitmap, no recheck:

CREATE INDEX CONCURRENTLY idx_events_covering
ON events (severity, source) INCLUDE (id, payload);

EXPLAIN (ANALYZE, BUFFERS)
SELECT id, payload
FROM events
WHERE severity = 'ERROR' AND source = 'auth-service';
-- Expect: Index Only Scan — no Bitmap Heap Scan, no Recheck Cond

A covering index removes not just the recheck overhead but also all heap I/O for matching rows, which is especially effective on wide tables. Note that covering indexes increase write amplification, so benchmark both reads and writes before deploying to production.

Before/After Plan Comparison #

The two critical metrics that change when lossy rechecks are eliminated:

-- BEFORE (lossy, work_mem=512kB)
Heap Blocks: exact=0 lossy=2380   →   Rows Removed by Index Recheck: 74912

-- AFTER (exact, work_mem=32MB or composite index)
Heap Blocks: exact=1240 lossy=0   →   Rows Removed by Index Recheck: 0

Execution time in this case dropped from 313 ms to 19 ms. The cost estimate in the plan did not change — the planner does not model the lossy/exact distinction — which is why EXPLAIN (ANALYZE, BUFFERS) rather than bare EXPLAIN is essential for diagnosing this class of problem. Understanding how cost estimation models work explains why the planner cannot anticipate this at planning time.

Common Pitfalls #

Treating Recheck Cond as the problem when lossy=0. The Recheck Cond line is always emitted for bitmap scans. When lossy=0, it does nothing — the bitmap already identified the exact rows. Only lossy > 0 is actionable.

Raising work_mem globally without checking concurrent session count. A global SET work_mem = '64MB' multiplied across 50 active connections can exhaust server RAM. Use SET LOCAL in critical session-level queries or apply it via a connection pooler parameter rather than postgresql.conf.

Building an index that still returns too many TIDs. A single-column index on a low-selectivity column (like severity with only a few distinct values) can return millions of TIDs. The bitmap will go lossy regardless of work_mem if the TID count exceeds the memory budget. The fix is a more selective composite index, not just more memory.

Overlooking Rows Removed by Filter on the same node. A Bitmap Heap Scan can show both Recheck Cond and a separate Filter. The Filter removes rows that do not match a predicate absent from the index condition entirely. These are independent: fixing the recheck (by adjusting memory) does not reduce rows removed by a filter that relies on a non-indexed column. See identifying plan bottlenecks for a method to triage multiple node-level signals together.

Frequently Asked Questions #

Does a Recheck Cond mean my index is broken or misconfigured?

Not necessarily. Recheck Cond is a standard part of bitmap scan execution, especially for GIN indexes and high-cardinality result sets. It becomes a problem only when lossy > 0 forces the engine to re-evaluate entire heap pages rather than the exact matching rows that the index found.

How does work_mem directly affect Filter vs Recheck behavior?

When work_mem is too small to hold exact row TIDs, PostgreSQL degrades the bitmap to page-level tracking. This forces the Recheck Cond to evaluate every row on those pages, including rows that do not match the predicate. Increasing work_mem restores exact TID tracking and removes that overhead. The filter pushdown mechanics section covers how predicate placement in the plan tree determines where this evaluation happens.

Can I eliminate Recheck Cond entirely?

A Recheck Cond with lossy=0 carries negligible overhead and is not worth eliminating. The goal is to drive lossy to zero via higher work_mem or a selective composite index. If you need to remove the bitmap phase entirely, a covering index that enables an Index Only Scan achieves that while also eliminating all heap I/O for the query.