Index Intersection Misuse

partial

Summary

The query planner chooses to use multiple single-column indexes and merge their results (bitmap AND) rather than using a single composite index, producing higher I/O and buffer cache pressure than a purpose-built composite index would: often because the correct composite index doesn't exist and the planner falls back to the suboptimal index intersection strategy.

Description

PostgreSQL and MySQL support index intersection (also called bitmap index AND): when no single index covers all predicate columns in a WHERE clause, the planner can use two or more single-column indexes, retrieve the matching row sets from each, compute their intersection, and fetch the matching rows.

This sounds efficient but often is not: 1. Each index scan retrieves a set of heap pointers (or primary key values in InnoDB) 2. The intersection step requires sorting and comparing both sets in memory (or on disk) 3. Heap fetches for the intersected set may be scattered across many pages (non-sequential I/O) 4. For selective predicates with small result sets, the overhead of two index scans

plus intersection exceeds the cost of a single composite index scan

A composite index on (col_a, col_b) directly retrieves only rows matching both predicates in a single B-tree traversal. For a query with WHERE col_a = X AND col_b = Y, the composite index is almost always superior to the index intersection plan.

The problem appears when: - A composite index does not exist and developers don't notice the index intersection plan - EXPLAIN output shows "BitmapAnd" (PostgreSQL) or "index_merge" (MySQL) for a hot query - Performance degradation appears gradually as table size grows

Characteristics

Propagationisolated

Time to detectRequires active query plan analysis. EXPLAIN shows "BitmapAnd" or "index_merge" on hot queries. Without query plan monitoring, the failure surfaces as elevated latency on specific features that may be attributed to other causes.

Blast radiusElevated latency for the specific query pattern using index intersection. If the query is on a hot path (user authentication, item lookup, order retrieval), the elevated latency affects that feature proportionally. Buffer cache pressure from the larger I/O footprint of the intersection plan can indirectly affect other queries sharing the same database instance.

Triggers

·Hot query with multiple equality predicates lacks a composite index
·Schema changes remove a composite index leaving only single-column indexes
·Query planner's cost model incorrectly favors index intersection over composite index

Detection Signals

alert

Mitigation Strategies

Create composite index on the combined predicate columnspreventscomplexity: low

CREATE INDEX CONCURRENTLY ON table (col_a, col_b) WHERE col_a IS NOT NULL. Column order in composite index matters: leftmost prefix is used for range scans. For equality predicates, put higher-selectivity columns first. For range predicates, the range column should be last in the composite index.

Regular EXPLAIN analysis of hot queriescomplexity: low

After each schema change or significant data growth, re-analyze the execution plans of high-frequency queries. Add query plan review to the deployment checklist. Tools: pg_stat_statements (PostgreSQL), slow query log (MySQL).

Disable index intersection for the specific query (workaround)complexity: low

PostgreSQL: SET enable_bitmapscan = off for the session to force a sequential scan or alternative plan. Not a long-term fix: add the composite index instead. Used only when an emergency plan hint is needed while the correct index is built.

Recovery Steps

1.Run EXPLAIN (ANALYZE, BUFFERS) on the affected query to confirm BitmapAnd/index_merge
2.Identify the predicate columns and design the correct composite index column order
3.CREATE INDEX CONCURRENTLY (PostgreSQL) to build without locking
4.Re-run EXPLAIN after index creation to verify the planner uses the new index
5.Monitor query latency to confirm improvement

Estimated recovery time: Index creation with CONCURRENTLY on a small table: seconds to minutes. On a large table (100M+ rows): 15 minutes to several hours depending on size and load. Query performance improves immediately after the index is built and the planner picks it up (automatic; may require ANALYZE to update statistics).

Affected Systems

Patterns

read replicasharding

Technologies

postgresqlmysql

Basis

Index intersection mechanics are documented in PostgreSQL query planning documentation and MySQL EXPLAIN documentation; the composite index superiority for equality predicates is a standard recommendation in database indexing literature