【摘 要】数据库系统在实际工作中应用非常广泛，对数据库进行查询优化对推动计算机技术的发展具有十分重要的意义。并行数据库查询优化的研究主要围绕具有多个JOIN操作的复杂关系数据库查询的优化问题进行，本文主要对并行数据库查询优化技术进行探索。

【關键词】查询优化；并行数据库；语义查询；机群

1 引言

并行数据库查询优化主要围绕具有多个JOIN 操作的复杂关系数据库查询（简称MJ查询）的优化问题进行研究。1990年，Schneider等研究了查询树模型，提出了左线性树（Left-Deep Trees）、右线性树（RIGHT-Deep Trees）和浓密树（Bushy Trees）的概念。一个MJ查询可以表示为一个查询树T=（V，E），其中V是结点集合，E是边集合。每个叶子结点表示一个关系，每个内结点表示一个JOIN操作，同时表示这个JOIN操作的结果关系，每条边表示一个JOIN操作，JOIN谓词也可以由边来表示，即MJ查询的查询树是一个二叉树。查询树分为三类左线性树、右线性树和浓密树。

语义查询优化技术，将一个查询变换成一个或数个语义等价的查询，进而寻找并执行这些等价查询中具有较好实现策略的一个；基于遗传算法的并行优化算法主要是基于机群并行数据库中关系存储的选择、多连接查询优化和查询处理等关键技术。

2 左线性树查询优化算法（简称LDT算法）

LDT方法把两个JOIN关系分为内关系和外关系，把HASH-JOIN分为BUILD和PROBE两个基本操作，BUILD操作扫描内关系，建立HASH表；PROBE操作扫描外关系，搜索匹配HASH表，完成JOIN操作。具体算法如下：

（1）搜索给定MJ查询的左线性树空间，选择具有最小响应时间的优化左线性树T；

（2）由T产生数据相关图DG；

（3）根据DG产生优化并行查询执行计划P；

（4）运行优化查询计划P。

3 右线性树的查询优化算法

由于MJ查询的左线性树优化并行查询算法最多只允许两个JOIN操作并行执行，存在明显局限性。为此，Schneider等研究了基于右线性树的MJ查询优化问题，并给出了基于右线性树的查询化化算法（简称RDT算法）。该算法类似于LDT算法，RDT算法产生的查询执行计划具有相当高的并行性，所以N个JOIN操作皆可并行执行。

该算法基本思想是：在BUILD阶段，每个JOIN关系被分成两部分，一部分进入内存，建立HASH表，另一部分留驻外存，等以后处理；在PROBE阶段，每个JOIN操作的结果也被分成两部分，一部分直接用来进行下一个JOIN操作的PROBE处理，另一部分存入外存，等以后处理。

4 基于浓密树的查询优化算法

浓密树GBT（General-Bushy-Tree）的MJ查询优化算法的查询计划分为同步和非同步两类。在同步查询计划中，一个MJ查询的处理过程划分为多个同步执行阶段，各个同步执行阶段顺序执行。在每一同步执行阶段，多个JOIN操作并行执行，其他的查询计划称为非同步执行计划。

文献[2]以同步执行计划为目标，提出了三种产生优化同步执行计划的启发工MJ查询优化算法，第一个算法称之为GP算法，是一种贪心算法，算法思想核心是同步执行段的划分，循环地为每一同步执行阶段选择尽量多的可并行执行的JOIN操作。该算法时间复杂性较大，为解决此问题，继而提出算法GPt，它仅产生如下类型的计划：只有第一同步执行阶段并行执行多个JOIN，其余同步执行阶段仅执行一个JOIN操作。

GBT查询优化方法具备了很高的并行性，但该执行计划空间十分庞大，因此查询优化算法的开销也非常大。

5 语义查询优化方法

语义查询比较有趣，它不同于上述优化方法。所谓语义优化是指对一指定的查询问题，写出不同的查询语句，从中挑出DBMS能够为之找到最高效实现方法的语句。据统计，语义完整性规则可能占一个数据库系统的概念模式描述内容的80%。

语义优化的实现，遵照以下步骤：确立约束目标，即确定对哪些关系应增加补充约束或者引入索引，或者引入、删除哪些关系；选择完整性约束；产生属性上的新约束；约束合并；查询约束的消除；形成等价的语义查询。有文献的对比实验表明，利用语义完整性规则进行查询优化，能够显著地提高效率。

6 遗传算法

遗传算法（Genetic Algorithm，GA）是近年发展起来的一种崭新的全局优化算法，1962年由Holland教授首次提出，它借用了生物遗传学的观点，通过自然选择、遗传、变异等作用机制，实现各个个体的适应性的提高。这一点体现了自然界中“物竞天择、适者生存”的进化过程。

传统的遗传算法中有关并行调度的讨论和代价估算是基于无共享资源的体系结构，首先，关系的分布算法在选择关系的分布属性、分布方式和处理机集合时，充分考虑了机群系统中引起数据重分布的因素，减少了额外的通信开销；同时兼顾了并行系统中的三种并行。其次，查询优化部分，提出了基于遗传算法的机群环下多连接查询的并行优化算法（简称BGA）。该算法研究了资源分配在查询执行代价估算中的作用和方法，提高了查询优化的效优选法。与此同时，为了节省风络通信的开销，查询计划代价模型的计算将网络的通信代价考虑在内，充分利用了查询中各关系的物理存储信息，减小了不必要的通信开销。

7 结论

传统的并行数据库查询优化技术有基于左线性树、右线性树、浓密树、操作森林的并行数据库查询优化，各有优劣。目前使用的遗传算法进行查询优化的方法中，我们认为仍存在两个问题：（1）在估算查询计划的代价时，没有考虑资源的分配情况，数据操作间的并行性得不到充分的开发；（2）在无共享体系结构的查询优化中，没有考虑网络的通信代价，无法避免额外的通信开销。

算法研究方面，遗传算法才刚起步，A算法、A*算法、模拟退火算法、神经网络算法在计算机的诸多方面都取得了巨大的成绩，但在并行数据库的查询优化方面基本还是一个空白，仍需积极探索。

参考文献

[1]厉阳春.基于线性浓密树的并行数据库查询优化算法[J].湖南理工学院学报：自然科学版，2006，19（1）：20-23

[2]玄萍.并行数据库查询优化的遗传算法[R].哈尔滨：黑龙江大学，2004

[3]许新华，胡世港，唐胜群等.数据查询优化技术的历史、现状与未来[J].计算机工程与应用，2009，45（18）：156-161

作者简介：谭玲丽，女，湖北武汉人。汉族。硕士。武汉东湖学院计算机科学学院，讲师。研究方向：软件工程，数据库技术。