3.4执行器如何工作
单表查询的例子，执行器从计划树取出计划节点，按照自底向上方的顺序进行处理，并调取节点相应的函数。这些函数在src/backend/executor目录中。如执行顺序扫描的函数(seqscan)定义在nodeSeqscan.c中，索引扫描(IndexScanNode)在nodeIndexScan.cSortNode节点对应的排序函数在nodeSort.c中。
mydb=# \d tb1_1
Table "public.tb1_1"
Column | Type | Collation | Nullable | Default
--------+---------+-----------+----------+---------
id | integer | | |
data | integer | | |
mydb=# explain select * from tb1_1 where id <300 order by data;
QUERY PLAN
---------------------------------------------------------------
4.Sort (cost=182.34..183.09 rows=300 width=8)
5. Sort Key: data
6. -> Seq Scan on tb1_1 (cost=0.00..170.00 rows=300 width=8)
7. Filter: (id < 300)
8. (4 rows)
--第六行,执行器通过函数执行顺序扫描
--第四行，通过nodeSort.c中定义的函数对顺序扫描的结果进行拍照
执行器处理查询时会使用工作内存和临时缓冲区，都在内存中分配。如果无法在内存完成，就会用临时文件，走磁盘
--可以通过以下命令实际执行，查看
explain analyze select id,data from tb1_25m order by id;
--如果因内存不足，生成临时文件，在base/pg_tmp子目录中。命名规则：
--"pgsql_tmp"+创建文本文件的Postgres进程的PID.{从0开始的序列号}
3.5连接
pg支持三种连接操作，分别是嵌套巡回连接、并归连接和散列连接
环境准备：
mydb=# select version();
version
---------------------------------------------------------------------------------------------------------
PostgreSQL 10.4 on x86_64-pc-linux-gnu, compiled by gcc (GCC) 4.4.7 20120313 (Red Hat 4.4.7-18), 64-bit
(1 row)
--创建表
create table tb1_a(id int primary key,data int);
create table tb1_b(id int primary key,data int);
--插入数据
insert into tb1_a select generate_series(1,10000),generate_series(1,10000);
insert into tb1_b select generate_series(1,10000),generate_series(1,10000);
嵌套循环(Nested Loop)
--下述语句默认先走hash，再走merge，所以先关闭
set enable_hashjoin=off;
set enable_mergejoin=off;
mydb=# select name,setting from pg_settings where name like '%join%' or name like '%loop%';
name | setting
---------------------+---------
enable_hashjoin | off
enable_mergejoin | off
enable_nestloop | on
join_collapse_limit | 8
(4 rows)
--查看执行计划,物化操作没有启动成本，其他有
mydb=# explain select * from tb1_a as a, tb1_b as b where a.data=b.data;
QUERY PLAN
-----------------------------------------------------------------------
4. Nested Loop (cost=0.00..375158.50 rows=5000 width=16)
5. Join Filter: (a.data = b.data)
6. -> Seq Scan on tb1_a a (cost=0.00..73.00 rows=5000 width=8)
7. -> Materialize (cost=0.00..98.00 rows=5000 width=8)
8. -> Seq Scan on tb1_b b (cost=0.00..73.00 rows=5000 width=8)
(5 rows)
第七行 执行器使用顺序扫描，物化内部表tb1_b；
第四行，执行执行嵌套顺序连接操作，外表是tb1_a,内表是物化的tb1_b.
物化节点意味着在执行上层节点之前，将树中其下方任何内容的输出（可以是扫描，或者是完整的联接之类的东西）存储到内存中。通常，当外部节点需要出于某种原因可以重新扫描的源时，便可以执行此操作。
其他，如果再外表上存在一个与连接条件相关的索引，那么在外表上也可以以索引扫描代替顺序扫描。特别是当where子句中的访问谓词可以使用该索引时，能缩小外表上的搜索范围，嵌套循环连接的代价可能会急剧减少。如：
mydb=# explain select * from tb1_a as a, tb1_b as b where a.id=b.data and a.id=100;
QUERY PLAN
--------------------------------------------------------------------------------
Nested Loop (cost=0.28..93.81 rows=1 width=16)
-> Index Scan using tb1_a_pkey on tb1_a a (cost=0.28..8.30 rows=1 width=8)
Index Cond: (id = 100)
-> Seq Scan on tb1_b b (cost=0.00..85.50 rows=1 width=8)
Filter: (data = 100)
(5 rows)
归并连接(merge join)
与嵌套连接不同， 归并连接只能用于自然连接和等值连接
set enable_mergejoin=on;
mydb=# explain select * from tb1_a as a,tb1_b as b where a.data=b.data and b.data<1000;
QUERY PLAN
-----------------------------------------------------------------------
4. Merge Join (cost=515.52..555.52 rows=1000 width=16)
5. Merge Cond: (a.data = b.data)
6. -> Sort (cost=380.19..392.69 rows=5000 width=8)
7. Sort Key: a.data
8. -> Seq Scan on tb1_a a (cost=0.00..73.00 rows=5000 width=8)
9. -> Sort (cost=135.33..137.83 rows=1000 width=8)
10 Sort Key: b.data
-> Seq Scan on tb1_b b (cost=0.00..85.50 rows=1000 width=8)
Filter: (data < 1000)
(9 rows)
--9行 执行器对内表tb1_b进行顺序扫描
--6行，对外表tb1_a进行顺序扫描
--4行，执行器归并连接操作，内外表都是排好序的
其他如外表相关列创建索引，内表相关列创建索引等。物化归并连接与普通归并连接基本无差异，区别在Materialize，对tb1_b排好序的结果进行物化。
散列连接（Hash join）
只能用于自然连接和等值连接
PostgreSQL中的散列连接的行为因表的大小而异。如果目标表足够小（确切地说，内表大小不超过工作内存的25%），那么散列连接就是简单的两阶段内存散列连接，否则将会使用带倾斜批次的混合散列连接。
内存散列连接
内存中的散列连接是在work_mem中处理的，在PostgreSQL中，散列表区域被称作处理批次。一个处理批次会有多个散列槽，内部称其为桶，桶的数量由nodeHash.c 中定义的ExecChooseHashTableSize()函数所确定。桶的数量总是2的整数次幂。
内存散列连接有两个阶段，分别是构建阶段和探测阶段。在构建阶段，内表中的所有元组都会被插入到处理批次中；在探测阶段，每条外表元组都会与处理批次中的内表元组比较，如果满足连接条件，则将两条元组连接起来。
带倾斜的混合散列连接
当内表的元组无法全部存储在工作内存中的单个处理批次时，PostgreSQL使用带倾斜批次的混合散列连接算法，该算法是混合散列连接的一种变体。
在第一个构建和探测阶段，PostgreSQL准备多个批次。与桶的数目类似，处理批次的数目由函数ExecChooseHashTableSize()决定，也就是2的整数次幂。工作内存中只会分配一个处理批次，而其他批次都以临时文件的形式创建。属于这些批次的元组将通过临时元组存储功能被写入到相应的文件中.
连接访问路径与连接节点
嵌套循环连接的访问路径由 JoinPath 结构表示，其他连接访问路径，诸如MergePath与HashPath都基于其实现。
如图3.30（page73)
连接节点
本节列出了三种连接节点，分别是NestedLoopNode、MergeJoinNode和HashJoinNode，它们都基于JoinNode实现.
#/pgdata/pgsql/include/postgresql/server/nodes/plannodes.h
/* ----------------
* Join node
*
* jointype: rule for joining tuples from left and right subtrees
* inner_unique each outer tuple can match to no more than one inner tuple
* joinqual: qual conditions that came from JOIN/ON or JOIN/USING
* (plan.qual contains conditions that came from WHERE)
*
* When jointype is INNER, joinqual and plan.qual are semantically
* interchangeable. For OUTER jointypes, the two are *not* interchangeable;
* only joinqual is used to determine whether a match has been found for
* the purpose of deciding whether to generate null-extended tuples.
* (But plan.qual is still applied before actually returning a tuple.)
* For an outer join, only joinquals are allowed to be used as the merge
* or hash condition of a merge or hash join.
*
* inner_unique is set if the joinquals are such that no more than one inner
* tuple could match any given outer tuple. This allows the executor to
* skip searching for additional matches. (This must be provable from just
* the joinquals, ignoring plan.qual, due to where the executor tests it.)
* ----------------
*/
typedef struct Join
{
Plan plan;
JoinType jointype;
bool inner_unique;
List *joinqual; /* JOIN quals (in addition to plan.qual) */
} Join;
/* ----------------
* nest loop join node
*
* The nestParams list identifies any executor Params that must be passed
* into execution of the inner subplan carrying values from the current row
* of the outer subplan. Currently we restrict these values to be simple
* Vars, but perhaps someday that'd be worth relaxing. (Note: during plan
* creation, the paramval can actually be a PlaceHolderVar expression; but it
* must be a Var with varno OUTER_VAR by the time it gets to the executor.)
* ----------------
*/
typedef struct NestLoop
{
Join join;
List *nestParams; /* list of NestLoopParam nodes */
} NestLoop;
typedef struct NestLoopParam
{
NodeTag type;
int paramno; /* number of the PARAM_EXEC Param to set */
Var *paramval; /* outer-relation Var to assign to Param */
} NestLoopParam;
/* ----------------
* merge join node
*
* The expected ordering of each mergeable column is described by a btree
* opfamily OID, a collation OID, a direction (BTLessStrategyNumber or
* BTGreaterStrategyNumber) and a nulls-first flag. Note that the two sides
* of each mergeclause may be of different datatypes, but they are ordered the
* same way according to the common opfamily and collation. The operator in
* each mergeclause must be an equality operator of the indicated opfamily.
* ----------------
*/
typedef struct MergeJoin
{
Join join;
bool skip_mark_restore; /* Can we skip mark/restore calls? */
List *mergeclauses; /* mergeclauses as expression trees */
/* these are arrays, but have the same length as the mergeclauses list: */
Oid *mergeFamilies; /* per-clause OIDs of btree opfamilies */
Oid *mergeCollations; /* per-clause OIDs of collations */
int *mergeStrategies; /* per-clause ordering (ASC or DESC) */
bool *mergeNullsFirst; /* per-clause nulls ordering */
} MergeJoin;
/* ----------------
* hash join node
* ----------------
*/
typedef struct HashJoin
{
Join join;
List *hashclauses;
} HashJoin;
- 如果联接的一侧只有很少的行，则首选嵌套循环联接。如果联接条件不使用相等运算符，则嵌套循环联接也将用作唯一选项。
- 哈希联接如果联接条件使用相等运算符并且联接的两端都很大并且哈希适合work_mem，则首选哈希联接。
- 合并联接如果联接条件使用相等运算符并且联接的两端都很大，则首选，但可以有效地对联接条件进行排序(例如，如果联接列中使用的表达式上有索引) )。
3.6创建多表查询计划树
预处理由planner.c中定义的subquery_planner()函数执行。
【上拉查询】如果FROM子句带有一个子查询，且该子查询没有用到GROUP BY、HAVING、ORDER BY、LIMIT和DISTINCT、INTERSECT或EXCEPT，那么计划器就会使用pull_up_subqueries()函数将其转换为连接形式。例如下面一个 FROM 子句含子查询的查询就可以被转换为自然连接查询。自不必说，这种转换是在查询树上进行的。
【获取代价最小的路径】
为了获取最佳计划树，计划器必须考虑各个索引与各种连接方法之间的所有可能组合。如果表的数量小于12张，计划器可以使用动态规划来获取最佳计划，否则计划器会使用遗传算法。
以下是使用动态规划确定最佳计划树的过程：
- 第一层：获得每张表上代价最小的路径，其存储在表相应的RelOptInfo结构中
- 第二层：所有表中选择两种表，为每种组合找出代价最低的路径
- 第三层及其后：继续进行同样处理，直到层级等于表数量
本节英文版