关系代数等价性与查询优化策略解析

### 关系代数等价性与查询优化策略解析 在数据库查询处理中，查询优化是提升性能的关键环节。查询优化器的核心任务是在众多可能的查询执行计划中挑选出成本最低的方案。这一过程依赖于关系代数等价性原理以及对不同查询场景的细致分析。 #### 1. 关系代数等价性 关系代数等价性为查询优化提供了理论基础，它允许优化器将一个关系代数表达式转换为另一个等价的表达式，而不改变查询结果。以下是几种重要的关系代数等价规则： - **选择操作等价性** - **选择级联**：$\sigma_{c_1\land c_2\land...c_n}(R) \equiv \sigma_{c_1}(\sigma_{c_2}(...(\sigma_{c_n}(R))...))$。此规则可将多个选择操作合并为一个，也可将一个复杂选择条件拆分为多个小选择操作，便于与其他等价规则结合使用。 - **选择交换律**：$\sigma_{c_1}(\sigma_{c_2}(R)) \equiv \sigma_{c_2}(\sigma_{c_1}(R))$，即选择条件的测试顺序可以互换。 - **投影操作等价性**：$\pi_{a_1}(R) \equiv \pi_{a_1}(\pi_{a_2}(...(\pi_{a_n}(R))...))$，其中$a_i$是关系$R$的属性集，且$a_i \subseteq a_{i + 1}$（$i = 1...n - 1$）。该规则表明连续消除列与直接消除除最终投影保留列之外的所有列是等价的，有助于与其他等价规则协同优化。 - **叉积和连接操作等价性** - **交换律**：$R \times S \equiv S \times R$，$R \bowtie S \equiv S \bowtie R$。这使得在连接两个关系时，可以灵活选择内外关系。 - **结合律**：$R \times (S \times T) \equiv (R \times S) \times T$，$R \bowtie (S \bowtie T) \equiv (R \bowtie S) \bowtie T$。结合交换律，意味着在连接多个关系时，可以任意选择连接顺序，这是查询优化器生成替代查询评估计划的基础。 - **选择、投影和连接的综合等价性** - **选择与投影交换**：若选择操作仅涉及投影保留的属性，则$\pi_{a}(\sigma_{c}(R)) \equiv \sigma_{c}(\pi_{a}(R))$。 - **选择与叉积或连接结合**：$R \bowtie_{c} S \equiv \sigma_{c}(R \times S)$，$\sigma_{c}(R \times S) \equiv \sigma_{c}(R) \times S$（$c$仅涉及$R$的属性），$\sigma_{c}(R \bowtie S) \equiv \sigma_{c}(R) \bowtie S$（$c$仅涉及$R$的属性）。这些规则可将部分选择条件提前到叉积或连接操作之前执行。 - **投影与叉积或连接交换**：$\pi_{a}(R \times S) \equiv \pi_{a_1}(R) \times \pi_{a_2}(S)$，$\pi_{a}(R \bowtie_{c} S) \equiv \pi_{a_1}(R) \bowtie_{c} \pi_{a_2}(S)$（$a_1$是$a$中出现在$R$的属性子集，$a_2$是$a$中出现在$S$的属性子集，且连接条件$c$中的属性都在$a$中）。 #### 2. 替代计划枚举 查询优化器在处理查询时，会枚举一定数量的替代计划，并选择估计成本最低的计划。但并非所有代数等价计划都会被考虑，因为这样会使优化成本过高。以下分单关系查询和多关系查询两种情况进行讨论： - **单关系查询** - **无索引计划**：以查询“对于每个大于 5 的评级，打印该评级以及该评级下 20 岁水手的数量，前提是至少有两个不同姓名的此类水手”为例，在没有合适索引的情况下，基本方法是扫描关系，对每个检索到的元组应用选择和投影操作，然后根据`GROUP BY`子句对结果进行排序，最后计算聚合函数。成本包括文件扫描成本、写出中间结果成本和排序成本。 - **利用索引的计划** - **单索引访问路径**：若有多个索引匹配`WHERE`子句中的选择条件，优化器可选择估计检索页面最少的访问路径，应用投影和非主选择项，再进行分组和聚合操作。 - **多索引访问路径**：多个匹配索引可用于检索一组记录标识符（rids），将这些 rids 集合相交，按页面 ID 排序后检索满足所有匹配索引主选择项的元组，再进行后续操作。