3.5 连接

临时元组存储

PostgreSQL内部提供了临时元组存储的模块，可用于各种操作：物化表，创建混合散列连接的批次，等等。该模块包含一系列函数，都在tuplestore.c中。这些函数用于从工作内存或临时文件读写元组。使用工作内存还是临时文件取决于待存储元组的总数。

testdb=# EXPLAIN SELECT * FROM tbl_a AS a, tbl_b AS b WHERE a.id = b.id;
                              QUERY PLAN                   
-----------------------------------------------------------------------
 Nested Loop  (cost=0.00..750230.50 rows=5000 width=16)
   Join Filter: (a.id = b.id)
   ->  Seq Scan on tbl_a a  (cost=0.00..145.00 rows=10000 width=8)
   ->  Materialize  (cost=0.00..98.00 rows=5000 width=8)
         ->  Seq Scan on tbl_b b  (cost=0.00..73.00 rows=5000 width=8)
(5 rows)

• 第7行：执行器使用顺序扫描，物化内部表tbl_b。
• 第4行：执行器执行嵌套循环连接操作，外表是tbl_a，内表是物化的tbl_b。

• 物化操作没有启动代价；其运行代价定义如下：\( \verb|run_cost| = 2 × \verb|cpu_operator_cost| × N_{\verb|inner|};\)
• 因此：\( \verb|run_cost|=2× 0.0025× 5000=25.0\)
• 此外，\( \verb|total_cost| = (\verb|start-up_cost|+ \verb|total_cost_of_seq_scan|)+ \verb|run_cost|\)
• 因此，\( \verb|total_cost| = (0.0+73.0)+25.0=98.0\)

• 嵌套循环没有启动代价，因此：\( \verb|start-up_cost|=0\)
• 在估计运行代价之前，先来看一下重扫描的代价，重扫描的代价定义如下：\( \verb|rescan_cost| = \verb|cpu_operator_cost| × N_{\verb|inner|}\)
• 这本例中：\( \verb|rescan_cost| = (0.0025)× 5000=12.5\)

testdb=# EXPLAIN SELECT * FROM tbl_c AS c, tbl_b AS b WHERE c.id = b.id;
                                   QUERY PLAN                       
--------------------------------------------------------------------------------
 Nested Loop  (cost=0.29..1935.50 rows=5000 width=16)
   ->  Seq Scan on tbl_b b (cost=0.00..73.00 rows=5000 width=8)
   ->  Index Scan using tbl_c_pkey on tbl_c c  (cost=0.29..0.36 rows=1 width=8)
         Index Cond: (id = b.id)
(4 rows)

• 该嵌套循环连接的启动代价，等于第6行中索引扫描的代价，因此：\( \verb|start-up_cost| = 0.285\)
• 索引嵌套循环扫描的总代价由下列公式所定义：\( \verb|total_cost|= (\verb|cpu_tuple_cost| + C^{\verb|total|}{\verb|inner,parameterized|} )× N {\verb|outer|}+C^{\verb|run|}*{\verb|outer,seqscan|}\)
• 这里\(C^{\verb|total|}* {\verb|inner,parameterized|}\)是参数化内表索引扫描的整体代价，
• 在本例中：\( \verb|total_cost|=(0.01+0.3625)× 5000 + 73.0 = 1935.5\)
• 而运行代价为：\( \verb|run_cost| = 1935.5-0.285=1935.215\)
• 如上所示，索引嵌套扫描的整体代价是\(O(N_{\verb|outer|})\)。

1. 使用外表索引扫描的嵌套循环连接

   testdb=# SET enable_hashjoin TO off;
   SET
   testdb=# SET enable_mergejoin TO off;
   SET
   testdb=# EXPLAIN SELECT * FROM tbl_c AS c, tbl_b AS b WHERE c.id = b.id AND c.id = 500;
                                      QUERY PLAN           
   -------------------------------------------------------------------------------
    Nested Loop  (cost=0.29..93.81 rows=1 width=16)
      ->  Index Scan using tbl_c_pkey on tbl_c c  (cost=0.29..8.30 rows=1 width=8)
            Index Cond: (id = 500)
      ->  Seq Scan on tbl_b b  (cost=0.00..85.50 rows=1 width=8)
            Filter: (id = 500)
   (5 rows)
   

