跳转至

查询优化

相同意思的查询语句有多种表达方式，而我们期望选择产生中间结果最小的，执行代价最小的。

给定一个关系代数表达式，查询优化器的任务是产生一个查询执行计划，该计划能够计算出与给定表达式相同的结果，并且能够以代价最小（或者至少代价比较可以接受）的方式来产生结果。

关系表达式的转换

存在以下的等价规则：

  1. 合取选择运算可以分解为单个选择运算的序列：\(\sigma_{F_1 \land F_2}(r) = \sigma_{F_1}(\sigma_{F_2}(r))\)

  2. 选择运算满足交换律：\(\sigma_F(r_1 \land r_2) = \sigma_F(r_2 \land r_1)\)

  3. 在一系列投影运算中，只有最后一个是必须的，其余可以省略。\(\prod_{L_1} \prod_{L_2} \prod_{L_3} E = \prod_{L_1} E\)

  4. 选择运算可以与笛卡尔积和\(\theta\)连接相结合：\(\sigma_F(r \times s) = E_1 \bowtie_{\theta} E_2\), 且\(\sigma_{\theta_1}(E_1 \bowtie_{\theta_1\land \theta_2} E_2) = E_1 \bowtie_{\theta_1} \sigma_{\theta_2}(E_2)\)

  5. \(\theta\)连接满足交换律，\(E_1 \bowtie_\theta E_2 = E_2 \bowtie_\theta E_1\)

  6. 自然连接满足结合律，\((E_1 \bowtie E_2) \bowtie E_3 = E_1 \bowtie (E_2 \bowtie E_3)\)，而\(\theta\)连接满足以下结合律\((E_1\bowtie_{\theta_1} E_2) \bowtie_{\theta_2 \land \theta_3} E_3 = E_1 \bowtie_{\theta_1 \land \theta_3}(E_2\bowtie_{\theta_2} E_3)\)，其中\(\theta_2\)只涉及\(E_2\)和\(E_3\)的运算。

  7. 选择条件\(\theta_1\)中的所有属性只涉及一个被连接的表达式的属性时，满足以下分配律

\[ \sigma_{\theta_1}(E_1 \bowtie_{\theta} E_2) \equiv (\sigma_{\theta_1}(E_1)) \bowtie_{\theta} E_2 \]

如果\(\theta_1\)只涉及\(E_1\)，\(\theta_2\)只涉及\(E_2\)

\[ \sigma_{\theta_1 \land \theta_2}(E_1 \bowtie_{\theta} E_2) \equiv (\sigma_{\theta_1}(E_1)) \bowtie_{\theta} (\sigma_{\theta_2}(E_2)) \]
  1. 投影运算在如下条件下对\(\theta\)连接运算满足分配律： 令\(L_1\)和\(L_2\)分别代表\(E_1\)和\(E_2\)的属性，假设连接条件\(\theta\)只涉及\(L_1\cup L_2\)中的属性
\[ \Pi_{L_1 \cup L_2}(E_1 \bowtie_{\theta} E_2) \equiv (\Pi_{L_1}(E_1)) \bowtie_{\theta} (\Pi_{L_2}(E_2)) \]

\(L_1\)和\(L_2\)分别代表\(E_1\)和\(E_2\)的属性，\(L_3\)是\(E_1\)中出现在\(\theta\)但不出现在\(L_2\)中的属性；\(L_4\)同理

\[ \Pi_{L_1 \cup L_2}(E_1 \bowtie_{\theta} E_2) \equiv \Pi_{L_1 \cup L_2}\left((\Pi_{L_1 \cup L_3}(E_1)) \bowtie_{\theta} (\Pi_{L_2 \cup L_4}(E_2))\right) \]

  1. 集合的并与交运算满足交换律：\(E_1\cap E_2 = E_2\cap E_1, E_1\cup E_2 = E_2\cup E_1\)，集合的差运算不满足

  2. 集合的并与交运算满足结合律：\((E_1\cup E_2)\cup E_3=E_1\cup(E_2\cup E_3)\)，\((E_1\cap E_2)\cap E_3=E_1\cap(E_2\cap E_3)\)

  3. 选择运算对集合的分配律

\[ \sigma_{\theta}(E_1 \cup E_2) \equiv \sigma_{\theta}(E_1) \cup \sigma_{\theta}(E_2) \]
\[ \sigma_{\theta}(E_1 \cap E_2) \equiv \sigma_{\theta}(E_1) \cap \sigma_{\theta}(E_2) \]
\[ \sigma_{\theta}(E_1 - E_2) \equiv \sigma_{\theta}(E_1) - \sigma_{\theta}(E_2) \]
  1. 投影运算对并满足分配律
