# 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](/files/-LapLhiFd-K0h3ymRLff)

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

### Query Rewriting

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

* Predicate Pushdown
* Projections Pushdown

#### Predicate Pushdown

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

![](/files/-LapNAe4jAlZq14MNkER)

![](/files/-LapNLNF-tdxCHKIpcFm)

核心思想如下：

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

#### Projections Pushdown

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

![](/files/-LapOlNeBS4k6SZ45deL)

### 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})
$$

![](/files/-LarU2zcfYm_HWSiLkJi)

*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)
$$

其韦恩图如下所示：

![](/files/-LarWB1Rqe-kbuLR5ZhJ)

*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)
$$

其韦恩图如下所示：

![](/files/-LarWsXbvVeaDHg-28YK)

#### 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;
```

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

![](/files/-LaraXlcKkiV682OmASF)

然后再估计：

![](/files/-LaraeduBhwq8nBSXgGd)

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


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://zhenghe.gitbook.io/open-courses/cmu-15-445-645-database-systems/query-optimization.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.