cmu445_Query_Execution

Query Plan

如图所示，通常一个 SQL 会被组织成树状的查询计划，数据从 leaf nodes 流到 root，查询结果在 root 中得出。而本节将讨论在这样一个计划中，如何为这个数据流动过程建模，主要围绕：

Processing Models
Access Methods
Expression Evaluation

Processing Models

DBMS 的 processing model 定义了系统如何执行一个 query plan，目前主要有三种模型，不同模型的适用场景不同。

Model	Direction	Emits	Target
Iterator/Volcano	Top-Down	Single Tuple	General Purpose
Materialization	Bottom-Up	Entire Tuple Set	OLTP
Vectorized	Top-Down	Tuple Batch	OLAP

Iterator Model

query plan 中的每步 operator 都实现一个 next 函数，每次调用时，operator 返回一个 tuple 或者 null，后者表示数据已经遍历完毕。operator 本身实现一个循环，每次调用其 child operators 的 next 函数，从它们那边获取下一条数据供自己操作，这样整个 query plan 就被从上至下地串联起来，它也称为 Volcano/Pipeline Model：

Iterator 几乎被用在每个 DBMS 中，包括 sqlite、MySQL、PostgreSQL 等等，其它需要注意的是：

有些 operators 会等待 children 返回所有 tuples 后才执行，如 Joins, Subqueries 和 Order By；
Output Control 在 Iterator Model 中比较容易，如 Limit，只按需调用 next 即可；

Materialization Model

每个 operator 处理完所有输入后，将所有结果一次性输出，DBMS 会将一些参数传递到 operator 中防止处理过多的数据，这是一种从下至上的思路，示意如下：

materialization model适合：

OLTP 场景，因为后者通常指需要处理少量的 tuples，这样能减少不必要的执行、调度成本；
不太适合会产生大量中间结果的 OLAP 查询；

Vectorized/Batch Model

Vectorization Model 是 Iterator 与 Materialization Model 折衷的一种模型：

每个 operator 实现一个 next 函数，但每次 next 调用返回一批 tuples，而不是单个 tuple
operator 内部的循环每次也是一批一批 tuples 地处理
batch 的大小可以根据需要改变（hardware、query properties）

vectorization model 是 OLAP 查询的理想模型：

极大地减少每个 operator 的调用次数；
允许 operators 使用 vectorized instructions (SIMD) 来批量处理 tuples；

目前在使用这种模型的 DBMS 有 VectorWise, Peloton, Preston, SQL Server, ORACLE, DB2 等。

Access Methods

access method 指的是 DBMS 从数据表中获取数据的方式，它并没有在 relational algebra 中定义。主要有三种方法。

Sequential Scan

顾名思义，sequential scan 就是按顺序从 table 所在的 pages 中取出 tuple，这种方式是 DBMS 能做的最坏的打算。

for page in table.pages:
    for t in page.tuples:
        if evalPred(t):
            # do something

DBMS 内部需要维护一个 cursor 来追踪之前访问到的位置（page/slot）。Sequential Scan 是最差的方案，因此也针对地有许多优化方案：

Pre-fetching、Parallelization、Buffer Pool Bypass
本节：Zone Maps、Late Materialization、Heap Clustering

Zone Maps：

预先为每个 page 计算好 attribute values 的一些统计值，DBMS 在访问 page 之前先检查 zone map，确认一下是否要继续访问，如下图所示，当 DBMS 发现 page 的 Zone Map 中记录 val 的最大值为 400 时，就没有必要访问这个 page。

Late Materialization：

在列存储 DBMS 中，每个 operator 只选取查询所需的列数据，若该列数据在查询树上方并不需要，则仅需向上传递 offsets 即可：

Heap Clustering：

使用 clustering index 时，tuples 在 page 中按照相应的顺序排列，如果查询访问的是被索引的 attributes，DBMS 就可以直接跳跃访问目标 tuples。

Index Scan

DBMS 选择一个 index 来找到查询需要的 tuples。使用哪个 index 取决于以下几个因素：

index 包含哪些 attributes
查询引用了哪些 attributes
attribute 的定义域
predicate composition
index 的 key 是 unique 还是 non-unique

尽管选择哪个 Index 取决于很多因素，但其核心思想就是，越早过滤掉越多的 tuples 越好，如下面这个 query 所示，students 在不同 attributes 上的分布可能如下所示：

SELECT * FROM students
 WHERE age < 30
   AND dept = 'CS'
   AND country = 'US';

Scenario #1：使用 dept 的 index 能过滤掉更多的 tuples
Scenario #2：使用 country 的 index 能过滤掉更多的 tuples

Multi-Index/“Bitmap” Scan

如果有多个 indexes 同时可以供 DBMS 使用，就可以做这样的事情：

计算出符合每个 index 的 tuple id sets
基于 predicates (union vs. intersection) 来确定是对集合取交集还是并集
取出相应的 tuples 并完成剩下的处理

Postgres 称 multi-index scan 为 Bitmap Scan。仍然以上一个 SQL 为例，使用 multi-index scan 的过程如下所示，其中取集合交集可以使用 bitmaps, hash tables 或者 bloom filters。

Index Scan Page Sorting

当使用的不是 clustering index 时，实际上按 index 顺序检索的过程是非常低效的，DBMS 很有可能需要不断地在不同的 pages 之间来回切换。为了解决这个问题，DBMS 通常会先找到所有需要的 tuples，根据它们的 page id 来排序，完毕后再读取 tuples 数据，使得整个过程每个需要访问的 page 只会被访问一次。如下图所示。体现的还是一个批处理，预处理的思想。

Expression Evaluation

