Skip to main content

execute_bitmap_scan

reddb::storage::query::executors::bitmap_scan

Function execute_bitmap_scan 

Source 
pub fn execute_bitmap_scan<F>(
    bitmap: &TidBitmap,
    fetcher: &F,
    rows_per_page: u32,
) -> Result<Vec<<F as RowFetcher>::Row>, <F as RowFetcher>::Error>
where
    F: RowFetcher,
Expand description

Execute a bitmap heap scan over bitmap, invoking fetcher for each surviving TID in sorted order. Returns the materialised rows in the same TID order.

rows_per_page is the table’s fixed row density — the planner supplies this from schema metadata. For reddb’s default 8 KB pages with ~64-byte rows it’s ~128.

Three-phase algorithm:

  1. Group by page: bitmap.group_by_page(rows_per_page) returns (page_id, Vec<row_within_page>) sorted by page. This turns the iteration into a sequential-read- friendly pattern.
  2. Fetch each page’s rows: for each page group, the fetcher is called once per target row within that page. The fetcher is responsible for caching the page’s buffer so repeated fetches within the same page don’t re-read the disk.
  3. Materialise the output: rows from all pages flow into a single result Vec in their natural ascending TID order.