河南财经学院 Henan University of Fit nance an Id Economics 分布式数据库系统及其应用 崔明义 (mycu369@126cm) 计算机应用技术2007级研究生
崔明义 （mycui369@126.com) 计算机应用技术2007级研究生
(第3章分布式数据库中的查询处理和优化 1.分布式查询优化概述 2.分布式查询优化基础知识 3.分布式查询分类和层次结构 4.基于关糸代数等价安换的查询优化处理 5.基于半连接算法的查询优化处理 6.基于直接连接算法的查询优化处理 7.直接连接振作的常用簟略
1. 分布式查询优化概述 2. 分布式查询优化基础知识 3. 分布式查询分类和层次结构 4. 基于关系代数等价变换的查询优化处理 5. 基于半连接算法的查询优化处理 6. 基于直接连接算法的查询优化处理 7. 直接连接操作的常用策略 第3章分布式数据库中的查询处理和优化
1分布式查询优化概述 11分布式查询优化的目标 查询处理问题 集中式 查询转换为代数表达式 从所有等价表达式中选择最优的代数表达式 分布式 除了集中式问题外,还有 站点之间交换数据的操作 选择最优的执行站点(分布) 数据被传送的方式
查询处理问题 • 集中式 – 查询转换为代数表达式 – 从所有等价表达式中选择最优的代数表达式 • 分布式 – 除了集中式问题外，还有 – 站点之间交换数据的操作 – 选择最优的执行站点(分布） – 数据被传送的方式 1.1 分布式查询优化的目标 1 分布式查询优化概述
1分布式查询优化概述 11分布式查询优化的目标 CPU代价(相对固定) 集中式 I/O代价(可变的,优化的目标) 总代价最小 CPU代价 I/O代价(访问磁盘) 目标 主要标准分布式 辅助标准 通讯代价 响应时间最短数据的分布和冗余增加了查询的并行处理 的可能性,从而可以缩减查询处理的响应 时间
1.1 分布式查询优化的目标 1 分布式查询优化概述 目标 总代价最小 响应时间最短 集中式 分布式 CPU代价（相对固定） I/O代价（可变的，优化的目标） CPU代价 I/O代价（访问磁盘） 通讯代价 数据的分布和冗余增加了查询的并行处理 的可能性，从而可以缩减查询处理的响应 时间 主要标准 辅助标准
1分布式查询优化概述 2分布式查询优化准则和代价分析 准则: 使得通讯费用最低和响应时间最短,即以最小的总代价,在最短的响应 时间内获得需要的数据。 1.通讯费用与所传输的数据量和通信次数有关 2.响应时间和通信时间有关,也与局部处理时间有关 查询代价分析 1.远程通讯网络 局部处理时间可以忽略不计,减少通讯代价是主要目标 2.高速局域网 传输时间比局部处理时间要短很多,以响应时间作为优化目标,局部处理 时间是关键
1.2 分布式查询优化准则和代价分析 1 分布式查询优化概述 准则： 使得通讯费用最低和响应时间最短，即以最小的总代价，在最短的响应 时间内获得需要的数据。 1. 通讯费用与所传输的数据量和通信次数有关 2. 响应时间和通信时间有关，也与局部处理时间有关 查询代价分析 1. 远程通讯网络 局部处理时间可以忽略不计，减少通讯代价是主要目标 2. 高速局域网 传输时间比局部处理时间要短很多，以响应时间作为优化目标，局部处理 时间是关键
1分布式查询优化概述 1.3分布式查询策略的重要性 例子 S(s#, sname,age,sex)104元组 Site a C(c#, cname, teacher)105元组 Site B SC(s#f, c#, grade) 106元组 Site a 每个元组长度100Bit,通讯传输速度104bit/sec 通讯延迟1sec Site B Site a S. SC
• 例子 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 S, SC Site A C Site B 1.3 分布式查询策略的重要性 1 分布式查询优化概述
1分布式查询优化概述 1.3分布式査询策略的重要性 查询:所有选修mahs课的男生学号和姓名 seLect S# sname FROM S.C. SC WHERE SS#=SC S# AND C c#=SC. c#t AND sex=男’ AND cname- maths
查询: 所有选修maths 课的男生学号和姓名. SELECT s#, sname FROM S, C, SC WHERE S.s#=SC.s# AND C.c#=SC.c# AND sex=‘男’ AND cname=‘maths’; 1.3 分布式查询策略的重要性 1 分布式查询优化概述
1分布式查询优化概述 1.3分布式査询策略的重要性 代价公式 QC=ⅣO代价+CPU代价+通讯代价 通讯代价 TC=传输延迟时间C0 +(传输数据量Ⅹ*数据传输速率C1)
• 代价公式 QC = I/O 代价 + CPU 代价 + 通讯代价 • 通讯代价 TC = 传输延迟时间C0 + (传输数据量X * 数据传输速率C1) 1.3 分布式查询策略的重要性 1 分布式查询优化概述
1分布式查询优化概述 SC B A 1.3分布式査询策略的重要性 策略1: 六种查询策略 A传CB把关系C传输到A地,在A地处理査询 ○T1=1+(10米米5*100/10*米4) S,SC通信1次C≈10*3秒≈16.7分钟 策略2: A传S,SCB把关系S和SC传输到B地,在B地处理查询 T2=(2+10水来4+10水*5)米100/10水*4 S,SC通信2次C≈10100秒≈28小时 策略3: A问10米5B先在A地求出男学生的成绩元组有10*来5 ○再根据C#的值询问B地,核实是否C= MATHS S,SC答10*米5CT3≈(2*10*米5*1)=2米10来*5秒≈2.3天
1.3 分布式查询策略的重要性 1 分布式查询优化概述 策略1: A 传 C B 把关系C 传输到A 地,在A 地处理查询 ○ ○ T1 = 1 + (10**5 * 100 / 10**4) S ,SC 通信1次 C ≈ 10**3 秒 ≈ 16.7 分钟 A 传S,S C B 把关系S 和SC 传输到 B 地 , 在 B 地处理查询 ○ ○ T2 = (2+10**4+10**5) * 100 / 10**4 S ,SC 通信2次 C ≈10100 秒≈ 28小时 A 问10**5 B 先在A地求出男学生的成绩元组有10**5 ○ ○ 再根据C#的值询问B地 ,核实是否C=‘MATHS’ S,SC 答10**5 C T3 ≈(2 * 10**5 *1)=2*10**5 秒≈2.3 天 策略2: 策略3: 六种查询策略 S, SC C A B
1分布式查询优化概述 SC B A 1.3分布式査询策略的重要性 策略4: 六种查询策略 A问10B先在B地求出 MATHS°的元组,有10个 O○再根据C#的值询问A地的S,SC的连接 SSC答10C核实是否为选修 MATHS的男生 T4≈(2*10*1)=20秒 策略5 A传输10**5B先在A地求出男生选课元组,有10*米5个 ◇○再把结果传输到B地,在B地执行查询, S,SC通信1次CT5=1+(10来*5*100)/10*米4 1000秒≈16.7分 策略6: A传输10B先在B地求出为 MATHS?的元组,有10个 再把结果传输到A地,在A地执行查询, S,SC通信1次CT6=1+(10来100)/10*4≈1秒
1.3 分布式查询策略的重要性 1 分布式查询优化概述 A 问10 B 先在B地求出‘MATHS’的元组,有10个 ○ ○ 再根据C#的值询问 A 地的S，SC的连接， S,SC 答10 C 核实是否为选修‘ MATHS ’的男生 T4 ≈ (2 * 10 * 1) = 20 秒 A 传输10**5 B 先在A地求出男生选课元组，有10**5个 ○ ○ 再把结果传输到B 地, 在 B 地执行查询， S ,SC 通信1次 C T5 = 1 + (10**5 * 100) / 10**4 ≈ 1000 秒≈ 16.7 分 A 传输10 B 先在B地求出为‘ MATHS ’的元组，有10个 ○ ○ 再把结果传输到 A 地 , 在A 地执行查询， S ,SC 通信 1次 C T6 = 1 + (10 * 100) / 10**4 ≈ 1 秒 策略 4： 策略 5： 策略 6： 六种查询策略 S, SC C A B