Chapter 12 Query Execution Part 1

PROCESSING MODEL

A DBMS's processing model defines how the system executes a query plan.

Different trade-offs for different workloads

ITERATOR MODEL

Each query plan operator implements a Next() function.

• On each invocation, the operator returns either a single tuple or a null marker if there are no more tuples.
• The operator implements a loop that calls Next() on its children to retrieve their tuples and then process them.

This is used in almost every DBMS. Allows for tuple pipelining.

Some operators must block until their children emit all their tuples. (Joins, Subqueries, Order By)

Output control works easily with this approach.

MATERIALIZATION MODEL

Each operator processes its input all at once and then emits its output all at once.

• The operator "materializes" its output as a single result.
• The DBMS can push down hints (e.g., LIMIT) to avoid scanning too many tuples.
• Can send either a materialized row or a single column.

The output can be either whole tuples (NSM) or subsets of columns (DSM).

Better for OLTP workloads because queries only access a small number of tuples at a time.

• Lower execution / coordination overhead.
• Fewer function calls.

Not good for OLAP queries with large intermediate results.

为什么物化模型适合OLTP工作负载而不适合OLAP查询

OLTP工作负载

• 特点：OLTP（在线事务处理）工作负载通常涉及大量的小型事务，每个事务只访问少量记录。这些事务通常是短时间的，并且要求低延迟。
• 适用原因：
  • 低开销：物化模型在处理少量元组时效率更高，因为每个操作符可以一次性处理并生成结果，减少了执行和协调的开销。
  • 减少函数调用：在OLTP系统中，减少函数调用可以进一步降低延迟，提高系统的整体性能。

OLAP查询

• 特点：OLAP（在线分析处理）查询通常涉及 对大量数据的复杂分析操作。这些查询通常需要处理和传递大量的中间结果，并且需要较长时间来完成。
• 不适用原因：
  • 大中间结果： 物化模型需要一次性处理并存储所有中间结果，这在处理大规模数据时会导致内存和存储资源的巨大消耗。
  • 效率低下：对于需要多次扫描和处理大数据集的复杂查询，物化模型的效率较低，因为 每个中间结果都需要完全物化，这增加了计算和存储的开销。

物化模型在处理少量数据时具有高效和低延迟的优势，非常适合OLTP工作负载，但在处理需要大量中间结果的大规模数据分析时，效率较低，不适合OLAP查询。

VECTORIZATION MODEL

Like the Iterator Model where each operator implements a Next() function, but…

Each operator emits a batch of tuples instead of a single tuple.

• The operator's internal loop processes multiple tuples at a time.
• The size of the batch can vary based on hardware or query properties.

• Ideal for OLAP queries because it greatly reduces the number of invocations per operator.
• Allows for operators to more easily use vectorized (SIMD) instructions to process batches of tuples.

Materialization vs. Vectorization

场景：假设我们有一个数据库查询，需要对一个包含数百万行的表进行聚合操作，例如计算每个类别的总销售额。

物化模型 (Materialization Model)

1. 操作过程：

   • 操作符一次性读取整个表的数据，计算每个类别的总销售额，并将结果全部存储在内存中（或临时磁盘存储）。
   • 完成聚合操作后，将所有结果一次性发出给下一个操作符使用。

2. 示例：

   • 假设表中有100万行，每行包含一个类别和销售额。物化模型会读取所有100万行，计算每个类别的总销售额，然后将整个结果集（例如包含1000个类别的总销售额）一次性传递给下一个操作符。
   • 中间结果（总销售额）被完全物化，可能需要大量内存或磁盘空间。

3. 特点：

   • 适用于每次处理少量数据的场景，因为每次处理时可以一次性完成，减少了函数调用和执行开销。
   • 对于需要处理大量数据的复杂查询，物化模型会产生大量中间结果，导致内存和存储资源消耗较大。

向量化模型 (Vectorization Model)

1. 操作过程：

   • 操作符以批处理的方式读取表的数据，一次处理多个元组（例如一次处理1000行）。
   • 内部循环一次处理这一批数据，计算每个类别的总销售额，并将这一批次的结果传递给下一个操作符。

