# 扫描路径生成
扫描路径主要包括：顺序扫描路径（SeqScanPath）、索引扫描路径（IndexScanPath）、位图扫描路径（BitmapScanPath）等几种类型，本节主要针对这几类扫描路径进行说明。
- 顺序扫描（SeqScan） 顺序扫描即全表扫描，是GaussDB中最基础的一种扫描方式。这种扫描方式直接从磁盘中按顺序读取基表相关页面，将表中的所有元组都取出来，然后再按照约束条件进行过滤，最终根据查询语句的指示返回符合过滤条件的元组，因此该扫描方式的算法复杂度是O(N)。
  以下结合具体示例来展示顺序扫描路径的原理，基表建表语句如下：
  ```
  gaussdb=# CREATE TABLE t1(a INT, b INT, c INT, d INT);
  NOTICE:  The 'DISTRIBUTE BY' clause is not specified. Using 'a' as the distribution column by default.
  HINT:  Please use 'DISTRIBUTE BY' clause to specify suitable data distribution column.
  CREATE TABLE
  gaussdb=# INSERT INTO t1 VALUES(1,2,3,4),(2,3,4,5),(3,4,5,6),(4,5,6,7),(5,6,7,8);
  INSERT 0 5
  gaussdb=# ANALYZE t1;
  ANALYZE
  gaussdb=# SET enable_fast_query_shipping = off;
  SET
  gaussdb=# SET explain_perf_mode=normal;
  SET
  ```
  执行如下SQL语句：
  ```
  gaussdb=# SELECT * FROM t1 WHERE t1.b = 3;
   a | b | c | d
  ---+---+---+---
   2 | 3 | 4 | 5
  (1 row)
  ```
  对于上述SQL，遍历t1表，并将t1表中b列值等于3的行返回，因此生成的查询计划如下所示：
  ```
  gaussdb=# EXPLAIN ANALYZE SELECT * FROM t1 WHERE t1.b = 3;
                                                   QUERY PLAN
  ------------------------------------------------------------------------------------------------------------
   Streaming (type: GATHER)  (cost=0.06..2.15 rows=1 width=16) (actual time=2.450..3.849 rows=1 loops=1)
     Node/s: All datanodes
     ->  Seq Scan on t1  (cost=0.00..2.02 rows=1 width=16) (actual time=[0.006,0.006]..[0.179,0.179], rows=1)
           Filter: (b = 3)
           Rows Removed by Filter: 4
   Total runtime: 4.367 ms
  (6 rows)
  ```
  该计划中，" Seq Scan on t1"表明由顺序扫描路径生成，"Filter: (b = 3)"是顺序扫描的过滤条件。根据上面计划的实际执行情况可知，执行器遍历了整个t1表，过滤掉4行数据（Rows Removed by Filter: 4），返回了1行数据"(actual time=2.450..3.849 rows=1 loops=1)"，与预期一致。
  上述示例删除建表语句如下：
  ```
  gaussdb=# DROP TABLE t1;
  DROP TABLE
  gaussdb=# RESET explain_perf_mode;
  RESET
  ```
  

