3.6 创建多表查询计划树

本节将说明多表查询计划树的创建过程。

3.6.1 预处理

预处理由 planner.c 中定义的 subquery_planner()函数执行。第 3.3.1节已经描述了单表查询的预处理。本节将描述多表查询的预处理，这块内容很多，这里只挑其中一部分来讲。

1.对CTE进行计划与转换

如果存在WITH列表，计划器就会通过SS_process_ctes()函数对每个WITH查询进行处理。

2.上拉子查询

如果FROM子句带有一个子查询，且该子查询没有用到GROUP BY、HAVING、ORDER BY、LIMIT和DISTINCT、INTERSECT或EXCEPT，那么计划器就会使用pull_up_subqueries()函数将其转换为连接形式。例如下面一个 FROM 子句含子查询的查询就可以被转换为自然连接查询。自不必说，这种转换是在查询树上进行的。

    # SELECT ＊ FROM tbl_a AS a, (SELECT ＊ FROM tbl_b) as b WHERE a.id = b.id;
                            ↓
    # SELECT ＊ FROM tbl_a AS a, tbl_b as b WHERE a.id = b.id;

3.将外连接转为内连接

如果可能的话，计划器会将OUTER JOIN查询转换为INNER JOIN查询。

3.6.2 获取代价最小的路径

为了获取最佳计划树，计划器必须考虑各个索引与各种连接方法之间的所有可能组合。如果表的数量超过某个水平，该过程的代价就会因为组合爆炸而变得非常昂贵，以至于根本不可行。

幸运的是，如果表的数量小于12张，计划器可以使用动态规划来获取最佳计划，否则计划器会使用遗传算法。详情如下：

以下是使用动态规划确定最佳计划树的过程，其步骤如下：

· 第一层

获得每张表上代价最小的路径，代价最小的路径存储在表相应的RelOptInfo结构中。

· 第二层

从所有表中选择两个表，为每种组合找出代价最低的路径。

举个例子，如果共有两张表，表A与表B，则表A和表B连接的各种路径中，代价最小的那条即为最终想要的答案。在下文中，两个表的RelOptInfo记作{A,B}。

如果有三个表，则需要获取{A,B}{、 A,C}{、 B,C}三种组合里各自代价最小的路径。

· 第三层及其后

继续进行同样的处理，直到层级等于表数量。

通过这种方式，在每个层级都能解决最小代价问题的一部分，且其结果能被更高层级的计算复用，从而使代价最小的计划树能够被高效地计算出来。

图3.31展示了使用动态规划获取代价最小的访问路径的方式。

图3.31 如何使用动态规划获取代价最小的访问路径

接下来会针对下面的查询，解释计划器是如何获取代价最小的计划的。

    testdb=# \d tbl_a
        Table "public.tbl_a"
     Column |  Type   | Modifiers
    --------+---------+-----------
     id      | integer | not null
     data   | integer |
    Indexes:
        "tbl_a_pkey" PRIMARY KEY, btree (id)
    testdb=# \d tbl_b
        Table "public.tbl_b"
     Column |  Type   | Modifiers
    --------+---------+-----------
     id      | integer |
     data   | integer |

    testdb=# SELECT ＊ FROM tbl_a AS a, tbl_b AS b WHERE a.id = b.id AND b.data < 400;

3.6.2.1 第一层的处理

在第一层中，计划器会为查询中涉及的关系创建相应的RelOptInfo结构，并估计每个关系上的最小代价。在这一步中，RelOptInfo 结构会被添加至该查询对应 PlannerInfo 的simple_rel_arrey数组字段中，如图3.32所示。

图3.32 第一层处理后的PlannerInfo与RelOptInfo

表tbl_a的RelOptInfo有三条访问路径，它们被添加至RelOptInfo的路径列表中。这三条路径分别被三个指针所连接，即三个指向代价最小路径的指针，分别是启动代价最小的路径、总代价最小的路径和参数化代价最小的路径。启动代价最小的路径与总代价最小的路径含义显而易见，因此，这里只介绍参数化索引扫描代价最小的路径。

如第3.5.1.3节所述，计划器会考虑为索引嵌套循环连接使用参数化路径（极少数情况下也会用于带外表索引扫描的索引化归并连接）。参数化索引扫描代价最小的路径，就是所有参数化路径中代价最小的那个。

表tbl_b的RelOptInfo仅有顺序扫描访问路径，因为tbl_b上没有相关索引。

3.6.2.2 第二层的处理

在第二层中，计划器会在PlannerInfo的join_rel_list字段中创建一个RelOptInfo结构。然后估计所有可能连接路径的代价，并且选择代价最小的那条访问路径。RelOptInfo会将最佳访问路径作为总代价最小的路径，如图3.33所示。

表3.1～表3.3展示了本例中连接访问路径的所有组合。本例中查询的连接类型为等值连接，并对全部三种连接算法进行评估。为方便起见，这里引入了一些有关访问路径的符号：

· SeqScanPath(table)表示表table上的顺序扫描路径。

