### Bitmap Heap Scan ![[assets/ex_bitmapheapscan.png|256]] ### The Explain Trace ```sql -- Consuming a bitmap to fetch data from the heap EXPLAIN (ANALYZE, COSTS, BUFFERS, VERBOSE) SELECT * FROM animals WHERE species_id = 1; ``` ```text Bitmap Heap Scan on public.animals (cost=51.29..249.29 rows=4000 width=27) (actual time=1.640..1.921 rows=4000 loops=1) Output: id, name, species_id, created_at Recheck Cond: (animals.species_id = 1) Heap Blocks: exact=148 Buffers: shared hit=148 read=5 -> Bitmap Index Scan on idx_animals_species_id (...) ``` --- > [!NOTE] > **Metaphor: Walking the Map.** The server takes the map they just marked and walks a single efficient lap around the room. They only stop at the tables with a "dot" on them. This ensures they visit each table (Page) exactly once, in physical order. ### How it Works The node consumes a **TIDBitmap** produced by a child `Bitmap Index Scan`. It translates the bitset into a sequence of physical block numbers (Pages) and fetches them from the **[[Manuscript/02 - Physical Storage & MVCC/2.3 - The Page (The Shipping Container)|Table Heap]]**. ### Physical Implementation - **Sequential Physical I/O**: Because the bitmap is sorted by Page ID, Postgres reads the disk in order. This turns expensive Random I/O into efficient Sequential I/O. - **The Recheck Condition**: If the child bitmap became "Lossy" due to memory pressure, Postgres only knows that a Page *might* contain valid records. It must re-verify the match condition for every tuple on that page. In `EXPLAIN` plans, this shows up as `Recheck Cond`. - **I/O Prefetching**: Because Postgres knows the entire "route" ahead of time, it can issue **Asynchronous I/O** requests to pre-fetch the next pages before the server even arrives at them. --- - **Operates on**: [[Structures/Page|Page]] [[Structures/Table|Table]] - **Factors**: `seq_page_cost`, `cpu_tuple_cost` - **Workloads**: - [[Workloads/IO/DataFile/DataFileRead|IO: DataFileRead]] - [[Workloads/IO/DataFile/DataFilePrefetch|IO: DataFilePrefetch]] - [[Workloads/LWLock/Buffers/BufferContent|LWLock: BufferContent]] - [[Workloads/LWLock/Buffers/BufferMapping|LWLock: BufferMapping]] - [[Workloads/IPC/Parallel/ParallelBitmapScan|IPC: ParallelBitmapScan]]