content

1. 查询优化概述1
2. 查询优化概述2
3. 查询分解
4. 数据本地化

 
 
 

查询优化概述1

▍代价

优化的目标就是指局部执行代价和网络传输代价的和最小。

• 局部执行代价 = I/O代价 + CPU处理代价
• 网络传输代价 = 启动代价 + 传输代价

▍执行策略

▍优化思路

• 执行运算的次序
• 执行运算的方法
• 执行运算本身所在的场地
• 执行运算所需数据的场地

 
 

查询优化概述2

▍问题

分布式查询处理器需要考虑的问题是查询分解（query decomposition）和数据局部化（data localization） —— 这也是接下来两个模块的内容

▍因素

• 两个方面 —— 转换（ transformation）和优化（optimization）

• 三个代价 —— CPU Time + I/O Time + Communication Time（和上面的优化代价是对应的～）

▍时机

• 静态的（Static）：编译时进行优化；是基于统计信息的穷举优化

• 动态的（Dynamic）：执行中进行优化；准确性好但代价高

▍层次

 
 
 

查询分解

▍步骤

1. 规范化（Normalization）—— 转化为标准的and或or形式
2. 分析（Analysis）—— 对于不正确的语义，尽早拒绝
3. 约简（Simplification）—— 删除冗余谓词
4. 查询重写（Restruction）—— 重点题型，下有例题

▍Demo（约简）

select name
from LoliHouse
where (not(name = "Alice") and (name = "Cocoa" or name = "Alice") and not(name = "Cocoa")) or name = "Hana"

// 设 P1: name = "Alice"
// 设 P2: name = "Cocoa"
// 设 P3: name = "Hana"
(非P1 ∧ (P1 ∨ P2) ∧ 非P2) ∨ P3
= (非P1 ∧ P1 ∧ 非P2) ∨ (非P1 ∧ P2 ∧ 非P2) ∨ P3
= false ∨ false ∨ P3
= P3

select name
from LoliHouse
where name = "Hana"

 
▍Demo（查询重写）

运算类型	执行代价
σ, Л(不消重)	O(n)
Л(消重), group	O(nlogn)
$\times$	O(n2)
$\infty 、\cup 、\cap 、-、\propto 、÷$	O(nlogn)

准则1：尽可能将一元运算移到查询树的底部（树叶），即优先执行一元运算
准则2：利用一元运算规则，缩减每一关系，减小关系尺寸，降低I/O代价和网络传输代价

select sanme
from supplier as ser, supply as sp, part as p
where ser.sno = sp.sno and sp.pno = p.pno
and ser.area = "北方"
and sp.num > 5000
and p.pname = "PPP"

 
 
 
 

数据本地化

▍定义

数据本地化讨论的是从全局查询到片段查询的变换。

利用的是全局关系与片段关系的等价变换。

其查询树被称为片段查询树

▍步骤

• 将分片树的水平（h）节点转换为查询树的并集（$\cup$）节点
• 将分片树的垂直（v）节点转换为查询树的连接（$\infty$）节点

 
▍片段查询优化（准则）

• 准则1：一元运算下沉到叶子的片段上（再看看可否消去一部分？）
• 准则2：对于出现连接的地方，若连接条件不满足，则置空消去
• 准则3：将连接运算（$\infty$）下沉到并运算（$\cup$）的下面
• 准则4：消去不影响查询的垂直片段

▍片段查询优化（Demo）

 
 
 
 
 
 
 
 
 
 
 
 

$More$