vault

Bitmap and Partial Indexes

18 min read

Bitmap and Partial Indexes

Beyond the default B-tree, engines offer specialized index shapes that trade generality for a large win on a specific workload. A bitmap index stores, for each distinct value of a column, a bitmap — one bit per row — with the bit set when that row holds that value; predicates then combine by bitwise AND/OR/NOT, which is extraordinarily fast and space-cheap when the column has few distinct values (low cardinality), making bitmap indexes the workhorse of read-mostly data-warehouse / OLAP querying and a poor fit for high-churn OLTP. A partial index (PostgreSQL) or filtered index (SQL Server) is an ordinary index built over only the subset of rows that satisfy a WHERE predicate — smaller, cheaper to maintain, and often more accurately estimated than a full-table index. The two ideas share a theme (index less, but index it better) and a common cousin, the expression / functional index, which indexes the result of a computation like lower(email) rather than a raw column. The single most-confused fact in this area, and the one this note is careful to pin: Oracle stores bitmap indexes on disk as a persistent structure, while PostgreSQL has no persistent bitmap index type at all — it builds bitmaps on the fly during query execution (the “bitmap heap scan”) from ordinary indexes and throws them away when the query ends.

Mental Model

Picture a table’s rows as columns of a grid and a low-cardinality attribute’s distinct values as the rows of the grid; each cell is a single bit. That grid is the bitmap index.

flowchart TB
  subgraph BMP["Bitmap index on cust_gender (2 distinct values, 7 rows)"]
    direction TB
    M["M : 1 0 1 1 1 0 0"]
    F["F : 0 1 0 0 0 1 1"]
  end
  subgraph MAR["Bitmap index on marital_status"]
    direction TB
    S["single   : 0 0 0 0 0 1 1"]
    D["divorced : 0 0 0 0 0 0 0"]
  end
  Q["Query: cust_gender='F'<br/>AND marital_status IN ('single','divorced')"]
  R["F AND (single OR divorced)<br/>= 0 0 0 0 0 1 1  ➜ rows 6 and 7"]
  BMP --> Q
  MAR --> Q
  Q --> R

A bitmap index answering a multi-predicate query by bitwise algebra, using Oracle’s own customers example. What it shows: each distinct value owns one bitmap of length = number of rows; the query gender='F' AND status IN ('single','divorced') is computed as F AND (single OR divorced), a handful of machine AND/OR word operations over the bitmaps, yielding 0000011 — rows 6 and 7 — before the table is touched at all (Oracle Database 23ai — Indexes). The insight to take: when a column has few distinct values, the whole predicate evaluation collapses to cache-friendly bitwise loops over compact bitmaps, and combining many ad-hoc predicates costs almost nothing — which is exactly why bitmap indexes dominate data-warehouse star-schema filtering and exactly why they fail under OLTP, where a single-row update must lock an entire value’s bitmap.

Mechanical Walk-through

Bitmap indexes — one bitmap per value, combined by bitwise algebra

The foundational treatment is O’Neil & Quass’s Improved Query Performance with Variant Indexes (SIGMOD 1997; PDF), which defines the structure precisely. Starting from a 1-to-1 mapping m from each row to an integer position, “A ‘Bitmap’ B is defined on T as a sequence of M bits. If a Bitmap B is meant to list rows in T with a given property P, then for each row r with row number j that has the property P, we set bit j in B to one; all other bits are set to zero. A Bitmap index for a column C with values v1, v2, …, vk, is a B-tree with entries having these keyvalues and associated data portions that contain Bitmaps for the properties C = v1, …, C = vk” (O’Neil & Quass 1997). The critical framing: “Bitmaps in this index are just a new way to specify lists of RIDs [row identifiers] for specific column values.” A bitmap is simply an alternative representation of a RID-list — instead of storing an explicit list of the row-ids that have a value, you store a dense bit-vector positionally indexed by row.

