本篇是TUM的内存数据库HyPer针对compile-based执行框架的改进。其中涉及到HyPer的动态编译和并行执行框架
动态编译文章的结尾提到了编译执行系统存在的2个问题，其中之一就是：不可控的编译时间。
背景
在具体的应用中，基于LLVM的compiler framework虽然已经是比较快速的了，但对于复杂的查询语句，其编译的时间还是很长的，如果处理的数据量比较少，导致执行时间很短，则编译/执行的比例将会非常高，产生非常差的用户体验，可能不如解析执行的响应速度快。有些非常复杂的（自动生成）SQL，甚至无法编译出来，因此如果没有自适应编译执行的能力，compile-based的系统在实用性上是有很大缺陷的。
可以看到，整个optimize的过程+code generation的过程，相对于LLVM opt+compile，占比极低，大概是50 - 100倍的差异。
总体思路
为此HyPer中引入了解析执行的能力，它总是要先把query plan通过Codegen生成LLVM IR的表示，但可以通过快速的translation转换成一种自定义的LLVM bytecode，然后使用解析器进行解析执行，从而避免编译过程。
基于这种机制，提出了自适应切换execution mode的framework，可以有3种执行mode：
- 基于LLVM bytecode解析执行（高效），这是默认模式。
- 基于LLVM IR做无优化的编译，生成machine code
- 基于LLVM IR做有优化的编译，生成更高效的machine code
可以看到，3种执行模式，bytecode的translation是很快的，而非优化编译/优化+编译，则要慢很多。
这样其实编译执行 vs 解析执行，本质就是吞吐量 vs 延迟， 编译时间会增加单条query的rt，但编译的代码执行效率更高可以产生更高计算吞吐，解析执行可以快速响应因此对rt影响更小，但代码效率低会影响吞吐。
此外，由于HyPer的mosel-driven的并行执行框架，在compile期间是串行的，所有worker thread都要等待直到编译完成，而解析方式可以立即开始并行执行。
理想情况下，应该是：
- 对于小型的query(数据量小），使用解析执行，保证低延迟
- 对于大型的query，使用优化编译执行，保证高吞吐量
- 对于中型的query，使用非优化编译执行，相当于前两者的折中
自适应方案
HyPer中基于动态编译 + morsel驱动的并行执行可以用下图理解：
plan会被优化器编译为多个pipeline job(上图中右侧各颜色所示），每个线程Tx针对各个morsel粒度的数据，执行编译生成的一个个的pipeline job。
在执行过程中，针对每个pipeline job，动态利用feedback进行推断，选择后续是否需要切换到编译模式来更快速的的执行，这种基于morsel的方式是细粒度的，这样可以使一个query中，长时间的part和短时间的part，使用不同的execution mode，效率达到最优。
为了实现自适应编译框架，需要3个基本组件：
- 高效的bytecode 解析器
- Track 执行过程中的信息，从而动态决定是否切换，而不是提前利用optimizer的cost/card estimation来静态决定
- 根据推断动态切换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的执行函数，通过切换执行函数的指针，即可很自然完成切换，如下图所示
- 切换规则
在每个morsel处理完成时，一个worker thread要判断是否进行切换，就是通过feedback估计当前pipeline中，tuple的处理速率，由于每个pipeline的起点 -> 终点都是物化点，morsel的数据量已知，因此可以根据当前速率，预估剩余的执行时间，也会估计compilation time + compiled code的执行加速比（经验估计），然后计算其他2种mode的执行时间，如果更优则开始启动编译。在编译的同时，其他worker thread继续解析执行，具体算法如下：
这里r0/r1/r2是处理tuple的速率，c1/c2是编译时间，t0/t1/t2是计算的剩余执行时间。
- 高效的解析执行
HyPer使用了一种对LLVM IR进行对等translation的方式，转换为bytecode的形式（类似informix stored procedure），解析器通过对OPCODE的解析来做switch case的执行逻辑，相当于java的VM。
上图是HyPer VM中解析OPCODE并执行的代码片段，可以看到有大量的指令类型。
性能
上图是对TPCH Q11的3种执行mode下的性能profiling，optimized compilation没有给出因为编译时间实在太长。从图中可以看到这种细粒度(morsel)的控制，可以让长的执行部分(scan partsupp1, scan partsupp2) 使用compiled code，短的(hash table scan)则是解析执行，混合起来得到最佳效果。
