为什么优化器有时会选择一个糟糕的计划？

基于成本的优化器依赖于对每个操作将产生多少行的估计。当数据倾斜或列之间存在关联时，这些估计可能会有很大偏差，并且错误会在连接中累积。错误的估计可能导致优化器选择一个糟糕的连接顺序或访问路径，即使该计划在纸面上看起来很便宜。

为什么连接排序要使用动态规划？

可能的连接顺序数量随表的数量呈组合式增长，因此穷举搜索是不可行的。动态规划通过较小子集的最佳计划来构建较大关系集的最佳计划，从而显著减少工作量，同时仍能为典型查询大小找到一个好的（通常是最佳的）连接顺序。

基于成本的查询优化在查询的等效执行计划空间中进行搜索，并利用数据统计信息和执行成本模型，选择估计成本最低的计划。

用 PaperMind 寻找选题即将推出Find papers & topics

Tools & resources

Learn & explore

视频即将推出

基于成本的查询优化是从数据统计信息和成本模型中，估计查询的替代等效计划的执行成本，并选择估计成本最低的计划的过程，通常通过动态规划选择连接顺序。

本主题涵盖优化器如何选择计划：由关系代数等价性和替代物理操作符生成的计划搜索空间、对计划进行评分的成本模型（主要考虑I/O和CPU）、基于统计信息和直方图的基数和选择性估计，以及System R引入的连接顺序枚举的动态规划方法。它不包括操作符本身的实现以及超出计划生成范围的规则驱动逻辑重写。

System R动态规划优化: Selinger的优化器使用动态规划自下而上地枚举连接顺序，为每个关系子集（以及每个有趣的排序顺序）保留最便宜的计划，这使得搜索大型连接顺序空间变得可行。
基数和选择性估计: 优化器使用表统计信息、直方图和选择性公式来估计每个操作产生的元组数量；这些估计驱动成本模型，并且是优化错误的主要来源。
成本模型和搜索策略: 计划通过结合I/O、CPU和内存效应的成本模型进行评分；除了System R的动态规划，基于转换的优化器通过重写规则探索计划，以将优化扩展到更丰富的操作符和分布式设置。

优化器是允许用户编写声明性SQL而无需指定如何执行它的组件；其成本估计和搜索的质量直接决定了大型数据库上的查询是否快速，因此基于成本的优化是数据库系统中最受研究且商业上最重要的部分之一。

Selinger及其同事于1979年提出的System R优化器引入了基于成本的优化，包括动态规划连接排序和基于选择性的成本估计，从而定义了该领域。后来基于转换的优化器，如Volcano和Cascades，泛化了搜索，而当前关于基数估计（包括学习模型）的持续工作则解决了该框架的核心弱点。

基数估计与自适应执行: 由于基于成本的优化仅在其大小估计准确时才有效，而对于相关数据，这些估计往往不准确，因此研究人员争论是应该投入更多精力改进统计数据和机器学习估计器，还是更多地依赖自适应的运行时重新优化，在执行过程中纠正不良计划。

为什么优化器有时会选择一个糟糕的计划？: 基于成本的优化器依赖于对每个操作将产生多少行的估计。当数据倾斜或列之间存在关联时，这些估计可能会有很大偏差，并且错误会在连接中累积。错误的估计可能导致优化器选择一个糟糕的连接顺序或访问路径，即使该计划在纸面上看起来很便宜。
为什么连接排序要使用动态规划？: 可能的连接顺序数量随表的数量呈组合式增长，因此穷举搜索是不可行的。动态规划通过较小子集的最佳计划来构建较大关系集的最佳计划，从而显著减少工作量，同时仍能为典型查询大小找到一个好的（通常是最佳的）连接顺序。