· Materialized -> SeqScanPath(table)表示表table上的物化顺序扫描路径。

图3.33 第二层处理后的PlannerInfo和RelOptInfo

· IndexScanPath(table,attribute)表示按表table中属性attribute上的索引扫描路径。

· ParameterizedIndexScanPath(table,attribute1,attribute2)表示表 table中属性attribute1上的参数化索引路径，并使用外表上的属性attribute2参数化。

表3.1 嵌套循环连接

表3.2 归并连接

表3.3 哈希连接

例如在嵌套循环连接的部分总共评估了 7条连接路径。第一条表示在外表 tbl_a 和内表tbl_b上都使用顺序扫描路径；第二条表示在外表tbl_a上使用路径顺序扫描路径，而在内表tbl_b上使用物化顺序扫描路径，诸如此类。

计划器最终从估计的连接访问路径中选择代价最小的那条，并且将其添加到RelOptInfo{tbl_a,tbl_b}的路径列表中，如图3.33所示。

在本例中，如下面EXPLAIN的结果所示，计划器选择了在内表tbl_b和外表tbl_c上进行散列连接。

    1.testdb=# EXPLAIN  SELECT ＊ FROM tbl_b AS b, tbl_c AS c WHERE c.id = b.id AND b.data < 40
    0;
    2.                                  QUERY PLAN
    3.----------------------------------------------------------------------
    4. Hash Join  (cost=90.50..277.00 rows=400 width=16)
    5.   Hash Cond: (c.id = b.id)
    6.   ->  Seq Scan on tbl_c c  (cost=0.00..145.00 rows=10000 width=8)
    7.   ->  Hash  (cost=85.50..85.50 rows=400 width=8)
    8.          ->  Seq Scan on tbl_b b  (cost=0.00..85.50 rows=400 width=8)
    9.                 Filter: (data < 400)
    10.(6 rows)

3.6.3 获取三表查询代价最小的路径

涉及三表的查询，其代价最小的路径的获取过程如下所示：

    testdb=# \d tbl_a
        Table "public.tbl_a"
     Column |  Type   | Modifiers
    --------+---------+-----------
     id      | integer |
     data   | integer |

    testdb=# \d tbl_b
        Table "public.tbl_b"

    Column |  Type   | Modifiers
   --------+---------+-----------
    id      | integer |
    data   | integer |

   testdb=# \d tbl_c
        Table "public.tbl_c"
    Column |  Type   | Modifiers
   --------+---------+-----------
    id      | integer | not null
    data   | integer |
   Indexes:
      "tbl_c_pkey" PRIMARY KEY, btree (id)

   testdb=# SELECT ＊ FROM tbl_a AS a, tbl_b AS b, tbl_c AS c
   testdb-#                   WHERE a.id = b.id AND b.id = c.id AND a.data < 40;

· 第一层

计划器估计所有表上各自开销最小的路径，并将该信息存储在表相应的 RelOptInfos 结构{tbl_a}、{tbl_b}和{tbl_c}中。

· 第二层

计划器从三个表中选出两个，列出所有组合，分别评估每种组合里代价最小的路径。然后，规划器将信息存储在组合相应的 RelOptInfos 结构{tbl_a,tbl_b}、{tbl_b,tbl_c}和{tbl_a,tbl_c}中。

· 第三层

计划器根据所有已获取的RelOptInfos，选择代价最小的路径。更确切地说，计划器会考虑三种 RelOptInfos 组合，即{tbl_a,{tbl_b,tbl_c}}、{tbl_b,{tbl_a,tbl_c}}和{tbl_c,{tbl_a,tbl_b}}，而{tbl_a,tbl_b,tbl_c}如下所示：

{tbl_a, tbl_b, tbl_c} = min({tbl_a,{tbl_b, tbl_c}},{tbl_b,{ tbl_a, tbl_c}}, {tbl_c,{ tbl_a, tbl_b}}).

计划器会估算这里面所有可能连接路径的代价。

在处理{tbl_c,{tbl_a,tbl_b}}对应的 RelOptInfo 时，计划器会估计 tbl_c 和{tbl_a,tbl_b}连接代价最小的路径。本例中{tbl_a,tbl_b}已经选定内表为tbl_a且外表为tbl_b的散列连接。如第3.6.2.2节所述，在估计时三种连接算法及其变体都会被评估，即嵌套循环连接及其变体，归并连接及其变体，散列连接及其变体。

计划器以同样的方式处理{tbl_a,{tbl_b,tbl_c}}与{tbl_b,{tbl_a,tbl_c}}对应的RelOptInfo，并最终从所有估好的路径中选择代价最小的访问路径。

该查询的EXPLAIN命令结果如下所示：

最外层的连接是索引嵌套循环连接（第5行），第13行显示了内表上的参数化索引扫描，外表则是一个散列连接的结果，该散列连接的内表是 tbl_a，外表是 tbl_b（第 7～12行）。因此，执行程序首先执行tbl_a和tbl_b上的散列连接，再执行索引嵌套循环连接。