PostgreSQL优化器解析

引言

优化器的好坏是衡量一个数据库的重要标准，PostgreSQL作为最先进的开源数据库，优化器的能力也是相当卓越的。

SQL的执行过程

当一条SQL进来之后，可以看到会经过Parser → Analyzer → Rewriter → Planner → Executor这一系列步骤。若是DDL语句，无需进行优化，到utility模块处理，对于DML则需要按照完整的流程。

另外就是我们所熟知的绑定变量，类似于把执行计划缓存起来，下次执行的时候免去parser 这些阶段，提升速度，相较于Oracle，PostgreSQL有一个五次机制

当前5次执行时，每次都会根据实际传入的实际绑定变量新生成执行计划进行执行，即每次都是硬解析，同时会记录这5次的执行计划；

当第6次开始执行时，会生成一个通用的执行计划（generic plan），同时与前5次的执行计划进行比较，如果比较的结果是通用执行计划不比前5次的执行计划差，以后就会固定把这个通用的执行计划固定下来，这之后即使传入的值发生变化后，执行计划也不再变化。这就相当于Oracle打开了绑定变量窥视的功能。

当然，当第6次开始执行时，如果通用的执行计划（generic plan）比前5次的某一个执行计划差，则以后则每次都重新生成执行计划，即以后永远都是硬解析了。

Figure-4-prepared-statement-flow-in-Postgres

postgres=# select command_tag,message from postgres_log ;
command_tag | message
PARSE | PARSER STATISTICS
PARSE | PARSE ANALYSIS STATISTICS
PARSE | REWRITER STATISTICS
BIND  | PLANNER STATISTICS
SELECT | execute : SELECT * FROM test WHERE a = $1
PARSE | PARSER STATISTICS
PARSE | PARSE ANALYSIS STATISTICS
PARSE | REWRITER STATISTICS
BIND  | PLANNER STATISTICS
SELECT | execute : SELECT * FROM test WHERE a = $1
PARSE | PARSER STATISTICS
PARSE | PARSE ANALYSIS STATISTICS
PARSE | REWRITER STATISTICS
BIND  | PLANNER STATISTICS
SELECT | execute S_1: SELECT * FROM test WHERE a = $1   ---跳过了parse rewriter阶段
BIND  | PLANNER STATISTICS
SELECT | execute S_1: SELECT * FROM test WHERE a = $1

Parser

第一阶段是parser阶段，对于数据库来说，传入的SQL语句不过是一串"文本"，PostgreSQL并不知晓这一串文本是什么意思，因此我们需要告诉数据库该如何理解这一串文本，之后SQL语句就会被转化为内部结构，即语法解析树（parser tree）。

首先需要做的就是词法分析，在大学的时候想必各位也学过《编译原理》。词法分析就是将SQL语句做一个切割，切割成一个个词条（token）进行归类，比如是否是关键字、标识符、常量、运算符、逻辑符等

词法分析就像刀削面的过程，拿着一段字符串（面条）一端不断下刀，当面条被切完也就完成了词法分析，所以词法分析是 字符串转化为一堆字符段的过程。

比如SQL的Token可以大致分为这么几类

