Paper Reading: Access Path Selection in Main-Memory Optimized Data Systems

这篇paper是 Access Path Selection in Main-Memory Optimized Data Systems: Should I Scan or Should I Probe?, in SIGMOD, 2017。

对应15-721的Query Execution & Processing部分，主要涉及数据库的访问路径选择，如何最优地查询数据，比如sequential scan还是index scan，依赖于硬件和并发。

Introduction

列式数据分析引擎的出现，推动了scan算子的一系列优化。比如列式存储、向量化执行、SIMD和multi-core执行。并且如今计算资源，可以有更大的内存 和 更深的缓存层，因此需要重新审视access path的选择。下面会从不同角度，深入理解Access Path。

Access Path Selection：简单来说，如何查询到底层存储的数据。比如，一个query的filter key是clustered index，则通过聚集索引访问底层数据，会更加高效。比如，一个query的filter key是secondary index，则需要比较secondary index scan和sequential scan的cost，最后的selection取决于，底层硬件属性/系统配置/数据分布情况。

Access Path In Modern Analytical Systems：过年20年中，数据库系统从传统的row-based设计，转向columnar-based(以及chunk-based)的内存模型，以及基于主内存的access paths。它们带来的优势：

• 基于column的内存模型，减少了大量不需要的fields查询
• 算子从"tuple-at-a-time"到"chunk-at-a-time”，减少了大量虚函数overhead
• 多个query需要scan相同的数据时，可以利用sharded scans，减少额外的scan cost
• 基于columnar的内存模型，带来了更高的压缩率，减少传输时的内存使用
• 基于columnar的内存模型，利用SIMD，提高计算效率

Access Path Decisions In Many-Memory：本质上来说，传统的row-based存储利用secondary index的原因是，尽量减少数据在磁盘上的移动。由于data layout和large memory的改变，secondary index不在是critical path了。因此，许多现代的 分析型系统，不在包括二级索引，而是专注于使用 single access path去最大化scan performance。比如，clustered index, data skipping技术。

Open Questions：文章引出了几个问题

1. secondary index 在现代 analytical system 中是否还适用？
2. 随着硬件和系统的进步，我们如何做 access path selection？

第一个问题：许多现代系统已经不选择secondary index，而是持续的优化scan性能。原因：对这些分析型系统，shared scans持续变多，并发query指数型增长，会出现多个query，可以通过一个sequential scan来包含，而不是通过2次secondary indexing(回表成本)；考虑到许多查询，亚秒级性能，是否还有时间去计算best access path，需要trade-off。

Access Path Selection in Modern Analytical Systems：现代分析型系统，在Access Path Selection时，query并发度也是要在optimizer中考虑的。如下图：其中selectivity的解释是，selectivity factor，即选择性因子，它是一个number。High Selectivity 表示查询结果需要很多 tuples，反之是low selectivity。举例：selectivity越高，需要扫描越多数据，更倾向于sequential scan。反之 index scan。

图中的主要变化是：

• 传统的方式，系统会根据硬件条件，存在一个fixed selectivity。如果预计查询结果，比这selectivity point大，则会走sequential scan
• 现在的变化，用一个斜度值替换之前的固定值，因为随着并发查询增多，shared scan性能更好

Access Path Selection

这一章介绍，如何定义Access Path Selection的模型，以便更加准确的做出选择。

模型设计

模型所包含的参数有：查询负载，数据存储layout，硬件，index和scan设计。如下表1，包含模型的所有参数。

Other Scan Enhancement: 对单条query来说，通过 data skipping 技术，如 zonempas，来避免读取一组 不满足query的数据，通过数据的边界条件来判断。如下图展示，每一块数据中每一列都有一个range用来做边界，图片来自于Instance-Optimized Data Layouts for Cloud Analytics Workloads

zonemaps的缺陷是，随着查询并发增多，可以skip的zone会减少，因为要skip一个zone，必须是这个range内的所有数据都不需要才行。

Modeling In-Memory Shared Scans

sequential scan的核心是，在一个input的数组上进行iteration，根据predicate找到合适的tuples。很容易想到，可以通过for loop来实现，因此在in-memory的系统中，它主要受限于，内存带宽。

同时，for loop中需要对每个tuple进行 predicate evaluation ，因此CPU cost在sequential scan中也需要考虑到。

另一个影响scan cost的是，result writing。因为在for loop中 branch misprediction 会带来指令的浪费，影响效率，因此我们使用可预测的方式 生成结果集。

最后补充一下，分支预测，会涉及到了 指令级并行 的概念，可以参考 Denis Bakhvalov - Performance Analysis and Tuning on Modern CPUs中 pipelining 和 Instruction Level Parallelism。

开始前，感性理解下 pipelining 技术：假设 CPUs 是一个工厂，有许多机器执行不同的任务，在同一条产品线上。它们以一个相同的节拍执行任务，但是你可以发出不同的指令，工厂会在同一时刻，不同的路径上去执行。

CPU ILP

Pipelining is the foundational technique used to make CPUs fast wherein multiple instructions are overlapped during their execution。

通过pipelining技术，可以让多条指令 重叠执行。它灵感来源于，汽车装配流程线。CPU的指令会被划分为多个stages，不同指令的不同stage是可以并行操作，在不同的电路上。

如下图，一条指令被分为5-stage：

• Instruction fetch (IF)
• Instruction decode (ID)
• Execute (EXE)
• Memory access (MEM)
• Write back (WB)

在cycle 1时，指令x的IF stage进入pipeline，在cycle 2时，指令x进入ID stage，指令x+1进入IF stage。按照这个模式，随着clock cycle依次下去。在cycle 5时，CPU上的所有pipeline都在忙着不同的指令。

指令级并行，说的是，如果CPU上存在着多个 fetch 和 decode 电路，则可以在一个cycle中并行的执行fetch或decode，这被称为 超标量架构 Superscalar。

而我们的代码中，可能会影响到 指令级并行 的因素，就包含 branch misprediction。从上面的pipeline得知，我们需要在第一条指令还未完成时，第二条指令就需要进入pipeline，来保证pipeline上有源源不断的指令来执行。

因此，如果代码中出现了 分支情况 (if-then-else)，CPU会通过一些算法，预测下一阶段的指令，从而保证源源不断的指令进入pipeline，而不会出现卡壳。

但是，CPU如果预测错了branch，则这个pipeline整个会被清空，从fetch到execute阶段，从头再来开始。直观看来，misprediction就浪费了大量clock cycle。

其它影响指令级并行的问题还有，虚函数调用，指令间前后依赖等。

最后，回归上面的result writing cost问题，可以通过codegen方式解决。后面的paper reading会介绍。

Evaluating Access Path Selection

定义出一个比率值：APS(Access Path Selection)，$$ APS = \frac{ConcIndex}{SharedScan} $$

• ConcIndex：the cost of a concurrent secondary index access
• SharedScan：the cost of in-memory shared scan

当APS >= 1，选择sequential scan，当APS < 1，选择secondary index access。

文章后面，是对APS model的证明和分析，有兴趣的同学，可以参考2.4章节，这里不在展开。

总结

个人觉得，只要读到section 3就好了，后面基本都是些证明和解释。

文章的核心观点：查询计划的 sequential scan vs secondary scan，取决于 硬件性能 和 查询并发。

关于Query Execution & Processing，还推荐一篇向量化经典：MonetDB/X100: Hyper-Pipelining Query Execution, in CIDR, 2005，一下篇paper reading会介绍。

Reference

• Branch Prediction — Everything you need to know.