# Query Optimization

SQL 语句让我们能够描述想要获取的数据，而 DBMS 负责来根据用户的需求来制定高效的查询计划。不同的查询计划的效率可能出现多个数量级的差别，如 Join Algorithms 一节中的 Simple Nested Loop Join 与 Hash Join 的时间对比 (1.3 hours vs. 0.45 seconds)。

Query Optimizer 第一次出现在 IBM System R，那时人们认为 DBMS 指定的查询计划永远无法比人类指定的更好。System R 的 optimizer 中的一些理念至今仍在使用。

## Query Optimization Techniques

* Heuristics/Rules
  * Rewrite the query to remove stupid/inefficient things
  * Does not require a cost model
* Cost-based Search
  * Use a cost model to evaluate multiple equivalent plans and pick the one with the lowest cost

![Query Planning Overview](https://1008303647-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LMjQD5UezC9P8miypMG%2F-LapLaibKEqy0uOzxt1N%2F-LapLhiFd-K0h3ymRLff%2FScreen%20Shot%202019-03-25%20at%2010.56.56%20PM.jpg?alt=media\&token=d222e9cb-9f81-4b8a-9de7-1085e5c0034b)

这里的 Rewriter 负责 Heuristics/Rules，Optimizer 则负责 Cost-based Search。

### Query Rewriting

如果两个关系代数表达式 (Relational Algebra Expressions) 如果能产生相同的 tuple 集合，我们就称二者等价。DBMS 可以通过一些 Heuristics/Rules 来将关系几何表达式转化成成本更低的等价表达式，从而达到查询优化的目的。这些规则通常试用于所有查询，如：

* Predicate Pushdown
* Projections Pushdown

#### Predicate Pushdown

Predicate 通常有很高的选择性，可以过滤掉许多无用的数据。将 Predicate 推到查询计划的底部，可以在查询开始时就更多地过滤数据，举例如下：

![](https://1008303647-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LMjQD5UezC9P8miypMG%2F-LapLaibKEqy0uOzxt1N%2F-LapNAe4jAlZq14MNkER%2FScreen%20Shot%202019-03-25%20at%2011.03.21%20PM.jpg?alt=media\&token=c8e921c5-e475-4f4d-84b1-c2c8e34da8ab)

![](https://1008303647-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LMjQD5UezC9P8miypMG%2F-LapLaibKEqy0uOzxt1N%2F-LapNLNF-tdxCHKIpcFm%2FScreen%20Shot%202019-03-25%20at%2011.04.05%20PM.jpg?alt=media\&token=6022c0fd-f987-40ab-a3b0-ad1e36f89a2b)

核心思想如下：

* 越早过滤越多数据越好
* 重排 predicates，使得选择性大的排前面
* 将复杂的 predicate 拆分，然后往下压，如 `X=Y AND Y=3` 可以修改成 `X=3 AND Y=3`

#### Projections Pushdown

本方案对列存储数据库不适用。在行存储数据库中，越早过滤掉不用的字段越好，因此将 Projections 操作往查询计划底部推也能够缩小中间结果占用的空间大小，举例如下：

![](https://1008303647-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LMjQD5UezC9P8miypMG%2F-LapLaibKEqy0uOzxt1N%2F-LapOlNeBS4k6SZ45deL%2FScreen%20Shot%202019-03-25%20at%2011.10.13%20PM.jpg?alt=media\&token=83992979-3776-4adb-9eba-82684d0f9634)

### Cost-based Search

除了 Predicates 和 Projections 以外，许多操作没有通用的规则，如 Join：Join 操作既符合交换律又符合结合律，等价关系代数表达式数量庞大，这时候就需要一些成本估算技术，将过滤性大的表作为 Outer Table，小的作为 Inner Table，从而达到查询优化的目的。

#### Cost Estimation

一个查询需要花费多长时间，取决于许多因素 

* CPU: Small cost; tough to estimate
* Disk: #block transfers
* Memory: Amount of DRAM used
* Network: #messages

但本质上取决于：**整个查询过程需要读入和写出多少 tuples**

因此 DBMS 需要保存每个 table 的一些统计信息，如 attributes、indexes 等信息，有助于估计查询成本。值得一提的是，不同的 DBMS 的搜集、更新统计信息的策略不同。

#### Statistics

通常，DBMS 对任意的 table R，都保存着以下信息：

* $$N\_R$$ ：R 中 tuples 的数量
* $$V(A, R)$$ ：R 中 A 属性的不同取值 (distinct values) 个数
* $$A\_{max}, A\_{min}$$ ：A 属性取值的最大和最小值

利用上面两条数据，可以得到 selection cardinality，即 R 中 A 属性下每个值的平均记录个数：

$$
SC(A, R) = N\_R / \ V(A, R)
$$

需要注意的是，这种估计假设 R 中所有数据在 A 属性下均匀分布 (data uniformity)。

利用以上信息和假设，DBMS 可以估计不同 predicates 的 selectivity：

* Equality
* Range
* Negation
* Conjunction
* Disjunction

*Equality Predicate*

```sql
SELECT * FROM people WHERE age = 2;
```

设 people 表中有 5 条个人信息，即 $$N\_R = 5$$ 所有信息中的 age 有 5 个取值，即 $$V(age, people) = 5$$：

$$
sel(A=constant) = SC(P) / V(A, R) = \frac{1}{5}
$$

*Range Predicate*

```sql
SELECT * FROM people WHERE age >= 2;
```

可以利用 $$A\_{max}, A\_{min}$$ 来估计：

$$
sel(A>= a) = (A\_{max}-a)/(A\_{max}-A\_{min})
$$

![](https://1008303647-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LMjQD5UezC9P8miypMG%2F-LarNAd0l8U0m5ptaiEs%2F-LarU2zcfYm_HWSiLkJi%2FScreen%20Shot%202019-03-26%20at%208.52.35%20AM.jpg?alt=media\&token=77833efd-a8d4-4cea-be39-9737ee48b10c)

*Negation Query*

```sql
SELECT * FROM people WHERE age != 2;
```

利用 equality query 可以反向推导出 negation query 的情况：

$$
sel(not \ P) = 1 - sel(P) = 1 - SC(age=2) = \frac{4}{5}
$$

实际上这里所谓的 Selectivity 就是基于 uniformly distribution 假设下的 Probability。

*Conjunction Query*

```sql
SELECT * FROM people
 WHERE age = 2
   AND name LIKE 'A%';
```

若假设两个 predicates 之间相互独立，则可以推导出：

$$
sel(P1 \wedge P2) = sel(P1)\bullet sel(P2)
$$

其韦恩图如下所示：

![](https://1008303647-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LMjQD5UezC9P8miypMG%2F-LarNAd0l8U0m5ptaiEs%2F-LarWB1Rqe-kbuLR5ZhJ%2FScreen%20Shot%202019-03-26%20at%209.01.57%20AM.jpg?alt=media\&token=ac9383f5-01ae-450a-b3e6-fe217e20c7c5)

*Disjunction Query*

```sql
SELECT * FROM people
 WHERE age = 2
    OR name LIKE 'A%';
```

若假设两个 predicates 之间相互独立，则可以推导出：

$$
sel(P1 \vee P2) = sel(P1) + sel(P2) - sel(P1 \wedge P2) = sel(P1) + sel(P2) - sel(P1)\bullet sel(P2)
$$

其韦恩图如下所示：

![](https://1008303647-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LMjQD5UezC9P8miypMG%2F-LarNAd0l8U0m5ptaiEs%2F-LarWsXbvVeaDHg-28YK%2FScreen%20Shot%202019-03-26%20at%209.04.59%20AM.jpg?alt=media\&token=733b1457-57a2-46d5-b648-382895dfc4ad)

#### Joins

Result Size Estimation for Joins

考虑最通用的情况：假设 $$R\_{cols} \cap S\_{cols} = {A}$$ ，其中 A 不是 R 或 S 的 key，可以从两个方向思考：

* 对 R 中的每个 tuple，找到 S 中相应的 tuples： $$estSize \approx N\_{R} \bullet N\_{S} / V(A, S)$$ 
* 对 S 中的每个 tuple，找到 R 中相应的 tuples： $$estSize \approx N\_{R} \bullet N\_{S} / V(A, R)$$ 

综合两个方向，取小的：

$$
estSize \approx N\_R \bullet N\_S / max({V(A, S), V(A, R)})
$$

#### Samling

现代 DBMSs 也会使用采样技术来降低成本估计本身的成本，比如面对如下查询：

```sql
SELECT AVG(age)
  FROM people
 WHERE age > 50;
```

我们可以等间隔从表中对数据采样：

![](https://1008303647-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LMjQD5UezC9P8miypMG%2F-LarNAd0l8U0m5ptaiEs%2F-LaraXlcKkiV682OmASF%2FScreen%20Shot%202019-03-26%20at%209.25.19%20AM.jpg?alt=media\&token=ede930c2-b8bc-450a-bc16-976dfdd6a86b)

然后再估计：

![](https://1008303647-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LMjQD5UezC9P8miypMG%2F-LarNAd0l8U0m5ptaiEs%2F-LaraeduBhwq8nBSXgGd%2FScreen%20Shot%202019-03-26%20at%209.25.53%20AM.jpg?alt=media\&token=daad12fa-9f3b-4bda-bd3e-98fdd67991d3)

当然，为了避免重复采样，DMBS 会保存一份采样表，待 table 的变动较大时，再更新采样表。