# 连接路径生成
前面章节介绍了几类常用的基表扫描路径，包括：顺序扫描路径、索引扫描路径和位图扫描路径，但在实际的SQL查询场景中并非只涉及基表查询，而是经常需要对多个表做各种连接操作来生成最终查询结果，SQL查询中常用的连接操作包括：INNER JOIN、LEFT JOIN、SEMI JOIN等，因此针对这些连接运算GaussDB会在CBO优化器阶段生成不同的连接路径。这些路径指的是物理连接路径（区别于INNER JOIN、LEFT JOIN这些逻辑连接运算），即可以被执行器理解的具体算法，常见连接路径实现主要有三类：NestloopJoin路径、HashJoin路径和MergeJoin路径，连接路径的生成过程也就是不断尝试这三种路径的过程。
之所以会有不同的物理连接路径，是因为在不同的数据分布、索引条件和约束场景下，两个基表要建立连接关系，使用不同的物理路径在实际执行过程中性能会有差异，没有一种物理路径可以在所有场景下保持高性能，因此通常要针对不同的情况基于代价选择适合的连接路径，从而提升执行效率。
为了便于描述三种连接路径的生成方式，建立如下数据库表：
```
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, 10000), generate_series(1, 10000), floor(random()*10));
INSERT 0 10000
gaussdb=# ANALYZE t1;
ANALYZE
gaussdb=# CREATE TABLE t2(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_t2_a ON t2(a);
CREATE INDEX
gaussdb=# CREATE INDEX idx_t2_b ON t2(b);
CREATE INDEX
gaussdb=# INSERT INTO t2 (a, b, c) VALUES (generate_series(1, 10000), generate_series(1, 10000), floor(random()*10));
INSERT 0 10000
gaussdb=# ANALYZE t2;
ANALYZE
gaussdb=# SET enable_fast_query_shipping = off;
SET
gaussdb=# SET explain_perf_mode=normal;
SET
```
- NestloopJoin路径 NestloopJoin路径又被称为嵌套循环连接路径，是三种连接方式中最通用、最直观的一种连接方式，其在生成连接路径时会选择一张表做驱动表（或称作外表），另一张表做被驱动表（或称作内表），通过驱动表和被驱动表做双层循环遍历的方式进行数据匹配，时间复杂度为O(N\*M)。以两表的Nestloop场景为例，执行如下SQL语句：
  ```
  gaussdb=# EXPLAIN SELECT * FROM t1 LEFT JOIN t2 ON t1.a != t2.a AND t1.b != t2.b;
                                        QUERY PLAN
  ---------------------------------------------------------------------------------------
   Streaming (type: GATHER)  (cost=4.00..4750131.35 rows=99980001 width=32)
     Node/s: All datanodes
     ->  Nested Loop Left Join  (cost=0.00..584297.98 rows=99980001 width=32)
           Join Filter: ((t1.a <> t2.a) AND (t1.b <> t2.b))
           ->  Seq Scan on t1  (cost=0.00..48.33 rows=10000 width=16)
           ->  Materialize  (cost=0.00..999.65 rows=30000 width=16)
                 ->  Streaming(type: BROADCAST)  (cost=0.00..949.65 rows=30000 width=16)
                       Spawn on: All datanodes
                       ->  Seq Scan on t2  (cost=0.00..48.33 rows=10000 width=16)
  (9 rows)
  ```
  上述示例是一个典型的Nestloop路径生成计划的场景，该路径以t1表做驱动表，t2表做被驱动表进行双层循环遍历，外表t1表每扫描一行数据，即驱动内表t2表执行一次遍历，并将满足t1.a != t2.a AND t1.b != t2.b匹配条件的内外表行做连接操作。根据NestloopJoin路径的生成原理，这种连接方式除了FULL JOIN场景下无法使用，在类型Join场景下均可生成候选路径，因此可以作为其他连接路径无法生成时的最后选择，但是根据算法复杂度可以看出，在数据规模较大的场景下特别是约束条件过滤性较好时其性能不一定是最好的。
  NestloopJoin路径中还有一种特殊的路径形态，叫做参数化路径。假设t1表和t2表做Join的场景，连接条件为t1.a = t2.a, 根据谓词下推的原理，这个JOIN条件无法下推到内外表的任何一侧，因为t1.a = t2.a这个连接条件既关联了外表，又关联了内表，必须同时获取两个表的元组后才能应用这个约束条件，这种情况下即使在t2表的a列上存在索引也无法生成索引路径加速数据筛选。为了利用索引条件加速，可以考虑将外表条件列参数化，生成一个特殊的Param类型，在外表驱动内表过程中，当t1.a的值确定后就可以作为一个常数传递到t1.a = t2.a这个约束上，约束条件即可转换为t2.a = Const，对于常量谓词可以正常下推到内表上，从而在t2表上生成索引路径，利用索引条件的特性进行加速，典型的场景如下面SQL所示：
  ```
  gaussdb=# SET enable_hashjoin=off;
  SET
  gaussdb=# SET enable_mergejoin=off;
  SET
  gaussdb=# EXPLAIN SELECT * FROM t1 LEFT JOIN t2 ON t1.a = t2.a;
                                     QUERY PLAN
  --------------------------------------------------------------------------------
   Streaming (type: GATHER)  (cost=4.00..1417.36 rows=10000 width=32)
     Node/s: All datanodes
     ->  Nested Loop Left Join  (cost=0.00..1000.74 rows=10000 width=32)
           ->  Seq Scan on t1  (cost=0.00..48.33 rows=10000 width=16)
           ->  Index Scan using idx_t2_a on t2  (cost=0.00..0.28 rows=1 width=16)
                 Index Cond: (t1.a = a)
  (6 rows)
  ```
  这里为了展示参数化路径，关闭了HashJoin和MergeJoin，从上面的计划可以看出，t1.a = t2.a这个条件被下推到了t2表的索引条件上，当外表每执行一行，即可将该行的a列值作为常数传递到内表，内表即可将常量查询条件作用在t2表的索引上，达到快速检索数据的目的。
  

