3章_分布式数据库中的查询处理和优化2012-12-6.ppt

集中式数据库系统查询优化 集中式数据库系统查询优化 集中式数据库系统查询优化目标 为每一个用户查询通过某种代价模型计算出各种查询执行策略的执行代价，然后选取总代价最小的执行方案。 总代价是以查询处理期间 CPU代价和I/O 代价来衡量。即尽可能降低 I/O 代价，使查询的响应时间最短。 将查询转换为代数表达式，从所有等价代数表达式中选择最优的代数表达式。 查询优化按照优化的层次分类 ： 代数优化：指关系代数表达式的优化，即按照一定的规则，改变代数表达式中操作的次序和组合，使查询执行更高效； 物理优化：指存取路径和底层操作算法的选择； 分布式数据库系统查询优化目标：两种目标 一种目标是以总代价最小为标准，除考虑CPU代价和I/O代价之外，总代价还包括通过网络在站点之间传输数据或信息的代价，即通信代价。 另一种目标是以每个查询的响应时间最短为标准。因为分布式数据库系统的数据分布和冗余增加了查询的并行处理的可能性，可以缩减查询处理的响应时间，加快查询处理速度。 在分布式查询优化中，常同时使用这两种标准，根据系统应用的不同，一种作为主要标准，另一种作为辅助标准。例如，可以先找到一个总代价最小的执行方案，然后再在总代价不增加的条件下修正方案，使得响应时间也尽可能的短。 3. 查询代价的估算方法 设一个查询执行的预期代价为QC, 则 在集中式数据库中：QC=I/O代价+CPU代价 在分布式数据库中：QC=I/O代价+CPU代价+通信代价 通信代价可用如下公式作粗略估算： TC(X) = C0 + C1 * X 其中： X：为传输数据量，通常以bit为单位计算； C0：为两站点通信初始化一次所花费的时间，它由通信系统 确定，近似一个常数，以秒为单位； C1：为传输率 (传输速度的倒数)，即单位数据传输的时间， 单位是 s/b。 例3.1 在教学数据库中，有 S( s#, sname, age, sex) 104 元组 存放在Site A C( c#, cname, teacher) 105 元组 存放在Site B SC( s#, c#, grade) 106 元组 存放在Site A 假定：若每个元组长度100Bit, 通讯传输速度 104 bit/sec, 通讯延迟时间为 1sec。 问题：要求查出所有选修’MATHS’课的男学生的学号和姓名。 解: 在分片透明性的DDBMS支持下，SQL语句是： SELECT s#, sname FROM S, C, SC WHERE S.s#=SC.s# AND C.c#=SC.c# AND sex=‘男’ AND cname=‘MATHS’; 通信代价的估算公式是： T= 传输延迟时间C0+(传输的数据量X*数据传输速率C1) = (传输次数*1) + (传输的bit数/104) 为了实现这一查询，可以有六种可能的查询策略。 传统的集合运算 传统的集合运算 传统的集合运算 广义笛卡尔积 专门的关系运算 选择运算 选择运算 投影运算 连接运算（θ连接） 等值连接 自然连接 半连接 左外连接 右外连接 全外连接 除运算 除运算 关系代数表达式 关系代数表达式E2 SELECT sname FROM S WHERE S.s# in ( SELECT SC.s# FROM SC WHER c#=‘c03’); 关系代数表达式描述： ?sname( ?s.s#=SC.s# (S × ? SC.c#=‘c03’ SC) ) 关系代数表达式E3 SELECT sname FROM S , ( SELECT SC.s# FROM SC WHER c#=‘