Updated on 2025-03-13 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 performed among multiple result bitmaps scanned by multiple tables. Compared with the index scan, the BITMAPAND or BITMAPOR operation needs to compare the tuples filtered between tables, reducing 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 associated, indexes are available on the associated columns of one or more tables, and there is enough data in some or all tables.

Examples

Example: 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

-- Collect statistics.
gaussdb=# ANALYZE t_btm_test_1;
gaussdb=# ANALYZE t_btm_test_2;
gaussdb=# ANALYZE t_btm_test_3;

-- Execution result.
gaussdb=# SET enable_bitmapscan = on;
SET
gaussdb=# EXPLAIN SELECT /*+ hashjoin(t_btm_test_1 t_btm_test_2 t_btm_test_3) BitmapScan(t_btm_test_2 idx_btm_test_21 idx_btm_test_22) BitmapScan(t_btm_test_3 idx_btm_test_31 )*/ * 
        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
---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
 Streaming (type: GATHER)  (cost=3632.18..5782.71 rows=735 width=42)
   Node/s: All datanodes
   ->  Hash Join  (cost=3628.18..5748.21 rows=735 width=42)
         Hash Cond: (t_btm_test_1.c = t_btm_test_3.a)
         ->  Bitmap Heap Scan on t_btm_test_1  (cost=123.65..2227.20 rows=10169 width=14)
               Recheck Cond: (a = 1::numeric)
               ->  Bitmap Index Scan on idx_btm_test_11  (cost=0.00..122.38 rows=10169 width=0)
                     Index Cond: (a = 1::numeric)
         ->  Hash  (cost=3504.44..3504.44 rows=14 width=28)
               ->  Streaming(type: BROADCAST)  (cost=916.01..3504.44 rows=14 width=28)
                     Spawn on: All datanodes
                     ->  Hash Join  (cost=916.01..3503.81 rows=7 width=28)
                           Hash Cond: (t_btm_test_3.c = t_btm_test_2.a)
                           Join Filter: (((t_btm_test_2.a = 1::numeric) AND (t_btm_test_3.a = 1::numeric)) OR ((t_btm_test_2.a = 3::numeric) AND (t_btm_test_3.a = 3::numeric)))
                           ->  Bitmap Heap Scan on t_btm_test_3  (cost=244.56..2436.73 rows=19921 width=14)
                                 Recheck Cond: ((a = 1::numeric) OR (a = 3::numeric))
                                 ->  BitmapOr  (cost=244.56..244.56 rows=20022 width=0)
                                       ->  Bitmap Index Scan on idx_btm_test_31  (cost=0.00..122.06 rows=10081 width=0)
                                             Index Cond: (a = 1::numeric)
                                       ->  Bitmap Index Scan on idx_btm_test_31  (cost=0.00..117.53 rows=9941 width=0)
                                             Index Cond: (a = 3::numeric)
                           ->  Hash  (cost=669.12..669.12 rows=372 width=14)
                                 ->  Streaming(type: BROADCAST)  (cost=346.49..669.12 rows=372 width=14)
                                       Spawn on: All datanodes
                                       ->  Bitmap Heap Scan on t_btm_test_2  (cost=346.49..654.48 rows=186 width=14)
                                             Recheck Cond: ((b = 1::numeric) AND ((a = 1::numeric) OR (a = 3::numeric)))
                                             ->  BitmapAnd  (cost=346.49..346.49 rows=187 width=0)
                                                   ->  Bitmap Index Scan on idx_btm_test_22  (cost=0.00..111.80 rows=9481 width=0)
                                                         Index Cond: (b = 1::numeric)
                                                   ->  BitmapOr  (cost=234.42..234.42 rows=19702 width=0)
                                                         ->  Bitmap Index Scan on idx_btm_test_21  (cost=0.00..117.00 rows=9801 width=0)
                                                               Index Cond: (a = 1::numeric)
                                                         ->  Bitmap Index Scan on idx_btm_test_21  (cost=0.00..117.38 rows=9901 width=0)
                                                               Index Cond: (a = 3::numeric)
(34 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.