高级数据库笔记-分布查询

2020-07-02

1. 概述

输入：片段查询
输出：分布执行计划
找到好的（不必最优的）全局调度
- 基于代价的优化
  - 搜索空间(Solution space)
  - 代价函数(Cost function)
    - I/O 代价 + CPU 代价+ communication代价
  - 搜索算法(Search algorithm)

2. 优化的理论基础

分布执行过程实际上就是从查询场地发出查询命令、从数据源获取数据、确定最佳的执行场地和返回执行结果的过程
查询场地：指发出查询命令和存储最终查询结果的场地
源数据场地：指查询命令需要访问的数据副本所在的场地，可能涉及到一个或一个以上的场地
执行场地：指查询操作执行所在的场地。 执行场地可以和查询场地或源数据场地处于同一场地，也可不处于同一场地

2.1. 内容

确定执行查询的站点和需要移动的副本
确定片段查询表达式操作执行的最优顺序
- 重点是并操作和联接操作
选择执行每个操作的方法
- 如：尽量将同一场地上的、同一物理副本的全部操作组合在一起统一考虑完成

2.2. 代价模型

主要指传输代价（Ccom）、I/O代价（CIO）和CPU代价（Ccpu）
$Total cost = C_{com}+C_{IO}+C_{cpu}$
传输代价
费用
延迟
其中费用起决定作用
$C_{COM}（X）=C_0+C_1*X$
$C_0$：场地间传输数据的启动所需的固定费用（启动一次），简称启动代价
$C_1$：网络单位传输数据费用，简称单位传输代
$X$：需传输的数据量
I/O代价
$C_{IO}（X）=[X/P]*C_{IO}$
P：页面的大小
X：数据量大小
$C_{IO}$：为每页平均访问代价
CPU代价
$C_{CPU}（X）=X*C<{CPU}$
$C_{CPU}$：单位指令代价
X：为指令数

2.3. 查询模型

关系的基：指关系R包含的元组个数，记为Card(R) 

属性的长度：指属性A定义的取值字节数，记为Length(A) 

元组的长度：关系R中每个元组的字节数，记为Length(R)， Length(R)=∑Length(Ai)

关系的大小：关系R所包含的字节数，记为Size(R) Size(R)= Card(R)* Length(R)

属性的特征值：指关系R中属性A不同的属性值个数，记为Val(A) 

属性A的值域：记为Dom(A) 

属性A的最大值和最小值：记为Max(A)和Min(A)

选择度

满足选择谓词F的元组与R元组总数之比，记为ρ
- 基数：Card（S）=ρ* Card（R）
- ρ=val(T,a)/val(dom(a))

选择运算$S= σ_ρF (R)$

均匀分布

3. 半联接优化方法

对联接操作的优化有两种趋势，一种为采用半联接技术，减少联接操作的操作数，以降低传输费用；另一种为采用全联接技术，主要考虑局部代价
半联接操作是全联接操作的一种缩减。是一种导出操作，且具有不对称性。如：半联接操作（R∝T）是R与T自然连接后在R上的投影

例子

策略1：执行场地设在S2

需将EMP的Eno和Ename属性传送到S2场地
- COST = (Length(Eno)+Length(Ename))* Card(EMP) = 39*10000=39KB

策略2：执行场地设在S1 需将DEPT的Dname和Mgno属性传送到S1场地，操作后，再将结果传回场地S2。设R为结果

COST1=(Length(Dname)+Length(Mgno))*Card(DEPT) =39*100=3.9KB
COST2=(Length(Dname)+Length(Ename))* Card(R) =70*100=7KB
COST= COST1+ COST2=10.9KB

策略3：采用半联接

将DEPT的Mgno属性传送到S1场地，
- COST1=Length(Mgno)*Card(DEPT)=4*100=0.4KB
在场地S1。完成EMP与D1的联接，即实现E1=EMP∞D1。将E1的属性Eno和Ename传到S2
- COST2=(Length(Eno)+Length(Ename))* Card(E1) =39*100=3.9KB
在场地S2上计算： R=DEPT∞ E2。
COST= COST1+ COST2=0.4+3.9=4.3 KB

本质上：R′∞S =(R∝S)∞S= R∞S

4. SDD-1 系统优化技术

SDD-1 的查询优化就是对片段数据使用选择、投影、半联接操作来最大限度地缩减
SDD-1具体算法由两部分组成：一是根据评估缩减算法确定一个收益最大的执行策略，但此执行策略的效率可能不一定高；二是进行后优化处理，将基本算法得到的解进行修正，以得到更合理的执行策略

4.1. 连接图

4.2. 优化模型概要图

4.3. 基本优化思想

联接图中的每个关系都用一元运算进行局部缩减
对受益半联接集合中的所有半联接进行操作，逐个找出最优的操作
- 受益半连接集：对于一个给定的半连接集合，所有利益超过代价的半联接操作的集合，称为受益半联接集，记为P
- 半连接的代价：传输关系在连接属性上的投影的代价
  - $Cost(R∝_AS) = C_0+C_1Val(S, A) Length(S.A)$
  - $C_0$是通信启动代价，$C_1$是传输单位数据的代价
- 半连接的利益：半连接的利益是因半连接而节省了不需要传输的元组所对应的传输代价
  - $Benefit(R∝_AS)= C_1*(1-ρ)Card(R) Length(R)$
没有受益半连接，循环结束