Open mrdrivingduck opened 2 years ago
mrdrivingduck
commented
2 years ago 目前的 DB 在现代 CPU 上处理 计算密集型 应用时，IPC (Instructions-Per-Cycle) 指标非常低。本文分析了原因，并给出了一些设计查询执行器的意见。此外，本文提出了一个新的向量化查询执行引擎，CPU 效率较高。
现在 CPU 只有当能够找到足够多 无关 指令时，才能充分利用并行执行的能力。OLAP 负载就需要做大量的无关计算，理论上应该具有较高的 IPC 效率。然而，已有研究表明，DB 在现在 CPU 上运行这些负载时，取得了较低的 IPC 效率。所以需要深入分析一下关系型数据库是如何在现代超标量处理器上做查询执行的。
结论是，DBMS 普遍采用 火山迭代器 模型，一次处理一个元组，带来巨大的解释开销，同时使编译器无法使用一些性能攸关的优化技术。本文中实现了一个列式执行模型，使 DB 不再受火山模型的局限。
mrdrivingduck
commented
2 years ago CPU 主频提升的根源是芯片制造工艺的提升，意味着更小的线间距离和信号延迟。另外，通过 流水线 的方式执行指令，可以让主频进一步提升。每条 CPU 指令需要一个或多个阶段才能被执行完毕，每个阶段需要做的工作较少，这样就可以提升 CPU 主频。
指令流水线的两大克星：
另外，超标量 CPU 具有多条指令流水线，能够并行执行多条无关指令。
大多数编程语言不要求开发者显式指定哪些语句是相互无关的，而是由编译器来进行优化，从而达到较好的 CPU 利用率。其中最重要的技术：loop pipelining。对 n 个无关元素的多个相关操作 F() / G() 的顺序做如下调整：
# before
F(A[0]) G(A[0]) F(A[1]) G(A[1]) F(A[2]) G(A[2])
# after
F(A[0]) F(A[1]) F(A[2]) G(A[0]) G(A[1]) G(A[2])为什么可以这样优化？由于 F() 和 G() 的操作是相关的，因此对同一个元素的操作，G() 必须要等到 F() 的结果被运算出来，中间的时间被浪费了。而用后一种排序方式，G() 在等待 F() 的运行结果时，等待时间可以被用于执行其它 F()。
对于某些处理器，可以由编译器来决定将哪些指令同时放到不同的流水线中去（通常这是由 CPU 的乱序执行决定的），比如同时允许条件分支为 true 或 false 的指令同时进入两条流水线，然后视分支结果来决定 cancel 掉一条流水线。
另外，CPU 上的片上缓存对吞吐率的影响也非常大。访问内存的最快时间，对于 CPU 来说也有约 180 个周期的空转了。只有当大部分的访存指令都能够在 CPU 片上缓存中找到数据时，现代 CPU 才能发挥最大吞吐率。
总体来说，CPU 的指令吞吐率受以下因素影响，差距可能会达到跨数量级：
已有研究表明，商业 DBMS 系统中的 IPC 只有约 0.7，这个数值对于需要进行大量分析计算的 workload 来说有点过于慢了。DBMS 本可以做得更好。
mrdrivingduck
commented
2 years ago 对 DBMS 中的 表达式计算 进行分析。
TPC-H 的 Query 1 是一个 CPU-bound 的查询，因为其执行计划非常简单，优化器没有什么优化的余地。Query 1 会扫描事实表，并选择出基本所有的元组，然后进行一些定点数计算：
对于火山模型的执行器来说，一个扫描算子通常会有三个参数：ScanSelect(R, b, P)：
为了处理所有可能的 R、b、P，DBMS 需要实现通用的 表达式解释器，用于处理任意复杂度的表达式。这种解释器存在的问题是，真正做 real work 的开销只占总体开销中的一小部分。实验表明：
另外，对于每一个加法操作，需要 38 条指令的时钟周期，而实际上做两个浮点数的加法只需要 4 条指令：
LOAD src1, reg1
LOAD src2, reg2
ADD reg1, reg2, reg3
STOR dst, reg3其中第三条指令依赖于前两条指令执行完成，而第四条指令又依赖于第三条指令执行完成。由于 MySQL 是逐个元组执行上述几条指令的，因此没有机会使用 loop pipelining。根据平均每条指令延时 5 个周期计算，执行这 4 条指令需要 20 个时钟周期。剩下的时钟周期用于跳转进执行加法的函数以及后来的退出。总结：
如果使用按列处理，编译器能够对一个向量的加法做 loop pipeling，显著提升 CPU 的利用率。
10.1.1.101.7834.pdf
对于向量化执行为什么可以高效利用 CPU 的一些分析。