合 《PostgreSQL技术内幕——原理探索》第三章 查询处理

 

0    199    2

Tags：

👉 本文共约36133个字，系统预计阅读时间或需136分钟。

查询处理是PostgreSQL中最为复杂的子系统。如PostgreSQL官方文档所述，PostgreSQL支持SQL2011标准中的大多数特性，查询处理子系统能够高效地处理这些SQL。本章概述了查询处理的流程，特别关注了查询优化的部分。

本章包括下列三个部分：

  • 第一部分：3.1节

    这一节会简单介绍PostgreSQL中查询处理的流程。

  • 第二部分：3.2~3.4节

    这一部分会描述获取单表查询上最优执行计划的步骤。3.2节讨论代价估计的过程，3.3节描述创建计划树的过程，3.4节将简要介绍执行器的工作过程。

  • 第三部分：3.5~3.6节

    这一部分会描述获取多表查询上最优执行计划的步骤。3.5节介绍了三种连接算法：嵌套循环连接（Nested Loop Join），归并连接（Merge Join） ，散列连接（Hash Join）。3.6节将介绍为多表查询创建计划树的过程。

PostgreSQL支持三种技术上很有趣，而且也很实用的功能：外部数据包装（Foreign Data Wrapper, FDW），并行查询，以及版本11即将支持的JIT编译。前两者将在第4章中描述，JIT编译超出范围本书的范围，详见官方文档。

3.1 概览

尽管PostgreSQL在9.6版本后有了基于多个后台工作进程的并行查询，但大体上来讲，还是每个连接对应一个后端进程。后端进程由五个子系统组成，如下所示：

  1. 解析器（Parser）

    解析器根据SQL语句生成一颗语法解析树（parse tree） 。

  2. 分析器（Analyzer）

    分析器对语法解析树进行语义分析，生成一颗查询树（query tree）。

  3. 重写器（Rewriter）

    重写器按照规则系统中存在的规则，对查询树进行改写。

  4. 计划器（Planner）

    计划器基于查询树，生成一颗执行效率最高的计划树（plan tree）。

  5. 执行器（Executor）

    执行器按照计划树中的顺序访问表和索引，执行相应查询。

图3.1 查询处理

QueryProcessing

本节将概述这些子系统。计划器和执行器很复杂，后面的章节会对这些函数的细节进行描述。

PostgreSQL的查询处理在官方文档中有详细的描述

3.1.1 解析器（Parser）

解析器基于SQL语句的文本，生成一颗后续子系统可以理解的语法解析树。下面是一个具体的例子。

考虑以下查询：

语法解析树的根节点是一个定义在parsenodes.h中的SelectStmt数据结构。图3.2(a)展示了一个查询，而图3.2(b)则是该查询对应的语法解析树。

图3.2. 语法解析树的例子

ParseTree

SELECT查询中的元素和语法解析树中的元素有着对应关系。比如，(1)是目标列表中的一个元素，与目标表的'id'列相对应，(4)是一个WHERE子句，诸如此类。

当解析器生成语法分析树时只会检查语法，只有当查询中出现语法错误时才会返回错误。解析器并不会检查输入查询的语义，举个例子，如果查询中包含一个不存在的表名，解析器并不会报错，语义检查由分析器负责。

3.1.2 分析器（Analyzer）

分析器对解析器产出的语法解析树（parse tree）进行语义分析，并产出一颗查询树（query tree）。

查询树的根节点是parsenode.h中定义的Query数据结构，这个结构包含着对应查询的元数据，比如命令的类型（SELECT/INSERT等），还包括了一些叶子节点，叶子节点由列表或树组成，包含了特定子句相应的数据。

图3.3 查询树一例

QueyTree

简要介绍一下上图中的查询树：

  • targetlist 是查询结果中列（Column）的列表。在本例中该列表包含两列：id 和data。如果在输入的查询树中使用了*（星号），那么分析器会将其显式替换为所有具体的列。
  • 范围表rtable是该查询所用到关系的列表。本例中该变量包含了表tbl_a的信息，如该表的表名与oid。
  • 连接树jointree存储着FROM和WHERE子句的相关信息。
  • 排序子句sortClause是SortGroupClause结构体的列表。