2. 使用外表索引扫描的物化嵌套循环连接

   testdb=# SET enable_hashjoin TO off;
   SET
   testdb=# SET enable_mergejoin TO off;
   SET
   testdb=# EXPLAIN SELECT * FROM tbl_c AS c, tbl_b AS b WHERE c.id = b.id AND c.id < 40 AND b.id < 10;
                                      QUERY PLAN            
   -------------------------------------------------------------------------------
    Nested Loop  (cost=0.29..99.76 rows=1 width=16)
      Join Filter: (c.id = b.id)
      ->  Index Scan using tbl_c_pkey on tbl_c c  (cost=0.29..8.97 rows=39 width=8)
            Index Cond: (id < 40)
      ->  Materialize  (cost=0.00..85.55 rows=9 width=8)
            ->  Seq Scan on tbl_b b  (cost=0.00..85.50 rows=9 width=8)
                  Filter: (id < 10)
   (7 rows)
   

3. 使用外表索引扫描的索引嵌套循环连接

   testdb=# SET enable_hashjoin TO off;
   SET
   testdb=# SET enable_mergejoin TO off;
   SET
   testdb=# EXPLAIN SELECT * FROM tbl_a AS a, tbl_d AS d WHERE a.id = d.id AND a.id <  40;
                                      QUERY PLAN            
   -------------------------------------------------------------------------------
    Nested Loop  (cost=0.57..173.06 rows=20 width=16)
      ->  Index Scan using tbl_a_pkey on tbl_a a  (cost=0.29..8.97 rows=39 width=8)
            Index Cond: (id < 40)
      ->  Index Scan using tbl_d_pkey on tbl_d d  (cost=0.28..4.20 rows=1 width=8)
            Index Cond: (id = a.id)
   (5 rows)
   

# EXPLAIN SELECT * FROM tbl_a AS a, tbl_b AS b WHERE a.id = b.id AND b.id < 1000;
                               QUERY PLAN
-------------------------------------------------------------------------
 Merge Join  (cost=944.71..984.71 rows=1000 width=16)
   Merge Cond: (a.id = b.id)
   ->  Sort  (cost=809.39..834.39 rows=10000 width=8)
         Sort Key: a.id
         ->  Seq Scan on tbl_a a  (cost=0.00..145.00 rows=10000 width=8)
   ->  Sort  (cost=135.33..137.83 rows=1000 width=8)
         Sort Key: b.id
         ->  Seq Scan on tbl_b b  (cost=0.00..85.50 rows=1000 width=8)
               Filter: (id < 1000)
(9 rows)

• 第9行：执行器对内表tbl_b进行排序，使用顺序扫描（第11行）。
• 第6行：执行器对外表tbl_a进行排序，使用顺序扫描（第8行）。
• 第4行：执行器执行归并连接操作，外表是排好序的tbl_a，内表是排好序的tbl_b。

testdb=# EXPLAIN SELECT * FROM tbl_a AS a, tbl_b AS b WHERE a.id = b.id;
                                    QUERY PLAN                         
---------------------------------------------------------------------------------
 Merge Join  (cost=10466.08..10578.58 rows=5000 width=2064)
   Merge Cond: (a.id = b.id)
   ->  Sort  (cost=6708.39..6733.39 rows=10000 width=1032)
         Sort Key: a.id
         ->  Seq Scan on tbl_a a  (cost=0.00..1529.00 rows=10000 width=1032)
   ->  Materialize  (cost=3757.69..3782.69 rows=5000 width=1032)
         ->  Sort  (cost=3757.69..3770.19 rows=5000 width=1032)
               Sort Key: b.id
               ->  Seq Scan on tbl_b b  (cost=0.00..1193.00 rows=5000 width=1032)
(9 rows)

• 第10行：执行器对内表tbl_b进行排序，使用顺序扫描（第12行）。
• 第9行：执行器对tbl_b排好序的结果进行物化。
• 第6行：执行器对外表tbl_a进行排序，使用顺序扫描（第8行）。
• 第4行：执行器执行归并连接操作，外表是排好序的tbl_a，内表是物化的排好序的tbl_b。

1. 使用外表索引扫描的归并连接

   testdb=# SET enable_hashjoin TO off;
   SET
   testdb=# SET enable_nestloop TO off;
   SET
   testdb=# EXPLAIN SELECT * FROM tbl_c AS c, tbl_b AS b WHERE c.id = b.id AND b.id < 1000;
                                         QUERY PLAN              
   ------------------------------------------------------------------------------
    Merge Join  (cost=135.61..322.11 rows=1000 width=16)
      Merge Cond: (c.id = b.id)
      ->  Index Scan using tbl_c_pkey on tbl_c c  (cost=0.29..318.29 rows=10000 width=8)
      ->  Sort  (cost=135.33..137.83 rows=1000 width=8)
            Sort Key: b.id
            ->  Seq Scan on tbl_b b  (cost=0.00..85.50 rows=1000 width=8)
                  Filter: (id < 1000)
   (7 rows)
   

2. 使用外表索引扫描的物化归并连接

   testdb=# SET enable_hashjoin TO off;
   SET
   testdb=# SET enable_nestloop TO off;
   SET
   testdb=# EXPLAIN SELECT * FROM tbl_c AS c, tbl_b AS b WHERE c.id = b.id AND b.id < 4500;
                                         QUERY PLAN              
   -------------------------------------------------------------------------------
    Merge Join  (cost=421.84..672.09 rows=4500 width=16)
      Merge Cond: (c.id = b.id)
      ->  Index Scan using tbl_c_pkey on tbl_c c  (cost=0.29..318.29 rows=10000 width=8)
      ->  Materialize  (cost=421.55..444.05 rows=4500 width=8)
            ->  Sort  (cost=421.55..432.80 rows=4500 width=8)
                  Sort Key: b.id
                  ->  Seq Scan on tbl_b b  (cost=0.00..85.50 rows=4500 width=8)
                        Filter: (id < 4500)
   (8 rows)
   

3. 使用外表索引扫描的索引归并连接

   testdb=# SET enable_hashjoin TO off;
   SET
   testdb=# SET enable_nestloop TO off;
   SET
   testdb=# EXPLAIN SELECT * FROM tbl_c AS c, tbl_d AS d WHERE c.id = d.id AND d.id < 1000;
                                         QUERY PLAN              
   -------------------------------------------------------------------------------
    Merge Join  (cost=0.57..226.07 rows=1000 width=16)
      Merge Cond: (c.id = d.id)
      ->  Index Scan using tbl_c_pkey on tbl_c c  (cost=0.29..318.29 rows=10000 width=8)
      ->  Index Scan using tbl_d_pkey on tbl_d d  (cost=0.28..41.78 rows=1000 width=8)
            Index Cond: (id < 1000)
   (5 rows)
   

SELECT * FROM tbl_outer AS outer, tbl_inner AS inner WHERE inner.attr1 = outer.attr2;

1. 在工作内存上创建一个处理批次。 在本例中，处理批次有八个桶；即桶的数量是2的3次方。
2. 将内表的第一个元组插入批次的相应的桶中。 具体过程如下：
   1. 找出元组中涉及连接条件的属性，计算其散列键。 在本例中，因为WHERE子句是inner.attr1 = outer.attr2，因此内置的散列函数会对第一条元组的属性attr1取散列值，用作散列键。
   2. 将第一条元组插入散列键相应的桶中。 假设第一条元组的散列键以二进制记法表示为0x000 ... 001，即其末三位（bit） 为001。 在这种情况下，该元组会被插入到键为001的桶中。 在本文中，构建处理批次的插入操作会用运算符 ⊕ 表示。
