本节课深入探讨了数据库系统如何执行查询计划，特别是涉及到的查询处理模型、数据访问方法以及表达式评估机制。理解这些概念对于优化数据库性能和理解查询执行的底层原理至关重要。

查询计划处理模型

数据库管理系统（DBMS）的查询计划处理模型定义了它如何执行查询计划。这些模型各有优缺点，适用于不同的工作负载和运行环境。

迭代模型（Iterator Model）

也叫火山模型（Volcano Model）/ 流水线模型（Pipeline Model）。

• 这是最常见的处理模型，几乎所有数据库系统都采用此模型，特别是基于行的系统。
• 其核心思想是，查询计划中的每个操作符（如连接、排序等）都实现了一个 Next() 函数。当一个父节点调用其子节点的 Next() 函数时，子节点会返回 一个元组 （tuple），或者在没有更多元组时返回一个空标记。这种机制使得数据能够像 流水线一样 在操作符之间流动，单个元组可以尽可能远地在查询计划中向上处理，从而最大化内存中元组的工作量，这在基于磁盘的系统中尤为重要，因为磁盘I/O非常昂贵。
• 尽管该模型支持高效的流水线处理，但某些操作符无法在接收到所有子元组之前继续处理，它们被称为 管道阻塞点（Pipeline Breakers） 。常见的管道阻塞点包括： 连接（Joins） 、 子查询（Subqueries） 和  ORDER BY 操作 。例如，一个哈希连接在探测阶段之前必须先构建完整的哈希表。
• 迭代模型易于理解和推理，并且与 LIMIT 子句等输出控制机制配合得很好。

物化模型（Materialization Model）

• 该模型是迭代模型的一个 专用版本 ，主要用于内存数据库系统。
• 与迭代模型每次返回一个元组不同，物化模型中的每个操作符会 一次性处理所有输入数据，然后一次性地发出所有输出数据 。这意味着操作符会“物化”其全部结果作为一个单一的输出。一旦操作符完成执行并返回其结果缓冲区，DBMS就无需再返回它来获取更多数据。
• 这种方法对于 OLTP（在线事务处理）工作负载非常适用 ，因为OLTP查询通常只访问少量元组。这样可以减少函数调用的开销。
• 然而，它 不适合处理具有大量中间结果的OLAP（在线分析处理）查询 ，因为这可能导致DBMS不得不将这些中间结果溢出到磁盘，从而降低性能。

向量化模型（Vectorized / Batch Model）

• 向量化模型 基于迭代模型 ，但进行了优化。
• 在每次调用 Next() 函数时，操作符不是返回一个元组，而是返回 一个批次（batch）或向量（vector）的元组 。
• 系统被设计成操作符的内部循环可以直接处理一整批元组，而不是逐个元组处理。批次的大小可以根据硬件和查询特性进行调整。
• 这种方法 非常适合OLAP查询 ，因为它们通常需要扫描大量元组，减少了 Next() 函数的调用次数。此外，它还允许操作符利用 向量化（SIMD）指令 来高效处理元组批次，极大地提升了性能。现代大型数据仓库系统广泛采用此模型.

除了上述模型，查询计划的执行方向通常是 从顶向下（Top-to-Bottom） ，即从根节点开始，并从其子节点“拉取”数据。但也存在 从底向上（Bottom-to-Top） 的方法，它允许更精细地控制CPU缓存和寄存器中的数据流，尽管这种方法对人类程序员来说更难理解和实现。

数据访问方法（Access Methods）

数据访问方法定义了DBMS如何从表中检索数据。它们是查询计划中的叶子操作符，负责将数据“喂给”上层的操作符。

顺序扫描（Sequential Scan）

• 这是最基本的访问方法，DBMS会遍历表中的 每一个数据页 ，将其从缓冲区池中取出。然后，它会遍历该页中的每一个元组，并评估谓词（WHERE子句）以决定是否包含该元组。DBMS会维护一个内部游标来跟踪已检查的最后一个页面和槽位。
• 优化措施 ：尽管顺序扫描在没有索引时是唯一的选择，但它在基于磁盘的系统中通常性能很慢。因此，有多种优化方法来提升其效率：

预取（Prefetching） ：提前获取后续的几个数据页，避免在需要时阻塞等待I/O。

缓冲区池旁路（Buffer Pool Bypass） ：扫描操作符将从磁盘获取的页面存储在其本地内存中，而不是污染共享的缓冲区池缓存，从而避免“顺序泛洪”问题。

