10-3 分布式数据库中的查询处理和优化.pptx

分布式数据库中的查询处理和优化分布式查询优化概述分布式查询优化中的基础知识分布式查询分类和层次结构基于关系代数等价变换的查询优化处理基于半连接算法的查询优化处理基于直接连接算法的查询优化处理典型分布式数据库系统中的查询优化策略和算法1 分布式查询优化概述1.1 分布式查询优化的目标查询处理问题集中式查询转换为代数表达式从所有等价表达式中选择最优的代数表达式分布式除了集中式问题外，还有站点之间交换数据的操作选择最优的执行站点(分布）数据被传送的方式1 分布式查询优化概述1.1 分布式查询优化的目标CPU代价（相对固定）集中式I/O代价（可变的，优化的目标）总代价最小CPU代价主要标准辅助标准I/O代价（访问磁盘）分布式目标通讯代价响应时间最短数据的分布和冗余增加了查询的并行处理的可能性，从而可以缩减查询处理的响应时间1 分布式查询优化概述1.2 分布式查询优化准则和代价分析准则： 使得通讯费用最低和响应时间最短，即以最小的总代价，在最短的响应时间内获得需要的数据。通讯费用与所传输的数据量和通信次数有关响应时间和通信时间有关，也与局部处理时间有关查询代价分析远程通讯网络 局部处理时间可以忽略不计，减少通讯代价是主要目标高速局域网 传输时间比局部处理时间要短很多，以响应时间作为优化目标，局部处理时间是关键1 分布式查询优化概述1.3 分布式查询策略的重要性CSite BS, SCSite A例子 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, 通讯延迟 1sec1 分布式查询优化概述1.3 分布式查询策略的重要性查询: 所有选修maths 课的男生学号和姓名. SELECT s#, sname FROM S, C, SC WHERE S.s#=SC.s# AND C.c#=SC.c# AND sex=‘男’ AND cname=‘maths’;1 分布式查询优化概述1.3 分布式查询策略的重要性代价公式 QC = I/O 代价 + CPU 代价 + 通讯代价 通讯代价 TC = 传输延迟时间C0 + (传输数据量X * 数据传输速率C1) 策略1:1 分布式查询优化概述1.3 分布式查询策略的重要性 A传C B 把关系 C 传输到 A 地,在 A 地处理查询 ○ ○ T1 = 1 + (10**5 * 100 / 10**4) S,SC 通信1次 C≈ 10**3 秒 ≈ 16.7 分钟策略2: A传S,SC B把关系 S 和SC 传输到 B 地, 在 B 地处理查询 ○ ○ T2 = 2+(10**4+10**6) * 100 / 10**4 S,SC通信2次 C≈10100 秒≈28小时策略3: A问10**5 B先在 A地求出男学生的成绩元组有10**5 ○ ○ 再根据C#的值询问B地,核实是否C=‘MATHS’CBS, SC S,SC答10**5 C T3 ≈(2 * 10**5 *1)=2*10**5 秒≈ 2.3 天A六种查询策略1 分布式查询优化概述1.3 分布式查询策略的重要性策略 4： A 问10 B先在 B地求出‘MATHS’的元组,有10个 ○ ○ 再根据C#的值询问A地的S，SC的连接，‘’ S,SC 答10 C 核实是否为选修MATHS的男生 T4 ≈ (2 * 10 * 1) = 20 秒 策略 5： A传输10**5 B 先在 A地求出男生选课元组，有10**5个 ○ ○ 再把结果传输到 B 地, 在 B 地执行查询， S,SC 通信1次 C T5 = 1 + (10**5 * 100) / 10**4 ≈ 1000 秒 ≈ 16.7 分 策略 6：CBS, SC A传输10 B先在 B地求出为‘MATHS’的元组，有10个A ○ ○ 再把结果传输到 A 地 , 在 A 地执行查询， S,SC 通信1次 C T6 = 1 + (10 * 100) / 10**4 ≈ 1 秒六种查询策略2 分布式查询优化中的基础知识A2.1 关系代数知识回顾相关表述记号⒈ 设关系模式为R(A1, A2, …, An)。它的一个关系设为R。 t∈R表示t是R的一个元组。t[Ai]则表示元组t中相应于属性Ai的一个分量 。 ⒉ 若A={Ai1, Ai2, …, Aik}，其中Ai1, Ai2, …, Aik是A1, A2, …, An中的一部分， 则A称为属性