高级数据库十五:查询优化器(一)

Optimizer Implementation(Part I)

背景

在讲述这个优化器的时候,就必须先了解查询过程。在本系列的数据库四:浅谈数据库查询过程(Query Processing)中大致地说明了一下数据库的查询过程,但是没提到查询优化器的具体策略与实现。

对于查询而言,我们期望优化器的作用是找到最小代价的正确执行方案。但是这是一个NP完全问题,所以没有一个优化器能够真正地找到真正的最佳方案。

关于OLTP的查询优化会更加简单,一般来说选取最好的索引,JOIN操作也大多使用外键,用一些简单的策略就行。

比如,大家可以画一棵关系代数查询树,如果我们将选择操作尽可能下放到深处,则在进行笛卡尔乘或者JOIN的时候,参与运算的数据就少了。这就是heuristic optimazation。

所以在这儿我们将说明OLAP查询的优化策略。

优化器基础

优化器粒度

单查询

  • 更小的搜索空间。
  • DBMS不能在查询中重复使用结果。
  • 为了解决资源争夺问题,成本模型必须考虑当前正在运行的内容。

多查询

  • 如果有很多类似的查询,效率会更高。
  • 搜索空间要大得多。
  • 用于扫描共享(之后的文章会提到,大致就是多个查询共用一个扫描表的结果,而不是各自扫描一次)

优化时间

静态优化

  • 在执行之前选择最佳计划。
  • 计划质量取决于成本模型的准确性。
  • 可以使用准备好的支票分摊执行。

动态优化

  • 主要在流式数据的时候使用
  • 查询执行时,即时选择运营商计划。
  • 将重新优化多次执行。
  • 难以实现/调试(非确定性)

混合优化

  • 使用静态算法编译。
  • 如果估计>阈值的误差,则重新优化。

计划稳定

提示

  • 运行数据库系统管理员帮助优化器进行决策,比如,我希望用hash表进行JOIN等
  • mysql、sqlserver似乎都支持这种方法

固定优化器版本

  • 设置优化器版本号并将查询逐个迁移到新优化器。比如,虽然用了新版本的数据库,但是对于某种特定的查询,我们发现了旧版本的优化器似乎更快,则可以将版本调回去。

向后兼容的计划

  • 从旧版本保存备份查询计划,并将其提供给新的DBMS。

优化器搜索策略

Heuristics

论文Query Processing In A Relational Database Management System

之前举了一个关系代数查询树的例子,说的就是Heuristics优化方法。它定义了一些规则,通过静态的方式来进行优化:

  • 尽早进行选择,越严格的限制应该越早进行
  • 在连接之前执行所有选择
  • 谓词/限制/投影下推
  • 基于基数加入排序

Oracle在早起非常受欢迎的原因就是因为它使用了这种方法。

优点:

  • 易于实施和调试。
  • 效果相当好,对于简单的查询很快。

缺点:

  • 依靠玄学常数来预测计划决策的有效性。
  • 当操作之间存在复杂的相互依赖关系时,几乎不可能产生好的查询计划。

论文Access path selection in a relational database management system

使用静态规则执行初始优化,然后使用动态规划来确定表格的最佳连接顺序。

  • 第一个基于成本的查询优化器
  • 使用分而治之搜索方法进行自底向上(向前链接)

现在也非常常用的技术,MySQL、SQLite都用这个。

SYSTEM R OPTIMIZER

假设都没有索引,则得到数据的方式就是线性扫描。

然后将所有的JOIN操作的可能性都列出来,并找出最少代价的JOIN策略。其中也包括每个具体的JOI操作的算法。

因为有ORDER BY,所以要进行排序

优点:

  • 通常找到一个合理的计划,而不必执行详尽的搜索。

缺点:

  • 所有与启发式方法相同的问题。
  • 左深连接树并不总是最佳的。
  • 必须考虑成本模型中数据的物理属性(例如排序顺序)。

Randomized Algorithms

执行随机遍历查询的所有可能(有效)计划的解决方案空间。
继续搜索,直到达到代价阈值或优化器运行一段特定的时间。

例如:Postgres的遗传算法。

优点:

  • 随机跳转搜索空间允许优化器跳出局部最小值(这个地方可以去看看遗传算法的文章来理解原理)。
  • 低内存开销(如果没有历史保存)。

缺点:

  • 很难确定为什么DBMS可能选择了一个特定的计划。
  • 必须做额外的工作来确保查询计划是确定性的。
  • 仍然必须执行正确性规则。

SIMULATED ANNEALING

用Heuristics方发生成的最初的查询计划,然后通过SQL运算符的随机排列(例如,交换两个表的连接顺序)来产生新的解。

  • 始终接受降低成本的更改
  • 只接受一个可能会增加成本的变化。
  • 拒绝违反正确性的任何更改(例如,排序顺序)

POSTGRES OPTIMIZER

更复杂的查询使用遗传算法来选择连接顺序的。

在每一轮开始时,生成查询计划的不同版本,选择成本最低的计划,并用其他计划进行排列。重复该操作。

  • 变异函数只产生有效的计划。

首先使用转换规则重写逻辑查询计划。

  • 引擎检查是否允许转换,然后才能应用。
  • 这一步从来不考虑成本。

然后执行基于成本的搜索,从而将逻辑查询计划映射到物理查询计划。

优点:

  • 在快速表现的实践中运作良好。

缺点:

  • 难以为转换指定优先级
  • 如果不计算多重成本估算,一些转换难以评估。
  • 规则维护是一个巨大的痛苦。

STARBURST OPTIMIZER

用此方法实现更好地System R optimizer。

阶段1:查询重写

  • 计算查询的SQL块级关系微积分表示。

阶段2:计划优化

  • 一旦查询重写完成,执行System RR风格的动态规划阶段。

使用唯一的一个搜索空间,统一逻辑- 逻辑和逻辑- 物理转换的概念。 不需要单独的阶段,因为一切都是转换。

这种方法产生了更多的转换,因此大量使用memoization来减少冗余工作。

VOLCANO OPTIMIZER

通用基于成本的查询优化器,基于关系代数上的等价规则。

  • 轻松添加新的操作和等价规则。
  • 计划过程中将数据的物理属性视为一流的实体。
  • 使用分枝定界搜索的自顶向下方法(反向链接)。

不过这种方法似乎只在实验室或者学校中才有用到,工业界似乎没有用过这种方式。

优点

  • 使用声明性规则来生成转换。
  • 通过高效的搜索引擎实现更好的可扩展性。 减少使用记忆的冗余估计。

缺点:

  • 在优化搜索之前,所有等价类都完全展开以生成所有可能的逻辑运算符。
  • 不容易修改谓词。

TOP-DOWN VS. BOTTOM-UP

自上而下的优化:从你想要的最终结果开始,然后在树上寻找最适合你的目标。

自下而上的优化:从一无所有开始,然后制定计划以达到您想要的最终结果。

本站公众号
   欢迎关注本站公众号,获取更多程序园信息
开发小院