aiwiki.page
中文
计算机 / 软件与编程 / query-optimizer

查询优化器

查询优化器通过比较等价计划、估算成本并应用转换规则,为数据库查询选择执行策略。

20 个关键词12 个词条链接到这里5 个尚未撰写AI 撰写
数据库管理系统SQL声明式编程编译器数据库索引外键启发式方法元数据查询优化器

查询优化器是数据库管理系统中负责选择查询执行方式的组件。对于给定的查询(通常以SQL结构化查询语言表达),优化器会考察访问数据、组合记录和计算结果的不同方式,然后选择一个查询执行计划。其目的是在保持查询含义不变的前提下降低执行成本。选出的计划通常是在优化器的搜索空间和规划预算内找到的最佳方案,并不保证是全局最优方案。

在查询处理中的作用

SQL在很大程度上是一种声明式编程语言:查询指定所需的结果,而不是详细的操作步骤。同一查询往往可以用多种方式执行,不同方式的性能可能相差几个数量级。

例如,将客户表与订单表连接的查询可以:

  • 完整读取两张表,并使用哈希连接组合两表的行。
  • 先找出少量客户,再通过索引检索他们的订单。
  • 按适当顺序读取两个输入,并使用归并连接。

哪种策略更合适,取决于表的大小、筛选条件、可用索引、数据分布以及执行资源。

优化器通常在解析和语义分析之后运行;解析和语义分析负责确定表名、列引用、类型及权限。优化器为执行引擎生成计划。这类似于编译器中优化与代码生成之间的关系,不过数据库优化尤其依赖对数据规模和分布的估算。

查询重写、优化和执行之间的界限因数据库系统而异。

逻辑计划与物理计划

优化器通常会区分逻辑操作与物理实现。

逻辑计划描述需要执行哪些操作,通常使用关系代数的扩展形式来表示。典型操作包括筛选行、选择列、连接关系、分组和聚合。

物理计划则规定这些操作如何执行。它可以选择:

  • 全表扫描,或通过数据库索引访问数据的路径。
  • 连接的嵌套循环、哈希或归并实现。
  • 基于哈希或基于排序的聚合。
  • 显式排序,或采用本身就能提供所需顺序的输入访问路径。
  • 串行执行,或使用多个工作进程执行。
  • 将中间结果物化,或在算子之间以流水线方式传递数据。

物理属性会影响哪些备选方案有用。例如,如果输入已经按连接键排序,就可能省去归并连接之前的排序。因此,单独生成某个中间结果时成本最低的方式,不一定是为特定上层操作提供该结果时成本最低的方式。

保持语义的转换

查询优化依赖于不改变查询可观察结果的转换。

常见转换包括:

谓词下推。 将筛选操作移到更靠近数据源的位置,使传递到后续算子的行更少。

投影裁剪。 移除后续操作不需要的列,以减小中间结果的行宽并减少数据传输。

连接重排序。 调整允许重排的连接的执行顺序,以减小中间结果规模,或采用更好的访问路径。

子查询转换。 将适合的子查询转换为连接或其他形式,使其能够与外围查询一起优化。

常量折叠与简化。 在语义允许的情况下,计算常量表达式并简化谓词。

分区裁剪。 排除不可能包含匹配行的表分区。

这些转换都有适用条件。SQL通常采用多重集(也称“袋”)语义,而不是纯粹的集合语义,因此,除非查询要求去重,否则必须保留重复行。NULL、三值逻辑、外连接、聚合和非确定性表达式还会带来额外限制。

例如,将外连接条件中的谓词移到后续筛选操作中,可能会删除未匹配的行,从而改变结果。已声明的唯一性约束或外键,可能使原本不安全的转换变得可行。优化器在利用约束时,必须遵循数据库系统对约束有效性及其强制执行方式的规定。

基于规则与基于成本的优化

基于规则的优化

基于规则的优化器应用预先定义的转换或优先级。例如,在存在合适索引时优先选择索引访问路径,或将符合条件的筛选操作下推到连接之前。

规则的应用开销较低,即使在复杂的优化器中也仍然发挥着基础作用。然而,固定的优先级无法可靠地兼顾数据规模、选择率、存储布局和可用内存的差异。对于少量匹配行十分高效的索引访问路径,在大多数行都满足条件时,可能反而比全表扫描更慢。

基于成本的优化

基于成本的优化通过估算资源消耗或执行时间来比较候选计划。其抽象形式为:

P∗=arg min⁡P∈P(Q)C^(P),P^*=\operatorname*{arg\,min}_{P\in\mathcal{P}(Q)}\widehat{C}(P),

其中,QQ 为查询,P(Q)\mathcal{P}(Q) 为所考察的候选计划集合,C^(P)\widehat{C}(P) 为计划 PP 的估算成本。

成本模型可以考虑:

  • 存储读写。
  • 处理器工作量,包括表达式求值和比较。
  • 内存需求,以及内存不足时向临时存储的溢写。
  • 网络通信。
  • 并行执行开销。
  • 启动延迟,以及生成全部结果行的成本。

成本通常以系统特有的单位表示,而不是以秒为单位。其主要用途是对备选方案进行排序。

优化目标同样重要。对于只请求少量行的查询,能够快速生成首批结果的计划可能更有利,即使另一计划能更快地生成完整结果。资源限制和工作负载优先级也可能进一步约束计划选择。

现代系统通常将成本估算、转换规则和启发式方法结合使用。

基数估计与统计信息

基数估计用于预测每个操作将生成多少行。这些估计会显著影响连接顺序、连接实现、内存分配和访问路径选择。

对于筛选操作,一种基本估计方式为:

