《PostgreSQL技术内幕-查询优化深度探索》节选之《查询树》

继上次分享的

《深入剖析查询优化技术内幕之概述篇》

之后，今天继续和大家分享关于查询树部分的内容。

《PostgreSQL技术内幕-查询优化深度探索》揭示了PostgreSQL数据库中查询优化的实现技术细节，先是对子查询提升、外连接消除、表达式预处理、谓词下推、连接顺序交换、等价类推理等逻辑优化方法进行了详细的描述，而后又结合统计信息、选择率、代价对扫描路径创建、路径搜索方法、连接路径的建立、Non-SPJ路径的建立、执行计划的简化与生成等进行了深度的探索，从而使读者可以对PostgreSQL数据库的查询优化器有深层次的了解。

这本书适合于从事数据库内核开发人员及相关领域的研究人员、数据库DBA、高等院校相关专业的本科生或者研究生阅读。

有购书需求的小伙伴可以点击文章底部“阅读原文”进行购买。本文转载已经过作者授权，未经同意请勿随意转载。

查询树

一个SQL查询语句在经过了词法分析、语法分析和语义分析之后会形成一棵查询树，这棵查询树实际上就对应了一个关系代数表达式，它是查询优化器的输入，贯穿了查询优化的整个过程。所谓“工欲善其事，必先利其器”，在开始对查询优化器的代码进行分析之前，对查询树必须要有一定的了解，下面就开始分析查询树的结构，同时也介绍一下查询树涉及的其他的数据结构。

Node的结构

PostgreSQL数据库中的结构体采用了统一的形式，它们都是基于Node结构体进行的“扩展”，Node结构体中只包含一个NodeTag成员变量，NodeTag是enum（枚举）类型。

其他的结构体则利用C语言的特性对Node结构体进行扩展，所有结构体的第一个成员变量也是NodeTag枚举类型，例如在List结构体里，第一个成员变量是NodeTag，它可能的值是T_List、T_intList或者T_OidList，这样就能分别指代不同类型的List。

而Query结构体也是以NodeTag枚举类型作为第一个变量，它的取值为T_Query。

这样无论是List结构体的指针，还是Query结构体的指针，我们都能通过Node结构体的指针（Node*）来表示，而在使用对应的结构体时，则通过查看Node类型的指针中的NodeTag枚举类型就可以区分出该Node指针所代表的结构体的实际类型。

Var结构体

Var结构体表示查询中涉及的表的列属性，在SQL语句中，投影的列属性、约束条件中的列属性都是通过Var来表示的，在语法分析阶段会将列属性用ColumnRef结构体来表示，在语义分析阶段会将语法树中的ColumnRef替换成Var用来表示一个列属性。下面来看一下Var结构体中各个变量的具体含义。

varno：用来确定列属性所在的表的“编号”，这个编号源自Query（查询树）中的rtable成员变量，查询语句中涉及的每个表都会记录在rtable中，而其在rtable中的“编号”（也就是处于链表的第几个，从1开始计数，这个编号用rtindex表示）是唯一确定的值，在逻辑优化、物理优化的过程中可能varno都是rindex，而在生成执行计划的阶段，它可能不再代表rtable中的编号，这在第10章中会进行介绍。

varattno/vartype/vartypmod：varattno确定了这个列属性是表中的第几列，vartype和vartypmod则和列属性的类型有关。在创建表的时候，PostgreSQL数据库会按照SQL语句中指定的列的顺序给列属性编号，并将编号记录在PG_ATTRIBUTES系统表中，同时会将SQL语句指定的列的类型也记录到PG_ATTRIBUTES中，因此可以说varattno、vartype、vartypemod都是取自PG_ATTRIBUTES系统表中的。

varlevelsup：确定了列属性对应的表所在的层次，这个层次值是一个相对值。

varnoold/varoattno：通常和varno/varattno相同，但是在等价变化的过程中，varno/varattno的值可能发生变化，而varnoold/varoattno记录变化前的初值。

例如有SQL语句：

SELECT st.sname FROM STUDENT st WHERE st.sno = ANY(SELECT sno FROMSCORE WHERE st.sno = sno);

