【CMU 15-445】12 查询处理 I

Slides
Notes

1. 查询计划 Query Plan

DBMS将SQL语句转换为查询计划。operators 排列成一棵树。数据从树叶流向根部。树中根节点的输出是查询的结果。通常，operators 是二元的(1-2个子运算符)。可以以多种方式执行相同的查询计划。大多数DBMS都希望尽可能多地使用索引扫描(一种数据访问方式)。

2. 处理模型 Processing Models

DBMS处理模型 定义系统如何执行查询计划。对于不同的工作负载，不同的模型具有不同的权衡。

还可以实现这些模型以自上而下 top-to-bottom (最常见)或自下而上 bottom-to-top 地调用运算符。

Iterator Model（迭代模型）

这是最常见的处理模型，几乎每个(基于行的)DBMS都使用它。允许流水线操作，其中DBMS可以在检索下一个元组之前通过尽可能多的运算符处理元组。

每个查询计划操作符都实现 next 函数：

每次调用next时，操作符要么返回单个元组，要么返回空标记(如果没有更多的元组)。
运算符实现了一个循环，该循环在其子级上调用next以检索其元组，然后处理它们(即，在父级上调用next，在其子级上调用next)。
一些操作符会一直阻塞，直到子级发出它们的所有元组(联接、子查询、排序依据)。这些被称为管道断路器pipeline breakers。

输出控制很容易使用这种方法(LIMIT)，因为一旦拥有了所需的所有元组，操作符就可以停止对其子运算符调用next。

Materialization Model（物化模型）

每个 operator 一次处理其所有输入，然后一次发出其所有输出。operator 将其输出“物化”为单个结果。

每个查询计划操作符都实现一个Output 函数：

操作符一次处理其子代的所有元组。
此函数的返回结果是运算符将发出的所有元组。当操作符完成执行时，DBMS再也不需要返回到它来检索更多数据。
这种方法更适合于OLTP工作负载，因为查询一次通常只访问少量的元组。因此，检索元组的函数调用较少。不适合具有大型中间结果的OLAP查询，因为DBMS可能不得不在操作符之间将这些结果溢出到磁盘。

Vectorization Model

就像迭代模型，其中每个操作符实现一个next函数。但每个运算符都会发出大量数据(即向量)，而不是单个元组：

运算符实现可以针对处理批数据进行优化，而不是一次只处理一个项目。
此方法非常适合必须扫描大量元组的OLAP查询，因为调用next函数的次数较少。

3. 访问方法 Access Methods

访问方法是DBMS访问 表中存储的数据 的方式。这些将是查询计划中的底部操作符，它们将数据“feed”到树中它上面的操作符中。关系代数中没有相应的运算符。

顺序扫描 Sequential Scan
对于表中的每一页，迭代每一页并从缓冲池中检索它。对于每个页面，迭代所有元组并计算谓词以决定是否包含元组。

优化：

• 预取 Prefetching：提前获取下几个页面，以便DBMS在访问每个页面时不必阻塞。
• 并行化 Parallelization：使用多个线程/进程并行执行扫描。
• 缓冲池绕过 Buffer Pool Bypass：扫描操作符将其从磁盘获取的页面存储在其本地内存中，而不是缓冲池中。这避免了顺序洪泛问题。
• 区域映射 Zone Map：预计算页面中每个元组属性的聚合。然后，DBMS可以通过首先检查其区域映射来检查它是否需要访问页面。每个页面的区域映射存储在单独的页面中，并且每个区域映射页面中通常有多个条目。因此，可以减少在顺序扫描中检查的总页数。
• 延迟物化 Late Materialization：每个操作符传递给下一个操作符所需的最少量信息(例如，记录ID)。这仅在列存储系统(即DSM)中有用。
• 堆聚簇 Heap Clustering：元组按照聚簇索引指定的顺序存储在堆页面中。

索引扫描 Index Scan

DBMS选择一个(或多个)索引来查找查询所需的元组。

当使用多个索引时，DBMS对每个索引执行搜索并生成一组匹配的记录ID。可以使用位图、哈希表或Bloom过滤器来实现此记录ID。DBMS根据查询的谓词(UNION和INTERSECT)组合这些集合。然后，它检索记录并应用任何剩余的术语。更高级的DBMS支持多索引扫描。

按元组在非聚簇索引中出现的顺序检索元组效率较低。DBMS可以首先找出它需要的所有元组，然后根据它们的页面ID对它们进行排序。

4. 表达评估 Expression Evaluation

DBMS将查询计划表示为树。运算符内部将是一个表达式树。例如，filter 操作符的 WHERE 子句。

树中的节点代表不同的表达式类型：

• 比较(=、<、>、！=)
• 交集(AND)、并集(OR)
• 算术运算符(+、-、*、/、%)
• 常量和参数V值
• 元组属性引用

为了在运行时计算表达式树，DBMS维护一个上下文句柄，该句柄包含执行的元数据，如当前元组、参数和表架构。然后，DBMS遍历树以计算其操作符并生成结果。