基于分布式数据库的查询处理和优化算法.pdfVIP

74 福 建 电 脑 2008年第7期 基于分布式数据库的查询处理和优化算法 于 萍，吴业福，李 紧 (武汉理工大学计算机学院，湖北 武汉430063) 【摘 要】：分布式查询处理和优化是用户与分布式数据库的接口，也是分布式数据库研究的主要问题之一。分布式数 据库中数据的数据分散存放和冗余使得查询处理和优化更加复杂．文章分析了分布式查询处理过程．重点阐述了优化的各 种策略和算法。分析了优缺点并给出了算法选择的方法。 【关键字】：分布式数据库；查询代价；查询处理；查询优化； 0、引言 找到一个查询的最优策略．既要确定执行查询的物理片段．也必 分布式数据库系统是集中式数据库技术与计算机网络技术 须确定查询中各操作执行的次序和执行站点．而这又依赖于每 相结合的产物。从概念上讲．分布式数据库是物理上分散在计算 个操作的执行方法 机网络各结点上．而逻辑上属于同一个系统的数据集合．其体系 2．2查询处理 结构与集中式数据库系统有很大的不同．这就引出了一系列与 按分布式数据库系统的体系结构．分布式查询处理过程可 集中式数据库系统不同的问题。在集中式数据库系统中．尽量减 分为四个层次：1查询分解：是将查询问题(例如SQL语句)转 少冗余是系统目标之一．而在分布式数据库系统中却通过冗余 化成一个定义在全局关系上的关系代数表达式。 数据本地 数据提高了系统的可靠性、可用性和改善系统的性能．但由于数 化：是把一个在全局关系上的查询．进行具体化．落实到合适的 据的分布性和冗余．使得分布式数据库查询处理增加了许多新 片段上的查询．即将在全局关系上的关系代数表达式变换为在 的内容和复杂性．其问题的规模和优化的因素都与集中式查询 相应片段上关系代数表达式 处理有质的不同．因此，分布式查询处理和优化显得更为重要。 3全局优化：通过前面两层 1、分布式查询处理和优化的代价分析 已经消除冗余表达式．全局优 在集中式数据库中．由于系统大都运行在单个处理器的计 化即是找出分片查询的最佳 算机上．一个查询执行的预期代价为I／O代价+CPU代价。而在 操作次序．包括使得代价函数 分布式数据库系统中，一个查询可能涉及多个站点．查询处理还 最小．其一个重要方面是关于 需要考虑站点间传输数据的通信费用．对不同的通信网络类型 连接操作的优化．输出是一个 有不同的查询处理算法。在远程通信网中．查询的局部处理时间 优化的、片段上的关系代数查 与通信所需要时间相比．可以忽略不计，因此．常以减少传输的 询。(4局部优化：采用集中式 次数和数据量作为优化的重要目标；而在高速局域网中，传输时 数据库系统中查询优化的算 间比局部处理时间要短得多．往往以响应时间作为优化目标。响 法．在各个片段执行相关的子 ，，●●● ●， J●、●●●● ●●●●● 图l：分布式查询层次结构图 应时间既与通信时间有关．也与局部处理时间有关，但局部处理 查询 具体的层次结构如图1 时间是关键。所以减少局部处理的时间是问题的主要方面。 3、查询优化算法 综上．分布式查询的总代价=I／O代价+CPU代价+通信代 查询优化有两种基本方法：一是查询转化：以不同的顺序执 价。其中通信代价可用下式作粗略估算：C0+CI*X(C0两站点问 行关系操作。如连接和投影操作；二是查询映射：使用一系列高 通信初始化一次所花费的时间，X为数据的传输量．C1为传输 效的算法来存取各种设备和实现关系操作。即查询映射是针对 的速率)。 关系的存取方法和操作的执行算法进行决策．而查询转化则是 2、分布式查询处理过程 针对操作执行的顺序及不同站点之间数据流动的顺序进行决 在集中式数据库系统中．查询处理问题为：查询转换为代数 策 目前对于分布式数据库系统的查询处理有以下几种方法。 表达式、从所有等价表达式中选择最优的代数表达式：而在分布 3．1基于关系代数