下载掌阅APP，畅读海量书库
立即打开
在数据库管理系统中，查询处理的主要任务是翻译用户所给出的查询语句并对若干可能有效的查询处理计划进行评价、比较，从中选出能优化其性能的一个方案。查询处理的效率对整个系统的性能有很大的影响，因此并行数据库系统中查询处理的并行实现也就成为并行数据库管理系统的一个重要指标。
对应于传统的顺序执行计划（Sequential Plan，SP），常称相应于并行处理环境下的执行计划为并行执行计划（Parallel Plan，PP）。
如果查询Q的某个并行执行计划PP与Q的一个顺序执行计划SP对应于相同的操作树，则称PP为SP的一个并行化方案；而由顺序执行计划SP得到某个PP的过程称为并行化。显然，一个串行执行计划可以通过不同的并行化过程得到不同的并行执行计划。
并行化过程可以由下述一些基本概念刻画：
（1）并行粒度：并行粒度指的是查询执行的并行程度，并行粒度从粗到细可分为如下四种：事务间并行性，查询间并行性（事务内的查询间的并行性），操作间并行性（事务内的查询内的操作间的并行性）和操作内并行性（事务内的查询内的操作内的并行性）。
一般来说，并行粒度越细，并行化程度就越高，而实现就越为复杂。一个好的并行数据库系统应该能实现操作内的并行性。
并行数据库系统通过开发事务间、查询间、操作间及操作内四种不同粒度的并行性来在OLTP及DSS（Decision Support System，决策支持系统）两种应用环境中提供优化的事务吞吐量和响应时间。
（2）并行化形式：并行化可分为水平并行化，也称独立并行化（Independent Parallelism）和垂直并行化，也称流水线并行化（Pipelining Parallelism）两种形式，图2-25给出了这两种形式的示意图。
图2-25 并行化的两种形式
如果两个操作无相互依赖关系，则称这两个操作相互独立；如果操作OP2直接依赖于OP1，并且OP2必须等待OPl处理完所有元组后方可开始执行，则称OP2以阻塞方式直接依赖于OP1；如果OP2无须等待OP1处理完所有结点即可开始执行，则称OP2以流水线方式直接依赖于OP1。
水平并行化指的是互相独立的多个操作或者一个操作内互相独立的多个子操作分别由不同的处理器并行执行的形式；垂直并行化则是指存在流水线方式依赖关系的操作分别由不同处理器并行执行的形式。
例如：排序操作、扫描操作由不同的处理器并行执行就是水平并行化的实例，而扫描操作→排序操作→连接操作→分组操作由不同的处理器并行执行是垂直并行化的实例，如图2-26所示。
图2-26 水平并行化与垂直并行化的例子
由于关系代数的封闭性和数据操作的相对独立性，关系查询具有三种固有并行性，即操作间的流水线并行性、操作间的独立并行性及操作内的独立并行性，这为关系代数的并行化提供了现实基础。
实现关系查询并行化的简单方法是并行数据流方法，这种方法的基本思想是使用顺序数据操作算法实现关系数据库的三种固有并行性。但是，许多研究表明，使用并行数据操作算法实现查询的并行处理可以更充分地发挥多处理器的并行性，极大地提高查询处理的效率。
目前并行操作算法大多是围绕连接操作而设计的，早期的连接算法都假定数据在连接属性的分布是均匀的，在此基础上，对原来的顺序算法进行改造而产生了基于嵌套循环的并行连接算法、基于合并扫描的并行连接算法、基于Hash的并行连接算法，基于索引的并行连接算法。近几年来，为了克服数据扭曲（数据分布很不均匀）对连接算法的影响，又出现了不少经过改进后的上述连接算法。
查询优化始终是数据库管理系统的重要组成部分。查询优化的目标在于提高执行效率，它主要是要对各种可能的查询执行计划进行评估，并从中选出最优的查询执行方案。并行查询优化的目标和任务也一样。并行查询优化的目标在于从查询的并行执行计划空间中找出最优的并行执行计划。
由于并行数据库环境中存在多个处理器，并行查询优化应尽可能地使每个操作并行处理，充分利用系统资源提高并行度来达到提高系统性能的目的，因此它的实现与传统的数据库查询优化有所不同，更强调数据分布的均匀性。
并行查询优化面临的两大困难在于：
（1）执行计划搜索空间的庞大。在传统的顺序查询优化中，往往采取穷尽的办法或者某种半穷尽的办法搜索整个查询计划空间，为每个查询计划估算出代价，而后找出代价最小的查询计划。然而，在并行环境下，并行执行计划空间往往成指数增长。
因此，依靠传统的穷尽办法进行并行查询优化是不现实的。并行查询优化应该可以提供某种启发式的方法对并行执行计划空间做裁剪以减少搜索空间的代价。为此，不少学者相继提出了基于左线性树的查询优化算法、基于右线性树的查询优化算法、基于片段式右线性树的查询优化算法、基于浓密树的查询优化算法、基于操作森林的查询优化算法。这些算法均是在搜索代价和最终获得的查询计划的效率之间有着不同的权衡。
（2）执行时的某些系统参数（例如，CPU数目、内存大小等）在优化时是未知的。在多用户环境下，系统参数如CPU数目、内存大小只能到计划执行时才能确定。
有的学者提出了两阶段优化的思想，将查询处理分为静态顺序优化和动态并行化两个阶段进行：
阶段1：在编译阶段，假设全部内存大小可为查询所用，利用传统查询优化策略得到最优顺序执行计划。
阶段2：执行阶段，根据阶段1的顺序执行计划得到给定缓冲区大小和处理器数目条件下的最优并行化方案。
将并行查询优化分解为两个阶段进行，有效地解决了并行查询面临的两大困难，同时又降低了并行查询优化算法的复杂性，但问题是，两阶段优化是否能保证并行执行计划的最优性。
希赛教育专家提示： 有关并行查询优化的策略和查询优化算法均处在进一步的研究之中。