Bitmap Index

A bitmap index represents each distinct value of a column as a separate bit array (bitmap). Each position in the array corresponds to a row in the database table. A bit is set to '1' if the row contains that specific value, and '0' otherwise.

• For a status column with values 'active' and 'inactive', two bitmaps are created.
• Row 1 is 'active', so the 'active' bitmap has a '1' at position 1, and the 'inactive' bitmap has a '0'.
• This binary representation is extremely space-efficient for low-cardinality columns (columns with few distinct values).

The primary power of a bitmap index lies in performing logical bitwise operations (AND, OR, NOT) across multiple bitmaps to resolve complex filter queries at CPU-native speeds.

• A query for status='active' AND department='sales' is executed by performing a bitwise AND between the 'active' bitmap and the 'sales' bitmap.
• The resulting bitmap has '1's only for rows that satisfy both conditions.
• Operations like OR (for disjunctive queries) and NOT (for exclusion) are equally efficient. This makes bitmap indexes ideal for Boolean filtering in faceted search and OLAP queries.

Bitmap indexes are most effective on columns with relatively low cardinality, meaning a limited number of distinct values compared to the total number of rows.

• Examples include: gender, country_code, product_category, order_status.
• High-cardinality columns (e.g., user_id, timestamp) would require a bitmap for each unique value, leading to excessive storage and diminishing returns.
• In vector databases, bitmap indexes are perfectly suited for metadata filtering on categorical tags, version numbers, or access control flags, acting as a fast pre-filter for ANN search.

While bitmaps for low-cardinality values are dense (many 1s), those for rare values are sparse (mostly 0s). To save memory, bitmap indexes employ run-length encoding (RLE) compression.

• Run-Length Encoding (RLE) compresses long sequences ('runs') of identical bits. The sequence '0000011111000' becomes [5 zeros, 5 ones, 3 zeros].
• This compression is highly effective and allows bitwise operations to be performed directly on the compressed format.
• Advanced variants like BBC (Byte-aligned Bitmap Code) and WAH (Word-Aligned Hybrid) optimize for modern CPU word sizes, balancing compression ratio with computational speed.

In hybrid search architectures, bitmap indexes are crucial for executing the filtered search phase with maximal efficiency before or during the vector similarity lookup.

• Pre-filtering: A bitmap index rapidly identifies all documents where category = 'legal' AND year >= 2023. This small candidate set is then passed to the vector index (e.g., HNSW) for similarity search.
• Integrated Filtering: Some vector index algorithms, like HNSW with filters, can interweave bitmap checks during graph traversal.
• This combination enables multi-stage retrieval systems to apply hard business logic filters at database speed, ensuring results are both semantically relevant and contextually valid.

Bitmap indexes serve a different optimization niche than traditional B-tree indexes.

Thus, bitmap indexes are a strategic choice in data warehousing and search backends where fast, complex filtering on categorical data is paramount.

A bitmap index is the optimal structure for executing pre-filtering in hybrid search architectures. Before performing an expensive approximate nearest neighbor (ANN) search across billions of vectors, the system uses bitmaps to instantly identify the subset of records that match hard metadata constraints (e.g., user_id=123, category='legal'). This drastically reduces the search space, lowering latency and compute cost. For example, applying a filter for date > 2024-01-01 might reduce 1B vectors to 10M candidates in microseconds.

Bitmap indexes power real-time faceted search and analytical drill-downs in AI applications. Each distinct value for a filterable field (like product_category or sentiment) has its own bitmap. When a user selects multiple facets, the database performs lightning-fast bitwise AND/OR operations on these bitmaps to compute the intersecting result set. This allows dashboards and search UIs to display instant counts (e.g., "235 documents match 'legal' AND 'draft'") and enables interactive exploration of large vector datasets.

Native integration of bitmap indexes with ANN algorithms like HNSW or IVF is essential for filtered vector search. Advanced vector databases modify graph traversal or centroid selection to respect bitmap-derived constraints during the search itself, rather than just pre- or post-filtering. This filter-aware ANN prevents the algorithm from exploring irrelevant regions of the vector space, maintaining high recall while obeying hard business rules. It solves the challenge where strict post-filtering could return too few results.

