当前位置: 首页 > >

第4章 分布式数据库中的查询处理和优化_图文

发布时间:

第4章 分布式数据库中的查询处理和优化 1. 分布式查询优化概述 2. 分布式查询分类和层次结构 3. 基于关系代数等价变换的查询优化处理 4. 基于半连接算法的查询优化处理 5. 基于直接连接算法的查询优化处理 6. 典型分布式数据库系统中的查询优化策略 和算法 1 分布式查询优化概述 1.1 分布式查询优化的目标 查询处理问题 ? 集中式 – 查询转换为代数表达式 – 从所有等价表达式中选择最优的代数表达式 ? 分布式 – – – – 除了集中式问题外,还有 站点之间交换数据的操作 选择最优的执行站点(分布) 数据被传送的方式 1 分布式查询优化概述 1.1 分布式查询优化的目标 CPU代价(相对固定) 集中式 I/O代价(可变的,优化的目标) 总代价最小 CPU代价 I/O代价(访问磁盘) 目标 主要标准 辅助标准 分布式 通讯代价 响应时间最短 数据的分布和冗余增加了查询的并行处理 的可能性,从而可以缩减查询处理的响应 时间 1 分布式查询优化概述 1.2 分布式查询优化准则和代价分析 准则: 使得通讯费用最低和响应时间最短,即以最小的总代价,在最短的响应 时间内获得需要的数据。 1. 2. 通讯费用与所传输的数据量和通信次数有关 响应时间和通信时间有关,也与局部处理时间有关 查询代价分析 1. 远程通讯网络 局部处理时间可以忽略不计,减少通讯代价是主要目标 2. 高速局域网 传输时间比局部处理时间要短很多,以响应时间作为优化目标,局部处理 时间是关键 1 分布式查询优化概述 1.3 分布式查询策略的重要性 ? 例子 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 Site A S, SC C Site B 1 分布式查询优化概述 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.3 分布式查询策略的重要性 A S, SC C B 策略 1: 六种查询策略 A 传C B 把关系C 传输到A地 ,在A地处理查询 ○ ○ T1 = 1 + (10**5 * 100 / 10**4) S ,SC 通信1次 C ≈ 10**3 秒 ≈ 16.7分钟 策略 2: A 传S ,S C ○ S ,SC 通信2次 B 把关系 S 和SC 传输到 B地 , 在 B 地处理查询 ○ T2 = 2+(10**4+10**5) * 100 / 10**4 C ≈ 10100秒≈ 28小时 策略 3: A 问10**5 B ○ ○ S,SC 答10**5 C 先在 A地求出男学生的成绩元组有10**5 再根据C#的值询问B地 ,核实是否C=‘MATHS’ T3 ≈(2 * 10**5 *1)=2*10**5 秒≈2.3 天 1 分布式查询优化概述 1.3 分布式查询策略的重要性 A S, SC C B 策略 4: A ○ S ,SC 问10 答10 B ○ C 六种查询策略 先在 B地求出 ‘MATHS’的元组,有 10个 再根据 C# 的值询问 A 地的 S, SC 的连接, 核实是否为选修 ‘ 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: A 传输10 B 先在 B地求出为‘ MATHS ’的元组,有10个 ○ ○ 再把结果传输到 A 地 , 在 A 地执行查询, S ,SC 通信 1次 C T6 = 1 + (10 * 100) / 10**4 ≈ 1 秒 2 分布式查询的分类与层次结构 2.1 分布式查询分类 ? 局部查询:只涉及本地. 单个站点的数据, 优 化同集中式 ? ? ? ? 选择和投影早做,中间结果大大减少 连接前进行预处理(属性排序、属性索引) 同时执行一串投影和选择操作 找出公共子表达式等 ? 远程查询:也只涉及单个站点的数据, 但要远 程通讯, 选择站点 ? 选择查询应用最近的冗余分配站点 ? 全局查询:涉及多个站点数据, 优化复杂 2 分布式查询优化概述 2.1 分布式查询分类 全局查询 ? 具体化 – 对查询进行分解,确定查询使用的物理副本,落实查询对象 – 非冗余具体化,所有要访问对象只有一个副本 – 冗余具体化,多个副本,研究如何如何选择副本,使通信代价最小 ? 确定操作执行的顺序 – 确定二元操作连接和并操作的顺序 ? 先执行所有连接操作,再执行并操作 ? 先执行部分并操作,再执行连接操作 – 选择和投影尽可能早进行 ? 确定操作执行的方法 – 把若干个操作连接起来在一次数据库访问中,确定可用的访问路径 – 连接方法在查询优化中起着重要作用 ? 确定执行的站点 – 执行站点不一定是发出查询的站点 – 考虑通讯费用和执行效率 分布关系上的查询表达 查询分解 全局模式 分 布



友情链接: