Index Intersection (Bitmap And)

Using two single-column indexes together to answer a multi-column query.

The idea

If you query SELECT * FROM users WHERE status='active' AND country='US', the best tool is a Composite Index on (status, country). But what if you only have a single index on status, and a separate single index on country? Before modern databases, the DB would pick one index, fetch all the rows, and manually filter the second condition. Today, databases use Index Intersection (Bitmap AND): they scan both indexes independently, create a list of Row IDs (a bitmap) from each, and mathematically intersect them in memory before touching the real table.

How it works (Bitmap Heap Scan)

In PostgreSQL, this shows up in your EXPLAIN plan as a BitmapAnd followed by a Bitmap Heap Scan. It builds an array of bits in RAM, where Bit #5 is true if Row 5 matches. It does this for both indexes, runs a bitwise AND, and the resulting 1s tell the database exactly which disk blocks to load.

-- The Query
SELECT * FROM users WHERE status='active' AND country='US';

-- The Execution Plan (Conceptual)
1. Bitmap Index Scan on idx_status  --> Returns Bitmap A: [1, 0, 1, 1]
2. Bitmap Index Scan on idx_country --> Returns Bitmap B: [1, 1, 0, 1]
3. BitmapAnd (A & B)                --> Resulting Bitmap: [1, 0, 0, 1]
4. Bitmap Heap Scan                 --> Fetch ONLY rows 0 and 3 from disk!

Cost

Index Intersection is a great fallback feature, but it requires building and scanning bitmaps in RAM on the fly. If millions of rows match the individual conditions, the bitmap gets huge and the bitwise AND is slow. A proper Composite Index is always faster and uses less CPU.

Watch out for

• Low Cardinality: If an index is on a boolean column (e.g. is_active), it has terrible selectivity. Half the table matches! Scanning that index to build a massive bitmap is slower than just ignoring the index entirely. Databases will often refuse to use low-cardinality indexes, even for intersections.