### Bitmap Index Scan ![[assets/ex_bitmapindexscan.png|256]] ### The Explain Trace ```sql -- Querying a medium-selectivity range EXPLAIN (ANALYZE, COSTS, BUFFERS, VERBOSE) SELECT * FROM animals WHERE species_id = 1; ``` ```text -> Bitmap Index Scan on idx_animals_species_id (cost=1.00..50.29 rows=4000 width=0) (actual time=1.629..1.629 rows=4000 loops=1) Index Cond: (animals.species_id = 1) Buffers: shared read=5 ``` --- > [!NOTE] > **Metaphor: Marking the Floor Map.** Instead of a server running to the kitchen for every individual order, they look at the list and mark every table that needs service on a clipboard map. This map is the **Bitmap**. ### How it Works Postgres traverses the index and gathers the **TIDs (Tuple Identifiers)** of every matching record. However, instead of using them to fetch data immediately, it compiles them into a **TIDBitmap**—a specialized in-memory bitset. ### Physical Implementation - **Bit-per-Page**: In most cases, the bitmap stores one bit per **Page (8KB block)** on the disk. A `1` means "this page contains at least one relevant record." - **Bit-per-Tuple**: If memory permits and the volume is low, the bitmap can store bits for individual tuples. - **Memory Constraint**: The bitmap is stored in **`work_mem`**. If the number of matching records is so large that the bitset exceeds `work_mem`, Postgres converts the bitmap to a **Lossy** state, where it only tracks bits at the Page level, discarding individual tuple knowledge to save space. --- - **Operates on**: [[Structures/Index|Index]] - **Factor**: `cpu_index_tuple_cost` - **Workloads**: - [[Workloads/IO/DataFile/DataFileRead|IO: DataFileRead]] - [[Workloads/LWLock/Buffers/BufferContent|LWLock: BufferContent]] - [[Workloads/LWLock/Buffers/BufferMapping|LWLock: BufferMapping]] - [[Workloads/IPC/Parallel/ParallelBitmapScan|IPC: ParallelBitmapScan]]