CMU15-445 数据库系统播客：查询规划与优化

什么是谓词？如何理解？ 谓词是指SQL查询中用于过滤数据的条件，通常出现在​​WHERE​​子句中。例如，​​e.grade = 'A'​​就是一个谓词。

查询优化概述

查询优化在数据库管理系统（DBMS）中至关重要。SQL是一种声明性语言，这意味着用户告诉DBMS他们想要什么结果，而不是如何获取结果。然而，执行同一个查询可以有多种不同的方式（例如，不同的连接算法），而这些执行计划的性能差异可能非常大。例如，一个表操作可能在1.3小时和0.45秒之间产生巨大差异。因此，DBMS需要一种方法来选择给定查询的“最佳”执行计划，这就是DBMS优化器的职责。

查询优化非常困难，这被认为是构建DBMS最困难的部分。成功的查询优化能力可以显著区分高端数据库系统（如Oracle、DB2、Teradata、SQL Server）与开源或免费系统（如Postgres，尽管Postgres也很好，但其查询优化器不如SQL Server复杂）。IBM在20世纪70年代首次实现了查询优化器，即System R项目。当时，人们认为DBMS无法选择比人类手写更好的查询计划。然而，System R证明了数据库系统可以通过优化器生成与人类编写的计划一样好甚至更好的计划。System R的许多概念和设计决策至今仍在使用。

查询优化的两种主要方法

查询优化主要有两种方法：

静态规则/启发式规则 (Static Rules / Heuristics)通过重写查询来消除低效或不必要的元素。这些技术不需要检查实际数据，但可能需要查阅系统目录（即元数据）。基于成本的搜索 (Cost-based Search)使用成本模型估算执行计划的成本。评估查询的多个等效计划，并选择成本最低的那个。

静态规则与查询重写

静态规则的核心思想是关系代数等价性。如果两个关系代数表达式或查询计划产生相同的元组集合，则它们是等效的。重要的是，这里强调的是“集合”，意味着不要求结果的顺序相同。这种等价性允许DBMS在不改变最终结果的前提下，通过转换或重排操作符来找到更高效的执行计划。这种高级技术通常被称为查询重写 (Query Rewriting)。

在查询优化架构中，SQL查询首先经过一个可选的SQL重写器，然后由解析器转换为抽象语法树。绑定器将语法树中的命名对象（如表、列名）转换为内部标识符，并查阅系统目录，生成逻辑计划。逻辑计划以高层方式描述查询要做什么（如扫描表、连接表），但不指定具体如何执行。随后，逻辑计划可以进入树重写器，在这里应用静态规则进行重写。

以下是一些常见的静态规则优化：

谓词下推 (Predicate Pushdown)

什么是谓词？如何理解？谓词是指SQL查询中用于过滤数据的条件，通常出现在WHERE子句中。例如，e.grade = 'A'就是一个谓词。

如何理解下推？假设SQL查询被分析并表示为一棵操作树，谓词下推就是将过滤操作从树的较高层（例如，在连接之后）移动到较低层（例如，在连接之前）。

举例子：把WHERE推到JOIN之前。例如，对于一个连接了student和enrolled表的查询，并且有一个WHERE e.grade = 'A'的条件。最初可能先执行连接，再应用过滤。通过谓词下推，优化器会先在enrolled表上应用grade = 'A'的过滤，从而在执行连接之前就大大减少参与连接的元组数量。这样做的目的是尽早减少数据量，从而减少后续操作的工作量。

此外，还可以重排谓词的顺序，优先应用选择性更高的谓词（即能过滤掉更多数据的谓词），以更快地减少处理的数据量。

需要注意的是，并非所有谓词都适合下推，例如，如果谓词涉及计算成本较高的用户定义函数（UDF），数据库可能会选择不将其下推。

投影下推 (Projection Pushdown)

在查询早期阶段执行投影操作，只保留查询所需或连接所需的属性。

这样可以最小化从一个操作符传递到下一个操作符的数据量，这在行式存储系统（避免复制宽行中不必要的列）和分布式数据库（减少网络传输的数据量）中尤为重要。

当DBMS分析SQL查询并将其转换为操作树时，投影下推意味着在查询执行的早期阶段，只保留查询所需或后续操作（例如连接操作）所需的属性（列）。其他不需要的列会在数据量较小的阶段就被“投影掉”，从而避免将它们复制和传递到后续的昂贵操作中。