• 注释。
• 关键字（SELECT、CREATE、DELETE）。
• 操作符（+、-、>=）。
• 开闭合标志（(、CASE）。
• 占位符（?）。
• 空格。
• 引号包裹的文本、数字、字段。
• 方言语法（${variable}）。

词法分析的定义在scan.l中，比如下面定义了空格、换行

/*
 * In order to make the world safe for Windows and Mac clients as well as
 * Unix ones, we accept either \n or \r as a newline.  A DOS-style \r\n
 * sequence will be seen as two successive newlines, but that doesn't cause
 * any problems.  Comments that start with -- and extend to the next
 * newline are treated as equivalent to a single whitespace character.
 *
 * NOTE a fine point: if there is no newline following --, we will absorb
 * everything to the end of the input as a comment.  This is correct.  Older
 * versions of Postgres failed to recognize -- as a comment if the input
 * did not end with a newline.
 *
 * XXX perhaps \f (formfeed) should be treated as a newline as well?
 *
 * XXX if you change the set of whitespace characters, fix scanner_isspace()
 * to agree.
 */

space     [ \t\n\r\f]
horiz_space  [ \t\f]
newline    [\n\r]
non_newline  [^\n\r]

comment    ("--"{non_newline}*)

whitespace  ({space}+|{comment})

这里定义了数据类型

/* we no longer allow unary minus in numbers.
 * instead we pass it separately to parser. there it gets
 * coerced via doNegate() -- Leon aug 20 1999
 *
 * {decimalfail} is used because we would like "1..10" to lex as 1, dot_dot, 10.
 *
 * {realfail1} and {realfail2} are added to prevent the need for scanner
 * backup when the {real} rule fails to match completely.
 */

integer    {digit}+
decimal    (({digit}*\.{digit}+)|({digit}+\.{digit}*))
decimalfail  {digit}+\.\.
real     ({integer}|{decimal})[Ee][-+]?{digit}+
realfail1   ({integer}|{decimal})[Ee]
realfail2   ({integer}|{decimal})[Ee][-+]

param     \${integer}

other     .

接着就是进行语法分析了，语法分析的任务是在词法分析的结果上将Tokens组合成各类语法短句，组织成有含义的短语和句子，正如在英语翻译中的语法。

组成的短句会与既定的语法规则进行匹配，语法分析的定义在gram.y中，该文件由一组语法规则以及在触发规则时执行的操作所组成，在gram.y文件里定义了所有的SQL语言的语法规则，若匹配成功则生成对应的抽象语法树（Abstract Syntax Tree，AST），否则报语法错误。

此处就定义了stmt的语法树，支持的标准SQL语法

/*
 * toplevel_stmt includes BEGIN and END.  stmt does not include them, because
 * those words have different meanings in function bodys.
 */
toplevel_stmt:
   stmt
   | TransactionStmtLegacy
  ;

stmt:
   AlterEventTrigStmt
   | AlterCollationStmt
   | AlterDatabaseStmt
   | AlterDatabaseSetStmt
   | AlterDefaultPrivilegesStmt
   | AlterDomainStmt
   | AlterEnumStmt
   | AlterExtensionStmt
   | AlterExtensionContentsStmt
   | AlterFdwStmt
   | AlterForeignServerStmt
   | AlterFunctionStmt
   | AlterGroupStmt
   | AlterObjectDependsStmt
   | AlterObjectSchemaStmt
   | AlterOwnerStmt
   | AlterOperatorStmt
   | AlterTypeStmt
   | AlterPolicyStmt
   | AlterSeqStmt
   | AlterSystemStmt
   | AlterTableStmt
   | AlterTblSpcStmt

词法分析和语法分析器是使用标准工具bison和Flex实现的，Flex将文件scan.l转化为C源文件scan.c，源码文件为gram.y通过Bison编译生成 gram.c。

注意Parser阶段生成语法解析树（parse tree）时只会检查语法，只有当SQL中出现语法错误时才会报错，而并不会检查表是否存在等，这一过程交由下一阶段分析器（analyzer）进行处理。

The parser does not check the semantics of an input query. For example, even if the query contains a table name that does not exist, the parser does not return an error. Semantic checks are done by the analyzer/analyser.

我们可以打开debug_print_parse参数，在日志中观察生成的parse tree

Fig. 3.2. An example of a parse tree.

Analyzer

经过词法分析和语法分析之后，便是语义分析，语义分析的任务是对语法解析得到的语法树（AST）进行有效性审查，即是否能否正确执行，比如表是否存在，列是否存在等。

假设现在有这样一个查询：select id from test where id > 4，语义分析阶段会做下面的检查

1. 检查SQL中的表test是否存在
2. 检查id列是否是from子句某个表或视图的属性
3. 检查id列是否是from子句某个关系或视图的属性且id列的类型是否能进行>4的比较操作
4. 检查用户是否有访问这些对象的权限

另外此时生成的解析树（parse tree）还和SQL语句息息相关，比如解析树中保存的还是一个表的名字，一个列的名字，但实际上在PostgreSQL数据库中对象的信息都是存放在系统表system catalog中，比如pg_class用来记录数据库对象的一些基础元信息，pg_attribute用来记录列的元信息等。

当我们创建一个表的时候，会在pg_class、pg_attribute等系统表中插入新的元数据，因此这时我们还需要用这些元数据的信息取代语法树中表的名字、列的名字、操作符的OID等等。

经过语义分析阶段之后，便产生出了一颗查询树（query tree），查询树的定义在parsenodes.h中。

Fig. 3.3. An example of a query tree.

Rewriter

这一步骤是基于规则系统，重写器（rewriter）会根据存储在pg_rule中的规则对查询树进行相应的转化。假如SQL还涉及到视图的话，会将视图进行展开，转化成具体的基表。

比如有这样一个视图

sampledb=# CREATE VIEW employees_list 
sampledb-#      AS SELECT e.id, e.name, d.name AS department 
sampledb-#            FROM employees AS e, departments AS d WHERE e.department_id = d.id;

然后查询视图

sampledb=# SELECT * FROM employees_list;

这一阶段，重写器会将视图进行展开

Fig. 3.4. An example of the rewriter stage.

假如还定义有其他的规则，也会在这一阶段进行处理和转化。

Planner

当重写完成之后，优化器（planner）便会基于查询树生成一颗能被执行器（executor）高效执行的计划树（plan tree），优化器会经过一系列复杂的逻辑优化和物理优化，最终产生一颗最优的计划树，计划树也就是我们所熟知的执行计划。优化器的好坏直接决定了一个数据库面对复杂语句的处理能力。

说白了，逻辑优化就是尽量对SQL进行等价或者推倒变换，以达到更有效率的执行计划。

逻辑优化主要包括查询重写、子查询提升、表达式预处理、外连接消除、谓词下推、连接顺序交换、等价类推理、条件化简和语义优化等。

逻辑优化

SQL的组成

首先了解一下SQL的组成。SQL的语法顺序是

1. SELECT[DISTINCT]
2. FROM
3. WHERE
4. GROUP BY
5. HAVING
6. UNION
7. ORDER BY

查询重写

查询重写主要目的是为了将视图展开，消除规则等。这个例子可以看到，PostgreSQL自动将视图展开了。

postgres=# create view myview as select test1.id1,test1.info1,test2.id2,test2.info2 from test1,test2;
CREATE VIEW
postgres=# explain select * from myview, test1 where myview.id1 = 2 and test1.info1 = 'hello';
                               QUERY PLAN                                
-------------------------------------------------------------------------
 Nested Loop  (cost=0.00..3.86 rows=30 width=27)
   ->  Nested Loop  (cost=0.00..2.26 rows=1 width=18)
         ->  Seq Scan on test1 test1_1  (cost=0.00..1.12 rows=1 width=9)
               Filter: (id1 = 2)
         ->  Seq Scan on test1  (cost=0.00..1.12 rows=1 width=9)
               Filter: (info1 = 'hello'::text)
   ->  Seq Scan on test2  (cost=0.00..1.30 rows=30 width=9)
(7 rows)

但是大多数时候视图展开是为了优化查询，提升性能。但是有时你会发现视图展开反而变慢了，因此我们可以告诉PostgreSQL不要做视图展开，如下我添加一个offset 0就行了，尽管两个视图的语义是一样的。

postgres=# create view myview2 as select test1.id1,test1.info1,test2.id2,test2.info2 from test1,test2 offset 0;  ---语义是一样的
CREATE VIEW
postgres=# explain select * from myview2, test1 where myview2.id1 = 2 and test1.info1 = 'hello';
                                      QUERY PLAN                                      
--------------------------------------------------------------------------------------
 Nested Loop  (cost=0.00..11.06 rows=1 width=27)
   ->  Subquery Scan on myview2  (cost=0.00..9.93 rows=1 width=18)    ---视图未展开
         Filter: (myview2.id1 = 2)
         ->  Nested Loop  (cost=0.00..6.18 rows=300 width=18)
               ->  Seq Scan on test2  (cost=0.00..1.30 rows=30 width=9)
               ->  Materialize  (cost=0.00..1.15 rows=10 width=9)
                     ->  Seq Scan on test1 test1_1  (cost=0.00..1.10 rows=10 width=9)
   ->  Seq Scan on test1  (cost=0.00..1.12 rows=1 width=9)
         Filter: (info1 = 'hello'::text)
(9 rows)

The PostgreSQL community did not dare to optimize this case of having an OFFSET 0 in a view. People are simply not supposed to do that. We will use this just as an example to observe how some operations can cripple performance and that we, as developers, should be aware of the underlying optimization process. However, if you happen to know how PostgreSQL works, this trick can be used as optimization.

常量折叠

可以看到，在此例中，PostgreSQL将谓词id = 3 + 2转化成了 id = 5，这样便可以使用到索引了。

第二个例子证明，换了个写法，就得使用顺序扫描了，因此这也是为什么会要求尽量确保过滤条件位于右侧的原因。

postgres=# create table t1(id int);
CREATE TABLE
postgres=# insert into t1 values(generate_series(1,10000));
INSERT 0 10000
postgres=# create index t1_idx on t1(id);
CREATE INDEX
postgres=# analyze t1;
ANALYZE
postgres=# explain select id from t1 where id = 3 + 2;    ---进行了推理
                              QUERY PLAN                              
----------------------------------------------------------------------
 Index Only Scan using t1_idx on t1  (cost=0.29..8.30 rows=1 width=4)
   Index Cond: (id = 5)
(2 rows)

postgres=# explain select id from t1 where id -3 = 2;     ---推理失败
                     QUERY PLAN                      
-----------------------------------------------------
 Seq Scan on t1  (cost=0.00..195.00 rows=50 width=4)
   Filter: ((id - 3) = 2)
(2 rows)

目前PostgreSQL的推理并没有那么智能，有很多限制才可以进行推理。更多细节可以去看下《PgSQL · 源码分析 · 优化器逻辑推理》

1. 约束中包含的表达式的操作符必须是B-tree-indexable operators(或者is null, or , is not null)，也就是可以被btree索引用于检索操作符，例如<,<=,=,>,>=以及<> (<>不能直接被索引使用，但是可以转换为< OR >来使用索引)；
2. SQL语句where字句中提供的表达式，同样操作符必须是B-tree-indexable operators；
3. SQL语句where字句中提供的表达式，操作符左侧的操作数必须与约束中的操作数完全一致。

postgres=# create table tt1(id int check (id is null));
CREATE TABLE
postgres=# explain select id from tt1 where id is not null;
                QUERY PLAN                
------------------------------------------
 Result  (cost=0.00..0.00 rows=0 width=0)
   One-Time Filter: false
(2 rows)

postgres=# explain select id from tt1 where id is null;
                     QUERY PLAN                      
-----------------------------------------------------
 Seq Scan on tt1  (cost=0.00..35.50 rows=13 width=4)
   Filter: (id IS NULL)
(2 rows)

-- WHERE中必须包含mod(id,4)表达式，并且由于mod是immutable函数，mod(1,4)可以转换为常数，因此以下SQL相当于 
-- explain select * from tt2 where mod(id,4)=1 and id=1; 这样才可以被逻辑推理。
postgres=# create table tt2( id int check(mod(id,4) = 0));
CREATE TABLE
postgres=# explain select * from tt2 where mod(id,4)=mod(1,4) and id=1;   ---推理成功
                QUERY PLAN                
------------------------------------------
 Result  (cost=0.00..0.00 rows=0 width=0)
   One-Time Filter: false
(2 rows)

postgres=# explain select * from tt2 where id=1;              ---推理失败
                     QUERY PLAN                      
-----------------------------------------------------
 Seq Scan on tt2  (cost=0.00..41.88 rows=13 width=4)
   Filter: (id = 1)
(2 rows)

子查询展平

postgres=# explain SELECT *
         FROM (SELECT *
               FROM generate_series(1, 10) AS x
              ) AS v1
        ORDER BY x DESC;
                                 QUERY PLAN                                  
-----------------------------------------------------------------------------
 Sort  (cost=0.27..0.29 rows=10 width=4)
   Sort Key: x.x DESC
   ->  Function Scan on generate_series x  (cost=0.00..0.10 rows=10 width=4)
(3 rows)

postgres=# explain select * from generate_series(1,10) as x order by x desc;  ---子查询进行了展平
                                 QUERY PLAN                                  
-----------------------------------------------------------------------------
 Sort  (cost=0.27..0.29 rows=10 width=4)
   Sort Key: x DESC
   ->  Function Scan on generate_series x  (cost=0.00..0.10 rows=10 width=4)
(3 rows)

子查询提升

子查询提升允许优化器做更好的优化，也可以更方便优化父查询

postgres=# create table tbl1(id int);
CREATE TABLE
postgres=# create table tbl2(id int);
CREATE TABLE
postgres=# insert into tbl1 values(generate_series(1,10));
INSERT 0 10
postgres=# insert into tbl2 values(generate_series(1,10));
INSERT 0 10
postgres=# analyze ;
ANALYZE
postgres=# explain select * from tbl1,(select * from tbl2) as a where tbl1.id = a.id;
                           QUERY PLAN                            
-----------------------------------------------------------------
 Hash Join  (cost=1.23..2.46 rows=10 width=8)
   Hash Cond: (tbl1.id = tbl2.id)
   ->  Seq Scan on tbl1  (cost=0.00..1.10 rows=10 width=4)
   ->  Hash  (cost=1.10..1.10 rows=10 width=4)
         ->  Seq Scan on tbl2  (cost=0.00..1.10 rows=10 width=4)
(5 rows)

postgres=# explain select * from tbl1,tbl2 where tbl1.id = tbl2.id;   ---两个执行计划等价，说明PostgreSQL自动做了转化
                           QUERY PLAN                            
-----------------------------------------------------------------
 Hash Join  (cost=1.23..2.46 rows=10 width=8)
   Hash Cond: (tbl1.id = tbl2.id)
   ->  Seq Scan on tbl1  (cost=0.00..1.10 rows=10 width=4)
   ->  Hash  (cost=1.10..1.10 rows=10 width=4)
         ->  Seq Scan on tbl2  (cost=0.00..1.10 rows=10 width=4)
(5 rows)

子查询提升也有限制的地方

1. 没有集合操作
2. 没有聚合操作
3. 不包含sort/limit/with/group
4. 没有易失函数
5. from非空

postgres=# explain select * from tbl1,(select * from tbl2 limit 1) as a where tbl1.id = a.id;
                              QUERY PLAN                               
-----------------------------------------------------------------------
 Hash Join  (cost=0.13..1.28 rows=1 width=8)
   Hash Cond: (tbl1.id = tbl2.id)
   ->  Seq Scan on tbl1  (cost=0.00..1.10 rows=10 width=4)
   ->  Hash  (cost=0.12..0.12 rows=1 width=4)
         ->  Limit  (cost=0.00..0.11 rows=1 width=4)
               ->  Seq Scan on tbl2  (cost=0.00..1.10 rows=10 width=4)
(6 rows)

postgres=# explain select * from tbl1,tbl2 where tbl1.id = tbl2.id limit 1;
                              QUERY PLAN                               
-----------------------------------------------------------------------
 Limit  (cost=0.00..0.37 rows=1 width=8)
   ->  Nested Loop  (cost=0.00..3.73 rows=10 width=8)
         Join Filter: (tbl1.id = tbl2.id)
         ->  Seq Scan on tbl1  (cost=0.00..1.10 rows=10 width=4)
         ->  Materialize  (cost=0.00..1.15 rows=10 width=4)
               ->  Seq Scan on tbl2  (cost=0.00..1.10 rows=10 width=4)
(6 rows)

外连接消除

以left join为例，left join(左连接) 返回包括左表中的所有记录和右表中连接字段相等的记录 ，如果右表没有匹配的记录，那么右表将会以NULL值代替，因此假如我们显式对右表指定了not null的话，PostgreSQL便会消除外连接。

postgres=# explain select * from tbl1 left join tbl2 on tbl1.id = tbl2.id;
                           QUERY PLAN                            
-----------------------------------------------------------------
 Hash Left Join  (cost=1.23..2.46 rows=10 width=8)
   Hash Cond: (tbl1.id = tbl2.id)
   ->  Seq Scan on tbl1  (cost=0.00..1.10 rows=10 width=4)
   ->  Hash  (cost=1.10..1.10 rows=10 width=4)
         ->  Seq Scan on tbl2  (cost=0.00..1.10 rows=10 width=4)
(5 rows)

postgres=# explain select * from tbl1 left join tbl2 on tbl1.id = tbl2.id where tbl2.id is not null;  ---消除了left join
                           QUERY PLAN                            
-----------------------------------------------------------------
 Hash Join  (cost=1.23..2.46 rows=10 width=8)
   Hash Cond: (tbl1.id = tbl2.id)
   ->  Seq Scan on tbl1  (cost=0.00..1.10 rows=10 width=4)
   ->  Hash  (cost=1.10..1.10 rows=10 width=4)
         ->  Seq Scan on tbl2  (cost=0.00..1.10 rows=10 width=4)
               Filter: (id IS NOT NULL)
(6 rows)

postgres=# explain select * from tbl1 inner join tbl2 on tbl1.id = tbl2.id where tbl2.id is not null;  ---inner join
                           QUERY PLAN                            
-----------------------------------------------------------------
 Hash Join  (cost=1.23..2.46 rows=10 width=8)
   Hash Cond: (tbl1.id = tbl2.id)
   ->  Seq Scan on tbl1  (cost=0.00..1.10 rows=10 width=4)
   ->  Hash  (cost=1.10..1.10 rows=10 width=4)
         ->  Seq Scan on tbl2  (cost=0.00..1.10 rows=10 width=4)
               Filter: (id IS NOT NULL)
(6 rows)

postgres=# explain select * from tbl1 left join tbl2 on tbl1.id = tbl2.id where tbl2.id is null;
                           QUERY PLAN                            
-----------------------------------------------------------------
 Hash Anti Join  (cost=1.23..2.36 rows=1 width=8)
   Hash Cond: (tbl1.id = tbl2.id)
   ->  Seq Scan on tbl1  (cost=0.00..1.10 rows=10 width=4)
   ->  Hash  (cost=1.10..1.10 rows=10 width=4)
         ->  Seq Scan on tbl2  (cost=0.00..1.10 rows=10 width=4)
(5 rows)

order by优化

索引是有序的（Btree），那么对于某些需要排序的操作，PostgreSQL便会自动进行转化，消除order by。

postgres=# explain select id from t1 order by id;
                                 QUERY PLAN                                 
----------------------------------------------------------------------------
 Index Only Scan using t1_idx on t1  (cost=0.29..270.29 rows=10000 width=4)
(1 row) 

类似的，还有Merge join，Merge join要求对表先排序再连接。

因为demo2上面已经创建了索引，因此无需再添加一个额外辅助节点Sort，而demo1则需要，因此这也是为什么会建议在排序列上创建索引。

postgres=# create table demo1(id int, id2 int);
CREATE TABLE
postgres=# insert into demo1 values(generate_series(1,1000), generate_series(1,1000));
INSERT 0 1000
postgres=# create table demo2(id int, id2 int);
CREATE TABLE
postgres=# create index demoidx2 on demo2(id);
CREATE INDEX
postgres=# insert into demo2 values(generate_series(1,100000), generate_series(1,100000));
INSERT 0 100000
postgres=# analyze;
ANALYZE
postgres=# explain select * from demo1, demo2 where demo1.id=demo2.id;
                                  QUERY PLAN
------------------------------------------------------------------------------------
 Merge Join  (cost=65.18..109.82 rows=1000 width=16)
   Merge Cond: (demo2.id = demo1.id)
   ->  Index Scan using demoidx2 on demo2  (cost=0.29..3050.29 rows=100000 width=8)
   ->  Sort  (cost=64.83..67.33 rows=1000 width=8)
      Sort Key: demo1.id
      ->  Seq Scan on demo1  (cost=0.00..15.00 rows=1000 width=8)
(6 rows)

连接精简

postgres=# CREATE TABLE x (id int, PRIMARY KEY (id));
CREATE TABLE
postgres=# CREATE TABLE y (id int, PRIMARY KEY (id));
CREATE TABLE
postgres=# explain select * from x left join y on x.id = y.id where x.id = 3;
                                QUERY PLAN                                 
---------------------------------------------------------------------------
 Nested Loop Left Join  (cost=0.31..16.36 rows=1 width=8)
   Join Filter: (x.id = y.id)
   ->  Index Only Scan using x_pkey on x  (cost=0.15..8.17 rows=1 width=4)
         Index Cond: (id = 3)
   ->  Index Only Scan using y_pkey on y  (cost=0.15..8.17 rows=1 width=4)
         Index Cond: (id = 3)
(6 rows)

稍微改一下只查询左表的列x.*，可以看到PostgreSQL自动优化了，只扫描了x表。

如果我们不需要从连接右侧获取数据，并且连接右侧是唯一的，就可能会发生连接精简，如下我删除了y表的主键，可以看到PostgreSQL并没有做连接精简。

postgres=# explain select x.* from x left join y on x.id = y.id where x.id = 3;
                             QUERY PLAN                              
---------------------------------------------------------------------
 Index Only Scan using x_pkey on x  (cost=0.15..8.17 rows=1 width=4)
   Index Cond: (id = 3)
(2 rows)

postgres=# CREATE TABLE y (id int);
CREATE TABLE
postgres=# analyze ;
ANALYZE
postgres=# explain select * from x left join y on x.id = y.id where x.id = 3;
                       QUERY PLAN                        
---------------------------------------------------------
 Nested Loop Left Join  (cost=0.00..0.01 rows=1 width=8)
   Join Filter: (x.id = y.id)
   ->  Seq Scan on x  (cost=0.00..0.00 rows=1 width=4)
         Filter: (id = 3)
   ->  Seq Scan on y  (cost=0.00..0.00 rows=1 width=4)
         Filter: (id = 3)
(6 rows)

postgres=# explain select x.* from x left join y on x.id = y.id where x.id = 3;    ---并没有连接精简
                       QUERY PLAN                        
---------------------------------------------------------
 Nested Loop Left Join  (cost=0.00..0.01 rows=1 width=4)
   Join Filter: (x.id = y.id)
   ->  Seq Scan on x  (cost=0.00..0.00 rows=1 width=4)
         Filter: (id = 3)
   ->  Seq Scan on y  (cost=0.00..0.00 rows=1 width=4)
         Filter: (id = 3)
(6 rows)

隐式连接

如下三条语句是相同的，优化器会以同样的办法处理。第一条语句是隐式连接，最后一个由显式连接组成。在内部，优化器会检查这些请求，对连接重新排序以获得最佳的运行时间。但问题是：有多少显式连接会修改成隐式的？可以修改join_collapse_limit来告诉优化器。

SELECT * FROM tab1, tab2, tab3
    WHERE tab1.id = tab2.id
    AND tab2.ref = tab3.id;
SELECT * FROM tab1 CROSS JOIN tab2
    CROSS JOIN tab3
    WHERE tab1.id = tab2.id
    AND tab2.ref = tab3.id;
SELECT * FROM tab1 JOIN (tab2 JOIN tab3
    ON (tab2.ref = tab3.id))
    ON (tab1.id = tab2.id);

见如下样例，类似的参数还有from_collapse_limit，用于控制多少个子查询可以展开

postgres=# EXPLAIN WITH x AS
(
SELECT * FROM generate_series(1, 1000) AS id
)
SELECT *
FROM x AS a
JOIN x AS b ON (a.id = b.id)
JOIN x AS c ON (b.id = c.id)
JOIN x AS d ON (c.id = d.id)
JOIN x AS e ON (d.id = e.id)
JOIN x AS f ON (e.id = f.id);
                                        QUERY PLAN                                         
-------------------------------------------------------------------------------------------
 Merge Join  (cost=428.98..48286.48 rows=3125000 width=24)
   Merge Cond: (a.id = d.id)
   CTE x
     ->  Function Scan on generate_series id  (cost=0.00..10.00 rows=1000 width=4)
   ->  Merge Join  (cost=209.49..669.49 rows=25000 width=12)
         Merge Cond: (c.id = a.id)
         ->  Sort  (cost=69.83..72.33 rows=1000 width=4)
               Sort Key: c.id
               ->  CTE Scan on x c  (cost=0.00..20.00 rows=1000 width=4)
         ->  Materialize  (cost=139.66..232.16 rows=5000 width=8)
               ->  Merge Join  (cost=139.66..219.66 rows=5000 width=8)
                     Merge Cond: (a.id = b.id)
                     ->  Sort  (cost=69.83..72.33 rows=1000 width=4)
                           Sort Key: a.id
                           ->  CTE Scan on x a  (cost=0.00..20.00 rows=1000 width=4)
                     ->  Sort  (cost=69.83..72.33 rows=1000 width=4)
                           Sort Key: b.id
                           ->  CTE Scan on x b  (cost=0.00..20.00 rows=1000 width=4)
   ->  Materialize  (cost=209.49..731.99 rows=25000 width=12)
         ->  Merge Join  (cost=209.49..669.49 rows=25000 width=12)
               Merge Cond: (f.id = d.id)
               ->  Sort  (cost=69.83..72.33 rows=1000 width=4)
                     Sort Key: f.id
                     ->  CTE Scan on x f  (cost=0.00..20.00 rows=1000 width=4)
               ->  Materialize  (cost=139.66..232.16 rows=5000 width=8)
                     ->  Merge Join  (cost=139.66..219.66 rows=5000 width=8)
                           Merge Cond: (d.id = e.id)
                           ->  Sort  (cost=69.83..72.33 rows=1000 width=4)
                                 Sort Key: d.id
                                 ->  CTE Scan on x d  (cost=0.00..20.00 rows=1000 width=4)
                           ->  Sort  (cost=69.83..72.33 rows=1000 width=4)
                                 Sort Key: e.id
                                 ->  CTE Scan on x e  (cost=0.00..20.00 rows=1000 width=4)
(33 rows)

postgres=# set join_collapse_limit to 3;    ---由默认的8修改为3之后，可以看到cost也由48286上涨至了57236
SET
postgres=# EXPLAIN WITH x AS
(
SELECT * FROM generate_series(1, 1000) AS id
)
SELECT *
FROM x AS a
JOIN x AS b ON (a.id = b.id)
JOIN x AS c ON (b.id = c.id)
JOIN x AS d ON (c.id = d.id)
JOIN x AS e ON (d.id = e.id)
JOIN x AS f ON (e.id = f.id);
                                              QUERY PLAN                                               
-------------------------------------------------------------------------------------------------------
 Merge Join  (cost=428.98..57236.48 rows=3125000 width=24)
   Merge Cond: (f.id = a.id)
   CTE x
     ->  Function Scan on generate_series id  (cost=0.00..10.00 rows=1000 width=4)
   ->  Sort  (cost=69.83..72.33 rows=1000 width=4)
         Sort Key: f.id
         ->  CTE Scan on x f  (cost=0.00..20.00 rows=1000 width=4)
   ->  Materialize  (cost=349.14..11839.14 rows=625000 width=20)
         ->  Merge Join  (cost=349.14..10276.64 rows=625000 width=20)
               Merge Cond: (d.id = a.id)
               ->  Merge Join  (cost=139.66..219.66 rows=5000 width=8)
                     Merge Cond: (d.id = e.id)
                     ->  Sort  (cost=69.83..72.33 rows=1000 width=4)
                           Sort Key: d.id
                           ->  CTE Scan on x d  (cost=0.00..20.00 rows=1000 width=4)
                     ->  Sort  (cost=69.83..72.33 rows=1000 width=4)
                           Sort Key: e.id
                           ->  CTE Scan on x e  (cost=0.00..20.00 rows=1000 width=4)
               ->  Materialize  (cost=209.49..731.99 rows=25000 width=12)
                     ->  Merge Join  (cost=209.49..669.49 rows=25000 width=12)
                           Merge Cond: (c.id = a.id)
                           ->  Sort  (cost=69.83..72.33 rows=1000 width=4)
                                 Sort Key: c.id
                                 ->  CTE Scan on x c  (cost=0.00..20.00 rows=1000 width=4)
                           ->  Materialize  (cost=139.66..232.16 rows=5000 width=8)
                                 ->  Merge Join  (cost=139.66..219.66 rows=5000 width=8)
                                       Merge Cond: (a.id = b.id)
                                       ->  Sort  (cost=69.83..72.33 rows=1000 width=4)
                                             Sort Key: a.id
                                             ->  CTE Scan on x a  (cost=0.00..20.00 rows=1000 width=4)
                                       ->  Sort  (cost=69.83..72.33 rows=1000 width=4)
                                             Sort Key: b.id
                                             ->  CTE Scan on x b  (cost=0.00..20.00 rows=1000 width=4)
(33 rows)

谓词下推

这个很好理解，就是为了连接之前的元组数量尽可能少。

postgres=# explain select * from test1,test2 where id1 < 5 and id2 > 50;
                        QUERY PLAN                         
-----------------------------------------------------------
 Nested Loop  (cost=0.00..2.53 rows=3 width=18)
   ->  Seq Scan on test2  (cost=0.00..1.38 rows=1 width=9)
         Filter: (id2 > 50)
   ->  Seq Scan on test1  (cost=0.00..1.12 rows=3 width=9)
         Filter: (id1 < 5)
(5 rows)

语义优化

典型案例便是在分区表的场景下，在10以前的版本中，分区表是基于触发器/规则 + 继承实现的，分区裁剪要用到constraint_exclusion参数。这个参数有三个选项 "off、on、partition"，默认参数为 off，意思不使用表上的 constraint 来生成计划，如果设置成 on，则对所有表生效，生成 PLAN 时会考虑表上的约束。设置成partition，则只对分区表生效，从而避免扫描分区表所有分区。比如某个表上存在check id > 100的约束，那么查询select id from test < 90时，优化器对比约束条件，知道压根没有小于90的记录，直接跳过对于该表的扫描，返回0行记录。当优化器使用约束排除时，需要花费更多的时间去对比约束条件和where中的过滤条件，默认是partition，对一张表做查询时，如果有继承表，优化器就会对这些子表进行约束排除分析。

见如下例子，当我设置为on了之后，那么对于普通的表也可以进行约束排除检查，发现表内压根没有小于25的数据，直接就返回false了。

postgres=# create table t2(id int check(id > 30));
CREATE TABLE
postgres=# insert into t2 values(generate_series(35,50));
INSERT 0 16
postgres=# analyze t2;
ANALYZE
postgres=# explain select * from t2 where id < 25;
                    QUERY PLAN                    
--------------------------------------------------
 Seq Scan on t2  (cost=0.00..1.20 rows=1 width=4)
   Filter: (id < 25)
(2 rows)

postgres=# set constraint_exclusion to "on";
SET
postgres=# explain select * from t2 where id < 25;
                QUERY PLAN                
------------------------------------------
 Result  (cost=0.00..0.00 rows=0 width=0)
   One-Time Filter: false
(2 rows)

当然无法进行推理的，还是得全表扫描

postgres=# explain select * from t2 where id <> 100;
                    QUERY PLAN                     
---------------------------------------------------
 Seq Scan on t2  (cost=0.00..1.20 rows=15 width=4)
   Filter: (id <> 100)
(2 rows)

MIN/MAX优化

可以看到，MIN和MAX也被转化了，转化成了select id from t1 where id is not null order by id limit 1;因为最小值就是排序列中非NULL的第一个值，最大值是非NULL的最后一个值，PostgreSQL也自动做了优化。

postgres=# explain select min(id) from t1;
                                     QUERY PLAN                                      
-------------------------------------------------------------------------------------
 Result  (cost=0.32..0.33 rows=1 width=4)
   InitPlan 1 (returns $0)
     ->  Limit  (cost=0.29..0.32 rows=1 width=4)
           ->  Index Scan using t1_idx on t1  (cost=0.29..343.29 rows=10000 width=4)
                 Index Cond: (id IS NOT NULL)
(5 rows)

postgres=# explain select max(id) from t1;
                                          QUERY PLAN                                          
----------------------------------------------------------------------------------------------
 Result  (cost=0.32..0.33 rows=1 width=4)
   InitPlan 1 (returns $0)
     ->  Limit  (cost=0.29..0.32 rows=1 width=4)
           ->  Index Scan Backward using t1_idx on t1  (cost=0.29..343.29 rows=10000 width=4)
                 Index Cond: (id IS NOT NULL)
(5 rows)

假如没有索引，那就得全表扫描了

postgres=# begin;
BEGIN
postgres=*# drop index t1_idx ;
DROP INDEX
postgres=*# explain select min(id) from t1;
                          QUERY PLAN                          
--------------------------------------------------------------
 Aggregate  (cost=170.00..170.01 rows=1 width=4)
   ->  Seq Scan on t1  (cost=0.00..145.00 rows=10000 width=4)
(2 rows)

distinct/group by优化

HashAggregate的工作方式是构建数据的哈希表，以便对它们进行分组。因此，如果聚合发生在未排序的数据集上，那么HashAggregate可以被组级聚合使用。GroupAggregate用于处理已经排好序的数据，因此不需要任何额外的数据结构。GroupAggregate可以被组级聚合使用，如果聚合是在排序数据集上。为了对已排序的数据进行分组，它可以显式排序(通过添加sort节点)，也可以对通过索引获取的数据进行隐式排序。

比如下面第一个例子，distinct就被优化为了HashAggregate，因为等效于先分组，然后分别从每个组中获取一个值。

postgres=# explain select distinct(id) from demo1;
                       QUERY PLAN
---------------------------------------------------------------
 HashAggregate  (cost=17.50..27.50 rows=1000 width=4)
   Group Key: id
   ->  Seq Scan on demo1  (cost=0.00..15.00 rows=1000 width=4)
(3 rows)

postgres=# explain select distinct(id) from demo2 where id<100;
                                 QUERY PLAN
-----------------------------------------------------------------------------------
 Unique  (cost=0.29..10.27 rows=99 width=4)
   ->  Index Only Scan using demoidx2 on demo2  (cost=0.29..10.03 rows=99 width=4)
      Index Cond: (id < 100)
(3 rows)

同理，假如GroupAggregate列上已经有索引了，那么就可以不进行排序

postgres=# explain select count(*) from demo2 group by id2;
                            QUERY PLAN
-------------------------------------------------------------------------
 GroupAggregate  (cost=9747.82..11497.82 rows=100000 width=12)
   Group Key: id2
   ->  Sort  (cost=9747.82..9997.82 rows=100000 width=4)
      Sort Key: id2
      ->  Seq Scan on demo2  (cost=0.00..1443.00 rows=100000 width=4)
(5 rows)

postgres=# create index idx1 on demo1(id);
CREATE INDEX
postgres=# explain select sum(id2), id from demo1 where id=1 group by id;   ---不用额外的Sort节点
                            QUERY PLAN
------------------------------------------------------------------------
 GroupAggregate  (cost=0.28..8.31 rows=1 width=12)
   Group Key: id
   ->  Index Scan using idx1 on demo1  (cost=0.28..8.29 rows=1 width=8)
      Index Cond: (id = 1)
(4 rows)

postgres=# explain select sum(id), id2 from demo1 where id=1 group by id2;  ---按照id2进行分组，因此需要一个额外的Sort节点
                               QUERY PLAN
------------------------------------------------------------------------------
 GroupAggregate  (cost=8.30..8.32 rows=1 width=12)
   Group Key: id2
   ->  Sort  (cost=8.30..8.31 rows=1 width=8)
      Sort Key: id2
      ->  Index Scan using idx1 on demo1  (cost=0.28..8.29 rows=1 width=8)
            Index Cond: (id = 1)
(6 rows)

Union加速

函数内联

函数内联的思想是尽可能减少函数调用，从而加快查询速度。

postgres=# create or replace function myfunc(v_id int)returns int 
as $$
select abs(v_id);
$$ language sql;
CREATE FUNCTION
postgres=# explain select * from generate_series(1,10) as x where myfunc(x) = 5;
                              QUERY PLAN                              
----------------------------------------------------------------------
 Function Scan on generate_series x  (cost=0.00..0.15 rows=1 width=4)
   Filter: (abs(x) = 5)
(2 rows)

可以看到，myfunc函数已经被替换成了abs。不过函数内联仅适用于SQL函数，其他语言的函数不行，并且你的SQL得简单。

postgres=# create or replace function myfunc(v_id int)returns int 
as $$
declare
 ret int;
begin
 select abs(v_id) into ret;
end;
$$ language plpgsql;
CREATE FUNCTION
postgres=# explain select * from generate_series(1,10) as x where myfunc(x) = 5;
                              QUERY PLAN                              
----------------------------------------------------------------------
 Function Scan on generate_series x  (cost=0.00..2.63 rows=1 width=4)
   Filter: (myfunc(x) = 5)
(2 rows)

函数三态

Oracle中的函数创建时可以指定DETERMINISTIC，确定性函数，确定性函数的性能好处是如果使用相同的输入调用函数两次，Oracle可以缓存第一个调用的结果，避免重复调用。在PostgreSQL里面，就是函数稳定性，分为三态，默认是volatile，还有immustable和stable，这三个值用来告诉优化器当函数执行完毕后得到的结果是否可以缓存下来以供下次使用。

在实际工作中，可能还会用到函数索引（表达式索引），在创建函数索引中可能也会遇到类似错误：error: functions in index expression must be marked immutable。

函数的三态会影响数据库的一些行为：

• 绑定变量，immutable函数(包含常量参数或不包含参数时)计算一次。stable函数每次bind的时候要重算
• 生成执行计划，stable、immutable函数作为where条件时可以被用于索引am，即允许采用索引优化
• 排除分区表不需要访问的分区，stable、immutable函数作为where条件时可用于过滤不需要访问的子表
• 是否可用于创建索引，只有immutable函数或操作符可以用于创建表达式索引
• 对数据的修改的可见性分两种情况。volatile , 调用该函数的SQL对数据的修改可见；stable、immutable , 调用该函数的SQL对数据的修改, 不可见.

见如下样例：

postgres=# create or replace function f_test() returns int as $$  
declare  
begin  
  return 5;  
end;  
$$ language plpgsql volatile;
CREATE FUNCTION
postgres=# explain select id from t1 where id < f_test();
                       QUERY PLAN                       
--------------------------------------------------------
 Seq Scan on t1  (cost=0.00..2670.00 rows=3333 width=4)
   Filter: (id < f_test())
(2 rows)
          
postgres=# alter function f_test() stable;
ALTER FUNCTION
postgres=# explain select id from t1 where id < f_test();
                              QUERY PLAN                              
----------------------------------------------------------------------
 Index Only Scan using t1_idx on t1  (cost=0.54..4.61 rows=4 width=4)
   Index Cond: (id < f_test())
(2 rows)

不难理解，为什么表达式索引必须要求是immutable的，因为得要求任何时候同一个输入都能得到相同的输出，不然不就乱套了，通过索引返回的数据会不一致。

等式约束

可以看到，id和id2两列的值一直是一样的，然后PostgreSQL自动判断出，可以使用id列上的索引。

postgres=# create table t3(id int,id2 int);
CREATE TABLE
postgres=# insert into t3 select n,n from generate_series(1,10000) as n;
INSERT 0 10000
postgres=# explain select id2 from t3 where id = id2 and id2 = 100;
                     QUERY PLAN                     
----------------------------------------------------
 Seq Scan on t3  (cost=0.00..197.55 rows=1 width=4)
   Filter: ((id = 100) AND (id2 = 100))
(2 rows)

postgres=# create index t3_idx on t3(id);
CREATE INDEX
postgres=# analyze t3;
ANALYZE
postgres=# explain select id2 from t3 where id = id2 and id2 = 100;
                           QUERY PLAN                            
-----------------------------------------------------------------
 Index Scan using t3_idx on t3  (cost=0.29..8.30 rows=1 width=4)
   Index Cond: (id = 100)
   Filter: (id2 = 100)
(3 rows)

其实这是PostgreSQL做的条件化简，如下第二条，自动将 id = id2 and id2 = 100转化成了 id = 100 and id2 = 100，这样便可以使用id列上的索引了。假如没有这个逻辑，优化器是无法使用id列上的索引进行索引扫描的。

规则	优化前	优化后
常量折叠	a=1+2	a=3
常量传递	a1=a2 and a2=100	a1=100 and a2=100
括号冗余	(a and b) and (c and d)	a and b and c and d
简化or	false or a>1	a> 1

类似的，PostgreSQL也能自动简化or

postgres=# explain select id from t3 where 1>2 or id = 100 ;
                              QUERY PLAN                              
----------------------------------------------------------------------
 Index Only Scan using t3_idx on t3  (cost=0.29..4.30 rows=1 width=4)
   Index Cond: (id = 100)
(2 rows)

分区裁剪

分区裁剪很熟悉了，带上分区键可以只扫描部分分区。

postgres=# set enable_partition_pruning to off;
SET
postgres=# explain select * from ptab01 where tm='2020-01-07'::timestamptz;
                                          QUERY PLAN                                           
-----------------------------------------------------------------------------------------------
 Gather  (cost=1000.00..17758.00 rows=5 width=12)
   Workers Planned: 2
   ->  Parallel Append  (cost=0.00..16757.50 rows=5 width=12)
         ->  Parallel Seq Scan on ptab01_202001 ptab01_1  (cost=0.00..3417.41 rows=1 width=12)
               Filter: (tm = '2020-01-07 00:00:00+08'::timestamp with time zone)
         ->  Parallel Seq Scan on ptab01_202003 ptab01_3  (cost=0.00..3417.41 rows=1 width=12)
               Filter: (tm = '2020-01-07 00:00:00+08'::timestamp with time zone)
         ->  Parallel Seq Scan on ptab01_202005 ptab01_5  (cost=0.00..3417.41 rows=1 width=12)
               Filter: (tm = '2020-01-07 00:00:00+08'::timestamp with time zone)
         ->  Parallel Seq Scan on ptab01_202004 ptab01_4  (cost=0.00..3307.88 rows=1 width=12)
               Filter: (tm = '2020-01-07 00:00:00+08'::timestamp with time zone)
         ->  Parallel Seq Scan on ptab01_202002 ptab01_2  (cost=0.00..3197.35 rows=1 width=12)
               Filter: (tm = '2020-01-07 00:00:00+08'::timestamp with time zone)
(13 rows)

postgres=# set enable_partition_pruning to on;
SET
postgres=# explain select * from ptab01 where tm='2020-01-07'::timestamptz;
                                      QUERY PLAN                                       
---------------------------------------------------------------------------------------
 Gather  (cost=1000.00..4417.51 rows=1 width=12)
   Workers Planned: 1
   ->  Parallel Seq Scan on ptab01_202001 ptab01  (cost=0.00..3417.41 rows=1 width=12)
         Filter: (tm = '2020-01-07 00:00:00+08'::timestamp with time zone)
(4 rows)

物理优化

物理优化关注的是表的扫描方式选择、多表组合方式、多表组合顺序等。表的扫描方式包括顺序扫描、索引扫描、仅索引扫描、位图扫描、TID扫描等。

扫描方式

顺序扫描

顺序扫描，顾名思义，挨个扫描所有的行指针，然后去堆表中取数据。假如有1亿条数据，哪怕你只取1条，也要扫描所有的数据块。因此，顺序扫描需要尽可能优化。

索引扫描

索引扫描，顾名思义，根据key扫描索引获取行指针，然后去堆表中获取数据，因此索引扫描会涉及到随机IO，并不是一股脑都用索引性能就会好，默认random_page_cost就是seq_page_cost的4倍。

仅索引扫描

传统的索引扫描，由于索引中不包含版本信息，即不知道数据是否可见，因此还需要回表去判断数据的可见性，同时有可能获取的数据，索引不能全部包括，因此也需要回表。既然知晓了原理，那么仅索引扫描就呼之欲出了，假如数据全部可见（VM文件的作用）同时索引里面就包括了所有的数据，就不需要回表了。不过要注意，并不是执行计划里面显式走了index only scan就真的不会回表了，具体得看Heap Fetch的数量，感兴趣的读者可以参照我之前的文章《index only scan的误区》和《index only scan的误区续》

位图扫描

传统的索引扫描每次从索引中去取一个tuple的指针，然后立马去表中取数据，每一次会造成一次随机IO。如果数据量较多的情况下，会比较低效。而bitmap scan一次性将符合条件的tuple-pointers全部取出来，每一个数据块一个比特位，然后在内存中进行地址排序，然后去取出数据，这时的读取数据由于进行的地址排序，读取时就变成了顺序的读。其实就是一个随机读转化为顺序读取的过程，但是取出的数据由于进行了地址的排序，就没有顺序。同时，对于limit这种sql，bitmap index scan这种就不适合，因为它一次会取出所有数据。

TID扫描

这个是PostgreSQL特有的，直接根据ctid查找数据，玩得溜的话，这个特性可以帮助我们做很多骚操作。在14中，支持了TID的范围扫描，在以前仅支持等于操作，假如也要使用范围查询，可以使用ctidscan插件。

postgres=# select version();
                                                 version                                                 
---------------------------------------------------------------------------------------------------------
 PostgreSQL 14.2 on x86_64-pc-linux-gnu, compiled by gcc (GCC) 4.8.5 20150623 (Red Hat 4.8.5-44), 64-bit
(1 row)

postgres=# select * from t3 where ctid < '(0,2)';
 id | id2 
----+-----
  1 |   1
(1 row)

组合方式

也就是表的join方式。PostgreSQL支持3种join方式，nestloop、hash join和merge join

Nestloop join

NestedLoop Join是一种最简单的连接算法，每条外部关系的记录与每条内部关系的记录相匹配。Nested Loop Join(NLJ)是最常用的连接方法，它几乎可以用于任何类型、任何数据集的连接子句。由于该算法需要扫描外表和内表的所有元组，因此Nested Loop Join被认为是开销最大的连接操作。

Hash Join

hash join使用两个表中较小的表，并利用连接键在内存中建立散列表，然后扫描较大的表并探测散列表，找出与散列表匹配的行。适用于较小的表可以完全放入内存中的情况。如果表很大，不能完全放入内存，优化器会将它分割成若干不同的分区，把不能放入内存的部分写入磁盘的临时段。

Merge Join

通常情况下Hash Join的效果都比排序合并连接要好，然而如果两表已经被排过序或者有索引，在执行排序合并连接时不需要再排序了，这时Merge Join的性能会优于Hash Join。Merge join的操作通常分三步：

1. 对连接的每个表做table access full;
2. 对table access full的结果进行排序。
3. 进行merge join对排序结果进行合并。

表的组合顺序

不同的组合顺序将会产生不同的代价，想要获得最佳的组合顺序，如果枚举所有组合顺序，那么将会有N! 的排列组合，计算量对于优化器来说难以承受。数据库路径的搜索方法通常有3种类型：自底向上方法、自顶向下方法、随机方法，而PostgreSQL采用了其中的两种方法：自底向上和随机方法，其中自底向上的方法是采用动态规划方法，而随机方法采用的是遗传算法，对于连接比较少的情况使用动态规划，否则使用遗传算法。

当一个SQL涉及到的表越多，那么执行计划就越复杂。表越多，planner的选择就越多，从逻辑上讲，规划的时间就会增加，在某些时候，光是规划的过程就会耗时很久时间，以至于经典的穷举法搜索已不再可行，这个时候就需要用到遗传算法了。

Pivotal公司的开源优化器ORCA用的就是自顶向下的方法，Tidb也是。

此处引用一下PostgreSQL及其子系统介绍

自底向上，又叫动态规划，通过将原问题分解成对子问题的求解，再使用代价模型，即可在茫茫的搜索空间中，最终选出全局最优解。

• step1：当查询只能一个表时

考虑一个最简单的SQL：select * from a where id=10，应该用什么方式执行最快？

答案是代价估算：

1. 全表顺序扫描肯定可以的，估算全表扫描的代价，系统表pg_statistic保存了数据表的一些统计数据，基于这些统计数据，可以估算出大概需要扫描多少个page，从而可以估算出整体的扫描代价，索引扫描原理也大概相同，后面不再赘述。
2. 检查id列是否有索引，如果有则分别估算其代价
3. 列出有可能的搜索路径，计算其代价，最终找到一条最优路径，即得到单表的最优解

• step2：当查询有两个表时

考虑SQL：select * from a join b on (a.id=b.id) where a.id>10;

ａ表 join b表，此前，我们已经通过上面介绍的方式，得到单个表的查询最优解，现在开始考虑两个表join的最优解。

1. nested join，即循环嵌套连接，通用模式，看看join能不能用上索引，估计其代价。
2. hash join，看看能不能用上hash索引，或者把其中一个表物化成hash table，估算其代价。
3. sort merge join，对两个子表分别进行归并排序，这种连接方式在那些btree索引上非常有效，因为btree索引本身就是按顺序排列的，估算其代价。
4. 其它join方式，join方式和优化方式非常多，这里不一一列举了，把这些可能的join方式全部列出来，然后分别计划其代价
5. 然后就得到两个表join的最优解

step3：当查询有3个或以上的表时

考虑查询有三个表：(A JOIN B) JOIN C

1. 前面已经介绍了如何解决两个表最优解问题，现在已知{A B} 、{A C} 、{B C}这三种JOIN的最优解，开始求解三张表的最优解
2. 分别求解 {A B} JOIN C、{A C} JOIN B、{B C} JOIN A 这三种JOIN的代价，得到代价最小的路径
3. 得到三个表的最优解，四个以上的表如此类推....最后得到全局最优解。

遗传算法（参照ken师傅的说法）：

• 对问题进行编码，确定搜索空间的大小

• 随机初始化群体（主要是给染色体赋初始值，计算每个染色体的适应度的值，并对各个染色体的适应度排序），以及计算好进化次数

• 循环：进行N次进化

• “随机”选出两个染色体，分别是momma和daddy
• 对于momma和daddy使用“杂交”方式，求出其孩子
• 求杂交得到的kid的适应度的值
• 把kid插入群体中（如果kid的适应度比群体中最差的适应度还差，则不插入，否则，替换掉最差的那个且排好序）

• 生成了最优路径

• 根据最优的连接路径生成查询执行计划和花费估算

postgres=# show geqo_threshold ;
 geqo_threshold 
----------------
 12
(1 row)

由geqo_threshold参数控制何时使用遗传算法，默认是12。

    else
    {
        ......
        // 如果有自定义join生成算法则使用
        if (join_search_hook)
            return (*join_search_hook) (root, levels_needed, initial_rels);
        // 如果开启了遗传算法且join关系大于阈值(默认12)则使用遗传算法
        else if (enable_geqo && levels_needed >= geqo_threshold)
            return geqo(root, levels_needed, initial_rels);
        else  // 否则，使用动态规划算法
            return standard_join_search(root, levels_needed, initial_rels);
    }
}