官方文档描述了查询树的细节。

3.1.3 重写器（Rewriter）

PostgreSQL的规则系统正是基于重写器实现的；当需要时，重写器会根据存储在pg_rules中的规则对查询树进行转换。规则系统本身也是一个很有趣的系统，不过本章略去了关于规则系统和重写器的描述，以免内容过于冗长。

视图

在PostgreSQL中，视图是基于规则系统实现的。当使用CREATE VIEW命令定义一个视图时，PostgreSQL就会创建相应的规则，并存储到系统目录中。

假设下面的视图已经被定义，而pg_rule中也存储了相应的规则。

当执行一个包含该视图的查询，解析器会创建一颗如图3.4(a)所示的语法解析树。

在该阶段，重写器会基于pg_rules中存储的视图规则将rangetable节点重写为一颗查询子树，与子查询相对应。

图3.4 重写阶段一例

rewriter

因为PostgreSQL使用这种机制实现视图，直到9.2版本，视图都是不能更新的。虽然9.3版本后可以对视图进行更新，但对视图的更新仍然存在很多限制，具体细节请参考官方文档。

3.1.4 计划器与执行器

计划器从重写器获取一颗查询树（query tree），基于查询树生成一颗能被执行器高效执行的（查询）计划树（plan tree）。

在PostgreSQL中，计划器是完全基于代价估计（cost-based）的；它不支持基于规则的优化与提示（hint）。计划器是RDBMS中最为复杂的部分，因此本章的后续内容会对计划器做一个概述。

pg_hint_plan

PostgreSQL不支持SQL中的提示（hint），并且永远也不会去支持。如果你想在查询中使用提示，可以考虑使用pg_hint_plan扩展，细节请参考官方站点。

与其他RDBMS类似，PostgreSQL中的EXPLAIN命令会显示命令的计划树。下面给出了一个具体的例子。

图3.5展示了结果相应的计划树。

图3.5 一个简单的计划树以及其与EXPLAIN命令的关系

planTree

计划树由许多称为计划节点（plan node）的元素组成，这些节点挂在PlannedStmt结构对应的计划树上。这些元素的定义在plannodes.h中，第3.3.3节与第3.5.4.2会解释相关细节。

每个计划节点都包含着执行器进行处理所必需的信息，在单表查询的场景中，执行器会按照从终端节点往根节点的顺序依次处理这些节点。

比如图3.5中的计划树就是一个列表，包含一个排序节点和一个顺序扫描节点；因而执行器会首先对表tbl_a执行顺序扫描，并对获取的结果进行排序。

执行器会通过第8章将介绍的缓冲区管理器来访问数据库集簇的表和索引。当处理一个查询时，执行器会使用预先分配的内存空间，比如temp_buffers和work_mem，必要时还会创建临时文件。

图3.6 执行器，缓冲管理器，临时文件之间的关系

dd

除此之外，当访问元组的时候，PostgreSQL还会使用并发控制机制来维护运行中事务的一致性和隔离性。第五章介绍了并发控制机制。

3.2 单表查询的代价估计

PostgreSQL的查询优化是基于代价（Cost）的。代价是一个无量纲的值，它并不是一种绝对的性能指标，但可以作为比较各种操作代价时的相对性能指标。

costsize.c中的函数用于估算各种操作的代价。所有被执行器执行的操作都有着相应的代价函数。例如，函数cost_seqscan() 和 cost_index()分别用于估算顺序扫描和索引扫描的代价。

在PostgreSQL中有三种代价：启动（start-up） ， 运行（run）和总和（total）。总代价是启动代价和运行代价的和；因此只有启动代价和运行代价是单独估计的。

  1. 启动代价（start-up）：在读取到第一条元组前花费的代价，比如索引扫描节点的启动代价就是读取目标表的索引页，取到第一个元组的代价
  2. 运行代价（run）： 获取全部元组的代价
  3. 总代价（total）：前两者之和

