Updated on 2025-05-29 GMT+08:00

Bitmap

Description

  1. Bitmap index scan: This operator uses the index scan to form a bitmap based on the TIDs of tuples that meet the filter conditions and returns the bitmap to the upper layer. The BitmapAnd or BitmapOr operation can be executed on multiple result bitmaps scanned from multiple tables. Unlike index scans that require comparing filtered tuples across tables, BitmapAnd and BitmapOr operations decrease the filtering time.
  2. Bitmap heap scan: The lower layer of this operator contains the bitmap index scan, which is used to scan the bitmap returned by the lower-layer operator to determine which tuples meet the certain conditions, obtain the tuples, and return them to the upper layer. The optimizer uses the bitmap index scan based on cost estimation and needs to return tuples that meet certain conditions. In this case, the upper layer usually uses the bitmap heap scan to filter tuples by scanning bitmaps and return the tuples.
  3. BitmapOr: This operator performs the OR operation on the lower-layer bitmap and returns the bitmap after the operation.
  4. BitmapAnd: This operator performs the AND operation on the lower-layer bitmap and returns the bitmap after the operation.

The prerequisite for using bitmap index scan and bitmap heap scan is that the GUC parameter enable_bitmapscan has been set to on.

Typical Scenarios

Multiple tables are joined, indexes are available on the joined columns of one or more tables, and there is enough data in some or all tables.

Examples

Join multiple tables with indexes.

-- Prepare data. Create three tables with data of the numeric type, randomly fill in data, and create indexes for each attribute of each table.
gaussdb=# SET enable_default_ustore_table = on;
SET
gaussdb=# CREATE TABLE t_btm_test_1(a numeric,b numeric,c numeric);
CREATE TABLE
gaussdb=# CREATE TABLE t_btm_test_2(a numeric,b numeric,c numeric);
CREATE TABLE
gaussdb=# CREATE TABLE t_btm_test_3(a numeric,b numeric,c numeric);
CREATE TABLE

gaussdb=# DECLARE 
    n1 numeric := 100;
    n2 numeric := 0; 
    n3 numeric := 100;
BEGIN 
    WHILE n1 > 0 LOOP 
        WHILE n2 < 100 LOOP
            WHILE n3 > 0 LOOP
                INSERT INTO t_btm_test_1 VALUES(n1, n2, n3); 
                INSERT INTO t_btm_test_2 VALUES(n1, n3, n2); 
                INSERT INTO t_btm_test_3 VALUES(n2, n1, n3);
                n3 := n3 - 1;
            END LOOP; 
            n2 := n2 + 1; 
        END LOOP;
        n1 := n1 - 1;
    END LOOP; 
END;
/
ANONYMOUS BLOCK EXECUTE 

gaussdb=# CREATE INDEX idx_btm_test_11 ON t_btm_test_1 USING UBTREE (a);
CREATE INDEX 
gaussdb=# CREATE INDEX idx_btm_test_12 ON t_btm_test_1 USING UBTREE (b);
CREATE INDEX
gaussdb=# CREATE INDEX idx_btm_test_13 ON t_btm_test_1 USING UBTREE (c); 
CREATE INDEX												    
gaussdb=# CREATE INDEX idx_btm_test_21 ON t_btm_test_2 USING UBTREE (a);
CREATE INDEX
gaussdb=# CREATE INDEX idx_btm_test_22 ON t_btm_test_2 USING UBTREE (b); 
CREATE INDEX
gaussdb=# CREATE INDEX idx_btm_test_23 ON t_btm_test_2 USING UBTREE (c); 
CREATE INDEX												    
gaussdb=# CREATE INDEX idx_btm_test_31 ON t_btm_test_3 USING UBTREE (a);
CREATE INDEX
gaussdb=# CREATE INDEX idx_btm_test_32 ON t_btm_test_3 USING UBTREE (b);
CREATE INDEX
gaussdb=# CREATE INDEX idx_btm_test_33 ON t_btm_test_3 USING UBTREE (c);
CREATE INDEX

gaussdb=# ANALYZE t_btm_test_1;
ANALYZE
gaussdb=# ANALYZE t_btm_test_2;
ANALYZE
gaussdb=# ANALYZE t_btm_test_3;
ANALYZE

