菜菜的秘密花园Access Path Selection in Main-Memory Optimized Data Systems
本文为论文 Access Path Selection in Main-Memory Optimized Data Systems: Should I Scan or Should I Probe? 的阅读笔记。
1 引言
🟥 我们提出了一个增强的访问路径成本模型，它可以捕捉到在支持访问共享的主内存优化的分析数据系统中的选择运算符的性能。
🟨 访问路径的选择是需要的；即使在快速扫描时，经过调整的二级索引也是有用的。
🟩 我们表明，除了【选择性】和【硬件特性】外，访问路径的选择还需要动态地考虑到【查询并发性】。
🟦 我们将访问路径选择整合到一个现代分析原型的优化器中，并表明即使访问路径选择现在是一个更复杂的操作，必须考虑到更多的信息，它仍然可以快速完成；并且可以在各种工作负载上进行。
🟪 使用该模型，我们展示了何时使用索引的决定是如何随着数据布局和硬件属性的变化而变化的。
2 访问路径选择
2.1 模型准备工作
索引的选择性： 指不重复的索引值和数据表的记录总数的比值，取值范围在
[0,1]之间。索引的选择性越高则查询效率越高，因为选择性高的索引可以让 MySQL 在查找时过滤掉更多的行。
2.2 内存中共享扫描建模
🔴 扫描的数据移动。给定内存带宽 $BW_S$ ，顺序扫描数据的成本为： $TD_S = \frac {N·ts}{BW_s}$ 。
🟡 谓词评估。假设 p 是时钟周期，fp 是指令流水线的常数，则谓词评估 PE 的 CPU 为： $PE = 2 · fp · p · N$ 。
🟢 写结果。输出整列的成本需要N行rw字节： $TD_R = \frac {N·rw}{BW_R}$ 。
🔵 扫描单个查询i的成本为： $SingleQueryCost = max(TD_S,PE) + s_i · TD_R$ 。
🟣 为查询生成结果集的成本为： $\sum_{i=1}^n s_i · TD_R = Stot · TD_R$ 。
🟤 综上，可以得到q个查询的内存共享扫描的总体成本： $SharedScan = max(TD_S,q·PE)+Stot·TD_R$ 。
2.3 内存中的辅助B+树建模
tree fanout：树中每个结点的孩子结点的个数，或者是每个结点的指针的个数。
🔴 对于扇出为b的B+树，从根到第一个对应叶的树遍历成本（以秒为单位）为：$TT = (1+[log_b(N)])·(C_M+\frac {b·C_A}2+\frac {b·f_p·p}2)$ 。（假设对每个内部节点，平均顺序读取一半的关键字）
🟡 假设 $N/b$ 是树中的叶子数量，则每个查询的叶子遍历成本为： $si·TL, where, TL = \frac {N ·C_M}b$ 。
🟢 每个查询的成本取决于属性宽度（aw）和偏移宽度（ow）：$si·TD_I, where, TD_I = \frac {N·(aw+ow)}BW_I$ 。
🔵 写入结果的成本：$RW=s_i·N·\frac {rw}{BW_R} = s_i·TD_R$ 。
🟣 为了将与扫描运算符相同的结果传递给下一个运算符，查询i的二级索引遍历需要根据rowID对输出进行排序。每次比较只计算一次缓存访问，排序成本等于：$SC_i=s_i·N·log_2(s_i·N)·C_A$ 。
🟤 综上，使用二级索引遍历的单个查询的成本（以秒为单位）为： $SingleIndexProbe = TT+s_i·(T L+TD_I)+RW+SC_i$ 。
⚫ 内存中共享辅助索引扫描的总体成本如下： $ConcIndex =q·TT+Stot·(TL+TD_I)+Stot·TD_R+\sum_{i=1}^q SC_i$ 。
2.4 评估访问路径选择
APS（访问路径选择）。 $APS=\frac {ConcIndex}{SharedScan}$ 。当 APS>1 时应使用扫描访问；当 APS＜1时，应使用辅助索引访问。其具体表达式如下：
APS 由两个不同的部分组成。
第一部分考虑了查询并发性q、数据集大小N、索引分支因子b和硬件权衡：带宽&LLC未命中以及带宽&L1延迟。
第二部分主要受谓词评估成本、总选择性Stot和数据布局的影响。
2.5 APS模型分析
🟥 在图4至图7中，x轴显示查询并发性q，y轴显示平均单个查询选择性（si）。图8至图10的x轴为关系大小N，y轴保持不变。
🟨 深蓝色区域的APS比率非常低，表明使用辅助索引将非常有益；浅蓝色区域对应于辅助索引将提供2-3的加速；绿松石区域对应于索引和扫描几乎相等的工作量；黄色区域扫描速度快1.5-2倍；红色区域对应于使用共享扫描更优。
🟩 在现代主存储器优化的分析数据系统中，存在关于共享扫描和索引扫描的性能的盈亏平衡点；需要选择访问路径以在所有场景中最大限度地提高性能。
🟦 在支持列组的混合系统中，辅助索引在更多情况下比普通列存储更有用，因为使用辅助索引有助于避免在内存层次结构中移动大量不必要的数据。
🟪 二级索引和扫描之间的决定取决于许多因素：查询选择性、硬件属性（缓存和内存延迟、内存带宽）以及查询并发性。
3 实验分析
✔ 【并发的影响】并发性（在相同数据上进行查询的数量），是影响访问路径选择的一个关键因素。
✔ 【数据集大小的影响】随着数据集大小的增加，选择性交叉点达到最大值，然后逐渐下降。
✔ 【数据布局的影响】鉴于混合布局的趋势，我们预计访问路径选择将变得越来越重要。
✔ 【硬件性能的影响】我们的优化器并不是专门针对单个硬件配置进行调优的。
✔ 【压缩的影响】使用字典压缩为扫描提供了一个小优势，然而，这两种访问路径仍然很有用。
✔ 可以通过考虑估计的选择性、并发性、数据大小和硬件属性来执行准确和动态的访问路径选择。
4 经验教训
🔶 当辅助索引扫描比顺序扫描更可取时，甚至当数据驻留在主内存中时，也会出现分析查询的情况，从而消除磁盘I/O瓶颈。
🔶 除了选择性、硬件规范、系统设计和数据布局之外，细粒度访问路径决策还需要将【查询并发性】作为运行时参数考虑。
🔶 数据集的大小可能至关重要。对小数据集来说，扫描数据在所有情况下都优于二级索引。索引对于较大的数据集仍然很有用，因为全属性扫描成本很高。
🔶 访问路径选择对于具有列式存储的系统很重要，对于混合存储中更广泛的元组来说，这更加重要。
🔶 随着缓存和内存延迟或者内存带宽的减少，辅助索引变得更加有益。相反，较慢的缓存或内存以及较快的内存总线有利于扫描。
参考资料：