EXPLAIN命令显示了每个操作的启动代价和总代价，下面是一个简单的例子：

在第4行显示了顺序扫描的相关信息。代价部分包含了两个值：0.00和145.00。在本例中，启动代价和总代价分别为0.00和145.00。

在本节中，我们将详细介绍顺序扫描，索引扫描和排序操作的代价是如何估算的。

在接下来的内容中，我们使用下面这个表及其索引作为例子。

3.2.1 顺序扫描

顺序扫描的代价是通过函数cost_seqscan()估计的。本节将研究顺序扫描代价是如何估计的，以下面的查询为例：

在顺序扫描中，启动代价等于0，而运行代价由以下公式定义： $$ \begin{align} \verb|run_cost| &= \verb|cpu_run_cost| + \verb|disk_run_cost | \ &= (\verb|cpu_tuple_cost| + \verb|cpu_operatorcost|) × N{\verb|tuple|} + \verb|seq_pagecost| × N{\verb|page|}, \end{align} $$ 其中seq_page_cost，cpu_tuple_cost和cpu_operator_cost是在postgresql.conf 中配置的参数，默认值分别为1.0，0.01和0.0025。$N{\verb|tuple|}$ 和$N{\verb|page|}$ 分别是表中的元组总数与页面总数，这两个值可以使用以下查询获取。

$$ \begin{equation}\tag{1} N_{\verb|tuple|}=10000 \end{equation} $$

$$ \begin{equation}\tag{2} N_{\verb|page|}=45 \end{equation} $$

因此： $$ \begin{align} \verb|run_cost| &= (0.01 + 0.0025) × 10000 + 1.0 × 45 = 170.0. \end{align} $$

最终： $$ \verb|total_cost| = 0.0 + 170.0 = 170.0 $$

作为验证，下面是该查询的EXPLAIN结果：

在第4行中可以看到，启动代价和总代价分别是0.00和170.0，且预计全表扫描返回行数为8000条（元组）。

在第5行显示了一个顺序扫描的过滤器Filter:(id < 8000)。更精确地说，它是一个表级过滤谓词（table level filter predicate）。注意这种类型的过滤器只会在读取所有元组的时候使用，它并不会减少需要扫描的表页面数量。

从优化运行代价的角度来看，PostgreSQL假设所有的物理页都是从存储介质中获取的；即，PostgreSQL不会考虑扫 描的页面是否来自共享缓冲区。

3.2.2 索引扫描

尽管PostgreSQL支持很多索引方法，比如B树，GiST，GIN和BRIN，不过索引扫描的代价估计都使用一个共用的代价函数：cost_index()。

本节将研究索引扫描的代价是如何估计的，以下列查询为例。

在估计该查询的代价之前，下面的查询能获取$N{\verb|index|,\verb|page|}$和$N{\verb|index|,\verb|tuple|}$的值：

$$ \begin{equation}\tag{3} N_{\verb|index|,\verb|tuple|} = 10000 \end{equation} $$

$$ \begin{equation}\tag{4} N_{\verb|index|,\verb|page|} = 30 \end{equation} $$

3.2.2.1 启动代价

索引扫描的启动代价就是读取索引页以访问目标表的第一条元组的代价，由下面的公式定义： $$ \begin{equation} \verb| start-up_cost| = {\mathrm{ceil}(\log2 (N{\verb|index|,\verb|tuple|})) + (H_{\verb|index|} + 1) × 50} × \verb|cpu_operatorcost| \end{equation} $$ 其中$H{\verb|index|}$是索引树的高度。

在本例中，套用公式(3)，$N{\verb|index,tuple|}$是10000；$H{\verb|index|}$是1；$\verb|cpu_operator_cost|$是0.0025（默认值）。因此 $$ \begin{equation}\tag{5} \verb|start-up_cost| = {\mathrm{ceil}(\log_2(10000)) + (1 + 1) × 50} × 0.0025 = 0.285 \end{equation} $$