JOIN的顺序

对于OUTER JOIN来说，JOIN顺序是固定的，所以路径数量相对较少(只需要考虑不同JOIN算法组成的路径)；然而对于INNER JOIN来说，表之间的JOIN顺序是可以不同的，这样就可以由不同的JOIN组合、不同的JOIN顺序组成非常多的不同路径。如A JOIN B JOIN C，路径有：

• (A⋈B)⋈C ：就有两种排列顺序(A JOIN B) JOIN C 和 C JOIN (A JOIN B)
• (A JOIN C) JOIN B
• A JOIN (C JOIN B)

我们可以将join_collapse_limit设置为1，这样就会强制PostgreSQL按照我们写的顺序去进行join。

PostgreSQL优化器主要考虑将执行计划树生成以下三种形式，包括左深树、右深树和紧密型树。

代价估算

参照internal db第三章和官网的Row Estimation Examples就行了，十分详细，此处不再赘述。

Executor

优化器选择了一个最优的执行计划之后，变交由Executor去执行了。

参考

PgSQL · 源码分析 · 优化器逻辑推理

Mastering PostgreSQL 11

Explaining the Postgres Query Optimizer

openGauss 语义分析

PgSQL · 源码分析 · PG优化器浅析

PostgreSQL查询优化器详解（物理优化篇）

PostgreSQL查询优化器详解（逻辑优化篇）

Introducing PostgreSQL SQL Parser

Inside the PostgreSQL Query Optimizer

PostgreSQL查询SQL的语法分析（1）——词法分析

PostgreSQL之系统对象介绍

OpenGauss SQL解析模块源码分析

精读《手写 SQL 编译器 - 词法分析》

Hacking Postgres 内核系列之一

HOW THE POSTGRESQL QUERY OPTIMIZER WORKS

数据库路径选择理论与PostgreSQL的实现

PostgreSQL及其子系统介绍