16.1 概述
查询优化(Query Optimization) 是数据库系统在诸多等价的执行计划中挑选一个代价最低者的过程。同一条 SQL 语句,写法虽然相同,但优化器可能生成的候选计划数目呈指数级增长,因此优化器必须依靠:
- 一组等价规则:用于把关系代数表达式变换成语义等价的另一种表达式;
- 统计信息:估计中间结果的规模;
- 代价模型:把物理执行计划的时间、I/O 折算为可比较的数字;
- 搜索策略:动态 规划、贪心或遗传算法,用来在庞大的计划空间中找出较优者。
优化的粒度可以分为两层:
- 逻辑优化:只在关系代数层面变换表达式,不涉及具体算法;
- 物理优化:为每个算子选择实现算法(顺序扫描 vs 索引扫描、块嵌套 vs 散列连接等),并根据统计信息估计代价。
16.2 关系表达式的转换
两个关系代数表达式若在所有实例上都产生相同的结果集合(多重集合),则称它们等价,记作 E1≡E2。优化器利用一批等价规则重写表达式,从而扩大候选计划集合。
16.2.1 等价规则
以下规则中,E,E1,E2 表示关系代数表达式,θ,θ1,θ2 表示谓词,L 表示投影属性列表。
-
合取选择级联
σθ1∧θ2(E)≡σθ1(σθ2(E))
-
选择交换
σθ1(σθ2(E))≡σθ2(σθ1(E))
-
投影只保留最外层
ΠL1(ΠL2(…(ΠLn(E))…))≡ΠL1(E)
-
选择与笛卡尔积组合成连接
σθ(E1×E2)≡E1⋈θE2
-
θ 连接的交换律
E1⋈θE2≡E2⋈θE1
-
自然连接结合律
(E1⋈E2)⋈E3≡E1⋈(E2⋈E3)
-
θ 连接结合律(需要保证 θ2 只涉及 E2,E3 的属性)
(E1⋈θ1E2)⋈θ2∧θ3E3≡E1⋈θ1∧θ3(E2⋈θ2E3)
-
选择下推到连接一侧(若 θ0 只涉及 E1 的属性)
σθ0(E1⋈θE2)≡(σθ0(E1))⋈θE2
-
投影下推(若 L1⊆attr(E1),L2⊆attr(E2),且 θ 只用到 L1∪L2)
ΠL1∪L2(E1