3.2.2.2 运行代价

索引扫描的运行代价是表和索引的CPU代价与IO代价之和。 $$ \begin{align} \verb|run_cost| &= (\verb|index_cpu_cost| + \verb|table_cpu_cost|) + (\verb|index_io_cost| + \verb|table_io_cost|). \end{align} $$

如果使用仅索引扫描，则不会估计table_cpu_cost与table_io_cost，仅索引扫描将在第七章中介绍。

前三个代价（即index_cpu_cost，table_cpu_cost和index_io_cost）如下所示：

$$ \begin{align} \verb|index_cpucost| &= \verb|Selectivity| × N{\verb|index|,\verb|tuple|} × (\verb|cpu_index_tuple_cost| + \verb|qual_op_cost|) \ \verb|table_cpucost| &= \verb|Selectivity| × N{\verb|tuple|}× \verb|cpu_tuple_cost| \ \verb|index_iocost| &= \mathrm{ceil}(\verb|Selectivity| × N{\verb|index|,\verb|page|}) ×\verb|random_page_cost| \end{align} $$

以上公式中的cpu_index_tuple_cost和random_page_cost在postgresql.conf中配置（默认值分别为0.005和4.0）。$\verb|qual_op_cost|$粗略来说就是索引求值的代价，默认值是0.0025，这里不再展开。选择率（Selectivity）是一个0到1之间的浮点数，代表查询指定的MARKDOWN_HASH5105e0481cb9b1e1d0dd3e10bab1f1c0MARKDOWNHASH子句在索引中搜索范围的比例。举个例子，$(\verb|Selectivity| × N{\verb|tuple|})$就是需要读取的表元组数量，$(\verb|Selectivity| × N_{\verb|index|,\verb|tuple|})$就是需要读取的索引元组数量，诸如此类。

选择率（Selectivity）

查询谓词的选择率是通过直方图界值（histogram_bounds）与高频值（Most Common Value, MCV）估计的，这些信息都存储在系统目录pg_statistics中，并可通过pg_stats视图查询。这里通过一个具体的例子来简要介绍选择率的计算方法，细节可以参考官方文档。

表中每一列的高频值都在pg_stats视图的most_common_vals和most_common_freqs中成对存储。

  • 高频值（most_common_vals）：该列上最常出现的取值列表
  • 高频值频率（most_common_freqs）：高频值相应出现频率的列表

下面是一个简单的例子。表countries有两列：一列country存储国家名，一列continent存储该国所属大洲。

考虑下面的查询，该查询带有WHERE条件continent = 'Asia'。

这时候，计划器使用continent列上的高频值来估计索引扫描的代价，列上的most_common_vals与 most_common_freqs如下所示：

与most_common_vals中Asia值对应的most_common_freqs为0.227979。因此0.227979会在估算中被用作选择率。

如果高频值不可用，就会使用目标列上的直方图界值来估计代价。

  • 直方图值（histogram_bounds）是一系列值，这些值将列上的取值划分为数量大致相同的若干个组。

下面是一个具体的例子。这是表tbl中data列上的直方图界值；

默认情况下，直方图界值会将列上的取值划分入100个桶。图3.7展示了这些桶及其对应的直方图界值。桶从0开始编号，每个桶保存了（大致）相同数量的元组。直方图界值就是相应桶的边界。比如，直方图界值的第0个值是1，意即这是bucket_0中的最小值。第1个值是100，意即bucket_1中的最小值是100，等等。

图3.7 桶和直方图界值

img

然后本节例子中选择率计算如下所示。假设查询带有WHERE子句data < 240，而值240落在第二个桶中。在本例中可以通过线性插值推算出相应的选择率。因此查询中data列的选择率可以套用下面的公式计算： $$ \verb|Selectivity| = \frac{2+(240-hb[2])/(hb[3]-hb[2])}{100}=\frac{2+(240-200)/(300-200)}{100}=\frac{2+40/100}{100}=0.024 \ (6) $$

