CMU 15-721 15-查询执行和处理过程 Query Execution & Processing
数据库架构
从整体数据库架构来看，我们可以知道分为网络协议层、优化器层、执行器、存储，详见下图：
SQL从客户端发送到数据库服务端，经过解析器、语法语义分析、逻辑优化和物理优化，从一个字符串转换为解析树、语法树到最终的执行计划，那么最终是如何变成机器可以执行的操作呢，本文重点就是来讲执行器的一些重要组件和原理。
执行器
我们先来了解下重要的一个查询的执行过程：
一个查询SQL变成执行计划后，既然叫执行计划，那么它一定可以序列化成一系列的操作。执行计划就是由一堆操作符组成的，每个操作符对应的实例对象就是一次操作符作用在一组数据上的调用。一次任务就是一系列这样的一个或多个操作符实例的执行。
执行层的优化
我们现在将要讨论的是那些数据集合能够整个加载到内存中的SQL执行过程中可以进行性能优化的方法。当我们不考虑磁盘问题时候，我们还有其他的一些瓶颈。
优化的目标
1: 减少指令数：用很少的指令去做更多的事情
2: 减少每个指令的周期：在较短周期内执行更多的CPU指令，这意味着需要减少由于cache misses和stalls的缓存加载和存储
3: 并行执行:使用多线程同时并行执行每一条SQL
主要介绍的内容包括：
MonetDB/X100的分析
执行模型
并行执行
MonetDB/X100
MonetDB/X100是从很低角度分析执行瓶颈的一个基于内存的OLAP数据库，它能够证明现在的数据库并没有针对目前CPU的架构体系来进行设计。2010年，被Actian收购后改名叫Vectorwise，后来改称为Actian Vector和Actian Avalanche。
CPU简介
CPUs会把很多指令变为流水线的各个阶段，目的是通过屏蔽那些在一个周期无法完成的指令，从而让所有处理器在一个周期内都能够处于忙碌状态。Super-scalar CPUs可以支持多流水线，即：
→ 如果指令相互独立，在一个周期内可以并行执行多个指令。
→ 费林分类: 单处理指令单数据(SISD)
那么目前数据库中对于CPU设计的问题有哪些呢？
1: 依赖性：如果一个指令依赖于另一个指令，那么它们就不能被立即推到同一个流水线里。
2: 分支预测：CPU尝试着预测程序中某一个代码分支，并将其指令填充到一个流水线里。如果预测失败，那它需要把所有的推测的工作全部扔掉并重新刷新流水线。
分支预测失败
对于长流水线，CPUs通常都会推测执行的代码分支，这里潜在的隐藏了那些互相依赖的执行之间的等待。在数据库领域，在一个顺序扫描中，最多执行的代码分支是filter操作，但是这个几乎不可能预测准确。
选择查询扫描
SELECT * FROM table
WHERE key >= $(low)
AND key <= $(high)下图可以看到，这条SQL如何通过分支的和无分支的方式进行扫描
那么看看效果，无分支较为稳定，而有分支的情况下随着SQL选择率不同表现出不同CPU指令数量的不同
过度指令
数据库需要支持不同的数据类型，所以它在对值进行执行任何操作的时候必须去检查值的类型，这样导致了巨大的选择语句，而且CPU都无法预测每一个代码分支。比如Postgres的NUMERIC类型.
执行模型
数据库的执行模型说明了数据库如何执行SQL的执行计划，不同工作的负载有不同的权衡：
1: 迭代模型（Iterator Model）
2: 物化模型（Materialization Model）
3: 向量化/批处理模型（Vectorized / Batch Model）
迭代模型
执行计划中的每个操作符都需要实现next函数，每一次调用，操作符都返回一个tuple或者EOF。实现loop的操作符，可以去调用子操作符的next来获取tuples并行进行处理。这个模型也叫火山模型或者流水线模型。
几乎所有的数据库都可以支持tuple的流水化处理，一些操作符可能需要等待它的子操作符返回所有的元组才能继续执行，比如Joins, Subqueries, Order By。这种模型对外输出是非常容易的。
下面是支持这种模型的数据库：
物化模型
每一个操作符需要一次性处理很多，然后一次一并对外输出。操作符物化把自己的输出当成一个单独的结果。数据库系统也可以把一些建议下推减少太多的tuples。它可以支持发送一个物化的行或者一个列数据。输出可以是多行(NSM)或者多列(DSM)。
这种模型更适合OLTP负载，因为那些查询只一次访问小规模的数据，更小的执行和协调的消耗，更少的函数调用。如果对于那些中间结果集很大的OLAP负载是不适合的。
下面是支持这种模型的数据库：
: 向量化和批处理模型
像迭代模型一样，每个操作符都实现了next函数，但是每个指令在内部都一次循环处理多个tuples，每次批处理的大小都取决于迎接或者查询的属性。
这种模型是OLAP查询的理想模型，因为它们极大的减少了操作符数量，可以允许操作符使用向量化指令去批量处理tuples，也可以认为是SIMD方式。
下面是支持这种模型的数据库：
并行执行
执行计划的处理方式
1: 自顶向下（Top-to-Bottom）：开始从顶端从子操作符拉数据，元组通常要通过所有的函数调用。
2: 自底向上（Bottom-to-Top）：开始从叶子推送数据到它们的父操作符，允许更严格的控制流水线中的缓存和寄存器。
INTER-QUERY并行
通过允许同时执行多个查询来改进整个的性能，通过并发控制方案去提供一个隔离的错觉，很难提供一个并发的方案不去极大的影响数据库的处理模型。
INTRA-QUERY并行
通过并行执行操作符来改进单查询的性能。
1: Intra-Operator (Horizontal)
2: Inter-Operator (Vertical)
这些技术并不是相互排斥的，每个关系操作符都有相应的并行算法。
Intra-Operator (Horizontal)
操作符并分解成相互独立的实例，用同一函数处理数据的不同子集。数据库用exchange操作符来合并自操作符的结果。
Inter-Operator (Vertical)
→ 操作是重叠的，目的是让数据从一个阶段流到下一个阶段，而不进行物化，也叫流水线并行。这种在传统数据库并不常见。不是所有操作符都能够把结果集输出，直到它们能够接收到子操作符的所有tuples，这种方式更多出现在流式处理系统中。
比如下列数据库：
这是它们的处理方式：
查询计划采用正确数量的workers取决于CPU cores、数据量及对应操作符的功能实现。
Worker的分配方式
1: 每Core一个Worker：每个core可以绑定到一个线程上，参考sched_setaffinity
2: 每Core多个Workers：每个core或者socket可以用在worker池中，允许CPU cores充分被利用。
TASK分配方式
1: Push：一个中心的分配器，分配任务到各个workers，并监控它们的执行过程。当有worker完成任务后，通知分配器分配下一个任务。
1: Pull：workers从队列中取下一个任务并处理，完毕后再处理队列中下一个任务。
最后的思考
最简单的方式是实现对现代CPUs的架构不会总是产生最有效的策略。我们可以看到向量化/自底向上的执行是执行OLAP查询最好的方式。
参考链接和文献：
- 课程原文CMU 15-721 15-查询执行和处理过程 Query Execution & Processing
[- P. Boncz, et al., MonetDB/X100: Hyper-Pipelining Query Execution, in CIDR, 2005
](https://15721.courses.cs.cmu.edu/spring2019/papers/15-execution/boncz-cidr2005.pdf)
- L. Shrinivas, et al., Materialization Strategies in the Vertica Analytic Database: Lessons Learned, in ICDE, 2013 (Optional)
