CMU 15445 11. Query 优化

SQL是声明性的。 这意味着用户告诉DBMS他们想要什么答案，而不是如何得到答案。 因此，DBMS需要将SQL语句转换为可执行的查询计划。 但是有不同的方法来执行查询（例如，连接算法），这些计划的性能会有所不同。 因此，DBMS需要一种方法来为给定查询选择“最佳”计划。 这是DBMS优化器的工作。

有2种优化的策略：

1. 基于规则的： 通过重写QUERY来消除不高效，不需要一个成本模型。
2. 基于成本的： 使用成本模型来评估多种等价计划然后选择成本最小的。

image.png

基于规则的优化

主要有2种手段。where下沉。表达式简化。

where 下沉

image.png

上述方法可以让filter提前过滤掉很多数据，使得只有少部分数据需要传输和join，从而来提高效率。

表达式简化

移除不必要的条件。

image.png
image.png

合并条件。

image.png

基于成本分析的优化

DBMS的优化器将使用内部成本模型来估计特定查询计划的执行成本。 这提供了一种估计，以确定一个计划是否优于另一个计划而不必实际运行查询（这对于数千个计划来说会很慢）。
此估计值是一个内部指标与实际指标不具有可比性，但可以通过估算不同资源的使用情况得出：
磁盘，内存，cpu，网络

为此，DBMS在其内部目录中存储有关表，属性和索引的内部统计信息。 不同的系统会在不同时间更新统计信息。 与开源系统相比，商业DBMS具有更强大和准确的统计数据。 这些是估算值，因此成本估算通常是不准确的

Derivable 统计

image.png

存储统计

维护一个直方图，来预估一个谓词会涉及到多少
如果不均匀的话，就以桶的形式使得每个高度尽可能接近。

image.png image.png

当然也可以使用抽样法。

image.png

搜索最少COST的算法

image.png

枚举顺序，枚举计划针对每个算子，枚举获取方式对每个表。使用动态规划减少成本估计的数量。