因此，根据公式(1)，(3)，(4)和(6)，有 $$ \begin{equation}\tag{7} \verb|index_cpu_cost| = 0.024× 10000 × (0.005+0.0025)=1.8 \end{equation} $$ $$ \begin{equation}\tag{8} \verb|table_cpu_cost| = 0.024 × 10000 × 0.01 = 2.4 \end{equation} $$

$$ \begin{equation}\tag{9} \verb|index_io_cost| = \mathrm{ceil}(0.024 × 30) × 4.0 = 4.0 \end{equation} $$

$\verb|table_io_cost|$ 由下面的公式定义： $$ \begin{equation} \verb|table_io_cost| = \verb|max_io_cost| + \verb|indexCorerelation|^2 × (\verb|min_io_cost|-\verb|max_io_cost|) \end{equation} $$

$\verb|max_io_cost_io_cost|$ 是最差情况下的I/O代价，即，随机扫描所有数据页的代价；这个代价由以下公式定义： $$ \begin{equation} \verb|max_iocost| = N{\verb|page|} × \verb|random_page_cost| \end{equation} $$

在本例中，由(2)，$N_{\verb|page|}=45$，得 $$ \begin{equation}\tag{10} \verb|max_io_cost| = 45 × 4.0 = 180.0 \end{equation} $$

$\verb|min_io_cost|$是最优情况下的I/O代价，即，顺序扫描选定的数据页；这个代价由以下公式定义： $$ \begin{equation} \verb|min_io_cost| = 1 × \verb|random_pagecost| + (\mathrm{ceil}(\verb|Selectivity| × N{\verb|page|})-1) × \verb|seq_page_cost| \end{equation} $$ 在本例中， $$ \begin{equation} \tag{11} \verb|min_io_cost| \ = 1 × 4.0 + (\mathrm{ceil}(0.024 × 45)-1) × 1.0 \end{equation} $$

下文详细介绍$\verb|indexCorrelation|$，在本例中， $$ \begin{equation} \tag{12} \verb|indexCorrelation| = 1.0 \end{equation} $$

由(10)，(11)和(12)，得 $$ \begin{equation} \tag{13} \verb|table_io_cost| = 180.0+1.0^2 × (5.0-180.0)=5.0 \end{equation} $$

综上，由(7)，(8)，(9)和(13)得 $$ \begin{equation}\tag{14} \verb|run_cost| = (1.8+2.4)+(4.0+5.0)=13.2 \end{equation} $$

索引相关性（index correlation）

索引相关性是列值在物理上的顺序和逻辑上的顺序的统计相关性（引自官方文档）。索引相关性的取值范围从$-1$到$+1$。下面的例子有助于理解索引扫描和索引相关性的关系。

表tbl_corr有5个列：两个列为文本类型，三个列为整数类型。这三个整数列保存着从1到12的数字。在物理上表tbl_corr包含三个页，每页有4条元组。每个数字列有一个名如index_col_asc的索引。

这些列的索引相关性如下：

当执行下列查询时，由于所有的目标元组都在第一页中，PostgreSQL只会读取第一页，如图3.8(a)所示。

而执行下列查询时则不然，PostgreSQL需要读所有的页，如图3.8(b)所示。

如此可知，索引相关性是一种统计上的相关性。在索引扫描代价估计中，索引相关性体现了索引顺序和物理元组顺序扭曲程度给随机访问性能造成的影响大小。

图3.8 索引相关性

indexcor

3.2.2.3 整体代价

由(3)和(14)可得 $$ \begin{equation}\tag{15} \verb|total_cost| = 0.285 + 13.2 = 13.485 \end{equation} $$

作为确认，上述SELECT查询的EXPLAIN结果如下所示：

在第4行可以看到启动代价和总代价分别是0.29和13.49，预估有240条元组被扫描。

在第5行显示了一个索引条件Index Cond:(data < 240)。更准确地说，这个条件叫做访问谓词（access predicate），它表达了索引扫描的开始条件与结束条件。

