AP计算-查询编译

Efficiently Compiling Efficient Query Plans for Modern Hardware

该文章首先提出了pipeline的定义：pipeline意味着数据的处理可以直接在寄存器中进行，不需要重新搬回内存。如果多个算子可以形成一个pipeline，处理速度会大大增加。而火山模型和batch模型都无法实现这个目标。因此，该文章解决的关键问题在于：提出一种利用编译的执行模型，尽可能使多个算子形成pipeline。

首先，该文章定义了pipe breaker，pipe breaker即算子需要将数据物化到内存，比如join。通过pipe breaker，将执行计划分割成多个pipeline。

而对于同一个pipeline的算子，在执行的时候会被编译在一起形成一个代码块，该代码块可以实现在寄存器中完成对数据的处理。这听起来很神奇，这篇文章提出了一个直观的方法来实现这个目标。

Untitled.png

假设我们有如上的执行计划，并且采用如下伪代码的传统火山模型执行模式：

struct Scan{
  child: Operator
}
impl Scan {
  fn next() -> Result<Data>{
    do_scan()
  }
}

struct Filter {
  child: Operator
}
impl Filter {
  fn next() -> Result<Data> {
    let data = child.next();
    do_filter(data);
  }
}

struct Project {
	child: Operator
}
struct impl {
  fn next() {
    let data = child.next();
    do_project(data);    
  }
}

当我们展开真正的执行栈，其会类似下面所示，可以看到实际的数据处理路径。

project
｜ filter.next
｜   ｜ scan.next
｜   ｜  ｜ do_scan
｜   ｜ do_filter(data)
｜  do_project

// 有效数据处理路径
do_scan
do_filter()
do_project()

因此，如果要将以上三个算子展开成一个代码块进行执行，它大概率会长成上面有效数据处理路径的样子。

💡 很自然这种样子是一种push模式，而非pull模式

那么如何生成长成有效数据处理路径的代码？一个简单的想法是，将以上do_* 换成print do_* ，即

project
｜ filter.next
｜   ｜ scan.next
｜   ｜  ｜ print "do_scan\n"
｜   ｜ print "do_filter(data)\n"
｜  print "do_project\n"

// print result 
"do_scan"
"do_filter"
"do_project"

如果将print do_* 进一步换成print <do_*中的内容> ，就可以生成一个完整的没有函数跳转的代码块，其行为和之前的数据处理是一致的。

这种方法正是该文章中提出的方法，它将next方法重新命名为produce，print *则，命名为comsume 。如文中例子所示：

Untitled.png

这种方法被后续一些系统采用，比如spark: https://github.com/apache/spark/pull/10735

#OLAP #Compute