3. 插入内表中的其余元组。 图3.24. 内存散列连接的探测阶段
4. 依外表的第一条元组进行探测。 详情如下：
   1. 找出第一条外表元组中涉及连接条件的属性，计算其散列键。 在这个例子中，假设第一条元组的属性attr2的散列键是0x000 ... 100，即其末三位（bit） 为100。 最后三位是100。
   2. 将外表中第一条元组与批次中的内表元组进行比较。如果满足连接条件，则连接内外表元组。 因为第一个元组的散列键的末三位为100，执行器找出键为100的桶中的所有内表元组，并对内外表元组两侧相应的属性进行比较。这些属性由连接条件（在WHERE子句中）所指明。 如果满足连接条件，执行器会连接外表中的第一条元组与内表中的相应元组。如果不满足则执行器不做任何事情。 在本例中，键为100的桶中有Tuple_C。如果Tuple_C的attr1等于第一条元组（Tuple_W）的attr2，则Tuple_C和Tuple_W将被连接，并保存至内存或临时文件中。 在本文中，处理批次的探测操作用运算符 ⊗ 表示。
5. 依次对外表中的其他元组执行探测。

SELECT * FROM customers AS c, purchase_history AS h 
WHERE c.name = h.customer_name;

1. 在工作内存中创建一个处理批次，以及一个倾斜批次。
2. 创建处理批次相应的临时文件，用于存储排好序的内表元组。 在本例中，内表被分割为四个批次，因此创建了三个批次文件。
3. 为内表的第一条元组执行构建操作。 细节如下：
   1. 如果第一条元组应当插入倾斜批次中，则将其插入倾斜批次；否则继续下一步。 在该例中，如果第一条元组属于前10％的客户，则将其插入到倾斜批次中。
   2. 计算第一条元组的散列键，然后将其插入相应的处理批次。
4. 对内表其余元组依次执行构建操作。 图3.27 混合散列连接，探测阶段第一轮
5. 创建临时处理批次文件，用于外表排序。
6. 为外表的第一条元组执行探测操作，如果外表第一条元组上相应字段取值为MCV，则在倾斜批次上进行探测，否则进行第七步。 在本例中，如果第一条元组是前10％客户的购买数据，则它会与倾斜批次中的内表元组进行比较。
7. 为外表的第一条元组执行探测操作。 操作的内容取决于该元组散列键的取值。如果该元组属于Batch_0则直接完成探测操作；否则将其插入相应的外表处理批次中。
8. 为外表的其余元组执行探测操作。 注意在本例中，外表中70％的元组已经在第一轮中的倾斜批次中处理了。 图3.28 构建阶段与探测阶段，第二轮
9. 移除倾斜批次与Batch_0，为下一轮处理批次腾地方。
10. 为批次文件batch_1_in中的内表元组执行构建操作。
11. 为批次文件batch_1_out中的外表元组依次执行探测操作。 图3.29 构建阶段与探测阶段，第三轮及后续
12. 为批次文件batch_2_in与batch_2_out执行构建操作与探测操作。
13. 为批次文件batch_3_in与batch_3_out执行构建操作与探测操作。

typedef JoinPath NestPath;
typedef enum JoinType
{
        /* 根据SQL JOIN语法确定的标准连接种类，解析器只允许输出这几种取值。
         * (例如JoinExpr节点) */
        JOIN_INNER,           /* 仅包含匹配的元组对 */
        JOIN_LEFT,            /* 匹配元组对 + 未匹配的左表元组 */
        JOIN_FULL,            /* 匹配元组对 + 未匹配的左右表元组  */
        JOIN_RIGHT,           /* 匹配元组对 + 未匹配的右表元组  */
        /* 关系理论中的半连接(semijoin)与否定半连接(anti-semijoin)并没有用SQL JOIN
         * 语法来表示，而是用另一种风格标准来表示(举个例子，EXISTS)。计划器会认出这些情景
         * 并将其转换为连接。因此计划器与执行器必须支持这几种取值。注意：对于JOIN_SEMI的
         * 输出而言，连接到哪一条右表元组是不确定的。而对于JOIN_ANTI的输出而言，会保证使用
         * 空值进行行扩展。*/
        JOIN_SEMI,            /* 左表元组的一份拷贝，如果该元组有相应匹配 */
        JOIN_ANTI,            /* 右表元组的一份拷贝，如果该元组有相应匹配 */
        /* 这几种代码用于计划器内部，执行器并不支持。(其实大多数时候计划器也不会用)   */
        JOIN_UNIQUE_OUTER,    /* 左表路径必须是UNIQUE的 */
        JOIN_UNIQUE_INNER     /* 右表路径必须是UNIQUE的 */
} JoinType;
typedef struct JoinPath
{
    Path       path;
    JoinType   jointype;
    Path       *outerjoinpath;        /* 连接外表一侧的路径 */
    Path       *innerjoinpath;        /* 连接内表一侧的路径 */
    List       *joinrestrictinfo;    /* 连接所适用的限制信息 */
    /* 参考RelOptInfo与ParamPathInfo才能理解为什么JoinPath需要有joinrestrictinfo
     * 且不能合并到RelOptInfo中。 */
} JoinPath;
typedef struct MergePath
{
    JoinPath   jpath;
    List       *path_mergeclauses;    /* 归并所需的连接子句 */
    List       *outersortkeys;        /* 用于外表显式排序的键，如果存在 */
    List       *innersortkeys;        /* 用于内表显式排序的键，如果存在 */
    bool       materialize_inner;    /* 为内表执行物化过程? */
} MergePath;

