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

0    80    2

Tags:

👉 本文共约36251个字,系统预计阅读时间或需137分钟。

查询处理是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 查询处理

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

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

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

3.1.1 解析器(Parser)

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

考虑以下查询:

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

图3.2. 语法解析树的例子

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

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

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

3.1.2 分析器(Analyzer)

分析器对解析器产出的语法解析树(parse tree)进行语义分析,并产出一颗查询树(query tree)

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

图3.3 查询树一例

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

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

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

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

3.1.3 重写器(Rewriter)

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

视图

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

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

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

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

图3.4 重写阶段一例

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

因为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命令的关系

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

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

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

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

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

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

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

除此之外,当访问元组的时候,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_costcpu_tuple_costcpu_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树,GiSTGINBRIN,不过索引扫描的代价估计都使用一个共用的代价函数: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_costtable_io_cost,仅索引扫描将在第七章中介绍。

前三个代价(即index_cpu_costtable_cpu_costindex_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_costrandom_page_costpostgresql.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_valsmost_common_freqs中成对存储。

  • 高频值(most_common_vals):该列上最常出现的取值列表
  • 高频值频率(most_common_freqs):高频值相应出现频率的列表

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

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

这时候,计划器使用continent列上的高频值来估计索引扫描的代价,列上的most_common_valsmost_common_freqs如下所示:

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

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

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

下面是一个具体的例子。这是表tbldata列上的直方图界值;

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

本人提供Oracle(OCP、OCM)、MySQL(OCP)、PostgreSQL(PGCA、PGCE、PGCM)等数据库的培训和考证业务,私聊QQ646634621或微信db_bao,谢谢!
《PostgreSQL技术内幕——原理探索》第三章 查询处理后续精彩内容已被小麦苗无情隐藏,请输入验证码解锁本站所有文章!
验证码:
请先关注本站微信公众号,然后回复“验证码”,获取验证码。在微信里搜索“DB宝”或者“www_xmmup_com”或者微信扫描右侧二维码都可以关注本站微信公众号。

标签:

Avatar photo

小麦苗

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

您可能还喜欢...

发表回复

嘿,我是小麦,需要帮助随时找我哦。
  • 18509239930
  • 个人微信

  • DB宝
  • 个人邮箱
  • 点击加入QQ群
  • 个人微店

  • 回到顶部