Aug 12, 2019

Eddies 原理浅析

Paper Info

从传统架构引入

传统的数据库查询优化器包含逻辑优化与物理优化部分，逻辑优化部分负责关系代数的转化，物理优化部分根据数据库统计信息选择出一个最优的执行计划。一条 SQL 语句输入之后经过语法分析器 (parser) 生成 AST (抽象语法树)，然后经过查询优化器生成最终执行计划交由执行器执行，最终结果返回给用户。

传统架构与 Eddies

Eddies 提出了一种在执行期间进行优化的框架，在生成 AST 后简单的进行预优化然后直接交由执行器执行，在执行的过程中再对操作进行重排序达到自适应查询的效果。

背景

为什么 Eddies 提出在查询执行时候再动态适应的架构呢？实际上在查询执行过程中数据库不是稳定的状态（尤其是在分布式系统下），主要体现在一下几个方面：

  • 性能：网络 I/O 性能抖动、不同节点计算性能及磁盘 I/O 性能不同
  • 数据复杂性：存储的数据不仅仅是便于获取统计信息的数值型或者字符型数据
  • 用户接口：针对大规模系统下的 OLAP 运算，用户可能指定只需要近似结果来减少查询计算量

这些状态抖动将直接影响到：

  • 数据或元组到达的速率
  • 查询的代价(Cost)
  • 选择率(或基数)

这里重点说一下选择率的变化。如果一张表是排过序的，那么在它传输进行运算的时候，可能选择率是动态变化的。考虑下面的 SQL 语句：

select id, name
  from employee
 where salary > 10000;

从员工表中获取薪资大于 10000 的员工 id 和 name，如果员工表按照 age 排过序，那么虽然满足条件的元组散落在整张表上，但是可能年龄较大的员工往往会有相对较高的薪资，这就可能导致表前面元组与后面元组的选择率不同。

框架浅析

本文会在最后一小节通过结合实验测试结果来详细说明框架及其中的算法，在这一节本文通过一个简单的查询执行计划举例来说明 Eddies 的工作原理。 为了说明，首先考虑一个简化后的查询执行计划树（不考虑连接的属性可以将部分表直接优化掉的情况）。关系 R 先做一个选择运算，然后与关系 S、T 的连接结果连接，最终进行投影获得查询结果。

简单的查询执行树

Eddies 考虑流式处理的情况，其中有多个 eddy 充当元组的路由，它将把元组路由到当前最适合这个元组的运算符上。这里考虑 𝜎(R)、R⋈S、S⋈T 三个运算，plan1 中的 𝜎(R) 与 S⋈T 实际上是可以实现运算符间并行。但是如果计算时由于关系 T 的元组传输速率很慢，关系 R 的选择运算已经完成，并且关系 S 已经全部到达或者当前关系 T 的到达速率已经不匹配运算速率，那么可以考虑先将 S 的元组与关系 R 的元组进行连接，最终结果再与传输完成的 T 的元组进行连接以提高效率，此时的执行计划将会变成 plan2。针对不同的执行时状态，对于不同的路由顺序对应了多种执行计划。

Eddy单元模型

上述的路由计算过程相当于在执行的过程中不断的调整当前执行的计划树。另外 eddies 的计算是以元组为单位的，所以对于不同的计算路由顺序中间的结果也会不同。直观上来讲，这种使用操作重排的动态自适应方法可以很好的匹配查询执行过程中的动态性，提高查询的执行效率。

关于算法的假设

论文对实现运算符的动态重排序的场景做了一定的假设：

  • 同步阻碍
    • 比如 S 和 F 两个已排序关系连接，F 到达计算节点的速度大于 S 到达的速度，且如果连接需要取得 S 排序过后后段的数据的选择率较高，F 将会被阻塞等待 S 到达，这将影响后续的计算
  • 对称性
    • 能够满足重排的运算符应该具有对称性，论文中举了 Ripple Join 的例子。因为元组到达的速率不同，所以在重排 Join 的时候需要考虑先后计算的问题，Ripple Join 的对称性很好的解决了这样的问题

这里简单介绍一下 Ripple Join：

Ripple Join

考虑普通的嵌套循环连接的实现，外关系表需要等待内关系表元组全部到达之后才能执行循环连接计算。Ripple Join 可以改变嵌套循环连接执行的方向。如上图所示，两个关系表的嵌套循环连接可以看作一个二维数组生成的过程，传统的嵌套循环连接相当于 R 的单个元组去匹配 S 的每一个元组，这样在执行过程中如果 S 的元组没有全部到达将会直接阻塞连接，但其实改变嵌套循环的方向可以先将已经到达的元组全部计算完，这样就不会因为算法的原因将计算阻塞。 Ripple Join 的论文还提出了几种优化的变种，具体可以参看 Ripple Join 的论文。

详细说明

首先详细复述一遍 eddy 路由的架构。考虑关系 R 需要进行两个选择运算，eddy 对关系的每个元组对应每个运算符号都会设置一个 ready 位和一个 done 位，ready 位表示该元组是否能够进行这个运算，done 位表示该元组已经执行过该运算。当运算执行完成之后检查所有的 done 位，如果还有位执行的运算，该元组将流回 eddy准备路由到下一个运算，当所有的运算都执行完成将流出 eddy。

