# Bitmap
#### 算子说明
1. Bitmap Index Scan，位图索引扫描，该算子的作用为用索引扫描的方式，将过滤出的符合条件的元组的tid形成一张位图并向上返回。多个表扫描出的多个结果位图之间可再做 BitmapAnd或者BitmapOr操作，相比于Index Scan还需要对表与表之间筛选出来的元组进行比对，可减少过滤时间。
2. Bitmap Heap Scan，位图堆扫描，该算子的下层通常有Bitmap Index Scan，作用为通过扫描下层算子返回的位图（bitmap）来判断哪些元组符合条件并取出然后向上返回。当优化器通过代价估算选择采用Bitmap Index Scan的扫描方式，且需要返回符合条件的元组时，通常上层会配套使用Bitmap Heap Scan来通过扫描位图过滤选取元组并返回。
3. BitmapOr，位图或操作，该算子作用为将下层的bitmap进行或操作，返回操作后的位图。
4. BitmapAnd，位图与操作，该算子作用为将下层的bitmap进行与操作，返回操作后的位图。
使用Bitmap Index Scan和Bitmap Heap Scan的前提条件为：GUC参数enable_bitmapscan设置为on。
#### 典型场景
多个表做关联，且在一个或多个表的关联列上有可用的索引，部分或全部表的表数据足够大。
#### 示例
示例：多表连接带索引。
```
--数据准备，创建3个表，数据均为numeric类型，随机填充数据，为每个表的每个属性创建索引。
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
--执行结果。 
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)
--删除表。
gaussdb=# DROP TABLE t_btm_test_1, t_btm_test_2, t_btm_test_3;
```
上述示例中，Bitmap Heap Scan算子输出信息如下所示。
| 信息名称             | 含义                                                                                                                            |
|:---|:---|
| Bitmap Heap Scan | 算子的名称。                                                                                                                        |
| Recheck Cond     | 在执行索引扫描后，数据库重新检查过滤的谓词，示例中Recheck Cond: ((a = 1::numeric) OR (a = 3::numeric))的过滤条件为，a列的值等于1或者等于3。在查询执行时，满足这些条件的行会被包含在最终的结果集中。 |
   
上述示例中，Bitmap Index Scan算子输出信息如下所示。
| 信息名称              | 含义                                    |
|:---|:---|
| Bitmap Index Scan | 算子的名称。                                |
| Index Cond        | 该算子的过滤谓词，在查询执行时，满足这些条件的行会被包含在最终的结果集中。 |
   
上述示例中，BitmapOr \& BitmapAnd算子输出信息如下所示。
| 信息名称      | 含义                                             |
|:---|:---|
| BitmapOr  | 算子的名称，代表将下层返回的bitmap进行or运算，通过该操作组成匹配更复杂条件的位图。  |
| BitmapAnd | 算子的名称，代表将下层返回的bitmap进行and运算，通过该操作组成匹配更复杂条件的位图。 |