-- Execution result.
gaussdb=# SET enable_bitmapscan = on;
SET
gaussdb=# EXPLAIN SELECT /*+ HashJoin(t_btm_test_2 t_btm_test_3 t_btm_test_1)
                             Leading(((t_btm_test_2 t_btm_test_3) t_btm_test_1))
                             NestLoop(t_btm_test_2 t_btm_test_3)
                             BitmapScan(t_btm_test_2 idx_btm_test_22 idx_btm_test_21 idx_btm_test_21)
                             BitmapScan(t_btm_test_3 idx_btm_test_31 idx_btm_test_31)
                             TableScan(t_btm_test_1)*/ *
                   FROM t_btm_test_1 , t_btm_test_2 , t_btm_test_3
                   WHERE t_btm_test_1.a = t_btm_test_2.b AND
                         t_btm_test_2.a = t_btm_test_3.c AND
                         t_btm_test_3.a = t_btm_test_1.c AND
                         t_btm_test_1.a = 1
                   AND (
                        (t_btm_test_2.a = 1 AND t_btm_test_3.a = 1) OR
                        (t_btm_test_2.a = 3 AND t_btm_test_3.a = 3)
                        );
                                                                            QUERY PLAN
-------------------------------------------------------------------------------------------------------------------------------------------------------------------
 Hash Join  (cost=23.80..31.87 rows=1 width=39)
   Hash Cond: (t_btm_test_3.a = t_btm_test_1.c)
   ->  Nested Loop  (cost=21.54..29.59 rows=1 width=26)
         Join Filter: ((t_btm_test_2.a = t_btm_test_3.c) AND (((t_btm_test_2.a = 1) AND (t_btm_test_3.a = 1)) OR ((t_btm_test_2.a = 3) AND (t_btm_test_3.a = 3))))
         ->  Bitmap Heap Scan on t_btm_test_2  (cost=13.02..17.04 rows=1 width=13)
               Recheck Cond: ((b = 1) AND ((a = 1) OR (a = 3)))
               ->  BitmapAnd  (cost=13.02..13.02 rows=1 width=0)
                     ->  Bitmap Index Scan on idx_btm_test_22  (cost=0.00..4.26 rows=1 width=0)
                           Index Cond: (b = 1)
                     ->  BitmapOr  (cost=8.52..8.52 rows=1 width=0)
                           ->  Bitmap Index Scan on idx_btm_test_21  (cost=0.00..4.26 rows=1 width=0)
                                 Index Cond: (a = 1)
                           ->  Bitmap Index Scan on idx_btm_test_21  (cost=0.00..4.26 rows=1 width=0)
                                 Index Cond: (a = 3)
         ->  Bitmap Heap Scan on t_btm_test_3  (cost=8.52..12.53 rows=1 width=13)
               Recheck Cond: ((a = 1) OR (a = 3))
               ->  BitmapOr  (cost=8.52..8.52 rows=1 width=0)
                     ->  Bitmap Index Scan on idx_btm_test_31  (cost=0.00..4.26 rows=1 width=0)
                           Index Cond: (a = 1)
                     ->  Bitmap Index Scan on idx_btm_test_31  (cost=0.00..4.26 rows=1 width=0)
                           Index Cond: (a = 3)
   ->  Hash  (cost=2.25..2.25 rows=1 width=13)
         ->  Seq Scan on t_btm_test_1  (cost=0.00..2.25 rows=1 width=13)
               Filter: (a = 1)
(24 rows)

-- Drop the table.
gaussdb=# DROP TABLE t_btm_test_1, t_btm_test_2, t_btm_test_3;

In the preceding example, the output of the bitmap heap scan operator is as follows.

Item

Description

Bitmap Heap Scan

Operator name.

Recheck Cond

After the index scan is performed, the database checks the filter predicate again. In the example, the filter condition of Recheck Cond: ((a = 1::numeric) OR (a = 3::numeric)) is that the value of column a is equal to 1 or 3. When a query is executed, rows that meet these conditions are included in the final result set.

In the preceding example, the output of the bitmap index scan operator is as follows.

Item

Description

Bitmap Index Scan

Operator name.

Index Cond

Filter predicate of the operator. When a query is executed, rows that meet these conditions are included in the final result set.

In the preceding example, the output of the BitmapOr and BitmapAnd operators is as follows.

Item

Description

BitmapOr

Operator name, indicating that the OR operation is performed on the bitmap returned by the lower layer to form a bitmap that matches more complex conditions.

BitmapAnd

Operator name, indicating that the AND operation is performed on the bitmap returned by the lower layer to form a bitmap that matches more complex conditions.