CMU15-445笔记10——query execution

Processing Model

明确了如何执行一个查询计划。查询是从上往下还是从下往上，在每个operator之间，我们实际该传多少东西。

Approach #1: Iterator Model

也称为Volcano model或者Pipeline model。

Approach #2: Materialization Model

Iterator model只返回一个tuple，但materialization model则返回全部。

• 适合于OLTP workloads，因为这类查询一次只会返回很小数量的tuples，这样开销很小（因为数据被读取在内存中时要考虑同步问题）。
• 不适合于OLAP workloads，因为这会导致中间结果返回过多的tuples。

Approach #3: Vectorized / Batch Model

当每次调用next函数时，传递的是一批次tuple而不是单个tuple，这样更为高效（因此其是对于iterator model的增强），同时避免了传递的数据过多的问题。

Plan Processing Direction

Approach #1: top-to-bottom

从根节点递归地调用函数。

Approach #2: bottom-to-top

从叶节点推数据到根节点中。

Access Methods

如何在数据库系统的表中查找数据。

Approach #1: Sequential Scan

从buffer pool中读取每一个数据，之后遍历每一个tuple判断其是否需要读取。DBMS维护一个内部的游标来追踪最后一个被检查的page与slot。

Optimization of Sequential Scan

• Prefetching

• Buffer pool bypass

• Parallelization

• Zone maps：预先计算一个page的一些属性并存储起来，之后读取可以不需要读取整个page而先读取page的这些属性值进行判断是否需要读取。（总是在OLAP中使用，而不是在OLTP中使用，因为这样维护成本过高。）

• Late materialization：延迟将数据从一个operator传播到下一个operator（延迟读操作），之后根据情况去读取具体的数据。

• heap clustering：利用聚簇索引，之前有介绍过。

Approach #2: Index Scan

数据库管理系统选择合适的索引去查找tuples（可能有多个索引可用）。

Approach #3: Multi-Index / “Bitmap” Scan

通过不同的索引进行多次查找，并合并结果。

Index Scan Page Sorting

对于非聚簇索引中的tuple，可能在索引上连续排列的tuple在物理位置上十分分散，因此数据库管理系统可以首先取到所有的tuples的page id并对它们进行排序，之后再进行读取。

Expression Evaluation

DBMS将where子句表示为一个表达式树。

利用JIT（即时编译）来处理类似1==1这种查询语句，这种语句总是编译为true这样的常量。