数据库|如何打造一款极速数据湖分析引擎( 三 ) 算法|CPU

（常见 CBO 实现架构）
Record Oriented vs Block Oriented
执行计划可以认为是一串 operator（关系代数的运算符）首尾相连串起来的执行流，前一个 operator 的 output 是下一个 operator 的 input 。传统的分析引擎是 Row Oriented 的，也就是说 operator 的 output 和 input 是一行一行的数据。
举一个简单的例子，假设我们有下面一个表和查询：
CREATE TABLE t (n int m int o int p int); SELECT o FROM t WHERE mn + 1; 例子来源： GitHub - jordanlewis/exectoy
上述查询语句展开为执行计划的时候大致如下图所示：

通常情况下，在 Row Oriented 的模型中，执行计划的执行过程可以用如下伪码表示：
next: for: row = source.next() if filterExpr.Eval(row): // return a new row containing just column o returnedRow row for col in selectedCols: returnedRow.append(row[col
) return returnedRow 根据 DBMSs On A Modern Processor: Where Does Time Go? 的评估，这种执行方式存在大量的 L2 data stalls 和 L1 I-cache stalls、分支预测的效率低等问题。
随着磁盘等硬件技术的蓬勃发展，各种通过 CPU 换 IO 的压缩算法、Encoding 算法和存储技术的广泛使用， CPU 的性能逐渐成为成为分析引擎的瓶颈。为了解决 Row Oriented 执行所存在的问题，学术界开始思考解决方案， Block oriented processing of Relational Database operations in modern Computer Architectures 这篇论文提出使用按 block 的方式在 operator 之间传递数据，能够平摊条件检查和分支预测的工作的耗时， MonetDB/X100: Hyper-Pipelining Query Execution 在此基础上更进一步，提出将通过将数据从原来的 Row Oriented ，改变成 Column Oriented ，进一步提升 CPU Cache 的效率，也更有利于编译器进行优化。在 Column Oriented 的模型中，执行计划的执行过程可以用如下伪码表示：
// first create an n + 1 result for all values in the n column projPlusIntIntConst.Next(): batch = source.Next() for ibatch.n: outCol[i
= intCol[i
+ constArg return batch // then compare the new column to the m column putting the result into // a selection vector: a list of the selected indexes in the column batch selectLTIntInt.Next(): batch = source.Next() for ibatch.n: if int1Colint2Col: selectionVector.append(i) return batch with selectionVector // finally we materialize the batch returning actual rows to the user // containing just the columns requested: materialize.Next(): batch = source.Next() for sbatch.n: i = selectionVector[i
returnedRow row for col in selectedCols: returnedRow.append(cols[col
[i
) yield returnedRow 可以看到， Column Oriented 拥有更好的数据局部性和指令局部性，有利于提高 CPU Cache 的命中率，并且编译器更容易执行 SIMD 优化等。
Pull Based vs Push Based
数据库系统中，通常是将输入的 SQL 语句转化为一系列的算子，然后生成物理执行计划用于实际的计算并返回结果。在生成的物理执行计划中，通常会对算子进行 pipeline 。常见的 pipeline 方式通常有两种：
基于数据驱动的 Push Based 模式，上游算子推送数据到下游算子基于需求的 Pull Based 模式，下游算子主动从上游算子拉取数据。经典的火山模型就是 Pull Based 模式。Push Based 的执行模式提高了缓存效率，能够更好地提升查询性能。
参考：Push vs. Pull-Based Loop Fusion in Query Engines
现代数据湖分析引擎的架构通过上一节的介绍，相信读者已经对数据湖分析引擎的前沿理论有了相应了解。在本节中，我们以 StarRocks 为例，进一步介绍数据湖分析引擎是怎么有机的结合上述先进理论，并且通过优雅的系统架构将其呈现给用户。

如上图所示， StarRocks 的架构非常简洁，整个系统的核心只有 Frontend (FE)、Backend (BE) 两类进程，不依赖任何外部组件，方便部署与维护。其中 FE 主要负责解析查询语句（SQL），优化查询以及查询的调度，而 BE 则主要负责从数据湖中读取数据，并完成一系列的 Filter 和 Aggregate 等操作。