假设有一个SQL查询，需要从student表和enrolled表中获取学生姓名（s.name）和课程ID（e.cid），并且两个表通过s.sid = e.sid进行连接。如果student表有上千个列，但这个查询只需要其中的sid和name列，enrolled表也只需要sid和cid列，那么：

原始（未优化）计划：可能会先将student表的全部列和enrolled表的全部列进行连接，然后再对连接后的巨大结果集进行投影，只保留name和cid。应用投影下推后：优化器会在这两个表被连接之前，就对student表执行一个投影操作，只保留sid和name列；对enrolled表执行投影操作，只保留sid和cid列。这样，在执行连接时，参与连接的元组会更“窄”，大大减少了需要处理的数据量。

这种优化在以下场景中尤为重要：

行式存储系统（Row-Store Systems）：在行式存储系统中，如果一个元组非常宽（即有很多列），并且查询只需要其中的少数几列，那么过早地将整个宽元组从一个操作符传递到下一个操作符会消耗大量内存和I/O。通过投影下推，可以尽早地剔除不必要的列，从而减少在内存中复制和处理的数据量。分布式数据库（Distributed Databases）：在分布式环境中，数据可能存储在不同的节点上，并且在执行连接等操作时需要在网络上传输。网络I/O是慢且低效的。如果能在数据传输到其他节点之前就进行投影，只发送必要的列，可以显著减少网络传输的数据量和开销。减少后续操作的开销：当数据量减少后，后续的连接、排序、聚合等操作的处理效率会更高，因为它们需要处理的数据总量更小。

需要注意的是，投影下推对列式存储系统（Column-Store Systems）来说可能不那么重要，因为列式存储本身就是按列存储数据，通常在读取时就只读取查询所需的列。

表达式简化与重写 (Expression Simplification and Rewriting)

简化复杂的谓词表达式。例如，WHERE X = Y AND Y = 3可以被简化为WHERE X = 3 AND Y = 3。

合并谓词：将多个范围谓词合并为更紧凑的形式。例如，WHERE val BETWEEN 1 AND 100 OR val BETWEEN 50 AND 150可以简化为WHERE val BETWEEN 1 AND 150。

这些处理属于明显的逻辑优化，它们在不查看实际数据内容的情况下，仅凭查询本身的结构和系统目录中的元数据（例如，主键不能为NULL）即可识别并进行重写。例如，优化器可以识别并移除不可能的谓词（如WHERE 1 = 0，总是假）或不必要的谓词（如WHERE 1 = 1，总是真），或者识别出冗余的自连接。

复杂查询与基于成本的搜索

对于复杂的查询，仅仅依靠静态规则是不够的。例如，不同的连接顺序（例如，对于N个表的连接，可能存在4^N种连接顺序，这是一个巨大的数字，即卡特兰数）以及使用什么连接算法（如哈希连接与嵌套循环连接的性能差异巨大）等决策，无法仅通过静态规则来确定。此时，就需要基于成本的搜索 (Cost-based Search)。

成本模型 (Cost Model)

数据库系统内部维护一个成本模型，用于估算每个潜在执行计划可能产生的成本。

这个成本是一个内部的、合成的数字，它只用于在同一DBMS内部比较不同查询计划的相对性能。它与实际的执行时间没有直接的外部映射关系。

成本估算通常基于多种因素，包括磁盘I/O次数、DRAM（内存）占用量，以及在分布式数据库中，网络消息的数量（因为网络I/O慢且低效）。

成本模型的核心目的是在不实际运行查询计划的情况下，近似估算其成本。实际运行查询是获得真实成本的唯一方式，但由于可能的计划数量巨大，这不切实际。

少数系统（如MongoDB）曾采用过简单的方法，即并行触发多个查询计划，选择第一个返回结果的计划，并将其作为后续相同查询的默认计划。

统计信息 (Statistics Information)

为了能够准确估算查询计划的成本，DBMS需要维护关于表结构的内部统计信息。

这些统计信息通常存储在系统目录中，包括表和索引的外观、元组中的值分布（如特定列的最小值/最大值、唯一值的数量、直方图等）。

统计信息的维护可以通过以下方式进行：

自动更新：当表数据发生一定比例（如10%）的变化时自动收集。查询时收集：在执行查询时，DBMS可以查看数据并更新相关统计信息。手动执行ANALYZE命令：用户或管理员可以显式运行ANALYZE函数（在不同系统中有不同的语法，但概念类似），这通常会启动一次全表扫描，检查数据并更新内部统计信息。

准确的统计信息对于优化器做出明智的成本估算至关重要。它们帮助优化器更好地理解数据的分布和选择性，从而更准确地预测不同操作的开销。