Bitmap indexes excel at filtering on high-cardinality fields, where attributes have many distinct values (e.g., user_id, session_id, product_sku). Traditional B-tree indexes can become inefficient for multi-value OR queries across thousands of IDs. A bitmap index represents each ID as a compact bit array. A query for user_id IN (id1, id2, ... id1000) is executed by performing a bitwise OR across 1000 bitmaps, a highly parallelizable and cache-efficient operation. This is common in multi-tenant AI platforms isolating user data.

Complex Boolean filters (e.g., (status='published' AND (category='tech' OR category='science')) NOT author='beta') are executed with deterministic speed using bitmap indexes. The query planner decomposes the expression into a sequence of bitwise logical operations (AND, OR, NOT, XOR) on the relevant bitmaps. The final result bitmap directly identifies the qualifying document IDs. This algebraic approach is far more efficient for analytical workloads than iterating through records, making it ideal for retrieval-augmented generation (RAG) systems that apply complex security or relevance rules.

In recommendation systems and hyper-personalization engines, bitmap indexes enable real-time user segmentation for vector-based retrieval. User profiles with hundreds of attributes (demographics, past behavior, entitlements) are represented as bitmaps. When generating recommendations, the system first computes a target segment bitmap (e.g., premium_users INTERSECT clicked_on_x) and then performs a maximum inner product search (MIPS) or cosine similarity search only over item vectors tagged with that segment. This ensures recommendations are both semantically relevant and compliant with business logic.

A retrieval process where metadata-based constraints, such as date ranges or categorical tags, are applied to narrow down the candidate set before or during a similarity or keyword search. This is the primary use case for a bitmap index.

• Key Mechanism: Uses Boolean logic (AND, OR, NOT) on structured fields.
• Performance Impact: Applying filters first (pre-filtering) dramatically reduces the search space for expensive vector operations.
• Example: Searching for 'sports cars' in vector space but only among documents tagged with category: automotive and date_published: 2024.

Approximate Nearest Neighbor (ANN) search algorithms that have been modified to efficiently respect hard metadata constraints during the vector similarity search process, rather than applying filters as a separate pre- or post-step.

• Core Challenge: Balancing filter adherence with search speed and recall.
• Common Implementation: Modifying graph traversal in indices like HNSW to only explore nodes that pass the filter predicate.
• Advantage: Avoids the performance penalty of searching the entire index only to discard most results later.

A critical database query optimization technique where filtering predicates are evaluated as early as possible in the query execution plan, ideally within the storage layer.

• Objective: Minimize data movement and processing overhead by discarding non-matching records before they are loaded into memory or joined with other datasets.
• Bitmap Index Role: Bitmap indexes are a classic enabler of filter pushdown, as the bitwise operations can be performed directly on the compact index data.
• Result: Significantly lower latency and reduced compute cost for complex filtered queries.

A logical expression, typically using AND, OR, and NOT operators, applied to metadata fields to include or exclude documents from a search result set based on precise criteria.

• Conjunctive Query: Uses AND (e.g., category:tech AND author:smith).
• Disjunctive Query: Uses OR (e.g., status:active OR status:pending).
• Bitmap Index Execution: Bitmap indexes excel at these operations. Each condition is a bitmap; AND becomes a bitwise AND, OR becomes a bitwise OR, and NOT becomes a bitwise NOT.

A measure, expressed as a fraction or percentage, that estimates the proportion of records in a dataset that will satisfy a given filter predicate.

• High Selectivity: A filter that selects a small percentage of records (e.g., user_id=12345).
• Low Selectivity: A filter that selects a large percentage of records (e.g., country=USA in a US-centric dataset).
• Query Optimizer Use: The database uses selectivity estimates to choose the most efficient execution plan, such as deciding whether to use an index or perform a full scan.

The overarching practice of applying constraints based on structured attributes (e.g., author, timestamp, category) associated with documents to restrict the scope of a search query.

• Contrast with Semantic Search: Filters operate on explicit, structured data, while vector search operates on learned, unstructured semantic meaning.
• Implementation Spectrum: Can be implemented via bitmap indexes, B-trees, inverted indexes, or brute-force scanning.
• Business Critical: Enables precise, compliance-aware retrieval (e.g., "find documents user X has permission to view").