### Bitmap And / Bitmap Or ![[assets/ex_bitmapandbitmapor.png|256]] ### The Explain Trace ```sql -- Combining results from two separate indexes EXPLAIN (ANALYZE, COSTS, BUFFERS, VERBOSE) SELECT * FROM animals WHERE species_id = 1 OR name = 'Capybara'; ``` ```text -> BitmapOr (cost=56.59..56.59 rows=4002 width=0) (actual time=1.056..1.057 rows=0 loops=1) -> Bitmap Index Scan on idx_animals_species_id (cost=1.00..50.29 rows=4000 width=0) -> Bitmap Index Scan on idx_animals_name (cost=1.00..5.30 rows=2 width=0) ``` --- > [!NOTE] > **Metaphor: Combining Map Overlays.** If two different patrons order the same dish, the server takes two transparent map overlays (the Bitmaps) and stacks them. Where the dots overlap (AND) or combine (OR) is where the server needs to go. ### How it Works These internal nodes combine two or more **TIDBitmaps** using logical bitwise operations. This is one of the most powerful features of the relational model: turning complex search logic into simple binary arithmetic. ### Physical Implementation - **Bitwise Intersection (AND)**: Performs a `&` operation on the bitsets. Only bits present in BOTH input bitmaps remain. - **Bitwise Union (OR)**: Performs a `|` operation on the bitsets. Bits present in EITHER input bitmap remain. - **Efficiency**: Because bitsets are extremely compact (1 bit per 8KB page), the CPU can process millions of rows in microseconds using standard registers. This allows Postgres to combine multiple un-related indexes (e.g., searching for animals that are `Species: Capybara` AND `Diet: Herbivore`) without needing a specialized "multi-column" index. --- - **Operates on**: [[Structures/Index|Index]] - **Factor**: `cpu_operator_cost` - **Workloads**: - [[Workloads/LWLock/Buffers/SharedTidBitmap|LWLock: SharedTidBitmap]] - [[Workloads/LWLock/Buffers/BufferContent|LWLock: BufferContent]] - [[Workloads/IPC/Parallel/ParallelBitmapScan|IPC: ParallelBitmapScan]]