第3章 分布式数据库的查询处理与优化.ppt

第3章 分布式数据库的查询处理与优化 2012.02 内容概要 分布式数据查询 分布式数据查询优化 3.1 分布式数据查询 集中式数据库查询总代价是以查询期间的CPU代价和I/O代价来衡量的。 分布式数据库查询优化通常有两个标准： 一个是以总代价最小为标准。 另一个是以每个查询的响应时间最短为标准。 分布式数据处理环境可分为： 远程通讯网络环境 高速局域网 查询分解 数据本地化 全局优化 局部优化 结论： 一个好的查询处理应该使数据的传输量和通信次数最少，这样才能使查询所花费的数据传输和/或通信时间最少，从而减少查询的总代价。 局部查询 远程查询 全局查询 3.2 分布式数据库查询优化 基于关系代数等价变换的查询优化处理 基于半连接算法的查询优化处理 基于直接连接算法的查询优化处理 优化算法 连接和合并尽可能上提（树根方向） 选择和投影操作尽可能下移（叶子方向） 直接把R送到站点2上执行连接操作（假定关系R的数据量小于关系S的数据量），其代价为： T全=C0+C1*size(B)*card(R) 基本原理是在传到另一个站点做连接前，消除与连接无关的数据，减少做连接操作的数据量，从而减小传输代价。 结论： 采用半连接实现连接操作需要两次传输：连接属性投影结果和半连接结果。但在通常情况下，T半T全。 半连接的得益：当card（R）card（R’），可减少站点间的数据传输量 半连接的损失：传输?B(S)=C0+C1*size(B)*val(B[S]) 采用半连接优化算法的步骤 计算每种半连接方案的代价，并从中选择一种最佳方案 选择传输代价最小的站点，计算采用全连接的方案的代价 比较两种方案，确定最优方案 四种基于直接连接的优化算法 利用站点依赖信息的算法 分片与复制算法 站点依赖和数据复制结合算法 Hash划分算法 分片和复制算法 数据传输总量是R 数据传送后,可能要重新创建索引 每个站点的连接数据量是(3/2)R,一个全关系和一个片段 Hash划分算法 数据传送量是R 索引方面, 比片段复制算法更低 每个站点的连接数据量同站点依赖 作业题 分布式数据查询考虑的内容有哪些？ 有哪些分布式数据查询策略和算法，它们的优缺点分别是什么？ 采用半连接将会导致通信次数的增加和本地处理时间的增加。 如果传输费用是主要的，采用半连接方案处理策略比较有利。 如果本地费用是主要的，采用直接连接方案处理策略比较有利。 基于直接连接算法的查询优化处理 R1 R2 站 点 关 系 S1 S2 F11 F12 F21 F22 ∪ ∞ ∞ 利用站点依赖信息的算法 站点依赖 设关系Ri分片Fi1和Fi2, Rj分片Fj1和Fj2 关系Ri和Rj在属性A上满足条件 Fis∞AFjt=?,其中s?t, 则称Ri和Rj在属性A上站点依赖 也就是说: Ri∞ARj=U(Fis∞AFjs), 对于包含着两个关系的片段的每个站点s都成立 此时关系的连接操作无站点间数据传输 R1∞R2 （F11∞F21）U （F12∞F22） = ？ 推论 若Ri和Rj在属性A上站点依赖，则Ri和Rj在任何包含A的属性集B上也站点依赖。 若Ri和Rj在属性A上站点依赖，另一属性（或属性组）B函数决定A，且A??，则Ri和Rj在B上也站点依赖。 若Ri和Rj在属性A上站点依赖，且若Rj和Rk在属性B上站点依赖，则（Ri∞ARj∞BRk）=（Fis∞AFjs∞BFks) 查询Ri∞ARj∞BRk的连接操作能够以无数据传输的方式处理。 站 点 关 系 S1 S2 F11 F12 R2 R2 R1 R2 分片和复制算法 在该算法中，选择一组站点，把查询引用某个关系的所有片段分布在这些站点上，其余被引用的关系复制到每一个选定的站点。 R1∞R2=Ui(F1i∞R2) 站 点 关