DBMS 使用 expression tree 来表示一个 WHERE 语句，如下图所示，然后根据 expression tree 完成数据过滤的判断，但这个过程比较低效，很多 DBMS 采用 JIT Compilation 的方式，直接将比较的过程编译成机器码来执行，提高 expression evaluation 的效率。

以上讨论的事如何将多个Operator组合在一起去执行一个query查询，我们假设查询通过单个worker或者线程执行的。下边我们讨论如何通过多个workers来执行查询。

Parallel Execution

背景

随着摩尔定律逐渐失效，处理器走向多核，系统可以通过并行执行增加吞吐量，减少延迟，使得系统响应更快。

Parallel 和 Distributed的区别：

Parallel：如运行在多核 CPU 上
- 每个 DB 节点物理上非常接近，通过高速 LAN 相连接
- 通信成本极小
Distributed：如分布式数据库
- 节点之间距离可能很远，通过公网相连接
- 通信成本和通信可能出现的问题不可忽略

Inter-query 和 Intra-query Parallelism的区别：

Inter-Query：不同的查询并行执行
- 增加吞吐量，减少延迟
Intra-Query：同样的查询的不同 operators 并行执行
- 减少长时查询的延迟，主要用于 Streaming

Process Model

DBMS 的 process model 定义了多用户数据库系统处理并发请求的架构。在下文中，用 worker 指代执行查询任务的单位，它可能是 Process(es)，也可能是 Thread(s)

Approach #1: Process per DBMS Worker

用户请求经过 Dispatcher 后，由 Dispatcher 分配相应的 Worker 完成查询并返回结果，每个 worker 都是单独的 OS Process。
- 依赖 OS scheduler 来调度
- 使用 shared-memory 来存储全局数据结构
- 单个 worker 崩溃不会引起整个系统崩溃
这种 Process Model 出现在 threads 跨平台支持很不稳定的时代，主要是为了解决系统的可移植性问题。使用这种 Process Model 的数据库有历史版本的 DB2、ORACLE 和 PostgreSQL 等。
Approach #2: Process Pool

用户请求经过 Dispatcher 后，由 Dispatcher 分配相应的 Worker 完成查询，将结果返回 Dispatcher，后者再返回给用户。每个 Worker 可以使用 Worker Pool 中任意空闲的 Process(es)：
- 依赖 OS scheduler 来调度
- 使用 shared-memory 来存储全局数据结构
- 不利于 CPU cache
使用这种 Process Model 的数据库有 DB2、PostgreSQL(2015)。
Approach #3: Thread per DBMS Worker

整个 DBMS 由一个 Process 和多个 Worker Threads 构成：
- DBMS 自己控制调度策略：每个查询拆成多少个任务、使用多少个 CPU cores、将任务分配到哪个 core 上，每个 task 的输出存储在哪里。自己控制调度策略的理由与自己构建 Buffer Pools 的理由是一样的：DBMS 比 OS 有更多的领域知识。
- dispatcher 不一定存在
- thread 崩溃可能导致整个系统崩溃
- 使用多线程架构的优势：
  - context switch 成本更低
  - 天然地可以在 threads 之间共享全局信息，无需使用 shared memory
使用这种 Process Model 的数据库有 DB2、MSSQL、MySQL、Oracle (2014) 及其它近 10 年出现的 DBMS 等。

Execution Parallelism

Inter-query Parallelism

通过并行执行多个查询来提高 DBMS 性能。如果这些查询都是只读查询，那么处理不同查询之间的关系无需额外的工作；如果查询存在更新操作，那么处理好不同之间查询的关系将变得很难。相关内容将在后续章节中介绍。
Intra-query Parallelism

通过并行执行单个查询的单个或多个 operators 来提高 DBMS 性能。这两个方法可以被同时使用，每个 relational operator 都有并行的算法实现。
- Approach #1：Intra-Operator
- Approach #2：Inter-Operator
Intra-operator Parallelism (Horizontal)

将 data 拆解成多个子集，然后对这些子集并行地执行相应的 operator，DBMS 通过将 exchange operator 引入查询计划，来合并子集处理的结果，过程类似 MapReduce，举例如下图所示：

Inter-operator Parallelism (Vertical)

将 operators 串成 pipeline，数据从上游流向下游，一般无需等待前一步操作执行完毕，也称为 pipelined parallelism，举例如下：

这种方式在传统 DBMSs 中并不常用，因为许多 operators，如 join，必须扫描所有 tuples 之后才能得到结果。它更多地被用在流处理系统，如 Spark、Nifi、Kafka,、Storm、Flink、Heron。

值得注意的是，使用额外的 processes/threads 来并行地执行查询可以通过提高 CPU 利用率来提高 DBMS 效率；但如果 DBMS 效率瓶颈出现在 disk 数据存取上，这种优化带来的效果就非常有限，甚至有可能因为 disk I/O 的提高导致整体性能下降，如 cache miss rate 提高等等。

I/O Parallelism

I/O Parallelism 通过将 DBMS 安装在多个存储设备上来实现：

Multiple Disks per Database
One Database per Disk
One Relation per Disk
Split Relation across Multiple Disks

Multi-disk Parallelism：

通过 OS 或硬件配置将 DBMS 的数据文件存储到多个存储设备上，整个过程对 DBMS 透明，如使用 RAID。一些 DBMS 甚至允许用户为单个 database 指定 disk location。

Partitioning：

Vertical Partitioning：原理上类似列存储数据库，将 table 中的部分 attributes 存储到不同的地方；
Horizontal Partitioning：基于某个可定制的 partitioning key 将 table 的不同 segments 分开存储；

包括：
- Hash Partitioning
- Range Partitioning
- Predicate Partitioning