本系列为 CMU 15-445 Fall 2022 Database Systems 数据库系统 [卡内基梅隆] 课程重点知识点摘录,附加个人拙见,同样借助CMU 15-445课程内容来完成MIT 6.830 lab内容。
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 中的一些理念至今仍在使用。
Heuristics/Rules
Cost-based Search
这里的 Rewriter 负责 Heuristics/Rules,Optimizer 则负责 Cost-based Search。
如果两个关系代数表达式 (Relational Algebra Expressions) 如果能产生相同的 tuple 集合,我们就称二者等价。DBMS 可以通过一些 Heuristics/Rules 来将关系几何表达式转化成成本更低的等价表达式,从而达到查询优化的目的。这些规则通常试用于所有查询,如:
Predicate 通常有很高的选择性,可以过滤掉许多无用的数据。将 Predicate 推到查询计划的底部,可以在查询开始时就更多地过滤数据,举例如下:
核心思想如下:
X=Y AND Y=3
可以修改成 X=3 AND Y=3
本方案对列存储数据库不适用。在行存储数据库中,越早过滤掉不用的字段越好,因此将 Projections 操作往查询计划底部推也能够缩小中间结果占用的空间大小,举例如下:
除了 Predicates 和 Projections 以外,许多操作没有通用的规则,如 Join:Join 操作既符合交换律又符合结合律,等价关系代数表达式数量庞大,这时候就需要一些成本估算技术,将过滤性大的表作为 Outer Table,小的作为 Inner Table,从而达到查询优化的目的。
一个查询需要花费多长时间,取决于许多因素
但本质上取决于:整个查询过程需要读入和写出多少 tuples 。
因此 DBMS 需要保存每个 table 的一些统计信息,如 attributes、indexes 等信息,有助于估计查询成本。值得一提的是,不同的 DBMS 的搜集、更新统计信息的策略不同。
通常,DBMS 对任意的 table R,都保存着以下信息:
利用上面两条数据,可以得到 selection cardinality,即 R 中 A 属性下每个值的平均记录个数:
需要注意的是,这种估计假设 R 中所有数据在 A 属性下均匀分布 (data uniformity)。
利用以上信息和假设,DBMS 可以估计不同 predicates 的 selectivity:
SELECT * FROM people WHERE age = 2;
SELECT * FROM people WHERE age >= 2;
SELECT * FROM people WHERE age != 2;
利用 equality query 可以反向推导出 negation query 的情况:
实际上这里所谓的 Selectivity 就是基于 uniformly distribution 假设下的 Probability。
SELECT * FROM people WHERE age = 2 AND name LIKE 'A%';
若假设两个 predicates 之间相互独立,则可以推导出:
其韦恩图如下所示:
SELECT * FROM people
WHERE age = 2
OR name LIKE 'A%';
若假设两个 predicates 之间相互独立,则可以推导出:
其韦恩图如下所示:
我们的公式是很好的,但是我们假设数据值是均匀分布的:
正常情况下,数据分布是不均匀的:
通过直方图(IntHistogram类)来计算选择性是通过以下步骤实现的:
通过直方图中各个桶中的数据值数量,可以估计出特定值或谓词选择的概率。具有更多数据值的桶通常具有较低的选择性,而具有较少数据值的桶通常具有较高的选择性。
请注意,选择性估计是基于对数据分布的假设和直方图的统计信息。对于非均匀分布或包含离群值的数据集,选择性估计可能会有一定的误差。因此,在进行查询优化时,需要综合考虑其他因素和优化技术。
现代 DBMSs 也会使用采样技术来降低成本估计本身的成本,比如面对如下查询:
SELECT AVG(age)
FROM people
WHERE age > 50;
我们可以等间隔从表中对数据采样:
然后再估计:
当然,为了避免重复采样,DMBS 会保存一份采样表,待 table 的变动较大时,再更新采样表。
现在我们可以(大致)估计谓词的选择性,那么我们实际上可以用它们做什么呢?
在进行基于规则的重写之后,数据库管理系统(DBMS)将为查询枚举不同的计划并估算它们的成本:
简单的启发式方法通常足够处理这个任务。
对于OLTP查询来说,选择最佳访问方法相对容易,因为它们是可搜索谓词(sargable):
多关系查询规划(Multi-Relation Query Planning)是指在执行涉及多个关系(表)的查询时进行的规划过程。这个过程包括选择适当的连接顺序、连接算法和访问方法,以生成最优的查询执行计划。
随着连接数量的增加,可供选择的备选计划数量迅速增长:
System R中的基本决策:只考虑左深连接树。
左深连接树是一种连接顺序,其中每个连接操作的右侧表是前一个连接操作的结果。这种限制连接顺序的方式有助于简化查询优化的任务,并降低了计划搜索的复杂性。
通过限制为左深连接树,查询优化器可以避免对所有可能的连接顺序进行枚举和计算,从而减少了查询优化的时间和计算成本。此外,左深连接树的特性也使得查询计划的生成和优化更加高效。
基于左深连接树的查询规划在某些情况下可以实现完全流水线化的计划,其中中间结果不需要写入临时文件:
对于每个表,枚举连接操作的顺序:
对于每个操作符,枚举计划:
对于每个表格,枚举访问路径:
在查询优化过程中,为了选择最佳的查询执行计划,需要枚举不同的连接顺序、操作符的计划和表格的访问路径。通过枚举不同的选择,可以比较它们的成本并选择最优的执行计划。
为了降低计划枚举的复杂性和避免重复的成本估计,动态规划被广泛应用于查询优化。动态规划技术可以利用之前计算过的成本估计结果,通过存储和重用中间计算结果,避免重复的计算,从而减少计算成本和时间。
通过使用动态规划,查询优化器可以有效地探索不同的连接顺序、操作符计划和表格访问路径的组合,以选择最佳的执行计划,并在优化过程中降低计算成本和复杂性。
如何生成搜索算法的计划:
立即剪除包含交叉连接的计划!
现实中的数据库管理系统并不按照这种方式进行计划生成。
实际情况更加复杂…
数据库管理系统(DBMS)将嵌套子查询在WHERE子句中视为接受参数并返回单个值或一组值的函数。
有两种处理方式:
对于更复杂的查询,优化器将查询分解为多个块,并集中处理一个块。子查询被写入临时表中,在查询完成后临时表会被丢弃。
查询优化确实是数据库管理系统中的一个具有挑战性的任务。为了实现高效的查询处理,采用了多种技术和策略。以下是其中一些技术:
查询优化是一个复杂且资源密集型的过程,涉及基于成本估计和数据的统计属性做出决策。数据库管理系统采用了各种技术来提高查询性能,但对于所有查询实现最佳性能是一项具有挑战性的任务。