根据这篇文章，PostgreSQL中的EXPLAIN命令不会区分访问谓词（access predicate）和索引过滤谓词（index filter predicate）。因此当分析EXPLAIN的输出时，即使看到了“IndexCond”，也应当注意一下预估返回行数。

seq_page_cost和random_page_cost

seq_page_cost和random_page_cost的默认值分别为1.0和4.0。这意味着PostgreSQL假设随机扫描比顺序扫描慢4倍；显然，PostgreSQL的默认值是基于HDD（普通硬盘）设置的。

另一方面，近年来SSD得到了广泛的应用，random_page_cost的默认值就显得太大了。使用SSD时如果仍然采用random_page_cost的默认值，则计划器有可能会选择低效的计划。因此当使用SSD时最好将random_page_cost的值设为1.0。

这篇文章报告了使用random_page_cost默认值导致的问题。

3.2.3 排序

排序路径（sort path） 会在排序操作中被使用。排序操作包括ORDER BY，归并连接的预处理操作，以及其他函数。函数cost_sort()用于估计排序操作的代价。

如果能在工作内存中放下所有元组，那么排序操作会选用快速排序算法。否则的话则会创建临时文件，使用文件归并排序算法。

排序路径的启动代价就是对目标表的排序代价，因此代价就是$O(N_{\verb|sort|}× \log2(N{\verb|sort|})$，这里$N{\verb|sort|}$就是待排序的元组数。排序路径的运行代价就是读取已经排好序的元组的代价，因而代价就是$O(N{sort})$。

本节将研究以下查询排序代价的估计过程。假设该查询只使用工作内存，不使用临时文件。

在本例中，启动代价由以下公式定义： $$ \begin{equation} \verb|start-up_cost| = \verb|C|+ \verb|comparisoncost| × N{\verb|sort|} × \log2(N{\verb|sort|}) \end{equation} $$

这里$C$就是上一次扫描的总代价，即上次索引扫描的总代价；由(15)可得C等于13.485；$N_{\verb|sort|}=240$；$\verb|comparison_cost|$ 定义为$2 × \verb|cpu_operator_cost|$。因此有

$$ \begin{equation} \verb|start-up_cost| = 13.485+(2×0.0025)×240.0×\log_2(240.0)=22.973 \end{equation} $$

运行代价是在内存中读取排好序的元组的代价，即： $$ \begin{equation} \verb|run_cost| = \verb|cpu_operatorcost| × N{\verb|sort|} = 0.0025 × 240 = 0.6 \end{equation} $$ 综上： $$ \begin{equation} \verb|total_cost|=22.973+0.6=23.573 \end{equation} $$ 作为确认，以上SELECT查询的EXPLAIN命令结果如下：

在第4行可以看到启动代价和运行代价分别为22.97和23.57。

3.3 创建单表查询的计划树

计划器非常复杂，故本节仅描述最简单的情况，即单表查询的计划树创建过程。更复杂的查询，换而言之即多表查询，其计划树创建过程将在第3.6节中阐述。

PostgreSQL中的计划器会执行三个处理步骤：

  1. 执行预处理
  2. 在所有可能的访问路径中，找出代价最小的访问路径
  3. 按照代价最小的路径，创建计划树

访问路径（access path）是估算代价时的处理单元；比如，顺序扫描，索引扫描，排序以及各种连接操作都有其对应的路径。访问路径只在计划器创建查询计划树的时候使用。最基本的访问路径数据结构就是relation.h中定义的Path结构体。它就相当于是顺序扫描。所有其他的访问路径都基于该结构，下面会介绍细节。

计划器为了处理上述步骤，会在内部创建一个PlannerInfo数据结构。在该数据结构中包含着查询树，查询所涉及关系信息，访问路径等等。

本节会通过一个具体的例子，来描述如何基于查询树创建计划树。

3.3.1 预处理

在创建计划树之前，计划器对先PlannerInfo中的查询树进行一些预处理。

预处理有很多步骤，本节只讨论和单表查询处理相关的主要步骤。其他预处理操作将在3.6节中描述。

  1. 简化目标列表（target list），LIMIT子句等；

    例如，表达式2+2会被重写为4，这是由clauses.c中eval_const_expressions()函数负责的。

  2. 布尔表达式的规范化

    例如，NOT(NOT a)会被重写为a

  3. 压平与/或表达式

    SQL标准中的AND/OR是二元操作符；但在PostgreSQL内部它们是多元操作符。而计划器总是会假设所有的嵌套AND/OR都应当被压平。

    这里有一个具体的例子。考虑这样一个布尔表达式(id = 1) OR (id = 2) OR (id = 3)，图3.9(a) 展示了使用二元表达式时的查询树，预处理会将这些二元算子简化压平为一个三元算子，如图3.9(b)所示。

    图3.9. 压平布尔表达式的例子

    扁平化

3.3.2 找出代价最小的访问路径

计划器对所有可能的访问路径进行代价估计，然后选择代价最小的那个。具体来说，计划器会执行以下几个步骤：

  1. 创建一个RelOptInfo数据结构，存储访问路径及其代价。

    RelOptInfo结构体是通过make_one_rel()函数创建的，并存储于PlannerInfo结构体的simple_rel_array字段中，如图3.10所示。在初始状态时RelOptInfo持有着baserestrictinfo变量，如果存在相应索引，还会持有indexlist变量。baserestrictinfo存储着查询的WHERE子句，而indexlist存储着目标表上相关的索引。

  2. 估计所有可能访问路径的代价，并将访问路径添加至RelOptInfo结构中。

    这一处理过程的细节如下：

    1. 创建一条路径，估计该路径中顺序扫描的代价，并将其写入路径中。将该路径添加到RelOptInfo结构的pathlist变量中。
    2. 如果目标表上存在相关的索引，则为每个索引创建相应的索引访问路径。估计所有索引扫描的代价，并将代价写入相应路径中。然后将索引访问路径添加到pathlist变量中。
    3. 如果可以进行位图扫描，则创建一条位图扫描访问路径。估计所有的位图扫描的代价，并将代价写入到路径中。然后将位图扫描路径添加到pathlist变量中。

  3. 从RelOptInfo的pathlist中，找出代价最小的访问路径。

  4. 如有必要，估计LIMIT，ORDER BY和AGGREGATE操作的代价。

为了更加清晰的理解计划器的执行过程，下面给出了两个具体的例子。

3.3.2.1 例1

首先来研究一个不带索引的简单单表查询；该查询同时包含WHERE和ORDER BY子句。

图3.10和图3.11展示了本例中计划器的处理过程。

图3.10 如何得到例1中代价最小的路径

img

  1. 创建一个RelOptInfo结构，将其保存在PlannerInfo结构的simple_rel_array字段中。

  2. 在RelOptInfo结构的baserestrictinfo字段中，添加一条WHERE子句。

    WHERE子句id<300会经由initsplan.c中定义的distribute_restrictinfo_to_rels()函数，添加至列表变量baserestrictinfo中。另外由于目标表上没有相关索引，RelOptInfo的indexlist字段为空。

  3. 为了满足排序要求，planner.c中的standard_qp_callback()函数会在PlannerInfo的sor_pathkeys字段中添加一个pathkey。

    Pathkey是表示路径排序顺序的数据结构。本例因为查询包含一条ORDER BY子句，且该子句中的列为data，故data会被包装为pathkey，放入列表变量sort_pathkeys中。

  4. 创建一个Path结构，并使用cost_seqscan函数估计顺序扫描的代价，并将代价写入Path中。然后使用pathnode.c中定义的add_path()函数，将该路径添加至RelOptInfo中。

    如之前所提到过的，Path中同时包含启动代价和总代价，都是由cost_seqscan函数所估计的。

在本例中，因为目标表上没有索引，计划器只估计了顺序扫描的代价，因此最小代价是自动确定的。

图3.11 如何得到例1中代价最小的路径（接图3.10）

img

  1. 创建一个新的RelOptInfo结构，用于处理ORDER BY子句。

    注意新的RelOptInfo没有baserestrictinfo字段，该信息已经被WHERE子句所持有。

  2. 创建一个排序路径，并添加到新的RelOptInfo中；然后让SortPath的subpath字段指向顺序扫描的路径。

    SortPath结构包含两个Path结构：path与subpath；path中存储了排序算子本身的相关信息，而subpath则指向之前得到的代价最小的路径。

    注意顺序扫描路径中parent字段，该字段指向之前的RelOptInfo结构体（也就是在baserestrictinfo中存储着WHERE子句的那个RelOptInfo）。因此在下一步创建计划树的过程中，尽管新的RelOptInfo结构并未包含baserestrictinfo，但计划器可以创建一个包含Filter的顺序扫描节点，将WHERE子句作为过滤条件。

这里已经获得了代价最小的访问路径，然后就可以基于此生成一颗计划树。3.3.3节描述了相关的细节。

3.3.2.2 例2

下面我们将研究另一个单表查询的例子，这一次表上有两个索引，而查询带有一个WHERE子句。

图3.12到3.14展示了本例中计划器的处理过程。

  1. 创建一个RelOptInfo结构体

  2. 在baserestrictinfo中添加一个WHERE子句；并将目标表上的索引（们）添加到indexlist中。

    在本例中，WHERE子句'id <240'会被添加至baserestrictinfo中，而两个索引：tbl_2_pkey和tbl_2_data_idx会被添加至RelOptInfo的列表变量indexlist中。

  3. 创建一条路径，估计其顺序扫描代价，并添加到RelOptInfo的pathlist中。

图3.12 如何得到例2中代价最小的路径

img

  1. 创建一个IndexPath，估计索引扫描的代价，并通过add_path()函数将IndexPath添加到RelOptInfo的pathlist中。

    在本例中有两个索引：tbl_2_pkey与tbl_2_data_index，这些索引会按先后顺序依次处理。

    一条针对tbl_2_pkey的IndexPath会先被创建出来，并进行启动代价与总代价的评估。在本例中，tbl_2_pkey是id列上的索引，而WHERE子句也包含该id列；因此WHERE子句会被存储在IndexPath的indexclauses字段中。

  2. 创建另一个IndexPath，估计另一种索引扫描的代价，并将该IndexPath添加到RelOptInfo的pathlist中。

    接下来，与tbl_2_data_idx相应的IndexPath会被创建出来，并进行代价估计。本例中tbl_2_data_idx并没有相关的WHERE子句；因此其indexclauses为空。

注意add_path()函数并不总是真的会将路径添加到路径列表中。这一操作相当复杂，故这里就省去了具体描述。详细细节可以参考add_path()函数的注释。

图3.13 如何得到例2中代价最小的路径（接图3.12）

img

  1. 创建一个新的RelOptInfo结构

  2. 将代价最小的路径，添加到新RelOptInfo的pathlist中。

    本例中代价最小的路径是使用tbl_2_pkey的索引路径；故将该路径添加到新的RelOptInfo中。

图3.14 如何得到例2中代价最小的路径（接图3.13）

本人提供Oracle(OCP、OCM)、MySQL(OCP)、PostgreSQL(PGCA、PGCE、PGCM)等数据库的培训和考证业务，私聊QQ646634621或微信dbaup66，谢谢！
AiDBA后续精彩内容已被站长无情隐藏，请输入验证码解锁本文！
验证码：
获取验证码： 请先关注本站微信公众号，然后回复“验证码”，获取验证码。在微信里搜索“AiDBA”或者“dbaup6”或者微信扫描右侧二维码都可以关注本站微信公众号。

标签：

Avatar photo

小麦苗

学习或考证，均可联系麦老师，请加微信db_bao或QQ646634621

您可能还喜欢...

发表回复