资源描述：
《基于遗传算法的多连接表达式并行查询优化》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、1000-9825/2002/13(02)0250-08©2002JournalofSoftware软件学报Vol.13,No.2基于遗传算法的多连接表达式并行查询优化Ã曹阳,方强,王国仁,于戈(东北大学信息科学与工程学院,辽宁沈阳110004)E-mail:{wanggr,yuge}@mail.neu.edu.cnhttp://www.neu.edu.cn摘要:多连接表达式的并行查询优化是提高数据库性能的关键问题之一.提出了使用遗传算法来解决多连接表达式的并行查询优化问题.为了提高查询处理器的执行效率,采用启发式规则来搜索最优的多连接表达式并行调度执行计划.文中给出了详
2、细的测试结果和性能分析.实验结果表明,结合启发式知识的遗传算法是解决多连并行查询优化的有效途径,对提高数据库的性能起到重要作用.关键词:遗传算法;多连接表达式;查询优化;并行调度中图法分类号:TP311文献标识码:A多连接表达式的并行查询优化涉及到多个连接的连接顺序问题,还和处理机的有效分配密切相关,因此可能存在相当多的并行执行计划供选择.到目前为止仍未有令人满意的通用方法能快速找到计算多连接表达式最小代价的并行执行计划.本文使用遗传算法求解多连接表达式的连接顺序,为兼顾查询优化器的处理效率,结合启发式方法,进行并行查询优化.在并行处理机平台上寻找多连接表达式的并行查询最
3、优执行计划可分为两个步骤:(1)如何构造一棵代价最小的多连接查询树,(2)如何为该多连接查询树分配处理机.代价最小的多连接查询树的查找可以通过枚举法、启发式算法、搜索算法和遗传算法构造多连接树.枚举法通过解空间中的每个可能解来找到最优解.当解空间增大时求解效率相当低.启发式算法则是寻求一种能产生可行解的启发式规则来找到一个最优解或近似最优解.但该方法在不同的限定条件,不同的并行环境和体系结构要有不同的启发式规则,不具有通用性,同时[1]不能保证所得的结果最优.搜索算法在可行解集合的一个子集内进行搜索,搜索算法的随机性和盲目性不能保证得到最优解,该算法结合一些启发知识才能在
4、一定程度上达到要求.遗传算法是模拟生物在自然环境中的[2]遗传和进化过程而形成的一种自适应全局优化概率搜索算法.它将原问题的解空间映射到位串空间中,然后再实施遗传操作,强调个体基因结构的变化对其适应度的影响.现有遗传算法主要存在下面问题:仅考虑使用简单的遗传算法;对演化计算的其他方法没有加以讨论和改进;只涉及到多连接表达式的执行顺序,没有进一步研究多处理机的并行调度问题.为多连接树分配处理机是复杂的组合优化问题,涉及的限制条件包括每个连接的负载大小、连接关系的物理存储情况、连接操作间的依赖、并行资源以及调度策略本身的性能等.文献[3]给出了4种连接树的处理机分配策略:顺序
5、并行执行策略(SP)、同步执行策略(SE)、分段右深树的执行策略(RD)和完全并行的执行策略(FP).顺序并行执行策略(SP).SP方法只有连接内的并行操作,没有连接间的并行操作,把所有的处理机全部分给一个连接操作,操作完成之后再分配给下一个连接操作.Ã收稿日期:2001-04-20;修改日期:2001-09-24基金项目:国家教育部高等学校骨干教师资助项目;教育部高等学校优秀青年教师教学和科研奖励基金资助项目;教育部跨世纪人才基金资助项目作者简介:曹阳(1976－),女,辽宁大连人,硕士,主要研究领域为并行数据库技术;方强(1975－),女,湖北武汉人,硕士,主要研究领
6、域为并行数据库技术;王国仁(1966－),男,湖北崇阳人,博士,教授,主要研究领域为并行数据库,对象数据库,Web数据库技术;于戈(1962－),男,辽宁大连人,博士,教授,博士生导师,主要研究领域为数据库理论和技术,分布式系统.曹阳等:基于遗传算法的多连接表达式并行查询优化251同步执行策略(SE).SE方法也称为自上而下的分配策略,把处理机同时分配给彼此独立的不同的连接操作,[4]利用了操作内的并行性和操作间的并行性.并行度和处理机的利用率较高,适用于大型的并行系统.分段右深树的执行策略(RD).RD方法利用管道的并行性,对于连接树上的右深子树用流水线的方式并行处理,
7、其他部分用SP方法处理.完全并行执行策略(FP).FP方法是SE和RD方法的结合,把处理机按一定比例分配给每个连接结点,兼顾操作间的并行性和流水线的并行性.根据相关工作和上面提出的问题,可以使用遗传算法选出一些相对较优的多连接表达式的连接操作符树,然后根据限定条件和不同调度策略的启发式算法,找到代价最小的并行执行计划.本文有关并行调度的讨论和代价估算是基于无共享资源的体系结构.本文第1节介绍遗传算法.第2节介绍基于遗传算法的多连接表达式的查询优化.第3节介绍了结合启发式规则的多连接并行查询优化技术.第4节是仿真实验的设计和性能