2. 示例：

   • 假设表中有100万行，每行包含一个类别和销售额。向量化模型会将数据分成多个批次（例如每次处理1000行），每次计算1000行的总销售额，然后将这一批次的结果传递给下一个操作符。
   • 批处理减少了函数调用的次数，提高了缓存命中率和处理效率。

3. 特点：

   • 适用于需要处理大量数据的场景，因为批处理方式更好地利用了CPU缓存和向量化指令，提高了整体处理性能。
   • 通过减少函数调用和优化内存访问，可以更高效地处理大规模数据，适合OLAP查询。

对比总结

1. 物化模型：整个数据集一次性处理和物化，适合处理较小规模的数据，特别是OLTP工作负载。对于大规模数据处理不够高效，因为所有中间结果都需要完全物化，导致资源消耗较大。

2. 向量化模型：通过批处理方式处理数据，每次处理较小规模的数据批次，但 整体上可以处理大规模数据。适合处理大规模数据和复杂查询，特别是OLAP工作负载。向量化模型通过优化内存访问和函数调用，提高了整体处理效率。

3. 向量化模型并不仅仅是“规模较小”的物化模型，而是通过批处理来优化处理大规模数据的一种方法。

4. 向量化模型更注重批处理的效率和内存的优化使用，以提高大规模数据处理的性能。
5. 物化模型更适合一次性处理和生成完整结果，但在大规模数据处理上性能较低。

PLAN PROCESSING DIRECTION

Approach #1: Top-to-Bottom

• Start with the root and "pull" data up from its children.
• Tuples are always passed with function calls.

Approach #2: Bottom-to-Top

• Start with leaf nodes and push data to their parents.
• Allows for tighter control of caches/registers in pipelines. (since it can reduce function calls)

ACCESS METHODS

An access method is the way that the DBMS accesses the data stored in a table.

Not defined in relational algebra.

Three basic approaches:

• Sequential Scan
• Index Scan (many variants)
• Multi-Index Scan

SEQUENTIAL SCAN

For each page in the table:

• Retrieve it from the buffer pool.
• Iterate over each tuple and check whether to include it.

The DBMS maintains an internal cursor that tracks the last page / slot it examined.

SEQUENTIAL SCAN: OPTIMIZATIONS

DATA SKIPPING

Approach #1: Approximate Queries (Lossy)

• Execute queries on a sampled subset of the produce approximate results.

Approach #2: Zone Maps (Loseless)

• Pre-compute columnar aggregations per page that allow the DBMS to check whether queries need to access it.
• Trade-off between page size vs. filter efficacy.

数据跳过是数据库系统优化查询性能的一种方法，通过避免访问与查询无关的数据来提高效率。这里讨论了两种数据跳过的实现方法：近似查询和区域映射。

Note

方法 #1：近似查询 (Approach #1: Approximate Queries)（有损）

1. 方法说明：

   • 对数据库中的一部分数据进行采样，并在这个采样子集上执行查询，从而得到近似的查询结果。

2. 特点：

   • 近似结果：由于只对一部分数据进行操作，结果是近似的，而非精确的。
   • 提高速度：减少了需要处理的数据量，从而加快了查询速度。
   • 有损性：结果不完全准确，有一定的误差。

3. 示例：

   • 假设我们有一个包含10亿行数据的表。通过随机采样，只选择其中的1%（即1000万行）进行查询。虽然结果不完全精确，但能在很短的时间内提供一个大致的答案。

方法 #2：区域映射 (Approach #2: Zone Maps)（无损）

1. 方法说明：

   • 在每页数据上预先计算列的聚合信息（如最小值和最大值），以便数据库管理系统（DBMS）能够检查查询是否需要访问该页。
   • 页面大小和过滤效率之间存在权衡：页面越小，过滤效率越高，但可能导致更多的页面元数据；页面越大，过滤效率降低，但元数据减少。

2. 特点：

   • 无损性：结果是精确的，不会有数据丢失。
   • 高效过滤：通过预先计算的聚合信息，DBMS可以快速判断某些数据页是否包含查询所需的数据，从而跳过不相关的页。
   • 性能优化：减少了需要扫描的页面数量，提高了查询性能。

