# Bitmap Index Scan (The Mapper) ![[assets/ex_bitmapindexscan.png|256]] > [!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/DataFileRead|IO: DataFileRead]] - [[Workloads/LWLock/Buffers/BufferContent|LWLock: BufferContent]] - [[Workloads/LWLock/Buffers/BufferMapping|LWLock: BufferMapping]] - [[Workloads/IPC/Parallel/ParallelBitmapScan|IPC: ParallelBitmapScan]]