BitmapOr and BitmapAnd for OR and Combined Conditions #

WHERE email = $1 OR phone = $2 on a 60-million-row contacts table has an index on each column and still runs as a sequential scan. Split into two queries, each returns in under a millisecond. The planner can combine the two indexes — but only when each branch of the OR is indexable on its own and the combination looks cheaper than reading the table.

Index access paths normally use one index per scan, as described in sequential vs index scans. Bitmap scans are the exception: they can merge the results of several index scans before touching the heap.

The Planner Condition #

A bitmap index scan does not fetch rows; it builds a bitmap of matching row locations (TIDs, or whole pages once memory runs short). Bitmaps from different index scans can be combined:

• BitmapOr — union of bitmaps, for a = 1 OR b = 2. Every branch of the OR must be satisfiable by some index; if even one branch has no usable index, the whole OR needs a sequential scan (or a Filter over another access path).
• BitmapAnd — intersection of bitmaps, for a = 1 AND b = 2 when no single multicolumn index covers both and each condition alone is not selective enough.

A Bitmap Heap Scan then visits the heap pages in physical order and rechecks conditions where needed. The costs that matter:

• each bitmap index scan’s cost is added, so an OR with ten branches pays ten index scans;
• the heap scan’s cost depends on the combined selectivity, estimated by combining branch selectivities (for OR, roughly s1 + s2 − s1 × s2);
• when a bitmap exceeds work_mem it becomes lossy, which adds rechecks — see understanding Filter vs Recheck conditions.

BitmapAnd is often a sign that a composite index is missing: intersecting two large bitmaps is much more work than one descent into a (a, b) index. BitmapOr is usually the best available plan for an OR across different columns, short of rewriting it as UNION.

Annotated EXPLAIN Evidence #

Without an index on one branch:

EXPLAIN (ANALYZE, BUFFERS)
SELECT id FROM contacts
WHERE email = '[email protected]' OR lower(phone) = '+4712345678';

Seq Scan on contacts  (actual time=4.1..14820.6 rows=2 loops=1)
  Filter: ((email = '[email protected]'::text) OR (lower(phone) = '+4712345678'::text))
  Rows Removed by Filter: 60412008
  Buffers: shared hit=40220 read=1082014
Execution Time: 14821.0 ms
-- the phone branch wraps the column in lower(): no index matches it
-- one unindexable OR branch forces the whole predicate onto a sequential scan

With both branches indexable:

EXPLAIN (ANALYZE, BUFFERS)
SELECT id FROM contacts
WHERE email = '[email protected]' OR phone = '+4712345678';

Bitmap Heap Scan on contacts  (actual time=0.07..0.08 rows=2 loops=1)
  Recheck Cond: ((email = '[email protected]'::text) OR (phone = '+4712345678'::text))
  Heap Blocks: exact=2
  Buffers: shared hit=9
  ->  BitmapOr  (actual time=0.06..0.06 rows=0 loops=1)
        ->  Bitmap Index Scan on contacts_email_idx  (actual rows=1 loops=1)
              Index Cond: (email = '[email protected]'::text)
        ->  Bitmap Index Scan on contacts_phone_idx  (actual rows=1 loops=1)
              Index Cond: (phone = '+4712345678'::text)
Execution Time: 0.11 ms
-- BitmapOr rows=0 is normal: bitmap nodes do not report row counts

Step-by-Step Resolution #

1. List every branch of the OR and check that each one matches an index exactly — same column, no function, compatible type and collation.

2. Make unindexable branches indexable, either by querying the bare column or by adding an expression index:

   CREATE INDEX CONCURRENTLY contacts_lower_phone_idx ON contacts (lower(phone));
   ANALYZE contacts;

3. Rewrite as UNION when the planner still refuses, for example because the branches are correlated and the combined estimate is poor. Each half is planned independently:

   SELECT id FROM contacts WHERE email = '[email protected]'
   UNION
   SELECT id FROM contacts WHERE phone = '+4712345678';

   Use UNION ALL only if duplicates cannot occur or are acceptable.

4. For BitmapAnd, test a composite index. If both conditions are frequently used together, CREATE INDEX … (a, b) replaces two bitmap scans and an intersection with one descent; the column order rules are in multicolumn index column ordering.

5. Watch for lossy bitmaps on large OR results: Heap Blocks: lossy= above zero means work_mem was too small for the combined bitmap.

6. Check IN lists separately. col IN (1, 2, 3) on one column is a single = ANY index condition and needs no BitmapOr.

Before and After #

-- BEFORE: OR with lower(phone) and no matching index
Seq Scan on contacts  Filter: (… OR lower(phone) = …)  Rows Removed by Filter: 60412008   Execution Time: 14821.0 ms

-- AFTER: expression index on lower(phone)
Bitmap Heap Scan → BitmapOr → Bitmap Index Scan × 2   Heap Blocks: exact=2              Execution Time: 0.14 ms

OR across a join is a different problem #

Everything above applies to OR within one table. An OR whose branches reference different tables — WHERE a.owner_id = $1 OR b.assignee_id = $1 after a join — cannot be satisfied by bitmap combination at all, because the branches filter different relations. The planner must produce the join first and filter afterwards, which is frequently the slowest query in an application. The fix is the UNION rewrite, applied to the whole join:

SELECT … FROM a JOIN b ON … WHERE a.owner_id = $1
UNION
SELECT … FROM a JOIN b ON … WHERE b.assignee_id = $1;

Each half can then drive from its own selective index. ORMs generate cross-table OR conditions readily from filter chaining, so check generated SQL whenever a search endpoint combines “mine” or “assigned to me” style filters.

Common Pitfalls #

Assuming any index helps an OR. One unindexable branch disables the combination. Diagnostic signal: Seq Scan with an OR in Filter. Fix: index or rewrite that branch.

Casts and functions in one branch. id::text = $1 OR email = $1 looks harmless but the cast prevents index use on id. Diagnostic signal: a :: cast inside the filter. Fix: compare with the column’s native type.

Ignoring BitmapAnd as a hint. Repeated intersections of two big bitmaps cost far more than one composite index lookup. Diagnostic signal: BitmapAnd in hot queries. Fix: create the composite index.

UNION ALL producing duplicates. A row matching both branches is returned twice. Diagnostic signal: duplicate rows after the rewrite. Fix: use UNION, or add AND NOT (first condition) to the second branch.

Frequently Asked Questions #

Why does an OR condition cause a sequential scan in PostgreSQL? #

The planner can only combine indexes for an OR if every branch can be satisfied by some index. If one branch has no matching index — often because a function or cast wraps the column — the whole predicate must be evaluated as a filter over a sequential scan.

What is BitmapOr in EXPLAIN? #

It is a node that merges the row-location bitmaps from several bitmap index scans into one, so a single Bitmap Heap Scan can fetch rows matching any branch of an OR condition.

Is UNION faster than OR? #

Often, when the branches cannot be combined with BitmapOr or when they filter different tables in a join. Each UNION branch is planned independently and can use its own index. When BitmapOr already works, the two usually perform similarly.

Related #

• Sequential vs Index Scans — parent guide: access path selection
• Bitmap Heap Scan vs Index Scan Thresholds — sibling: when bitmaps win over plain index scans
• Understanding Filter vs Recheck Conditions — lossy bitmaps and rechecks

Up: Sequential vs Index Scans