并行化（Parallelization） ：使用多个线程或进程并行执行扫描操作。

区域图（Zone Maps） ：对每个数据页中的属性值预先计算聚合信息（如最小值、最大值、平均值等）。在访问页面之前，DBMS首先检查区域图，如果区域图指示该页面不可能包含满足条件的元组，就可以 跳过整个页面 的读取，从而大大减少磁盘I/O。然而，区域图的 维护成本较高 ，不适用于高更新频率的OLTP系统，但对于“一次写入，多次读取”的OLAP工作负载非常有用。

延迟物化（Late Materialization） ：在列式存储系统（DSM）中，可以延迟拼接完整元组的时机。操作符只传递最少必要的信息（例如记录ID）给下一个操作符，只有当上层查询计划需要实际数据时，才回表获取完整元组数据。这避免了不必要的数据移动，尤其是在仅需要部分列的情况下。

堆聚簇（Heap Clustering） ：如果元组在堆页中按照聚簇索引的顺序存储，DBMS可以直接跳转到需要的页面，从而实现顺序访问。

索引扫描（Index Scan）

• DBMS选择一个或多个索引来快速定位查询所需的元组，从而 减少不必要的工作量 。
• 选择最佳索引是复杂的，取决于索引中包含的属性、查询中引用的属性、属性值的分布、谓词的类型（如小于、大于、等于）以及索引是否唯一等因素。
• 多索引/位图扫描（Multi-Index / Bitmap Scan） ：当查询条件可以利用多个索引时，DBMS会分别在每个匹配的索引上执行查找，生成匹配的记录ID集合。然后，根据查询的谓词（AND子句使用 交集 ，OR子句使用 并集 ）将这些集合进行组合。最后，DBMS根据组合后的记录ID去检索实际的元组并应用任何剩余的谓词。Postgres称之为“位图扫描”，它通常使用位图、哈希表或Bloom过滤器来实现集合操作。
• 二级索引回表随机I/O优化（Index Scan Page Sorting） ：对于 非聚簇索引（unclustered index） ，通过索引扫描获取记录ID后，由于元组在磁盘上的存储顺序可能与索引的逻辑顺序不同，直接回表可能会导致大量 随机I/O ，效率低下。为了解决这个问题，DBMS可以 先通过索引扫描，收集所有满足条件的记录ID 。然后， 不立即回表，而是根据这些记录ID所在的页面ID进行排序 。这样，当实际去读取数据页时，相关的元组将集中在少数几个页面中，从而将大量的随机I/O转换为更高效的 顺序I/O ，每个页面只需读取一次。

表达式评估（Expression Evaluation）

DBMS将SQL查询中的 WHERE 子句等谓词表示为 表达式树（Expression Tree） 。树中的节点代表不同类型的表达式，如比较运算符、逻辑运算符（AND/OR）、算术运算符、常量值和元组属性引用等。

• 评估过程 ：在运行时评估表达式树时，DBMS会维护一个上下文句柄，其中包含当前正在处理的元组、查询参数和表模式等元数据。然后，DBMS会 遍历表达式树 （通常是深度优先），从叶子节点开始，计算出中间值并向上层节点传递，直到根节点产生最终的布尔结果（真或假），以判断元组是否匹配谓词。
• 性能瓶颈与JIT编译 ：虽然表达式树在概念上易于理解和实现，但对于 大量数据（例如数十亿行） ，每次评估一个元组时都重复遍历表达式树会变得 非常慢 。因为每次遍历都需要进行函数调用、分支跳转、类型检查和运算符调度等开销。
• 为了解决这个问题，高端数据库系统采用了 即时编译（Just-In-Time Compilation, JIT） 技术。JIT编译可以将表达式树 直接编译成机器码指令 ，这些指令可以非常高效地在CPU上执行，从而避免了重复的树遍历开销。一些先进的系统甚至可以将整个查询计划编译成一条指令流水线，进一步减少间接跳转，使得查询执行如同手动编写并编译的代码一样高效。

总结 ：本节课强调，数据库查询计划的执行方式有多种，具体取决于数据库系统所处的环境和所处理的工作负载。在大多数情况下，DBMS会尽可能优先使用索引扫描。而表达式树虽然灵活易懂，但在处理大量数据时会因其解释执行的特性而变得缓慢，因此通过 JIT编译 将其优化为原生机器码是提升性能的关键。