其中st.sno虽然在子查询（SELECT sno FROM SCOREWHERE st.sno = sno）中被引用，但是它是父查询中的STUDENT表的属性，因此它的varlevelsup的值为1，说明该属性所在的表在当前子查询的“上1层”，而子查询的约束条件中的另一个sno是SCORE表的列属性，它的varlevelsup的值为0，意味着该列属性所在的表就在当前的层次，表2-1显示了st.sno对应的Var的各个值。

表2-1 Var结构体成员变量的值

示例中另一个SCORE.sno对应的Var的成员变量的值如表2-2所示。

表2-2 Var结构体成员变量的值

示例中的st.sname对应的Var的成员变量的值如表2-3所示。

表2-3 Var结构体成员变量的值

RangeTblEntry 结构体

RangeTblEntry（范围表，简称RTE）描述了查询中出现的表，它通常出现在查询语句的FROM子句中，范围表中既有常规意义上的堆表，还有子查询、连接表等。

RangeTblEntry根据成员变量rtekind来确定自己的类型，类型不同RangeTblEntry成员变量的作用也不同，例如针对RTE_RELATION类型的RangeTblEntry，成员变量relid和relkind就是有用的，而对于RTE_SUBQUERY类型的RangeTblEntry，它是一个子查询衍生的RangeTblEntry，本身没有relid和relkind，因此relid和relkind这时就处于无用的状态，而这时有效的是subquery成员变量。

例如有SQL语句：

SELECT * FROM STUDENT LEFT JOIN SCORE ON TRUE, (SELECT * FROMTEACHER) AS t, COURSE, (VALUES(1,1)) AS NUM(x, y), GENERATE_SERIES(1,10) ASGS(z);

它对应的各种类型的RangeTblEntry如表2-4所示。

表2-4 RangeTblEntry结构体类型对照表

示例中对应的RangeTblEntry在Query->rtable中的结构如图2-1所示，其中RTE_JOIN类型的RangeTblEntry中保存的是STUDENT和SCORE表中的投影的Var，varno== 1代表是STUDENT表中的列，varno== 2代表是SCORE表中的列。

图2-1 Query->rtable链表内容示意图

RangeTblRef 结构体

RangeTblEntry只保留在查询树的Query->rtable链表中，而链表是一个线性结构，它如何保存树状的关系代数表达式中的连接操作呢？答案是在Query->jointree中保存各个范围表之间的连接关系。

如果在Query->jointree中还保存同样的一份RangeTblEntry，那么一方面会造成存储的冗余，另一方面也容易产生数据不一致的问题，因此在查询树的其他任何地方都不再存放新的RangeTblEntry，每个范围表在Query->rtable链表中有且只能有一个，在其他地方使用到范围表都使用RangeTblRef来代替。RangeTblRef是对RangeTblEntry的引用，因为RangeTblEntry在Query->rtable中的位置是确定的，因此可以用它在Query->rtable链表中的位置rtindex来标识。

JoinExpr 结构体

在查询语句中如果显式地指定两个表之间的连接关系，例如A LEFT JOIN B ON Pab这种形式，就需要一个JoinExpr结构体来表示它们，我们先看一下JoinExpr结构体的定义。

我们来看几个示例。

例1：SELECT* FROM STUDENT INNER JOIN SCORE ON STUDENT.sno = SCORE.sno; 这个示例语句明确指定了两个表进行内连接操作，因此它们需要用JoinExpr来表示，JoinExpr->quals中保存的是STUDENT.sno= SCORE.sno。

例2：SELECT* FROM STUDENT LEFT JOIN SCORE ON STUDENT.sno = SCORE.sno; 这个示例语句中明确指定了两个表进行左外连接操作，因此它也必须使用JoinExpr来表示，JoinExpr->quals中保存的是STUDENT.sno= SCORE.sno。

例3：SELECT * FROM STUDENT LEFTJOIN SCORE ON TRUE LEFT JOIN COURSE ON SCORE.cno = COURSE.cno;这个示例语句中明确指定了3个表之间的连接关系，它需要有两个JoinExpr来表示，如图2-2所示。

图2-2JoinExpr的内存结构示意图