\[ \Pi_L(E_1 \cup E_2) \equiv (\Pi_L(E_1)) \cup (\Pi_L(E_2)) \]
  1. G是一组属性的集合，A是一组聚集表达式的集合。当\(\theta\)仅设计G中的属性时，下面的表达式成立
\[ \sigma_{\theta}(G_{\gamma(A)}(E)) \equiv G_{\gamma(A)}(\sigma_{\theta}(E)) \]
  1. 全外连接满足交换律
\[ E_1 \bowtie E_2 \equiv E_2 \bowtie E_1 \]

左外连接和右外连接没有交换律，但是可以以以下形式交换：

\[ E_1 \bowtie_{\text{左}} E_2 \not\equiv E_2 \bowtie_{\text{右}} E_1 \]
  1. 在某些情况下，选择运算对左外连接和右外连接满足交换律，具体而言，当选择条件\(\theta_1\)只涉及被连接的其中一个表达式（比如\(E_1\)）中的属性时，下面的规则成立：
\[ \sigma_{\theta_1}(E_1 \bowtie_{\text{左}\theta} E_2) \equiv (\sigma_{\theta_1}(E_1)) \bowtie_{\text{左}\theta} E_2 \]
\[ \sigma_{\theta_1}(E_2 \bowtie_{\text{右}\theta} E_1) \equiv E_2 \bowtie_{\text{右}\theta} (\sigma_{\theta_1}(E_1)) \]
  1. 某些情况下，外连接可以替换为内连接：每当\(E_2\)的属性是空时：
\[ \sigma_{\theta_1}(E_1 \bowtie_{\text{左}\theta} E_2) \equiv \sigma_{\theta_1}(E_1 \bowtie E_2) \]
\[ \sigma_{\theta_1}(E_2 \bowtie_{\text{右}\theta} E_1) \equiv \sigma_{\theta_1}(E_2 \bowtie E_1) \]

应用上面的规则可以将查询的中间结果缩小

选择合理的连接次序很重要！

查询优化器可以使用等价规则来系统地产生与给定的查询表达式等价的表达式，表达式的代价时根据统计信息来计算的。

表达式结果的统计信息估计

数据库系统目录存储了有关数据库关系的下面统计信息：

  • \(n_r\) 关系 r 中的元组数
  • \(b_r\) 包含关系 r 中元组的块数
  • \(l_r\) 关系r中一个元组的字节数
  • \(f_r\) 关系r的块因子，一个块中能够容纳的关系r的元组数
  • \(V(A,r)\) 关系 r 中出现的对于属性A的非重复值数量

关于索引的统计信息，比如B+树索引的高度和叶节点的页数也在目录中维护。

但是每次更新都维护这个信息的代价太大，所以一般的选择是在系统处于轻负载的时候更新这些统计信息。

选择规模估计

对于\(\sigma_{A=a}(r)\)，如果a是一个出现次数有可用统计值的频繁出现的值，可以直接使用，否则就假设数据是均匀分布的然后进行估计。

对于\(\sigma_{A\leq v} (r)\)，假设有最大值和最小值的数据，如果大于最大值和小于最小值很好估计，否则就假设在这个区间内均匀分布。

复杂选择，比如合取和析取，对每个组合的简单规则用上面的规则进行估计，然后假设各条件相互独立，进行估计。合取就是简单乘积

连接规模估计

笛卡尔积相对简单，\(r\times s\)的元组数为\(n_r*n_s\)。每个元组占用\(l_r+l_s\)个字节。

估计自然连接的规模会困难一点，假设\(r(R)\)和\(s(S)\)为两个关系

  • 若\(R\cap S\)为空，则\(r\bowtie s\)的元组数为\(n_r*n_s\)
  • 若\(R\cap S\)是R的码，s的一个元组至多与r的一个元组相连接，所以不会超过s中的元组数，如果是s的码，同理
  • \(R\cap S\)既不是R的码也不是S的码。这种情况下，每个值是等概率出现的。考虑r中的元组\(t\)，且\(R\cap S=\{A\}\)，估计元组t在\(r\bowtie s\)中产生\(\frac {n_s} {V(A,s)}\)个元组。估计一共有\(\frac {n_r*n_s} {V(A,s)}\)个元组。

对于\(\theta\)连接，可以写成\(\sigma_{\theta}(r\times s)\)，然后用估计选择运算和估计笛卡尔积运算的方式来估计它的规模。

执行计划的选择

虽然理论上的连接的方案很多，但是实际上可以用动态规划算法，复用前面找到的最优结果而不是对每个一直重新算。

物理等价规则：允许诸如连接那样的逻辑运算转换成散列-连接、嵌套-循环连接这样的物理运算

但是即使查询优化的代价可以通过巧妙的算法来降低，但是一个查询的不同执行计划的数量还是非常大，仍然需要很大的计算代价。所以还有一些启发式的方法：

  • 尽早执行选择运算
  • 尽早执行投影运算