/* ----------------
 *        连接节点
 *
 * jointype:    连接左右子树元组的规则
 * joinqual:    来自 JOIN/ON 或 JOIN/USING 的连接限定条件
 *                (plan.qual 包含了来自WHERE子句的条件)
 *
 * 当jointype为INNER时，joinqual 与 plan.qual 在语义上可以互换。对于OUTER而言这两者
 * 则无法互换；只有joinqual会被用于匹配判定，以及是否需要生成空值扩展的元组。
 * (但 plan.qual 仍然会在实际返回一条元组前生效。)
 * 对于外连接而言，只有joinquals能被用于归并连接或散列连接的连接条件。
 * ----------------
 */
typedef struct Join
{
    Plan        plan;
    JoinType    jointype;
    List        *joinqual;    /* 连接条件 (除 plan.qual 外) */
} Join;
/* ----------------
 *        嵌套循环连接节点
 * 
 * nestParams的列表标识出了执行器所需的参数，这些参数从外表子计划中的当前行获取，
 * 并传入内表子计划中用于执行。当前我们限制这些值为简单的Vars，但也许某一天这一限制
 * 会放松。（注意在创建执行计划期间，paramval实际上可能是一个PlaceHolderVar表达式；
 * 但当其进入执行器时，它必须转换为varno为OUTER_VAR的Var。）
 * ----------------*/
typedef struct NestLoop
{
    Join       join;
    List       *nestParams;   /* NestLoopParam 节点的列表*/
} NestLoop;
typedef struct NestLoopParam
{
    NodeTag   type;
    int       paramno;        /* 需要配置的PARAM_EXEC参数数量 */
    Var       *paramval;      /* 需要赋值给Param的外表变量 */
} NestLoopParam;
/* ----------------
 *        归并连接节点
 * 
 * 待归并列上期待的顺序是通过一个btree运算符族的OID，一个排序规则的OID，一个方向字段
 * （BTLessStrategyNumber 或 * BTGreaterStrategyNumber)，以及一个 NULL FIRST
 * 标记位描述的。注意归并语句的两侧可能是不同的数据类型，但它们会按照共同的运算符族与排序
 * 规则，以同样的方式排序。每个归并子句中的算子必须为相应运算符族中的等值运算。
 * ---------------- */
typedef struct MergeJoin
{
    Join    join;
    List    *mergeclauses;        /* mergeclauses 是一颗表达式树 */
    /* 这些字段都是数组，但与mergeclauses列表有着同样的长度： */
    Oid     *mergeFamilies;      /* B树运算符族的OID列表，每条子句一个 */
    Oid     *mergeCollations;    /* 排序规则的OID列表，每条子句一个 */
    int     *mergeStrategies;    /* 顺序(ASC 或 DESC)的列表，每条子句一个 */
    bool    *mergeNullsFirst;    /* 空值顺序，每条子句一个  */
} MergeJoin;
/* ----------------
 *        散列连接节点
 * ---------------- */
typedef struct HashJoin
{
    Join    join;
    List    *hashclauses;
} HashJoin;