3. 示例：

   • 假设我们有一个包含年龄列的表。对于每个数据页，预先计算该页中的最小年龄和最大年龄。
   • 当执行一个查询，比如查找年龄在20到30岁之间的所有记录时，DBMS可以利用这些预先计算的最小值和最大值，快速跳过那些年龄范围不在20到30岁的页面。

ZONE MAPS

Pre-computed aggregates for the attribute values in a page. DBMS checks the zone map first to decide whether it wants to access the page.

INDEX SCAN

The DBMS picks an index to find the tuples that the query needs.

MULTI-INDEX SCAN

If there are multiple indexes that the DBMS can use for a query:

• Compute sets of Record IDs using each matching index.
• Combine these sets based on the query's predicates (union vs. intersect).
• Retrieve the records and apply any remaining predicates.

Note

多索引扫描通过利用多个索引的优势，结合记录ID集合来提高查询效率。它可以有效减少全表扫描，提高查询性能。主要步骤包括：

• 通过每个匹配索引计算记录ID集合
• 根据查询条件合并这些集合（并集或交集）
• 检索记录并应用剩余的查询谓词

Example-1 (2 indexes)

假设我们有一个员工表 employees，有两个索引，一个是基于年龄的索引（index_age），另一个是基于部门的索引（index_department）。我们要执行一个查询，查找年龄在30岁以上且部门为“销售”的员工：

SELECT * FROM employees WHERE age > 30 AND department = 'Sales';

1. 计算每个匹配索引的记录ID集合：

   • 使用 index_age 查找年龄大于30岁的员工，得到记录ID集合：{1, 2, 3, 5, 6}。
   • 使用 index_department 查找部门为“销售”的员工，得到记录ID集合：{2, 3, 4, 6, 7}。

2. 合并这些集合：

   • 查询条件是“和”（AND），因此需要计算两个集合的交集。
   • 交集结果：{2, 3, 6}。

3. 检索记录并应用剩余的查询谓词：

   • 根据记录ID集合 {2, 3, 6}，从表 employees 中检索实际记录。
   • 对这些记录应用任何剩余的查询谓词（在本例中已经全部应用），得到最终的查询结果。

Example-2 (2+ indexes)

MODIFICATION QUERIES

Operators that modify the database (INSERT, UPDATE, DELETE) are responsible for modifying the target table and its indexes.

• Constraint checks can either happen immediately inside of operator or deferred until later in query/transaction.

The output of these operators can either be Record Ids or tuple data (i.e., RETURNING).

UPDATE/DELETE:

• Child operators pass Record IDs for target tuples.
• Must keep track of previously seen tuples.

INSERT:

• Choice #1: Materialize tuples inside of the operator.
• Choice #2: Operator inserts any tuple passed in from child operators.

INSERT

修改操作的职责

• 修改目标表：操作符负责对表中的数据进行插入、更新或删除。
• 修改索引：操作符还必须更新相关的索引，以保持数据一致性和索引的正确性。

这些修改操作的输出可以有两种形式：

1. 记录ID (Record IDs)：
2. 操作符可以返回被插入、更新或删除记录的ID。

3. 这些ID可以用于后续操作或日志记录。

4. 元组数据 (Tuple Data)：

5. 操作符可以返回修改后的数据。
6. 例如，RETURNING 子句允许在执行 INSERT、UPDATE 或 DELETE 后 返回被修改的行的数据。
7. 这对于需要立即使用修改后的数据的情况非常有用。

INSERT 操作

假设我们有一个表 employees，插入新员工时需要检查唯一约束（如员工ID）和外键约束（如部门ID）。我们还希望插入后返回新员工的详细信息。

INSERT INTO employees (employee_id, name, department_id) 
VALUES (123, 'Alice', 10)
RETURNING *;

1. 约束检查：
2. 如果立即检查：插入时会立即检查员工ID的唯一性和部门ID的外键约束。

3. 如果延迟检查：插入后暂时允许约束违规，最终在事务提交时进行检查。