Oracle’s manual gives the same definition operationally: “In a bitmap index, the database stores a bitmap for each index key… Each bit in the bitmap corresponds to a possible rowid. If the bit is set, then the row with the corresponding rowid contains the key value. A mapping function converts the bit position to an actual rowid, so the bitmap index provides the same functionality as a B-tree index although it uses a different internal representation” (Oracle 23ai).

The reason bitmaps win is that Boolean combination is a hardware operation. O’Neil & Quass: “Boolean operations, such as AND, OR, and NOT are extremely fast for Bitmaps. Given Bitmaps B1 and B2, we can calculate a new Bitmap B3, B3 = B1 AND B2, by treating all bitmaps as arrays of long ints and looping through them, using the & operation of C.” NOT needs one extra step — you AND against an Existence Bitmap (EBM) marking positions that correspond to real rows, so that non-existent slots don’t flip to 1. A COUNT is a population-count over the result bitmap. Their benchmark makes the payoff concrete: a grouping query that ANDed 250 pairs of one-million-bit bitmaps and counted the results ran in 19.25 seconds, versus 248 seconds for the equivalent sort-based plan on a contemporary DB2 (ibid.).

Cardinality and density — why bitmap indexes are for low-cardinality columns

O’Neil & Quass define density as the proportion of one-bits: “A Bitmap index for a column with 32 values will have Bitmaps with average density of 1/32.” The storage argument follows: an uncompressed bitmap index’s size “is proportional to the number of column values,” and “For a column index with a very small number of values, the Bitmaps will have high densities (such as 50% for predicates such as GENDER = ‘M’ or GENDER = ‘F’), and the disk savings is enormous. On the other hand, when average Bitmap density for a Bitmap index becomes too low, methods exist for compressing a Bitmap” (O’Neil & Quass 1997). In other words: two-value gender yields two ~50%-dense bitmaps that pack tightly; a million-value email column would need a million sparse bitmaps, ballooning storage and defeating the point. Oracle’s guidance matches: bitmap indexes suit columns where “the number of distinct values is small compared to the number of table rows,” in tables that are “read-only or not subject to significant modification by DML” (Oracle 23ai). A pleasant bonus Oracle notes: “Bitmap indexes can include keys that consist entirely of null values, unlike B-tree indexes” — so COUNTs and IS NULL predicates that a B-tree cannot serve are natural for bitmaps.

The confusion pinned: Oracle stores bitmaps; PostgreSQL builds them on the fly

Here is the distinction that trips up nearly everyone. Oracle (and Db2, and the Sybase IQ lineage from the O’Neil paper) implements a persistent, on-disk bitmap index you create explicitly: CREATE BITMAP INDEX …. Oracle even stores those bitmaps inside a B-tree keyed by column value: “Oracle AI Database uses a B-tree index structure to store bitmaps for each indexed key,” each leaf entry holding a keyvalue, a low/high rowid range, and the bitmap for that range (Oracle 23ai). The bitmaps live on disk permanently and are maintained as rows change.

PostgreSQL has no such index type. What PostgreSQL calls a bitmap scan is a runtime execution strategy, not a stored structure. When a query can use several indexes, “the system scans each needed index and prepares a bitmap in memory giving the locations of table rows that are reported as matching that index’s conditions. The bitmaps are then ANDed and ORed together as needed by the query. Finally, the actual table rows are visited and returned. The table rows are visited in physical order, because that is how the bitmap is laid out” (PostgreSQL 18 — Combining Multiple Indexes). These bitmaps are “constructed on-the-fly during query execution” from ordinary B-tree indexes and discarded afterward. This is why an EXPLAIN in PostgreSQL shows Bitmap Index Scan → Bitmap Heap Scan (and BitmapAnd / BitmapOr nodes) yet PostgreSQL offers no CREATE BITMAP INDEX — the bitmap is transient. The visible consequence: because the heap is “visited in physical order… any ordering of the original indexes is lost, and so a separate sort step will be needed if the query has an ORDER BY clause” (ibid.). So the phrase “bitmap index” means two very different things depending on the engine — a permanent structure in Oracle, an ephemeral query-plan artifact in PostgreSQL. Conflating them is the classic error the MOC warns about.

