分布式数据库技术：涉网查询优化概述

2023-10-28 理论教育版权反馈

【摘要】：涉网查询优化的问题主要包括三部分，其过程简述如下。查询优化器可以由三个成分构成：搜索空间、成本模型和搜索策略。图7.17查询优化过程1.搜索空间查询执行计划是算符树的一种表现形式，对执行序有更明确的表示，有丰富的附加信息，如为每个操作选择最佳实施方法。图7.19连接树的两种主要形态2.搜索策略查询优化器最常用的搜索策略是动态规划，称为确定策略。

因为我们面临的是分布式数据库的分配模式，所以要面对一个全局查询。要确定如何从不同的数据片上重构全局关系的问题，需要先说明一个概念，这个概念为构造执行体（materialization）。所谓构造执行体，是指如何从分布环境中分派到多个节点，并且从有副本存在的分片关系中选出（重构）一个全局关系作为执行体的问题。因为有多种组合选择，构造执行体就是从中选出（重构）一个组合来构建一个全局关系。

确定构造执行体以后，查询处理器的下一个任务是实施分布查询优化。所谓优化，就是在许多可供选择的方法中选取一种访问代价最小的方法。

在分布式数据库中，查询优化的目的是，最快地找出存储在分布式数据库中所需要的数据，并且要求成本最低、时间最少、效率最高。

要选择最佳策略，则涉及对各种候选执行序的执行开销的预测。执行开销可以看成是I/O、CPU和通信开销的加权组合。一般的考虑是忽略本地处理开销，而把通信开销（排除I/O和CPU开销）看成是决定性的。而估算执行开销的重要输入是数据片的统计信息、关系概貌及操作结果的估算值。

涉网查询优化的问题主要包括三部分，其过程简述如下。

●确定和选取数据片（fragments）的物理副本，执行查询，并给这些数据片指定查询表达式。这就是确定执行体（materialization）问题，即选择分布式数据库数据对象的一份非冗余的完整（关系）副本。

●选择运算的执行顺序，确定较好的连接、半连接和并运算序列。这里的执行顺序是指查询代数变换后产生的运算符树所定义的一种运算偏序。然而，这并不是一种完整地解决优化问题的方法，因为还要指定在树的同一层上所执行的子表达式的求值顺序。此外，从树叶向树根攀登也不一定能获得最好的解决方法。因此，这里还涉及查询树的扫描策略问题。

●选择执行每一种运算（如连接运算）的具体实现方法。

本节我们讨论涉网查询优化的任务。查询优化是指生成一个查询执行计划（query execution plan，QEP）的过程，查询执行计划是一种查询执行策略。数据库管理系统的查询优化器是一个软件模块，负责完成查询优化。查询优化器可以由三个成分构成：搜索空间、成本模型和搜索策略。

搜索空间是关于输入查询可能执行计划的集合。这些执行计划是等价的，虽然执行序/方法不同，但产生的结果相同，从而在性能上有差别。成本模型是对这些给定的执行计划进行估算。搜索策略负责探索搜索空间和使用成本模型来选择最佳计划。

查询优化过程可以用图7.17来表示。由图可见，用户输入查询信息后首先经历的是生成搜索空间，然后通过评估来确定搜索策略，这个过程会反复。一旦搜索策略确定，就生成查询执行计划（QEP）。生成搜索空间的基础是一套转换规则，确定搜索策略的依据主要是成本模型。

pagenumber_ebook=144,pagenumber_book=129

图7.17　查询优化过程

1.搜索空间

查询执行计划是算符树的一种表现形式，对执行序有更明确的表示，有丰富的附加信息，如为每个操作选择最佳实施方法。对于一个给定查询，查询空间按照转换规则生成的等价算符树的集合来进行定义。为了方便又不失一般性，忽略本地运算，这里只考虑连接运算和笛卡儿积运算。

pagenumber_ebook=145,pagenumber_book=130

图7.18　等价连接树

【例7.17】考查如下查询：

Se l ec t sname，cname

f rom Student，SC，COURSE

where Student.sno=SC.sno

AND SC.cno=COURSE.cno

忽略一元运算（选择、投影），结果只剩下以下两个连接运算。

（1）Student∞sno=sno SC。

（2）SC∞cno=cno COURSE。

图7.18是例7.17这个查询的3棵等价连接树。按照每个算符的成本估算，可以为每棵树计算成本开销。