- HashJoin路径 HashJoin路径是一种利用hash表加速连接操作的Join方式，要求连接条件指定列的数据类型可以做hash运算（如数值类型），且连接条件必须为等值条件。以两表HashJoin场景为例，执行如下SQL语句：
  ```
  gaussdb=# SET enable_hashjoin=on;
  SET
  gaussdb=# EXPLAIN SELECT * FROM t1 LEFT JOIN t2 ON t1.a = t2.a;
                                  QUERY PLAN
  --------------------------------------------------------------------------
   Streaming (type: GATHER)  (cost=93.99..600.78 rows=10000 width=32)
     Node/s: All datanodes
     ->  Hash Left Join  (cost=89.99..184.15 rows=10000 width=32)
           Hash Cond: (t1.a = t2.a)
           ->  Seq Scan on t1  (cost=0.00..48.33 rows=10000 width=16)
           ->  Hash  (cost=48.33..48.33 rows=9999 width=16)
                 ->  Seq Scan on t2  (cost=0.00..48.33 rows=10000 width=16)
  (7 rows)
  ```
  上面示例是一个典型的HashJoin路径生成计划场景，在该场景中t1表的a列和t2表的a列都是整型值，且满足等值连接约束，因此可以生成HashJoin路径。其中，t1表作为驱动表，t2表作为被驱动表，在实际执行时，首先会对内表中的数据按指定列（示例场景中为t2表的a列）建hash表，然后使用外表驱动内表，对于外表的每一条数据，利用hash表查找匹配条目。
  根据Hash表的原理可知通常情况下，HashJoin路径的效率要高于NestloopJoin路径，对比NestloopJoin计划如下所示：
  ```
  gaussdb=# SET enable_hashjoin=off;
  SET
  gaussdb=# SET enable_mergejoin=off;
  SET
  gaussdb=# EXPLAIN SELECT * FROM t1 LEFT JOIN t2 ON t1.a = t2.a;
                                     QUERY PLAN
  --------------------------------------------------------------------------------
   Streaming (type: GATHER)  (cost=4.00..1417.36 rows=10000 width=32)
     Node/s: All datanodes
     ->  Nested Loop Left Join  (cost=0.00..1000.74 rows=10000 width=32)
           ->  Seq Scan on t1  (cost=0.00..48.33 rows=10000 width=16)
           ->  Index Scan using idx_t2_a on t2  (cost=0.00..0.28 rows=1 width=16)
                 Index Cond: (t1.a = a)
  (6 rows)
  ```
  为了保证生成NestloopJoin路径计划，本例中关闭了生成HashJoin和MergeJoin路径的逻辑，对比两个计划可知NestloopJoin路径生成的计划代价明显高于HashJoin路径生成的计划。
  

