> [!NOTE] Bitmap Index Scan > <table> > <tr> > <td width="25%"><img src="assets/ex_bitmapindexscan.png"></td> > <td>Traverses an index to find matching rows but instead of fetching them immediately, it populates a bitmap in memory marking which pages in the table contain matches. This bitmap can then be combined with others (AND/OR) before the heap is visited.</td> > </tr> > </table> > > ```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]]