对一个复杂查询（涉及许多关系和算符）来说，等价算符树的数目会很多。例如，对N个关系来说，通过交换律和结合律生成的等价连接树的数目为O（n！）。如果要对大型搜索空间进行探索，则会有很强的时间限制，有时成本会远高于实际执行的时间成本。因此，要限制搜索空间的大小。首先是使用启发式方法，即执行选择和投影操作。其次是避免执行笛卡儿积操作。再次是观察连接树的形状。一种典型的形状是线性连接树，另一种形状是灌木丛连接树（见图7.19）。线性连接树的特点是每个算符至少有一个操作数为一个基关系（树叶）。灌木丛连接树很普遍，其中，许多算符的操作数不涉及基关系，而是以中间关系形式出现。线性连接树的搜索空间可以归结为O（2n）。

pagenumber_ebook=145,pagenumber_book=130

图7.19　连接树的两种主要形态

2.搜索策略

查询优化器最常用的搜索策略是动态规划，称为确定策略（deterministic strategy）。搜索策略的确定从基关系开始，每一步连接一个关系，直到获得完整的计划，如图7.20所示。动态编程在选择“最佳”计划前，先采用广度优先算法构造所有可能的计划。为了减少优化成本，有些明显不合理的计划马上去掉。相比之下，贪心算法则采用深度优先算法。

动态规划耗费是极大的，但能够保证找出所有“最佳”计划。它要承受可接受的优化成本（依据空间和时间），条件是查询涉及的关系数不是很大。如果涉及的关系数大于5或6，那么开销会显著增加。为此，有人建议采用随机策略（randomized strategies）。这个策略可以降低优化的复杂性，但无法保证找出所有计划中的“最佳”计划。随机策略允许优化器在优化时间和执行时间之间寻找折中。(www.chuimin.cn)

有些问题是优化器必须考虑的，典型的如分布成本模型和成本函数。

pagenumber_ebook=146,pagenumber_book=131

图7.20　确定搜索策略的优化步骤

（1）分布成本模型。优化器分布成本模型包括预测算符开销的成本函数、统计数据、基关系和估算中间关系大小的公式等。

（2）成本函数。分布执行策略的开销可以用总（耗费）时间或响应时间来表示。总时间是全部时间成分的总和，响应时间是从开始到完成查询跨越的时间间隔。确定总时间的一般公式如下：

Ttotal-time=TCPU*＃insts+TI/O*＃I/O+T MSG*＃msgs+T TR*＃bytes

这里用两个成分来量度本地处理时间，TCPU是CPU指令的时间，TI/O是磁盘I/O的时间。＃为变量表示数目，如＃insts表示执行的机器指令数，＃I/O表示磁盘的I/O存取数，＃bytes表示消息传递的字节数。通信时间用两个成分来表述：TMSG为启动和接收一个消息需要的固定时间，T TR为从一个节点到另一个节点传输一个数据单元花费的时间。数据单元以字节计（＃bytes为所有消息大小的总和），但单元的单位可不同。一般假设T TR是常数。当然，这也不是很精确，因为广域网上不同节点间数据单元传送所需的时间是不一样的。但为了简化，不得不把它看成是常数。传输＃bytes数据的通信开销可以看成是线性函数，例如：

TC（＃bytes）=T MSG+T TR*＃bytes

成本一般用时间来表示，当然也能转换成其他单位，如货币。

在分布式数据库系统里，成本因素有新的含义，原因是网络的拓扑结构会严重影响它。广域网（如Internet）里，通信时间一般成为决定因素。局域网里，本地处理开销和通信时间之间的差异不会像广域网里那么大。这样，大多数早期的分布式数据库系统在设计时忽略了本地处理开销，而只关注通信开销的最小化。为局域网设计的分布式数据库系统，同时考虑3个成本成分（CPU开销、传输消息数开销和传输字节数开销）。

概括来说，在集中式数据库中，查询优化主要强调两点：I/O操作的数量，执行查询所要求的CPU时间。

在分布式数据库中，还要增加节点之间传输的数据量及相关开销。有些系统仅考虑传输代价，原因是通信和本地处理的差异很大（本地处理很快，而通信延迟很大），尤其是广域网，差异更大。其思路如下。

●对分布式数据库系统，考虑传输代价是理所当然的。一般传输代价是两个节点之间发送数据量的函数。

●可把分布式查询优化分解为两个互相独立的问题：在节点之间访问策略的分配，只需考虑传输便可实现这种分配；在每个节点确定局部访问策略，这可采用传统的集中式数据库方法。

如果只考虑传输代价，则可以分两种情况考虑，即考虑传输费用和传输延迟。

●当考虑传输费用时，对应用要求的所有传输费用求和，便可得到应用性能的度量。这种方法相当于通信网络中总的传输开销最小化。

●当考虑传输延迟时，使用应用的启动和完成之间所经过的时间来度量该应用性能。缩短延迟相当于提高执行的并行程度，但缩短延迟与总的传输开销的最小化不一定相当。

pagenumber_ebook=147,pagenumber_book=132