总结一些有关PostgreSQL查询计划，查询优化的相关内容，比较基础。
sql是一种申明性(declared)语言，也就是说，它并不是一种程序。它没有其他编程语言里的流控制语言，比如while，也无法控制操作顺序，比如有名的”goto”。
sql只是描述一个结果，并非过程。
结果一致，但如果过程不同，所带来的系统消耗可谓天差地远。所以所有的RDBMS里都需要有查询优化器来获得一条执行代价最小的方式来获取期望的结果。
在PostgreSQL里，和查询优化器紧密相连的便是查询计划。
查询计划的目标主要是：
查询计划的决策包括:
- 对表的访问策略
- 顺序扫描(Sequential Scan),索引扫描(Index Scan)，位图索引扫描(Bitmap Index Scan)，仅索引扫描(Index-Only Scan)
- 表连接策略
- 表连接顺序
- 连接方法：嵌套循环(nested loop),合并连接(merge join)，哈希连接(hash join)
- 内连接，外连接；内表与外表
- 分组策略
- 简单分组，排序分组，哈希分组
查询成本参数
Postgresql里，查询计划是按照成本计算的，也就是基于成本的查询计划(cost-based plan)，其中影响成本计算的参数包括(后面括号的值为其缺省值)：
- cpu_index_tuple_cost (0.005)
- cpu_operator_cost (0.0025)
- cpu_tuple_cost (0.01)
- random_page_cost (4.0)
- seq_page_cost (1.0)
与成本计算相关的试图包括:
- pg_class
- pg_stats（pg_statistic）
- most_common_vals：最常使用的列值
- most_common_freqs：最常使用的列值的频率
- histogram_bounds：数据分布列
- n_distinct：
成本计算方法
一个查询的总代价包括读取数据的I/O代价和其他各种操作的代价之和。 I/O代价包括顺序读取数据或索引页（seq_scan_cost）和随机读取数据页（random_scan_cost）的代价，操作代价包括处理表元组（cpu_tuple_cost）、处理比较操作（cpu_operator_cost）和处理索引元组（cpu_index_tuple_cost）。
比如，如果在一个表上做全表顺序扫描，那么其代价公式为:
Cost = seq_scan_cost*relpages + cpu_tuple_cost*reltuples
如果是在一个表上做全表顺序扫描并执行过滤，则代价公式为:
Cost = seq_scan_cost*relpages + cpu_tuple_cost*reltuples + cpu_operator_cost*reltuples
对于预算要返回的行数量，其计算公式为:
rows = reltuples*估算频率
这里，估算频率通过sys_stats视图中统计的列值和出现频率计算得出
顺序扫描
顾名思义，顺序扫描就是从头到尾将扫描表的每一条记录，此时表的所有页面都要读取一遍。其代价为页面读取（relpages*seq_page_cost）+元组处理(reltuples*cpu_tuple_cost),顺序扫描在任何情况下都能使用，它不需要读取索引，因此对于表，不需要预先创建索引。
顺序扫描的基本原理如下图:
以下几种情况是顺序扫描的最佳(或不得不)使用场景:
索引扫描
索引扫描，使用索引定位到元组所在的页面，读取元组，此时只读取符合索引过滤条件的元组所在的页面和少量的索引页面。
索引扫描的基本原理如下图:
索引扫描的代价为索引页面读取+数据页面读取+元组处理。索引扫描在一个巨量表里获取较少行时能获得相当高的性能，但是不要忘记了索引扫描基本上都是随机I/O。同时索引扫描是交替读取索引和表。
仅索引扫描(in 9.2+)
这是PostgreSQL9.2以上版本才有的功能，它和索引扫描有类似的功能和有点，另外，它有时可以避免读取行记录。如果一个表修改的很多，仅索引扫描可能表现不好。而且它要求所有查询的列都在索引里。
位图索引扫描
其原理图如下：
- 在检查表之前先所秒所有的索引，构成一个元组ID(Tuples-ID,TID)的位图
- 顺序读表，可以跳跃
- 结果以物理排序返回
- 对于有多个条件的组合（AND、OR），可以分别对每个条件做Bitmap Index Scan，然后再对结果进行AND或OR操作
- 处理limit很弱
连接
连接计划
- 修复连接顺序和连接策略无疑是查询计划中最难的部分
- 随着表数量的增加，连接方式的可能性成指数级剧增
- 当搜索空间较小，查询计划差不多是做穷举搜索
- 当搜索太大，查询计划使用启发式或基因查询优化(Genetic Query Optimization,GEQO)来限制计划时间和内存使用
连接方法
当连接2个表时，可以计划用于执行表连接，每一种连接方法使用一个外表(outer)和一个内表(inner)来产生一个结果表(result).
- 嵌套循环连接(Nested loop join)
- 带内表顺序扫描
- 带内表索引扫描
- 合并连接(Merge join)
- 哈希连接(Hash join)
Nested Loop Join
当内表较小时，对于外表的每一条记录，都去扫描依次内表获得匹配，其原理图如下：
其实现的伪代码如下：
1 2 3 4 |
for(i=0;i < length(outer); i++) for(j=0; j < length(inner); j++) if (outer[i] == inner[j]) output(outer[i],inner[j]) |
如果内表很大，且有查询列都有索引，则每次外表的每一行都会通过内表的索引去匹配，如果成功，则返回匹配的行。基本原理如下图所示：
其实现的伪代码如下:
1 2 3 4 5 6 7 8 |
for(i=0; i < length(outer);i++){ index_entry =get_first_match(outer[j]) while (index_entry){ output(outer[i],inner[index_entry]); index_entry=get_next_match(index_entry) `` } } |
这里的内表或外表可以是基本表，也可以是其他连接生成的结果。该连接的代价大致和两个表大小的乘积相当，如果两个都很大的话，代价很大。所以要求整个查询返回的结果集不能太大，要把返回子集较小表的作为外表,而且在内表的连接字段上一定要有索引。
Merge Join
合并连接的要点是首先将连接的两个表进行排序(使用sort/index扫描)，然后并行扫描两个表，找出相等的值返回。其基本原理见下图：
其实现伪代码如下：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
sort(outer); sort(inner); i=0; j=0; save_j=0; while ( i < length(outer)) { if (outer[i] == inner[j]) output[outer[i],inner[j]) if (outer[i] >= inner[j] && j < length(inner)){ j++; if (outer[i] < inner[j]) save_j = j; else i++; j = save_j; } } |
合并连接只能处理相等条件连接，比如a.x = b.x这样的。根据上述原理图我们可以看出，通常情况下，一个元组只需要访问一次，但是如果外表有重复值的话，内表就需要多次扫描。比如外表是{1 2 2 3},内表是{2 2 3 4}的情况
Hash Join
和Merge join类似，Hash join也只能处理相等条件连接。首先在把内表的每一行通过hash函数进行hash，从而在内存内创建一个hash表。而后针对外表的每一行进行hash，来和内存的中的hash表进行匹配。其原理图如下：
其实现的伪代码如下：
1 2 3 4 5 6 7 8 9 10 |
for (j = 0; j < length(inner); j++) { hash_key = hash(inner[j]); append(hash_store(hash_key),inner[j]); } for (i = 0; i < length(outer); i++) { hash_key = hash(outer[i]); for (j = 0; j < length(hash_store(hash_key]); j++) if (outer[i] == hash_store[hash_key][j]) output(outer[i],inner[j]); } |