The OLTP problem — bitmap locking granularity

Bitmap indexes fail under transactional write load for a specific mechanical reason: the lock granularity is the value, not the row. Oracle: “If the indexed column in a single row is updated, then the database locks the index key entry (for example, M or F) and not the individual bit mapped to the updated row. Because a key points to many rows, DML on indexed data typically locks all of these rows” (Oracle 23ai). Updating one employee’s job title takes “exclusive access to the index key entry for the old value… and the new value,” locking every row those two bitmaps cover until the UPDATE commits. “For this reason, bitmap indexes are not appropriate for many OLTP applications” (ibid.). In a warehouse loaded in nightly batches this never bites; in a busy transactional table it produces crippling lock contention. This is the concurrency face of the same read-mostly assumption baked into the O’Neil paper’s very first sentence: “The read-mostly environment of data warehousing makes it possible to use more complex indexes to speed up queries than in situations where concurrent updates are present” (O’Neil & Quass 1997).

Partial (filtered) indexes — index only the rows that matter

A partial index shrinks an ordinary index by indexing a subset of rows. PostgreSQL: “A partial index is an index built over a subset of a table; the subset is defined by a conditional expression (called the predicate of the partial index). The index contains entries only for those table rows that satisfy the predicate” (PostgreSQL 18 — Partial Indexes). SQL Server’s equivalent is the filtered index: “an optimized disk-based rowstore nonclustered index especially suited to cover queries that select from a well-defined subset of data. It uses a filter predicate to index a portion of rows in the table” (SQL Server — Create Filtered Indexes).

There are three classic motivations, all from the PostgreSQL manual. (1) Exclude common values: “a query searching for a common value… will not use the index anyway, [so] there is no point in keeping those rows in the index at all. This reduces the size of the index, which will speed up those queries that do use the index.” (2) Exclude uninteresting values: e.g. index only unbilled orders — CREATE INDEX orders_unbilled_index ON orders (order_nr) WHERE billed is not true; — so the index stays tiny even though the table is huge, because processed rows drop out. (3) Enforce uniqueness on a subset: CREATE UNIQUE INDEX tests_success_constraint ON tests (subject, target) WHERE success; enforces uniqueness only among successful rows “without constraining those that do not” (PostgreSQL 18 — Partial Indexes). SQL Server frames the benefits as improved plan quality (the filtered statistics “are more accurate than full-table statistics because they cover only the rows in the filtered index”), reduced maintenance (“maintained only when… DML statements affect the data in the index”), and reduced storage (SQL Server).

The subtle rule is the predicate-implication requirement: the optimizer uses a partial index only when the query’s WHERE provably implies the index’s predicate. PostgreSQL: “a partial index can be used in a query only if the system can recognize that the WHERE condition of the query mathematically implies the predicate of the index,” and it warns that “PostgreSQL does not have a sophisticated theorem prover” — it recognizes simple inequality implications like x < 1 implies x < 2, “otherwise the predicate condition must exactly match part of the query’s WHERE condition or the index will not be recognized as usable” (PostgreSQL 18 — Partial Indexes). And crucially this happens at plan time, so “parameterized query clauses do not work with a partial index” — a prepared x < ? can never be proven to imply x < 2 for all parameter values (ibid.). SQL Server states the same design contract informally: “the WHERE clause of the query should be a subset of the WHERE clause of the filtered index, to benefit from the filtered index” (SQL Server).

Expression / functional indexes — the close cousin

