网站使用教程,企业网站大全,梅州在建高铁最新消息,太原网站建设总部在哪在关系型数据库中#xff0c;查询调度器与计划执行器#xff0c;有着与查询优化器同样重要的地位#xff0c;随着计算机硬件技术的飞速进步#xff0c;这两大模块的重要性日益凸显#xff0c;成为提升数据库性能的关键所在。接下来#xff0c;本文将由来自 OceanBase 的技…在关系型数据库中查询调度器与计划执行器有着与查询优化器同样重要的地位随着计算机硬件技术的飞速进步这两大模块的重要性日益凸显成为提升数据库性能的关键所在。接下来本文将由来自 OceanBase 的技术专家和我们一同回顾并探讨执行器技术发展历程中的那些重要变化。 在关系数据库中当大家提到SQL查询自然而然的想到查询优化器毋庸置疑这是关系数据计算中非常重要并且复杂的一个模块它决定了查询关系以哪种方式执行能够得到一个最优的结果。但是在关系计算的过程中还有两个同等重要的模块那就是查询调度器和计划执行器。
在关系数据库发展的早期受制于计算机IO能力的约束计算在查询整体的耗时占比并不明显这个时候调度器和执行器的作用被弱化一个查询的好坏更主要取决于优化器对执行计划的选择好坏。但是在今天随着计算机硬件的发展调度器和执行器也逐渐彰显了它们的重要地位这里我们重点介绍下数据库执行器发展过程中的一些演变。 绕不开的火山
Volcano Model是一种经典的基于行的流式迭代模型(Row-BasedStreaming Iterator Model)在我们熟知的主流关系数据库中都采用了这种模型例如OracleSQL Server, MySQL等。
在Volcano模型中所有的代数运算符(operator)都被看成是一个迭代器它们都提供一组简单的接口open()—next()—close()查询计划树由一个个这样的关系运算符组成每一次的next()调用运算符就返回一行(Row)每一个运算符的next()都有自己的流控逻辑数据通过运算符自上而下的next()嵌套调用而被动的进行拉取。 上图展示了Spark1.0的查询迭代器模型(OceanBase0.5中采用了相同的结构)这是一个最简单的火山模型例子拉取数据的控制命令从最上层的Aggregate运算符依次传递到执行树的最下层而数据流动的方向正好相反。
火山模型中每一个运算符都将下层的输入看成是一张表next()接口的一次调用就获取表中的一行数据这样设计的优点是
每个运算符之间的代数计算是相互独立的并且运算符可以伴随查询关系的变化出现在查询计划树的任意位置这使得运算符的算法实现变得简单并且富有拓展性。数据以row的形式在运算符之间流动只要没有sort之类破坏流水性的运算出现每个运算符仅需要很少的buffer资源就可以很好的运行起来非常的节省内存资源。
但是这种运算符的嵌套模型也有它的缺点
火山模型的流控是一种被动拉取数据的过程每行数据流向每一个运算符都需要额外的流控操作所以数据在操作符之间的流动带来了很多冗余的流控指令。运算符之间的next()调用带来了很深的虚函数嵌套编译器无法对虚函数进行inline优化每一次虚函数的调用都需要查找虚函数表同时也带来了更多的分支指令复杂的虚函数嵌套对CPU的分支预测非常不友好很容易因为预测失败而导致CPU流水线变得混乱。这些因素都会导致CPU执行效率低下。
通常一个查询的直接开销主要取决于两个因素第一个因素就是跨存储和计算操作符之间的数据传输开销另一个因素就是数据运算所花费的时间。
火山模型最早于1990年Goetz Graefe在Volcano, an Extensible and Parallel Query Evaluation System这篇论文中提出在90年代早期计算机的内存资源十分昂贵相对于CPU的执行效率IO效率要差得多因此运算符和存储之间的IO交换是影响查询效率的主要因素IO墙效应火山模型将更多的内存资源用于IO的缓存设计而没有优化CPU的执行效率是在当时的硬件基础上很自然的权衡。
随着硬件的发展计算机的内存容量变得越来越大更多的数据可以直接存储在内存中而单核CPU的运算能力并没有显著提升这个时候CPU对执行效率的影响就变得更加重要因此越来越多对CPU执行效率的优化被提出。 操作符融和
优化操作符的执行效率最简单有效的方法就是减少执行过程中操作符的函数调用。由于ProjectOp和FilterOp在计划树中最为常见的两个操作符因此在OceanBase1.0中我们将这两种操作符融合在其它特定的代数操作符中这大大减少了计划树中的运算符的个数以及运算符之间的next()嵌套调用同时PorjectOp和FilterOp变成每个操作符内部的一种能力这也增强了代码局部性能力优化了CPU的分支预测能力。 上图展示了select count(*) from store_sales where ss_item_sk1000;这条查询在OceanBase1.0的执行计划操作符从原来的4个变成了2个而FilterOp和SelectOp成为了操作符中的一个局部运算。
RowSet迭代
在火山模型的基础上另一种简单有效的优化方式就是RowSet机制简而言之就是每一次数据流的传递不再是单行的形式而是若干的row组成的集合这使得运算更多的停留在next()内部而不是在函数调用间频繁的切换从而保证代码局部性和减少函数间调用次数。
RowSet机制将数据在各个环节的流向变成了一个局部范围的循环操作这迎合了现代编译器技术和CPU动态指令预测技术对简单循环指令的极致优化同时RowSet的构造可以通过CPU的SIMD指令进行加速这也比单行数据在内存中的拷贝更加高效这使得一些结果集比较大的查询执行效率能够明显提升。
推送模型
推送模型最早在一些流媒体计算中被使用随着大数据时代的来临在一些基于内存设计的OLAP数据库也被大量使用起来例如HyPer、LegoBase等。 上图展示了拉取模型和推送模型两种不同的控制流和数据流方向从图中我们可以看出拉取模型的控制流程更符合查询执行的直观印象上层运算符按需的向下层运算符获取数据并执行这本质是一层层的函数嵌套调用。而推送引擎刚好相反通过将上层的计算下推到数据产生的操作符中由数据的最终生产者驱动上层运算符对数据进行消费。
为了更直观的比较拉取模型和推送模型对代码结构的影响我们将图1中提到的简单查询各个运算符中next()接口的实现展开成伪代码如下图所示 通过上图的对比很容易可以看出相比于拉取模型推送模型改变了数据迭代过程中的嵌套调用关系大大简化了查询过程中的指令跳转流程从而使得推送模型有更好的代码局部性优化了CPU执行效率。但是推送模型实现也更为复杂Hyper系统通过设计模式中的Visitor模式来实现了计算推送引擎基本思想是每个operator提供了两个接口produce()用来生产数据consume()接口用来消费数据和拉取模型不同的是consume()并不像next()那样需要关心流控逻辑而只用关心operator本身的关系代数逻辑流控逻辑被produce()接管。
这里有个问题是对于一些本身和流控相关的operator很难用这种模型实现或者说反而执行效率不如拉取模型的高例如limit、merge join、nested loop join等操作其关系代数运算本身就和流控相关查阅了Hyper相关论文作者并没有详细解释怎么去解决这个问题我的猜测是Hyper处理的场景是OLAP为主在该场景下流控operator出现概率是较少的不用特别去关注它们的执行效率并且在一些极端场景中可以将这些运算在其它算子中做特殊处理。
拉取推送模型融合
对于一个通用的关系数据库可能不得不考虑推送模型中这些缺点因为在OLTP场景下merge join、nested loop join这类操作出现的频率可能远远高于hash join操作所以在通用数据库的执行引擎中融合使用拉取模型和推送模型是一个较好的选择在一些比较耗时的物化操作中(例如Hash Join中的hash table构建Aggregate操作等)通过next()接口调用向下层传递一个callback函数将耗时的阻塞运算通过callback下压到下一个阻塞操作符中当下层运算符生产好数据后再依次调用callback list中的回调函数。
而对于limit、merge join、nested loop join这类运算则不会通过callback下压这种实现方式还有一个好处就是原有的火山模型并不需要大改同时也能发挥出推送模型的一些优势这也是一个比较自然的权衡选择。
编译执行
拉取模型和推送模型影响的是执行流程的代码布局但只要是解释执行就无法避免运算符之间的虚函数调用。随着计算机硬件的发展内存变得越来越大这意味着越来越多的数据可以直接cache在内存中而访问磁盘的频率被大幅度的降低这个时候“IO墙”的效应被削弱而由于解释执行无法感知CPU寄存器高频的内存访问使CPU和内存之间形成了“内存墙”效应为了解决这个问题越来越多的内存数据库开始使用编译执行来优化自己的查询效率例如HyPer、MemSQL、Hekaton、Impala、Spark Tungsten等。
相比于解释执行编译执行具有以下优点
1. inline虚函数调用在火山模型中处理一行数据最少需要调用一次next()。这些函数的调用是由编译器通过虚函数调度实现(vtable)而编译执行的过程中没有函数调用并且大量裁剪了解释执行中的流控指令这使得CPU执行会更加高效。
2.内存和CPU寄存器中的临时数据在火山模型中运算符在传递行数据的时候都需要将行数据存储在一个内存buffer中每一次执行至少需要访问一次内存而编译执行没有数据的迭代过程临时数据被直接存放在CPU寄存器中(当然前提是寄存器的数量足够多)而直接访问寄存器的效率要比访问内存高一个数量级。
3. 循环展开(Loop unrolling)和SIMD当运行简单的循环时现代编译器和CPU是令人难以置信的高效。编译器会自动展开简单的循环甚至在每个CPU指令中产生SIMD指令来处理多个元组。CPU的特性比如管道(pipelining)、预取(prefetching)以及指令重排序(instruction reordering)使得运行简单的循环非常地高效。然而编译器和CPU对复杂函数调用的优化极少而火山模型具有非常复杂的流控调用。
在OceanBase2.0中我们利用LLVM对执行引擎中的表达式运算和PL也进行了编译执行的优化。这里主要介绍下OceanBase的表达式编译执行 在编译阶段主要有三个步骤 1. IR代码生成对于表达式(c1c2)*c1(c1c2)*3我们假设所有的类型都为bigint通过分析表达式语义树使用LLVM codegen的API生成IR代码如图(a)。 2. 代码优化我们可以看到c1c2表达式做了两次计算而这个表达式是可以作为公共表达式进行抽取的经过LLVM 优化后IR代码如图(b), 只进行了一次c1c2的计算总的执行命令也得到减少。另外使用表达式解释执行时所有的中间结果都需要在内存中物化而编译后的代码可以将中间结果保存在CPU的寄存器中直接用于下一步的计算大大的提升了执行效率。LLVM还提供了很多类似的优化我们都可以直接使用从而大大提升表达式的计算速度。 3. 即时编译 通过LLVM中ORC(On-RequestCompilation) JIT对优化IR代码进行即时编译生成可执行机器码并获取该函数指针。 结果对比
我们使用TPC-H lineitem表1G数据(约600w行)对不同数据库在同样的测试环境进行了性能测试对比执行SQL:
SELECT SUM(CASE WHEN l_partkey IN(1,2,3,7) THEN l_linenumber l_partkey 10 ELSE l_linenumber l_partkey 5 END) AS result
FROM lineitem; 从上图的结果可以看出在大数据量的情况下编译执行相比于解释执行有明显的优势当数据量变得更大的时候这种优势会更加明显。但编译执行也有它本身的缺点
单纯的将Volcano模型编译成代码块可能会带来函数inline后代码成倍增长反而使得执行效率很难提升。因此单纯的拉取模型并不适合编译执行拉取和推送结合是一个很好的选择。对于编译执行感兴趣的同学强烈推荐阅读Hyper作者Thomas Neumann的一篇论文Efficiently CompilingEfficient Query Plans for Modern Hardware在这篇论文中作者详述了一些复杂operator的优化技巧以及如何写编译执行代码能够使执行效率最大化。编译执行的binary code生成非常耗时往往是10ms级别的时间开销对于OLAP型数据库而言编译消耗的时间并不算太坏因为查询主要时间消耗来自于数据的计算而对于OLTP型数据库在一些高频的小数据查询中这样的编译耗时是无法容忍的OceanBase的解决方案是通过Plan Cache机制将编译的结果缓存并复用消除同一个查询的编译次数。 写在最后
软件技术的发展总是和硬件技术的发展紧密结合在一起的迎合硬件技术的发展而改变软件技术栈的相应策略能够使得设计的系统获得更大的受益。虽然OceanBase不是一个单纯的内存数据库但是通过合理的分区方式我们可以将用户访问较热的数据cache在内存中使其近似于一个分布式的纯内存数据库因此针对于内存数据库设计的这些优化思想也同样适合OceanBase的架构模型。
现在OceanBase正在基于这些学术上的新思想做更多工程化的实践比如更加普及的编译执行计算下推分布式并行执行等技术.同时我们也在关注列式存储格式对数据库执行引擎技术的影响探索将列存计算引擎的一些优势融入到OceanBase的方法强化OceanBase在分析型计算场景的执行能力突出其HTAP数据库的定位。
