Struct BitmapIndex 

pub struct BitmapIndex { /* private fields */ }

Bitmap Index for low-cardinality columns

Optimized for BOOLEAN, status, and category columns where the number of distinct values is small (< 1000).

Key features:

• One RoaringBitmap per distinct value
• O(n/64) AND/OR/NOT operations for multi-predicate queries
• Automatic compression (array, bitmap, or RLE per 8KB chunk)
• Thread-safe with RwLock

Memory efficiency:

For 1M rows with 10 distinct values:

• B-tree: ~80 MB
• Bitmap: ~500KB - 2.5MB (30-160x savings)

Row ID Support:

Uses RoaringTreemap which supports full i64 row IDs (up to u64::MAX). This is implemented as a BTreeMap of RoaringBitmaps for efficient storage while supporting the full 64-bit range.

Implementations

impl BitmapIndex

pub fn new( name: String, table_name: String, column_names: Vec<String>, column_ids: Vec<i32>, data_types: Vec<DataType>, is_unique: bool, ) -> Self

Create a new BitmapIndex

pub fn cardinality(&self) -> usize

Get the current cardinality (number of distinct values)

pub fn is_high_cardinality(&self) -> bool

Check if cardinality is too high for efficient bitmap operations

pub fn get_bitmap(&self, value: &Value) -> Option<RoaringTreemap>

Get the bitmap for a specific value (for AND/OR operations)

pub fn and_values(&self, values: &[Value]) -> RoaringTreemap

Perform AND operation on multiple values (for multi-predicate queries) Returns row IDs that match ALL values

pub fn or_values(&self, values: &[Value]) -> RoaringTreemap

Perform OR operation on multiple values Returns row IDs that match ANY value

pub fn not_value(&self, value: &Value) -> RoaringTreemap

Perform NOT operation on a value Returns row IDs that do NOT match the value Note: Requires knowing all row IDs in the table

Trait Implementations

impl Debug for BitmapIndex

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.

impl Index for BitmapIndex

fn name(&self) -> &str

Returns the name of the index

fn table_name(&self) -> &str

Returns the name of the table this index belongs to

fn build(&mut self) -> Result<()>

Builds the index from existing data

fn add(&self, values: &[Value], row_id: i64, _ref_id: i64) -> Result<()>

Adds values to the index with the given row IDs

fn add_arc( &self, values: &[CompactArc<Value>], row_id: i64, _ref_id: i64, ) -> Result<()>

Adds CompactArc references to the index - shares ownership without cloning

fn add_batch(&self, entries: &FxHashMap<i64, Vec<Value>>) -> Result<()>

Adds multiple entries to the index in a single batch operation

fn remove(&self, values: &[Value], row_id: i64, _ref_id: i64) -> Result<()>

Removes values from the index

fn remove_arc( &self, values: &[CompactArc<Value>], row_id: i64, _ref_id: i64, ) -> Result<()>

Removes CompactArc references from the index - avoids cloning when you have Arc refs

fn remove_batch(&self, entries: &FxHashMap<i64, Vec<Value>>) -> Result<()>

Removes multiple entries from the index in a single batch operation

fn column_ids(&self) -> &[i32]

Returns the column IDs for this index

fn column_names(&self) -> &[String]

Returns the column names for this index

fn data_types(&self) -> &[DataType]

Returns the data types for the indexed columns

fn index_type(&self) -> IndexType

Returns the type of index (BTree, Bitmap, Hash)

fn is_unique(&self) -> bool

Returns true if this is a unique index

fn find(&self, values: &[Value]) -> Result<Vec<IndexEntry>>

Finds all entries where the columns equal the given values

fn find_range( &self, _min: &[Value], _max: &[Value], _min_inclusive: bool, _max_inclusive: bool, ) -> Result<Vec<IndexEntry>>

Finds all entries where the columns are in the given range

fn find_with_operator( &self, op: Operator, values: &[Value], ) -> Result<Vec<IndexEntry>>

Finds all entries matching the given operator and values

fn get_row_ids_equal(&self, values: &[Value]) -> Vec<i64>

Returns row IDs with the given values (convenience method)

fn get_row_ids_equal_into(&self, values: &[Value], buffer: &mut Vec<i64>)

Appends row IDs with the given values to the provided buffer

fn get_row_ids_in_range( &self, _min_value: &[Value], _max_value: &[Value], _include_min: bool, _include_max: bool, ) -> Vec<i64>

Returns row IDs with values in the given range (convenience method)

fn get_filtered_row_ids(&self, expr: &dyn Expression) -> Vec<i64>

Returns row IDs that match the given expression

fn get_all_values(&self) -> Vec<Value>

Returns all unique values in the index (for ORDER BY optimization)

fn close(&mut self) -> Result<()>

Closes the index and releases any resources

fn get_row_ids_in(&self, value_list: &[Value]) -> Vec<i64>

Returns row IDs for values in the given list (IN clause optimization)

fn get_min_value(&self) -> Option<Value>

Returns the minimum value in the index (for MIN aggregate optimization)

fn get_max_value(&self) -> Option<Value>

Returns the maximum value in the index (for MAX aggregate optimization)

fn get_row_ids_ordered( &self, _ascending: bool, _limit: usize, _offset: usize, ) -> Option<Vec<i64>>

Returns row IDs in sorted order by index value (for ORDER BY optimization)

fn get_grouped_row_ids(&self) -> Option<Vec<(Value, Vec<i64>)>>

Returns grouped row IDs in sorted order by index value (for GROUP BY optimization)

fn for_each_group( &self, _callback: &mut dyn FnMut(&Value, &[i64]) -> Result<bool>, ) -> Option<Result<()>>

Iterates through groups in sorted order, calling the callback for each group.