4. 输出形式：

5. RETURNING * 返回新插入的员工的详细信息，包括 employee_id、name 和 department_id。

UPDATE

UPDATE 操作

更新员工的部门，并返回更新后的员工信息：

UPDATE employees 
SET department_id = 20 
WHERE employee_id = 123
RETURNING *;

1. 约束检查：
2. 如果立即检查：更新时会立即检查部门ID的外键约束。

3. 如果延迟检查：更新后暂时允许约束违规，最终在事务提交时进行检查。

4. 输出形式：

5. RETURNING * 返回更新后的员工信息，包括 employee_id、name 和新的 department_id。

DELETE

DELETE 操作

删除一个员工，并返回被删除的员工信息：

DELETE FROM employees 
WHERE employee_id = 123
RETURNING *;

1. 约束检查：
2. 如果立即检查：删除时会立即检查任何相关的约束，如外键引用。

3. 如果延迟检查：删除后暂时允许约束违规，最终在事务提交时进行检查。

4. 输出形式：

5. RETURNING * 返回被删除的员工的信息，包括 employee_id、name 和 department_id。

HALLOWEEN PROBLEM

Anomaly where an update operation changes the physical location of a tuple, which causes a scan operator to visit the tuple multiple times.

• Can occur on clustered tables or index scans.

Solution: Track modified record ids per query.

EXPRESSION EVALUATION

The DBMS represents a WHERE clause as an expression tree.

Evaluating predicates in this manner is slow.

This idea is to avoid traversing the entire tree for each tuple, instead, it uses "Hardcode" to operate on each single tuple.

Expression trees are flexible but slow. JIT compilation can (sometimes) speed them up.

JIT (Just-In-Time) 编译是一种在程序运行期间将代码编译成机器码的技术，而不是在程序执行之前就完成编译。JIT 编译可以在代码实际执行之前对其进行优化，以提高运行时性能。以下是关于 JIT 编译的一些详细信息：

JIT 编译的工作原理

1. 解释执行：

   • 在程序开始执行时，解释器会逐行解释和执行代码。
   • 这种方法的缺点是每次执行代码时都需要进行解释，导致性能较低。

2. 热点检测：

   • JIT 编译器会监视代码的执行，识别出哪些部分是“热点”，即被频繁执行的代码段。
   • 这些热点代码段是 JIT 编译优化的主要目标，因为优化这些部分可以显著提高程序的整体性能。

3. 编译优化：

   • 识别出热点代码后，JIT 编译器会将这些代码编译成机器码。
   • 在编译过程中，JIT 编译器可以应用多种优化技术，例如内联展开、循环优化、常量折叠等，以生成高效的机器码。

4. 执行优化后的机器码：

   • 编译后的机器码存储在内存中，后续的执行可以直接使用这些优化后的代码，而不再需要解释执行。
   • 这种方式显著提高了执行效率，因为机器码可以直接在 CPU 上运行，无需解释器的参与。

示例

Java 和 .NET 等平台广泛使用 JIT 编译。例如，Java 虚拟机 (JVM) 中的 HotSpot JIT 编译器和 .NET 的 CLR (Common Language Runtime) 中的 JIT 编译器都是通过在运行时编译字节码来提高程序性能的。

假设我们有一段简单的 Java 代码：

public class Example {
    public static void main(String[] args) {
        for (int i = 0; i < 1000000; i++) {
            System.out.println("Hello, JIT!");
        }
    }
}

1. 初始执行：在程序开始时，解释器逐行解释和执行代码。
2. 热点检测：JIT 编译器识别出 for 循环和 System.out.println 是热点代码。
3. 编译优化：JIT 编译器将热点代码编译成机器码，并应用优化技术，如内联展开和循环优化。
4. 执行机器码：后续执行直接使用编译后的机器码，大大提高了执行效率。

总结

JIT 编译是一种在运行时将代码编译成机器码的技术，通过实时优化可以显著提高程序的执行性能。它广泛应用于 Java、.NET 等平台，用于提高解释性语言和虚拟机运行时的性能。