Adaptive Execution of Compiled Queries 论文解读

本文涉及的产品
云数据库 RDS SQL Server,基础系列 2核4GB
RDS MySQL Serverless 基础系列,0.5-2RCU 50GB
RDS PostgreSQL Serverless,0.5-4RCU 50GB 3个月
推荐场景:
对影评进行热评分析
简介: 本篇是TUM的内存数据库HyPer针对compile-based执行框架的改进。其中涉及到HyPer的动态编译和并行执行框架动态编译文章的结尾提到了编译执行系统存在的2个问题,其中之一就是:不可控的编译时间。

本篇是TUM的内存数据库HyPer针对compile-based执行框架的改进。其中涉及到HyPer的动态编译和并行执行框架

动态编译文章的结尾提到了编译执行系统存在的2个问题,其中之一就是:不可控的编译时间。

背景

在具体的应用中,基于LLVM的compiler framework虽然已经是比较快速的了,但对于复杂的查询语句,其编译的时间还是很长的,如果处理的数据量比较少,导致执行时间很短,则编译/执行的比例将会非常高,产生非常差的用户体验,可能不如解析执行的响应速度快。有些非常复杂的(自动生成)SQL,甚至无法编译出来,因此如果没有自适应编译执行的能力,compile-based的系统在实用性上是有很大缺陷的。

image.png

可以看到,整个optimize的过程+code generation的过程,相对于LLVM opt+compile,占比极低,大概是50 - 100倍的差异。

总体思路

为此HyPer中引入了解析执行的能力,它总是要先把query plan通过Codegen生成LLVM IR的表示,但可以通过快速的translation转换成一种自定义的LLVM bytecode,然后使用解析器进行解析执行,从而避免编译过程。

基于这种机制,提出了自适应切换execution mode的framework,可以有3种执行mode:

  1. 基于LLVM bytecode解析执行(高效),这是默认模式。
  2. 基于LLVM IR做无优化的编译,生成machine code
  3. 基于LLVM IR做有优化的编译,生成更高效的machine code

image.png

可以看到,3种执行模式,bytecode的translation是很快的,而非优化编译/优化+编译,则要慢很多。

这样其实编译执行 vs 解析执行,本质就是吞吐量 vs 延迟, 编译时间会增加单条query的rt,但编译的代码执行效率更高可以产生更高计算吞吐,解析执行可以快速响应因此对rt影响更小,但代码效率低会影响吞吐。

此外,由于HyPer的mosel-driven的并行执行框架,在compile期间是串行的,所有worker thread都要等待直到编译完成,而解析方式可以立即开始并行执行。

理想情况下,应该是:

  • 对于小型的query(数据量小),使用解析执行,保证低延迟
  • 对于大型的query,使用优化编译执行,保证高吞吐量
  • 对于中型的query,使用非优化编译执行,相当于前两者的折中

自适应方案

HyPer中基于动态编译 + morsel驱动的并行执行可以用下图理解:

image.png

plan会被优化器编译为多个pipeline job(上图中右侧各颜色所示),每个线程Tx针对各个morsel粒度的数据,执行编译生成的一个个的pipeline job。

在执行过程中,针对每个pipeline job,动态利用feedback进行推断,选择后续是否需要切换到编译模式来更快速的的执行,这种基于morsel的方式是细粒度的,这样可以使一个query中,长时间的part和短时间的part,使用不同的execution mode,效率达到最优。

为了实现自适应编译框架,需要3个基本组件:

  1. 高效的bytecode 解析器
  2. Track 执行过程中的信息,从而动态决定是否切换,而不是提前利用optimizer的cost/card estimation来静态决定
  3. 根据推断动态切换execution mode

基本模式是,所有query总是以解析模式开始,多worker threads并行执行,在执行中通过收集+推断,当判断后续采用compile方式更有益时,则使用一个worker thread开始异步编译过程,其他worker继续解析执行,当编译完成时,后续所有worker都切换到compiled function继续执行。这种处理方式是以pipeline为单元的,并以morsel为监控+推断+切换的基本单位。

  • Track Query progress

基于HyPer morsel-driven的并行执行方式,一个pipeline一个pipeline的处理,每个pipeline中,各个worker thread在处理完一个morsel后,要更新相关的执行timing信息,而由一个特定的worker thread,在完成每个morsel后,要进行推断过程。

  • 切换

由于各个worker thread在处理morsel时是相互独立的,他们各自使用什么mode来来执行时无关的,因此只要执行的语义相同,切换就会很自然,各种执行方式都是等价的,HyPer中使用一个handle结构来做了抽象,其中包含了不同execution mode的执行函数,通过切换执行函数的指针,即可很自然完成切换,如下图所示