An expression index (PostgreSQL) or functional index indexes the result of a computation rather than a stored column: “An index column need not be just a column of the underlying table, but can be a function or scalar expression computed from one or more columns of the table” (PostgreSQL 18 — Indexes on Expressions). The canonical case is case-insensitive lookup: CREATE INDEX test1_lower_col1_idx ON test1 (lower(col1)); makes WHERE lower(col1) = 'value' an indexed equality — “the system sees the query as just WHERE indexedcolumn = 'constant'” (ibid.). The query must use the same expression as the index for the match to fire. The cost is on writes: “Index expressions are relatively expensive to maintain, because the derived expression(s) must be computed for each row insertion and non-HOT update. However, the index expressions are not recomputed during an indexed search, since they are already stored” — so expression indexes “are useful when retrieval speed is more important than insertion and update speed” (ibid.). Partial and expression indexes combine freely: CREATE INDEX … ON orders (lower(email)) WHERE status = 'active' indexes a computed value over a row subset.

Configuration and Examples

Oracle — a stored bitmap index for a warehouse dimension

-- Low-cardinality dimension column in a read-mostly fact/dimension table.
CREATE BITMAP INDEX customers_gender_bix ON customers (cust_gender);
 
SELECT COUNT(*) FROM customers
WHERE cust_gender = 'F'
  AND cust_marital_status IN ('single','divorced');
-- Oracle ANDs/ORs the stored bitmaps: F AND (single OR divorced),
-- filtering rows *before* touching the table. (Oracle 23ai worked example.)
  • CREATE BITMAP INDEX builds a persistent structure — this syntax has no PostgreSQL equivalent.
  • Bitmap-combine plans (BITMAP AND, BITMAP OR, BITMAP MERGE) let Oracle answer ad-hoc conjunctions over several low-cardinality columns cheaply — the star-schema filtering pattern.
  • Do not do this on an OLTP customers table with frequent single-row updates: each update locks the whole M or F bitmap segment.

PostgreSQL — bitmaps are ephemeral (no CREATE BITMAP INDEX)

-- Ordinary B-tree indexes:
CREATE INDEX ON orders (x);
CREATE INDEX ON orders (y);
 
EXPLAIN SELECT * FROM orders WHERE x = 5 AND y = 6;
--  Bitmap Heap Scan on orders
--    Recheck Cond: ((x = 5) AND (y = 6))
--    ->  BitmapAnd
--          ->  Bitmap Index Scan on orders_x_idx  (Index Cond: x = 5)
--          ->  Bitmap Index Scan on orders_y_idx  (Index Cond: y = 6)
  • The BitmapAnd builds two in-memory bitmaps from ordinary indexes and ANDs them — Postgres’s version of combining predicates, per the combining-indexes docs.
  • Bitmap Heap Scan then visits matching heap pages in physical order — hence a following ORDER BY needs its own Sort.
  • Nothing is stored: the bitmap exists only for this query’s execution.

PostgreSQL partial index and SQL Server filtered index

-- PostgreSQL: index only the "hot" unprocessed rows.
CREATE INDEX orders_unbilled_index ON orders (order_nr) WHERE billed IS NOT TRUE;
-- Used by:  SELECT ... FROM orders WHERE order_nr = ? AND billed IS NOT TRUE;
-- (the query WHERE must imply the index WHERE)
 
-- SQL Server: filtered index over rows whose EndDate is set.
CREATE NONCLUSTERED INDEX FIBillOfMaterialsWithEndDate
  ON Production.BillOfMaterials (ComponentID, StartDate)
  WHERE EndDate IS NOT NULL;
-- Used by a query whose WHERE is a subset, e.g. WHERE EndDate IS NOT NULL AND ComponentID = 5 ...

Both are the engines’ own documented examples (PostgreSQL 18; SQL Server). SQL Server filtered indexes ship since SQL Server 2008 (the primary Microsoft doc documents currently-supported versions from 2016 onward and does not itself state the introduction release; the 2008 origin is well established in the SQL Server literature). They “only support simple comparison operators… don’t support LIKE,” cannot be built on a view, and the clustered key is auto-included (SQL Server).