STUDENTLEFT JOIN SCORE ON TRUE LEFT JOIN COURSE ON SCORE.cno = COURSE.cno;这个示例语句中明确指定了3个表之间的连接关系，它需要有两个JoinExpr来表示，如图2-2所示。

FromExpr 结构体

FromExpr和JoinExpr是用来表示表之间的连接关系的结构体，通常来说，FromExpr中的各个表之间的连接关系是InnerJoin，这样就可以在FromExpr->fromlist中保存任意多个表，默认它们之间是内连接的关系，我们先来看一下它的结构体的定义。

我们来看几个示例。

例1：SELECT * FROM STUDENT, SCORE, COURSE WHERESTUDENT.sno = SCORE.sno；这个示例中的3个表没有明确地指定连接关系，默认它们是InnerJoin，因此可以通过FromExpr来表示，FromExpr->fromlist中保存了语句中的3个表，FromExpr->quals中保存了STUDENT.sno= SCORE.sno这个约束条件。

例2：SELECT * FROMSTUDENT, SCORE LEFT JOIN COURSE ON SCORE.cno = COURSE.cno；如图2-3所示。

图2-3 FromExpr的内存结构示意图

Query 结构体

Query结构体是查询优化模块的输入参数，其源自于语法分析模块，一个SQL语句在执行过程中，经过词法分析、语法分析和语义分析之后，会生成一棵查询树，PostgreSQL用Query结构体来表示查询树。

查询优化模块在获取到查询树之后，开始对查询树进行逻辑优化，也就是对查询树进行等价变换，将其重写成一棵新的查询树，这个新的查询树又作为物理优化的输入参数，进行物理优化。

rtable：在查询中FROM子句后面会指出需要进行查询的范围表，可能是对单个范围表进行查询，也可能是对几个范围表做连接操作，rtable中则记录了这些范围表。rtable是一个List指针，所有要查询的范围表就记录在这个List中，每个表以RangeTblEntry结构体来表示，因此rtable是一个以RangeTblEntry为节点的List链表。

jointree：rtable中列出了查询语句中的表，但没有明确指出各个表之间的连接关系，这个连接的关系则通过jointree来标明，jointree是一个FromExpr类型的结构体，它有3种类型的节点：FromExpr、JoinExpr和RangeTblRef。

targetlist：targetlist中包含了需要投影（Project）的列，也就是SFW查询中的投影列。

例1：SELECT* FROM STUDENT WHERE SNO = 1; Query结构体中变量对应的值如表2-5所示。

表2-5　例1对应的Query结构体内容

例2：SELECTst.sname, sc.degree FROM STUDENT st, SCORE sc WHERE st.sno = sc.sno; Query结构体变量对应的值如表2-6所示。

表2-6　例2对应的Query结构体内容

例3：SELECTst.sname, sc.degree FROM STUDENT st INNER JOIN SCORE sc ON st.sno = sc.sno;Query结构体变量对应的值如表2-7所示。

表2-7　例3对应的Query结构体内容

例4：SELECTst.sname, c.cname, sc.degree FROM STUDENT st , COURSE c INNER JOIN SCORE sc ON c.cno= sc.cno WHERE st.sno = sc.sno;如图2-4所示。

图2-4　例4对应的Query结构体内存示意图

查询树的展示

PostgreSQL数据库提供了参数让我们查看查询树和执行计划树，如表2-8所示。

表2-8　展示查询树的GUC参数

在调试查询优化源代码的过程中，通常需要不止一次地打印查询树，因为在逻辑优化阶段需要对查询树进行重写，我们可以通过打印查询树的功能来查看查询树重写前和重写后的区别，读者可以在查询重写前和重写后在源代码中增加对应的函数（例如elog_node_display函数），这样能更方便地查看查询重写的内容。例如我们可以在子查询提升函数的前后分别通过elog_node_display函数来打印查询树，这样就能看出子查询提升前和提升后的查询树的内容发生了哪些变化。

增加elog_node_display函数到代码中这种方法在我们尝试对查询优化功能进行修改的时候同样有用，例如现在要在逻辑优化中增加一个新的优化规则，我们可以通过打印查询树更好地规划修改方案。

查询树的遍历