image.png

  • 切换规则

在每个morsel处理完成时,一个worker thread要判断是否进行切换,就是通过feedback估计当前pipeline中,tuple的处理速率,由于每个pipeline的起点 -> 终点都是物化点,morsel的数据量已知,因此可以根据当前速率,预估剩余的执行时间,也会估计compilation time + compiled code的执行加速比(经验估计),然后计算其他2种mode的执行时间,如果更优则开始启动编译。在编译的同时,其他worker thread继续解析执行,具体算法如下:

image.png

这里r0/r1/r2是处理tuple的速率,c1/c2是编译时间,t0/t1/t2是计算的剩余执行时间。

  • 高效的解析执行

HyPer使用了一种对LLVM IR进行对等translation的方式,转换为bytecode的形式(类似informix stored procedure),解析器通过对OPCODE的解析来做switch case的执行逻辑,相当于java的VM。

image.png

上图是HyPer VM中解析OPCODE并执行的代码片段,可以看到有大量的指令类型。

性能

image.png

上图是对TPCH Q11的3种执行mode下的性能profiling,optimized compilation没有给出因为编译时间实在太长。从图中可以看到这种细粒度(morsel)的控制,可以让长的执行部分(scan partsupp1, scan partsupp2) 使用compiled code,短的(hash table scan)则是解析执行,混合起来得到最佳效果。

遥凌
+关注
目录
打赏
0
0
0
0
40
分享
相关文章
文献解读-Sentieon DNAscope LongRead – A highly Accurate, Fast, and Efficient Pipeline for Germline Variant Calling from PacBio HiFi reads
PacBio® HiFi 测序是第一种提供经济、高精度长读数测序的技术,其平均读数长度超过 10kb,平均碱基准确率达到 99.8% 。在该研究中,研究者介绍了一种准确、高效的 DNAscope LongRead 管道,用于从 PacBio® HiFi 读数中调用胚系变异。DNAscope LongRead 是对 Sentieon 的 DNAscope 工具的修改和扩展,该工具曾获美国食品药品管理局(FDA)精密变异调用奖。
76 2
文献解读-Sentieon DNAscope LongRead – A highly Accurate, Fast, and Efficient Pipeline for Germline Variant Calling from PacBio HiFi reads
【文献学习】Channel Estimation Method Based on Transformer in High Dynamic Environment
一种基于CNN和Transformer的信道估计方法,用于在高度动态环境中跟踪信道变化特征,并通过实验结果展示了其相比传统方法的性能提升。
129 0
Adaptive Statistics
Adaptive Statistics
49 0
OneEE: A One-Stage Framework for Fast Overlapping and Nested Event Extraction 论文解读
事件抽取(EE)是信息抽取的基本任务,旨在从非结构化文本中抽取结构化事件信息。大多数先前的工作集中于抽取平面事件,而忽略了重叠或嵌套的事件。
196 0
New Dynamic Programming Algorithm for the Generation of Optimal Bushy Join Trees
MySQL无疑是现在开源关系型数据库系统的霸主,在DBEngine的最新排名中仍然稳居第2位,与第3位SQL Server的积分差距并不算小,可以说是最受欢迎,使用度最高的数据库系统,这一点看看有多少新型数据库要兼容MySQL的协议和语法就知道了。
382 0
New Dynamic Programming Algorithm for the Generation of Optimal Bushy Join Trees
Efficiently Compiling Efficient Query Plans for Modern Hardware 论文解读
这应该是SQL查询编译的一篇经典文章了,作者是著名的Thomas Neumann,主要讲解了TUM的HyPer数据库中对于CodeGen的应用。 在morsel-driven那篇paper 中,介绍了HyPer的整个执行框架,会以task为单位处理一个morsel的数据,而执行的处理逻辑(一个pipeline job)就被编译为一个函数。这篇paper则具体讲如何实现动态编译。
496 0
Efficiently Compiling Efficient Query Plans for Modern Hardware 论文解读
Morsel-Driven Parallelism: A NUMA-Aware Query Evaluation Framework for the Many-Core Age 论文解读
这篇paper介绍了TUM的内存数据库系统HyPer中使用的,基于小块数据(morsel)来驱动的并行查询执行框架。用来解决many-cores(NUMA)环境下,分析型查询的scalability问题。
1617 0
Morsel-Driven Parallelism: A NUMA-Aware Query Evaluation Framework for the Many-Core Age 论文解读
AI助理

你好,我是AI助理

可以解答问题、推荐解决方案等