CMU15-721 Note4 | Query Execution & Processing I

文章发布时间:

2024-07-26

最后更新时间:

2024-09-12

文章总字数:

1.1k

预计阅读时间:

3 分钟

页面浏览: 加载中...

1. 操作节点(operator)执行

在OLAP系统中，顺序扫描是最基础最主要的查询执行方法。通过扫描大块数据并采取必要的操作来获取需要的结果。

为了高效的查询执行，需要最小化从硬盘或远程对象存储获取的数据量，同时最大化对硬件的利用。

Andy’s (unscientific) Top-3 execution optimizations

3种加速加速查询的技术：

查询执行基于生成的查询计划。相关术语：

提供对OLAP工作负载上内存中DBMS的执行瓶颈的低级别分析。研究结果表明，当时的DBMS针对现代CPU架构是如何错误地设计的。

CPU将指令组织到流水线阶段，目标是通过屏蔽无法在单个周期内完成的指令中的延迟，使处理器的所有部分在每个周期内保持繁忙。超标量处理器支持多条流水线，将会在一个周期内并行执行相互无依赖的多条指令(乱序执行)。

依赖：如果一条指令依赖于另一条指令，CPU不能将其立即推入流水线
分支预测：CPU尝试预测程序分支并将其放入流水线。如果预测出错，需要抛弃所有推测出的工作并清空流水线。比如：选择性扫描导致的分支预测错误；不同数据类型支持导致的过多指令。(因为分支预测，通常三目运算和switch比if-else性能更好)

两种处理方向：

自顶向下
- 从子节点拉取数据，父节点在子节点返回元组前会阻塞
- 总是使用调用函数的方式传递元组
- 使用LIMIT控制输出非常简单
- Next()通常是虚函数，会带来额外开销(虚函数表)
- 调用Next()时通常会有分支开销
自底向上
- 子节点向上推送数据
- 可以在for循环中融合操作节点，支持流水线中缓存和寄存器的更紧密的控制
- 无法确切控制中间结果集大小
- 某些操作节点很难实现

interface IteratorPlanNode {
    void  Open();
    Tuple Next();
    void  Close();
}

1
2
3

interface MaterializationPlanNode{
    Tuples Output();
}

interface VectorizationPlanNode {
    void   Open();
    Tuples Next();
    void   Close();
}

每个操作节点节点都输出一批元组而不是单个元组节点的内部循环单次处理多个元组每批元组数量基于硬件或者查询规模变化每批元组每列使用自己的null-bitmap而不是bool数组
利好OLAP数据库
- 极大的减少了每个操作节点节点的调用数量
- 允许CPU乱序执行和SIMD
- 无数据和控制依赖
- 热指令缓存