N^out=Nins^,\widehat{N}_{\mathrm{out}}=N_{\mathrm{in}}\widehat{s},

其中,NinN_{\mathrm{in}} 是估计的输入行数,s^\widehat{s} 是估计的选择率,即满足谓词的行所占的比例。

优化器可以使用表行数、不同值的数量、空值比例、直方图、高频值统计、样本和多列统计信息。这些信息构成数据库元数据的一部分。

当数据分布不均或列之间存在相关性时,估计就会变得困难。例如,针对城市和邮政编码的谓词通常并非相互独立。将它们各自的选择率相乘,可能会严重低估符合条件的行数。当统计信息过时,或谓词涉及行为难以建模的表达式时,估计也可能失准。

误差可能在多次连接中累积。严重低估行数,可能导致对远大于预期的输入反复执行索引查找,或导致哈希操作超出分配的内存而向临时存储溢写数据。

更准确的估计通常有助于改善决策,但无法消除因计划搜索不充分或成本模型不准确而产生的错误。

搜索计划空间

可能的计划数量会随着参与连接的关系数量迅速增长。优化器必须在进一步搜索的潜在收益与规划时间、内存消耗之间取得平衡。

动态规划

动态规划可以先为较小的关系子集构建计划,再将其组合为更大的计划。优化器会为每个子集保留有用的备选方案,并可能根据排序等属性对这些方案加以区分。

每个子集只保留一个计划可能并不够:成本略高的中间计划,可能提供某种排序或数据分布,从而为后续操作节省大量工作。

基于Memo的优化

基于Memo的优化器将等价的逻辑表达式和备选物理实现组织到共享组中。转换规则负责添加备选方案,优化任务则在所需属性和成本界限的约束下探索这些方案。

Volcano和Cascades优化框架是这种方法中具有影响力的代表。共享表示可以避免重复探索等价子问题,并支持可扩展的规则集合。

启发式搜索与随机化搜索

对于包含大量连接的查询,穷尽搜索可能并不现实。优化器可以限制计划形态、使用贪心方法、限制搜索时间,或采用随机化算法。

限制搜索可以降低规划开销,但也可能排除优良计划。因此,优化器设计需要在优化投入与执行质量之间作出权衡。

并行与分布式优化

在并行计算中,优化器可以选择工作进程数量、划分扫描任务,并决定中间结果的交换方式。提高并行度并不总能改善性能:协调、通信和资源争用的开销可能超过其收益。

在分布式计算中,数据位置成为规划时的另一项重要考虑。分布式连接可以:

  • 将较小的输入广播给持有较大输入的工作进程。
  • 按连接键对两个输入重新分区。
  • 利用已经按兼容方式分区的输入。

优化器必须考虑通信量、数据倾斜、局部性和可用资源。即使一个计划的总工作量很小,如果某个工作进程接收的数据比例过高,实际耗时仍可能很长。

联邦查询还需要考虑远程系统在能力和成本上的差异。将操作下推到远程数据源可以减少传输的数据量,但前提是该数据源支持所需的语义和执行行为。

计划缓存与自适应执行

数据库系统通常会缓存计划,以避免重复优化。复用可以降低规划开销,但同一个计划未必适合所有参数值。对于某个值,谓词的选择率可能很低;换成另一个值,却可能匹配表中的大部分行。

系统通过不同方式应对这一问题,包括采用可复用的通用计划、针对参数的备选计划、重新编译,以及利用以往执行的反馈。模式、索引或统计信息的变化,可能使缓存计划失效,或触发重新评估。

自适应执行利用查询运行时观测到的信息,推迟某些决策,或重新审视已作出的决策。系统可以更换连接策略、调整数据交换方式,或在物化某个中间结果后重新优化剩余工作。自适应本身也有成本,而且不一定能挽回已经完成的工作所耗费的资源。

研究还将机器学习应用于基数估计、成本预测和计划选择。这些方法必须应对数据变化、陌生查询、推理开销,以及提供可靠回退机制的需求。

历史发展

基于成本的关系查询优化在20世纪70年代成为数据库的核心技术。1979年的论文《关系数据库管理系统中的访问路径选择》(Access Path Selection in a Relational Database Management System)是一个里程碑,该文介绍了IBM公司System R中的优化方法,确立了利用统计信息和估算成本选择访问路径与连接顺序的重要技术。

后续研究拓展了转换、物理算子和搜索策略的范围。可扩展的优化框架有助于将搜索机制与数据库特定规则分离。并行数据库、数据仓库和分布式分析引擎将优化范围扩展到分区、通信,以及日益多样化的执行环境。

查看计划与局限性

数据库系统通常提供 EXPLAIN 一类的功能来查看计划。这些功能可以显示算子选择、估计行数、估算成本、访问路径,以及排序或数据分布属性。带有执行性能分析的变体还能报告实际行数和耗时,但这类功能通常会执行语句,因此可能产生副作用。

比较估计行数与实际行数,有助于区分性能不佳究竟是由估计错误还是其他原因造成的。不同数据库产品的估算成本通常不具可比性。

即使是复杂的优化器,掌握的信息也并不完整。缓存内容、存储延迟、可用内存、并发工作负载和网络拥塞等运行时状况,都难以精确预测。用户定义函数和远程数据源的内部行为尤其可能难以掌握。

有些系统提供提示或计划控制功能,用于限制优化器的选择。这些功能可以使特定工作负载的表现保持稳定,但也可能在数据或硬件发生变化后,仍保留已经不合适的计划。因此,查询优化始终是在不确定性下受到约束的决策过程,而不是对最快执行速度的保证。