Experiment

这里通过实验进一步理解 eddies 的工作原理。在前面也说到，在查询执行过程中由于状态波动将会影响到：

  • 数据或元组到达速率
  • 查询的代价(Cost)
  • 选择率(或基数)

Experiment 1

采用上面图的运算实验架构，考虑以下查询语句：

select *
  from R
 where s1() and s2();

R 需要执行 s1、s2 两个选择运算，这里设置实验条件：

  • 到达率：不变
  • Cost
    • s1：0 - 10 动态改变
    • s2：5
  • 选择率：50%（不变）

Experiment 1

这里如果一个操作 cost 比较大，那么先执行 cost 较小的操作将元组先筛除一部分会减小总体的执行开销。 从结果可以看到，由于设置 s1 的执行代价改变，在 s1 与 s2 执行顺序固定的执行计划下效果都不是很好，Naive（原始的 eddies）由于能够动态自适应查询执行的运算符顺序，所以在 cost 较小的时候与 s1 before s2 的执行计划性能相近，在 cost 较大的时候与 s2 before s1 的执行计划性能相同。Lottery 是 eddies 针对选择率改变时候的一个优化变体，将在后面的实验中具体说明。

那么 eddy 是如何感知到选择率的改变的？论文中说是采用了一个叫做流体动力学的模型，感觉很高级，其实也就是监听发送给运算符的元组是否阻塞。实现可以采用一个队列存储传入运算符的元组，通过判断队列长度变化反应该运算符上的 cost。

Experiment 2

依然采用之前的实验架构，这里改变选择率：

  • 到达率：不变
  • Cost：5（不变）
  • 选择率
    • s1：10% - 90% 动态改变
    • s2：50%

Experiment 2

这里如果先执行选择率较低的运算，产生的中间结果将会相对较小，对于选择率较高的运算其需要匹配的元组数量也会减小，从而减小总体执行开销。 s1 与 s2 执行顺序固定的执行计划结果很容易理解，但是 Naive 的 eddies 自适应执行计划效果似乎也不是很好。主要问题在于 Naive 的 eddies 无法察觉到选择率的改变。

这里 eddies 引入了一种 lottery 的机制来感知选择率的变化。每当 eddy 路由一个元组到一个运算(比如 s1)，它将给 s1 一张奖票，如果 s1 计算完成返回了一个元组给 eddy，那么 s1 将还给 eddy 一张奖票，下一批元组到达的时候将按照概率路由到不同的运算符号。由于奖票的张数（待计算元组数）是固定的，那么如果 s1 选择率低，它持有的奖票就多，下一次路由到的元组就会多。

Naive&Lottery

上面是 Naive eddies 与 Lottery eddies 在 s1 选择率变化的情况下路由到 s1 上的元组数的对比。可以看到由于 Lottery eddies 能够通过概率的方法感知到 s1 的选择率变化，所以在 s1 选择率较高的情况下路由到 s1 的元组比较少。

Experiment 3

这个实验考虑到多个关系表的元组进行连接运算的情况，针对以下的查询语句：

select *
  from R,S,T
 where R.a = S.a
   and S.b = T.b;

eddy 单元的结构如下：

StructureOfE3

这里元组到达率与运算符开销不变，改变选择率：

plan1:

  • 选择率
    • S in SR：180%
    • S in ST：10%

plan2:

  • 选择率
    • S in SR：100%
    • S in ST：
      • (1) 10%
      • (2) 180%

Join

首先看 Plan1 的结果，和 Experiment3 一样，由于 S⋈T(Index join) 的选择率比 S⋈R(Hash join) 的选择率要小，所以 Lottery eddies 和 Index First 的计划的执行时间是最少的，但是 Lottery 相比完全将所有元组全都先进行 S⋈T 的 Index First 来说也会在开始的时候将一部分元组路由到 S⋈R(Hash join)，所以时间会稍微长一点。Plan2 的结果同理，这里不再赘述。

Experiment 4

采用 Experiment4 的实验架构，这里改变元组到达率：

  • 到达率：R 延迟 10s 开始到达
  • Cost：不变
  • 选择率
    • S in SR：100%
    • S in ST：20%

Join-arrival

执行时间结果图(左)中可以看到 Eddy 的执行时间依然在另外两种计划的中间。 比较有趣的是，从右图可以看到关系 S 的元组在到达初期路由到 S⋈T 的元组数量是骤减的，这是由于关系 R 的延迟到达让 S⋈R 运算符阻塞并不会返回任何元组，使 Lottery 机制认为 S⋈R 的选择率很低所以将元组大量路由到 S⋈T，这也是 Lottery 可以改进的地方。

总结

Eddies 推翻了经典查询优化器的架构，提出了一种 runtime optimization 的查询优化方法，这种在框架上重新定义查询优化的方法是值得肯定的。同时由于 newSQL 的兴起，不同的数据库架构对查询优化器的挑战也越来越大，因此考虑在执行器上针对当前数据库架构的查询优化是值得考虑的。