- MergeJoin路径 MergeJoin路径是一种利用预排序加速连接操作的join方式，根据连接条件，将基表按连接条件指定列先进行排序，之后像归并排序那样，找出满足连接条件的条目（一般为等值条件）并输出。以两表Mergejoin场景为例，执行如下SQL语句：
  ```
  gaussdb=# SET enable_mergejoin=on;
  SET
  gaussdb=# SET enable_hashjoin=off;
  SET
  gaussdb=# EXPLAIN SELECT t1.a,t2.a FROM t1 LEFT JOIN t2 ON t1.a = t2.a;
                                         QUERY PLAN
  -----------------------------------------------------------------------------------------
   Streaming (type: GATHER)  (cost=4.00..589.11 rows=10000 width=8)
     Node/s: All datanodes
     ->  Merge Left Join  (cost=0.00..172.49 rows=10000 width=8)
           Merge Cond: (t1.a = t2.a)
           ->  Index Only Scan using idx_t1_a on t1  (cost=0.00..61.24 rows=10000 width=4)
           ->  Index Only Scan using idx_t2_a on t2  (cost=0.00..61.24 rows=10000 width=4)
  (6 rows)
  ```
  MergeJoin路径的性能通常介于HashJoin路径和NestloopJoin路径之间，但有些场景下也可以带来明显优势。根据上面的计划可知，对于MergeJoin路径主要利用了归并排序的原理，因为这个SQL中只输出t1表和t2表的a列，a列是分布列且两张表在a列上均有索引，利用索引的有序性可以提升归并排序算法的性能，因此可以带来比HashJoin更好的执行效率。
  
上述示例删除建表语句如下：
```
gaussdb=# DROP TABLE t1;
DROP TABLE
gaussdb=# DROP TABLE t2;
DROP TABLE
gaussdb=# RESET explain_perf_mode;
RESET
```
上面介绍了GaussDB中常用三类连接路径，但在实际场景中除了要考虑连接算法外还需要考虑表之间的连接顺序。以INNER JOIN为例，对于t1 INNER JOIN t2这样一组JOIN关系，在生成Nestloop Join路径时就有两种选择，可以让t1表做驱动表，也可以让t2表做驱动表，因为NestloopJoin适合小表驱动大表的场景，这时就需要根据t1表和t2表的数据分布情况进行选择，所以在生成连接路径时通常需要考虑表之间不同的连接顺序组合。由于SQL的复杂性，路径生成过程一般无法通过穷举实现，以最简单的两表JOIN场景为例，就需要至少尝试18种不同的路径（3种连接算法x2种连接顺序x3种扫描路径）, 实际情况更加复杂，还需要考虑是否有参数化路径、约束条件是否可以下推等，因此对于多表Join的情况，路径规模呈指数级增长。因此数据库中通常会采用一些智能算法来进行剪枝，避免搜索空间爆炸，常用的路径生成算法主要有：动态规划算法和遗传算法。以最广泛使用的动态规划算法为例，其核心思想是：将大问题分解为小问题，解决小问题，存储小问题的最优解，并用这些最优解来构造更大问题的最优解，避免重复计算。算法核心思想说明如下：
- 提取重复子问题
  图1提取子问题示例图   
  ![](https://support.huaweicloud.com/distributed-devg-v10-gaussdb/figure/zh-cn_image_0000002590200940.png "点击放大")
  如上图两颗连接树中的AXB的连接操作就属于重复子问题。对于Join Tree的每个子问题，可以通过不断获得子问题的最低代价路径，剪枝掉较差的代价路径，而逐层迭代式地"堆积"出完整连接树的最低代价路径。
  
- 获取最优子结构 对于路径生成来说，每个叶子节点都是表的扫描路径，但是当前扫描路径最优并不一定代表后续的连接路径最优。例如，顺序扫描代价 \< 索引扫描代价，顺序扫描代价 + 排序代价 \> 索引扫描代价，所以在优化器计算子问题的代价时，不仅要保存最优解，还同时保存较优解，它需要考虑最优的启动代价路径、参数化路径等。动态规划从求解的方式而言通常有递归和迭代两种方法，目前数据库采用的是迭代的方法进行求解，它先尝试求两个表的最优子路径，然后依次迭代成3个表、4个表。