Query Execution and Optimization
前面学了这么多SQL语言，DBMS的存储表示，缓冲池，DBMS的查询，是时候来学习一下，如何DBMS是如何执行查询的了。
Process Models
往大了说有两种，Top-to-Bottom和Bottom-to-Top。前者更为普遍，后者可以对流水线中的缓存/寄存器提供更精确、严格的控制
往分类来说，有三种执行模型
Iterator Model
AKA Valcano Model(火山模型)/Pipeline Model(流水线模型)
它通过为数据库中的每个运算符实现Next函数来工作。查询计划中的每个节点都对其子节点调用Next，直到到达叶子节点，叶子节点开始向其父节点发出元组进行处理。
- 每次调用Next时，如果没有更多的元组要发出，运算符将返回一个元组或一个空标记
- 操作符实现一个循环，该循环在其子级上调用 Next 以检索它们的元组，然后处理它们。通过这种方式，在父节点上调用 Next 将在子节点上调用 Next。作为响应，子节点将返回父节点必须处理的下一个元组
那么对于这种情况，我们很自然地想到用流水线去提高效率。因为每一级的结果都需要交由下级处理，等待下级处理完返回结果，在等待的过程中，上级其实是空闲的。而且对于火山模型，它不是非要等到一整个Tuple才会返回的，而是有一个就返回，这样才根本地提供了可流水线优化的可能性。
一些运算符会阻塞，直到子运算符发出所有元组。此类运算符的示例包括joins, subqueries, ORDER BY。这些操作运算符被称为pipleline breakers。主要就是因为他们每次生成都是生成一整个Tuple结果，而不是一个一个来的。
而输出控制很容易使用这种方法 LIMIT，因为一旦拥有所需的所有元组，运算符就可以停止在其子运算符上调用Next
虽然可以使用流水线增加效率，缺陷就是函数调用次数太多，函数栈空间太大，导致栈溢出。适用于OLTP系统，但不适用于OLAP系统。
Materialization Model
每个运算符一次处理其输入，然后一次发出其输出。每个运算符在每次到达时都会返回其所有元组，而不是有一个返回单个元组的下一个函数。所以输出的结果，一般都是整个元组结果的子集
因此，显然物化模型无法流水线优化，因为它一次处理返回整个输入，而不是一个一个的元组。
- 对于每个运算符，它一次处理其输入，然后一次发出其输出。
- 此函数的返回结果是运算符将发出的所有元组。当运算符执行完毕时，DBMS永远不需要返回它来检索更多数据
因此，物化模型适用于OLAP系统，因为它一次处理整个输入，而不是一个一个的元组。
Vectorization Model
就是上面两种的折中方案，每次不是返回一个，也不是返回一整个，而是返回一批(Tuple Batch)元组。
适合SIMD(Single Instruction Multiple Data)指令集架构，可以一次处理多个元组。
Access Methods
访问方法是DBMS访问表中存储的数据的方式。一般来说，有两种方法可以访问模型；数据要么从表中读取，要么通过顺序扫描从索引中读取。
它对应的是Process Models执行当中的叶子(最底层)部分，因为这是实际读取数据库本身的地方。所谓Access，其实就是接触数据库，并从中读取数据。
Sequential Access
顺序访问是最简单的访问方法。它从表的开头开始，逐个读取每个元组。它会迭代表中的每个页面(用一个cursor追踪，且以Page为单位)，并从缓冲池中检索它。当扫描迭代每个页面上的所有元组时，它会评估谓词以决定是否将元组发送给下一个运算符
显然它的效率低下，因而出现了很多优化方式
- Prefetching: 预先读取下一个页面，并将其缓冲在内存中，以便在下一次需要时立即使用。
- Buffer Pool Bypass: 读取的数据不放入缓冲池，因为我们知道Squential Access读取的内容下次很大可能不会再用。
- Parallelization: 并行读取多个页面，以提高吞吐量。
- Heap Clustering: 元组使用聚类索引指定的顺序存储在堆页面中。
- Zone Maps: 给每个页都进行统计计算，比如它的最小值最大值等，比如查询不在范围内的就可以直接跳过，以此增加效率。
- Late Materialization: 推迟物化，也就是在查询执行的过程中，我们不将Tuple本身上传，而是只上传它的Index/Offset(也就是行ID)。
Index Scan
索引扫描是一种顺序扫描，但它只扫描索引，而不扫描表。
差不多就是按给出的SQL语句中列为索引，在多个条件当中，哪个分组的人数少，意味着走这条索引的优化效果好。
当然还有进化版的Multi-Index Scan，它可以同时扫描多个索引，以提高查询效率。对于多个索引都取出结果，然后取交集。
Bloom-Filter(布隆过滤器)的优化
Parallel/Distributed Databases
前者的节点通过高速互连进行通信。假设资源之间的通信不仅快速，而且便宜可靠。后者资源可能相较甚远，节点通信可能耗时长且失败率高
Process Per Worker
这个是老旧的DBMS才用的，是落后的
还有进程池的加入
Thread Per Worker
自从pthread出现后，多线程编程变得非常简单。它允许多个线程同时运行在同一个进程中，从而提高了并行度。
由于木桶效应，速度一般最慢的磁盘，这个接触面一般会作为瓶颈。所以，我们可以将数据分布到多个磁盘上，以提高查询效率。
Plans and Optimization
查询优化是DBMS的核心任务之一。它涉及到三个方面：
- 选择最佳的查询计划
- 确保查询计划的正确性
- 确保查询计划的高效性
这个实在不是三言两语能说清楚的，真得看note或者lecture
大概就是说，有两种大的优化方式:
- Rule-Based Optimization: 基于规则的优化，它就是会根据已经定好的规则，去把我们拿到的分析好的SQL语句，去套这个规则。所以说比较死板、固定，但是也比较简单。
- Cost-Based Optimization: 基于代价的优化，它会根据代价模型，去分析SQL语句的执行计划，然后利用统计学模型预测代价最小的方案，选择最优的执行计划。所以说比较灵活、智能，但是也比较复杂。