- 索引扫描（IndexScan） GaussDB中表的物理存储方式是按堆表存储的，当插入一条数据时，其在物理磁盘上可能被存放在一个新开辟的页面上，也可能被存放在之前删除元组后空出来的页面上。这样组织的好处是存储结构比较简单，但是也带来一些问题，对于一些带有排序条件或等值过滤条件的场景无法利用有序查找算法来提升执行效率，由于数据是无序存储的，需要顺序扫描遍历整表才能找到所有满足条件的元组。
  为了提升数据库的查询性能，GaussDB提供了多种索引扫描方式来满足大数据量有序查询场景下的高性能诉求。一种常见的索引组织方式是B/B+树，其使用有序的树状结构对磁盘上的数据重新进行组织，添加额外的查找目录，使得对于SQL中包含"b = ?"这样过滤条件的数据查找复杂度降低到O(Log(N))。
  在GaussDB中想要生成索引路径，通常需要在过滤条件的基表列上有索引约束，否则无法生成索引路径。索引类型通常包含：主键索引、唯一索引（有NULL值）、唯一非空索引等。以下面场景为例，建表语句如下：
  ```
  gaussdb=# CREATE TABLE t1(a INT, b INT, c INT, d INT);
  NOTICE:  The 'DISTRIBUTE BY' clause is not specified. Using 'a' as the distribution column by default.
  HINT:  Please use 'DISTRIBUTE BY' clause to specify suitable data distribution column.
  CREATE TABLE
  gaussdb=# CREATE INDEX idx_t1_b ON t1(b);
  CREATE INDEX
  gaussdb=# INSERT INTO t1 (a, b, c) VALUES (generate_series(1, 5000), generate_series(1, 5000), floor(random()*10));
  INSERT 0 5000
  gaussdb=# ANALYZE t1;
  ANALYZE
  gaussdb=# SET enable_fast_query_shipping = off;
  SET
  gaussdb=# SET explain_perf_mode=normal;
  SET
  ```
  执行如下SQL语句：
  ```
  gaussdb=# SELECT * FROM t1 WHERE t1.b = 200;
    a  |  b  | c | d
  -----+-----+---+---
   200 | 200 | 2 |
  (1 row)
  ```
  对于上述SQL，遍历t1表，并将t1表中b列值等于200的行返回，生成的查询计划如下所示：
  ```
  gaussdb=# EXPLAIN ANALYZE SELECT * FROM t1 WHERE t1.b = 200;
                                                           QUERY PLAN
  -----------------------------------------------------------------------------------------------------------------------------
   Streaming (type: GATHER)  (cost=0.06..2.59 rows=1 width=16) (actual time=2.307..4.253 rows=1 loops=1)
     Node/s: All datanodes
     ->  Index Scan using idx_t1_b on t1  (cost=0.00..2.47 rows=1 width=16) (actual time=[0.033,0.033]..[0.055,0.057], rows=1)
           Index Cond: (b = 200)
   Total runtime: 4.645 ms
  (5 rows)
  ```
  该计划中，"Index Scan using idx_t1_b on t1"表明由索引扫描路径生成，使用的是t1表在b列上建立的idx_t1_b索引，而"Index Cond: (b = 200)"是索引扫描条件。根据上面计划的实际执行情况可知，执行器并没有遍历整个t1表， 而是直接通过索引找到了b = 200的行。对比前面的顺序扫描方式，其执行计划如下：
  ```
  gaussdb=# EXPLAIN ANALYZE SELECT /*+tablescan(t1)*/* FROM t1 WHERE t1.b = 200;
                                                   QUERY PLAN
  -------------------------------------------------------------------------------------------------------------
   Streaming (type: GATHER)  (cost=0.06..28.96 rows=1 width=16) (actual time=3.046..3.272 rows=1 loops=1)
     Node/s: All datanodes
     ->  Seq Scan on t1  (cost=0.00..28.84 rows=1 width=16) (actual time=[0.120,0.760]..[0.964,0.964], rows=1)
           Filter: (b = 200)
           Rows Removed by Filter: 4999
   Total runtime: 3.593 ms
  (6 rows)
  ```
  上面的查询计划通过tablescan()的HINT强制指定了顺序扫描方式，从这个计划可以看到，顺序扫描方式遍历了整个t1表，并将 b = 200的行返回，这种扫描方式需要过滤掉4999行无效数据，因此其执行时间对比索引扫描要高很多。
  索引扫描本身利用的是以空间换时间的思想，通过对堆存储的无序数据进行额外的索引排序，使其在索引树上变成有组织的数据结构，并与堆上的数据建立映射关系，从而达到可以快速查找目标数据的效果。除了普通索引路径，在一些特定场景下GaussDB还能生成一些特殊类型索引路径，例如，当SQL的过滤条件和投影中只包含索引列时，整个查询所需数据都可以在索引中获取到，就避免了再去查找一次整个元组的回表操作，从而可以生成一条IndexOnlyScan路径，典型的场景如下所示：
  ```
  gaussdb=# EXPLAIN ANALYZE SELECT b FROM t1 WHERE t1.b = 200;
                                                             QUERY PLAN
  ---------------------------------------------------------------------------------------------------------------------------------
   Streaming (type: GATHER)  (cost=0.06..1.49 rows=1 width=4) (actual time=2.171..2.370 rows=1 loops=1)
     Node/s: All datanodes
     ->  Index Only Scan using idx_t1_b on t1  (cost=0.00..1.37 rows=1 width=4) (actual time=[0.030,0.032]..[0.037,0.037], rows=1)
           Index Cond: (b = 200)
           Heap Fetches: 0
   Total runtime: 2.711 ms
  (6 rows)
  ```
  该计划中，"Index Only Scan using idx_t1_b on t1"表明其查询路径是由IndexOnlyScan生成的，实际查找数据时只需要访问索引节点即可，无需再从映射的元组中取数据。
  上述示例删除建表语句如下：
  ```
  gaussdb=# DROP TABLE t1;
  DROP TABLE
  gaussdb=# RESET explain_perf_mode;
  RESET
  ```
  