在对查询树进行重写的过程中，需要经常性地对查询树（Query）进行遍历，从中查找、替换、编辑某个结构体的值，以实现重写的功能。例如在子查询提升的过程中，由于在父查询和子查询中的Var具有不同的层次关系，因此它们的varlevelsup是不同的，但是在子查询提升之后，这种层次关系就消失了，因此需要调整一些Var的varlevelsup的值，这时候就需要从查询树中找出这些Var并编辑或替换这些Var。

由于在PostgreSQL数据库中所有的“节点”都是以类似于“类”的方式实现的，因此我们可以由基类Node的指针代表任何节点，并且能通过Nodetag快速地识别出当前Node的真实类型，这就为我们遍历查询树提供了便利。PostgreSQL数据库通过提供query_tree_mutator函数和query_tree_walker函数来对查询树进行遍历，实际上还需要借助expression_tree_mutator函数和expression_tree_walker函数来实现，walker函数的主要作用是对查询树进行遍历并且可能会修改某个结构体中的值，但是它不增加或删除节点，如果要增加或删除查询树中的某个节点，则应该使用mutator函数。这部分的源代码主要是借用递归的思想遍历各种表达式的结构体，有兴趣的读者可以自行分析。

执行计划的展示

本书中大量地使用EXPLAIN语句来展示查询语句的执行计划，这个执行计划是一个非完全的二叉树，每个父节点至少有一个子节点，同时最多有两个子节点，PostgreSQL数据库的查询执行器通过对这个二叉树迭代执行来获得查询结果，EXPLAIN的语法定义如下：

EXPLAIN [ ( _option_ [, ...] ) ] _statement_

EXPLAIN [ ANALYZE ] [ VERBOSE ] _statement_

其中的_option_可以是如下内容：

ANALYZE [ _boolean_ ]

VERBOSE [ _boolean_ ]

COSTS [ _boolean_ ]

BUFFERS [ _boolean_ ]

TIMING [ _boolean_ ]

FORMAT { TEXT | XML | JSON | YAML }

查询优化的主要目的就是将一个查询树（关系代数）转换为一个代价最低的非完全二叉树的执行算式，算式中的每一个节点对应一个物理路径，EXPLAIN语句打印的就是这个非完全二叉树，例如：

postgres=# EXPLAIN SELECT * FROM STUDENT, (SELECT * FROM SCORE) assc;

QUERY PLAN

--------------------------------------------------------------

Nested Loop (cost=0.00..2.15 rows=7 width=31)

-> Seq Scan on score (cost=0.00..1.01 rows=1 width=12)

-> Seq Scan on student (cost=0.00..1.07 rows=7 width=19)

(3 rows)

这个二叉树中有一个父节点和两个子节点，子节点分别对SCORE和STUDENT进行顺序扫描，父节点是对子节点的扫描结果做NestloopJoin，cost=0.00..2.15中的0.00代表的是启动代价，2.15代表的是这个节点和它的子节点共同的整体代价（启动代价和整体代价可以参考第6章）。

EXPLAIN还带有一些关键字作为选项，它们分别的含义如表2-9所示。

表2-9 EXPLAIN的参数

小结

本章主要介绍了查询树的构造形态，读者可以了解到查询树中最重要的几个成员变量，例如Var、RangeTblEntry、FromExpr、JoinExpr等，这样在针对查询树应用优化规则的时候，用户才能清楚地了解查询树变换的真正意图。

另外，查询优化的输入参数不只有查询树对应的结构体Query，另外还有PlannerInfo结构体（包括PlannerGlobal结构体），这个结构体是查询优化的上下文信息，它贯穿在整个查询优化的过程之中，因此现阶段很难清楚地说明它的每个成员变量的具体作用，因此我们把对PlannerInfo结构体的说明“散落”在本书的各个章节，在用到PlannerInfo的每个成员变量的时候再对其进行说明。

关于作者

张树杰

张树杰，目前在Pivotal公司从事Apache HAWQ数据库的内核开发工作，拥有超过13年的IT从业经验，多年从事国产数据库内核开发工作，对数据库内核各个方面均有涉猎，近些年尤其专注于研究对分布式数据库的查询优化、查询执行的改进工作。