Failure Modes and Common Misunderstandings

  • Bitmap index on a high-cardinality column. Millions of sparse bitmaps blow up storage and lose the density advantage — O’Neil & Quass’s whole density argument inverts. Bitmaps are for gender, status, region, not email or user_id.

  • Bitmap index on an OLTP table. The value-level lock (“DML on indexed data typically locks all of these rows,” Oracle 23ai) turns concurrent single-row updates into a lock convoy. Keep bitmap indexes in the batch-loaded warehouse.

  • Expecting a stored bitmap index in PostgreSQL. There isn’t one. CREATE BITMAP INDEX is a syntax error; you get bitmap scans over B-tree indexes at runtime instead. If you truly need persistent bitmaps in the Postgres ecosystem, that is an extension-territory / different-engine decision.

  • Partial index not chosen because the predicate doesn’t match. The query’s WHERE must imply the index predicate; PostgreSQL “does not have a sophisticated theorem prover” (PostgreSQL 18). A partial index WHERE billed IS NOT TRUE will not serve a query that merely says WHERE billed = false unless the planner can prove equivalence — write the query’s predicate to match.

  • Parameterized queries silently skip partial indexes. Because matching is at plan time, a prepared x < ? can’t imply a constant bound, so it never uses a WHERE x < 2 partial index (PostgreSQL 18). A subtle, easy-to-miss regression when moving from ad-hoc SQL to prepared statements.

  • Expression index missing because the expression differs. WHERE lower(email) = 'x' uses a lower(email) index; WHERE email ILIKE 'x' or WHERE upper(email) = 'X' does not — the expression must match textually (PostgreSQL 18 — Indexes on Expressions).

  • Using many partial indexes as a poor man’s partitioning. PostgreSQL cautions against creating many non-overlapping partial indexes by category, because “the system does not understand the relationship among the partial indexes, and will laboriously test each one to see if it’s applicable to the current query” (PostgreSQL 18). Use real partitioning instead.

Alternatives and When to Choose Them

For low-cardinality filtering in a read-mostly warehouse, a stored bitmap index (Oracle/Db2/Sybase IQ) is the strongest tool — cheap storage, near-free multi-predicate combination, NULL indexing, and fast COUNTs. In PostgreSQL, the same query shape is served by ordinary B-tree indexes combined via runtime bitmap scans; you lose the persistent-structure compactness but gain OLTP-safety and a single index type to reason about. For a known hot subset of rows, a partial/filtered index beats a full index on every axis — smaller, cheaper to maintain, better statistics — provided the workload’s predicates consistently imply the index predicate. For computed lookups (case-folding, JSON extraction, concatenation), an expression index is the right tool, paying extra write cost for indexed reads. And when the alternative is “one wide composite index,” recall that combining several single-column indexes via bitmap/index-merge (see Composite Keys and Index Column Order) is the more flexible — if slower — option for ad-hoc conjunctions. The unifying principle across all of these is the RUM trade-off seen from the index side: every one of these variants indexes less (fewer rows, fewer bits, or a pre-computed value) to cut space and write cost, betting that the narrower index still serves the query.

Production Notes

The operational discipline is to match the index variant to the workload’s cardinality and mutability, and to verify with the plan. In Oracle, confirm bitmap combination with BITMAP AND / BITMAP OR / BITMAP CONVERSION nodes in the plan, and never place a bitmap index on a hot transactional table — the lock-a-whole-value behavior is a well-known production foot-gun. In PostgreSQL, remember that a Bitmap Heap Scan in EXPLAIN is not evidence of a bitmap index; it is the planner combining or de-randomizing ordinary index scans, and a BitmapOr over WHERE x IN (…) is a common, healthy plan. For partial and filtered indexes, the highest-value pattern in practice is the “hot subset” — indexing only unprocessed/active/recent rows so the index stays tiny against an ever-growing table — but the plan-time predicate-implication rule means you must keep the application’s query predicates textually aligned with the index predicate, and watch for prepared-statement regressions. Filtered statistics (SQL Server) and the smaller partial index (PostgreSQL) also improve the optimizer’s cardinality estimates for the subset, which sometimes matters more than the raw lookup speed. Treat all of these as targeted structures added for measured hot paths, exactly as with Covering Indexes and Index-Only Scans — speculative specialized indexes are write-amplification and confusion with no payoff.

See Also

Graph View