- 位图扫描（BitmapScan） 位图扫描是一种特殊的索引扫描方式，它的原理是利用多个查询条件中的索引路径构建一个Bitmap集合，再结合Bitmap的交并集操作实现对数据归并处理，从而将原来只能顺序扫描的随机堆表访问转变为利用索引条件有序的堆表访问 。前面介绍了IndexScan路径生成的条件，在此基础上，如果SQL中存在多个查询约束条件，并且这些约束条件上都能生成索引路径，那么这些索引路径就可以作为位图扫描的待选路径；进而，如果这些约束条件是通过AND、OR等谓词连接的简单表达式，那么就可以生成BitmapScan路径。以下面场景为例，建表语句如下：
  ```
  gaussdb=# CREATE TABLE t1(a INT, b INT, c INT, d INT);
  NOTICE:  The 'DISTRIBUTE BY' clause is not specified. Using 'a' as the distribution column by default.
  HINT:  Please use 'DISTRIBUTE BY' clause to specify suitable data distribution column.
  CREATE TABLE
  gaussdb=# CREATE INDEX idx_t1_a ON t1(a);
  CREATE INDEX
  gaussdb=# CREATE INDEX idx_t1_b ON t1(b);
  CREATE INDEX
  gaussdb=# INSERT INTO t1 (a, b, c) VALUES (generate_series(1, 5000), generate_series(1, 5000), floor(random()*10));
  INSERT 0 5000
  gaussdb=# ANALYZE t1;
  ANALYZE
  gaussdb=# SET enable_fast_query_shipping = off;
  SET
  gaussdb=# SET explain_perf_mode=normal;
  SET
  gaussdb=# SET enable_bitmapscan=on;
  SET
  ```
  执行如下SQL语句：
  ```
  gaussdb=# SELECT * FROM t1 WHERE t1.a = 200 OR t1.b = 300;
    a  |  b  | c | d
  -----+-----+---+---
   200 | 200 | 5 |
   300 | 300 | 0 |
  (2 rows)
  ```
  对于上述SQL，遍历t1表，并将t1表中a列值等于200或者b列值等于300的行返回，其生成的查询计划如下所示：
  ```
  gaussdb=# EXPLAIN ANALYZE SELECT * FROM t1 WHERE t1.a = 200 OR t1.b = 300;
                                                                QUERY PLAN
  --------------------------------------------------------------------------------------------------------------------------------------
   Streaming (type: GATHER)  (cost=2.78..3.96 rows=2 width=16) (actual time=2.289..2.498 rows=2 loops=1)
     Node/s: All datanodes
     ->  Bitmap Heap Scan on t1  (cost=2.72..3.83 rows=2 width=16) (actual time=[0.046,0.046]..[0.097,0.098], rows=2)
           Recheck Cond: ((a = 200) OR (b = 300))
           ->  BitmapOr  (cost=2.72..2.72 rows=2 width=0) (actual time=[0.034,0.034]..[0.040,0.040], rows=0)
                 ->  Bitmap Index Scan on idx_t1_a  (cost=0.00..1.36 rows=1 width=0) (actual time=[0.020,0.020]..[0.027,0.027], rows=1)
                       Index Cond: (a = 200)
                 ->  Bitmap Index Scan on idx_t1_b  (cost=0.00..1.36 rows=1 width=0) (actual time=[0.012,0.012]..[0.013,0.013], rows=1)
                       Index Cond: (b = 300)
   Total runtime: 2.890 ms
  (10 rows)
  ```
  如上面的示例，位图扫描中实际上包含了4种不同的路径，其包括：BitmapHeap路径、BitmapOr路径或BitmapAnd路径以及IndexScan路径。在该计划中，"Bitmap Heap Scan on t1"表明该计划由Bitmap索引扫描路径生成，使用的是t1表在a列上建立的idx_t1_a索引和b列上建立的idx_t1_b索引。根据上面计划的实际执行情况可知，执行器先分别在两个索引路径上查找满足Index Cond约束的索引值，然后通过BitmapOR算子对索引扫描结果进行合并，最后通过Recheck Cond: ((a = 200) OR (b = 300)) 获取满足条件的结果集。对比顺序扫描方式，其执行计划如下：
  ```
  gaussdb=# EXPLAIN ANALYZE SELECT /*+tablescan(t1)*/* FROM t1 WHERE t1.a = 200 OR t1.b = 300;
                                                   QUERY PLAN
  -------------------------------------------------------------------------------------------------------------
   Streaming (type: GATHER)  (cost=0.06..33.13 rows=2 width=16) (actual time=3.943..4.879 rows=2 loops=1)
     Node/s: All datanodes
     ->  Seq Scan on t1  (cost=0.00..33.00 rows=2 width=16) (actual time=[0.164,1.066]..[1.265,1.265], rows=2)
           Filter: ((a = 200) OR (b = 300))
           Rows Removed by Filter: 4998
   Total runtime: 5.165 ms
  (6 rows)
  ```
  上面的查询计划通过tablescan()的HINT强制指定了顺序扫描方式，从这个计划可以看到，顺序扫描方式遍历了整个t1表，并将 a = 200或b=300的行返回，这种扫描方式需要过滤掉4998行无效数据，因此其执行时间对比BitmapOr扫描要高很多。
  上述示例删除建表语句如下：
  ```
  gaussdb=# DROP TABLE t1;
  DROP TABLE
  gaussdb=# RESET explain_perf_mode;
  RESET
  ```