3.6 创建多表查询计划树

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查询。

基因查询优化器

当执行一个多表连接查询时，大量时间耗费在了优化查询计划上。 为了应对这种情况，PostgreSQL实现了一个有趣的功能：基因查询优化器。 这种近似算法能在合理时间内确定一个合理的计划。 因此在查询优化阶段，如果参与连接的表数量超过参数geqo_threshold指定的阈值（默认值为12），PostgreSQL将使用遗传算法来生成查询计划。

• 第一层 获得每张表上代价最小的路径，代价最小的路径存储在表相应的RelOptInfo结构中。
• 第二层 从所有表中选择两个表，为每种组合找出代价最低的路径。 举个例子，如果总共有两张表，表A与表B，则表A和B表连接的各种路径中，代价最小的那条即为最终想要的答案。在下文中，两个表的RelOptInfo记做${A,B}$。 如果有三个表，则需要获取${A,B}, {A,C},{B,C}$三种组合里各自代价最小的路径。
• 第三层及其后 继续进行同样的处理，直到层级等于表数量。

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;

• SeqScanPath(table)表示表table上的顺序扫描路径。
• Materialized -> SeqScanPath(table)表示表table上的物化顺序扫描路径。
• IndexScanPath(table,attribute)表示按表table中属性attribute上的索引扫描路径。
• ParameterizedIndexScanPath(table,attribute1,attribute2)表示表table中属性attribute1上的参数化索引路径，并使用外表上的属性attribute2参数化。

testdb=# EXPLAIN  SELECT * FROM tbl_b AS b, tbl_c AS c WHERE c.id = b.id AND b.data < 400;
                              QUERY PLAN                    
----------------------------------------------------------------------
 Hash Join  (cost=90.50..277.00 rows=400 width=16)
   Hash Cond: (c.id = b.id)
   ->  Seq Scan on tbl_c c  (cost=0.00..145.00 rows=10000 width=8)
   ->  Hash  (cost=85.50..85.50 rows=400 width=8)
         ->  Seq Scan on tbl_b b  (cost=0.00..85.50 rows=400 width=8)
               Filter: (data < 400)
(6 rows)

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} 计划器会估算这里面所有可能连接路径的代价。