第七章 访问策略的优化.doc

第七章 访问策略的优化在第六章中，我们已经讨论了对于全局关系的查询算符树，如何依据准则1-2通过关系代数的等价变换来改良查询；对于规范化算符树则再依据准则3-5通过限定关系代数的等价变换来改良查询；这种改良可提高访问效率，但没有进行量化的讨论，如提高效率多少？减少开销多少？本章讨论内容已由标题醒目的点出：访问策略的优化，特点是基于数据库值的优化，有具体的量化，比较深入。即在各种可能的方案中选择一种费用最少的方案，相对而言，效率也较高，但往往得不到最忧方案，只是找一个较好的方案。7.1 查询优化概论 本节首先讨论查询处理问题、模型化问题和解决这些问题所需的假定，以及优化中使用的准则，然后建立查询的新模型及相应的定量参数。7.1.1 查询优化中的问题查询处理策略的选择包括：1.对某一段，给定一个查询表达式，决定要对这个段执行查询的物理拷贝，一般在文献中使用实质这个术语来表示对其执行查询的一个非冗余的拷贝，实质相当于为每个段选择它的一个拷贝。不同的查询可能使用不同的实质。2.选择操作执行的次序。即如何决定结合、半结合和并集操作这几种混合操作的次序。第六章查询变换以后产生的算符树隐含地定义了操作的部分次序，即从叶至根向上的执行操作，但这并没有完全规定优化问题的解，还要指出树的同一级上执行的各子表达式求值的次序，同时，从叶至根地向上执行并不一定能产生最佳结果。3. 选择执行每个操作的方法。包括在同一数据库访问中选择一起执行几个代数操作（如同时对同一操作执行选择和投影操作），以及在各种可用的方法中选择执行每个数据库访问的方法。最困难的是决定结合求值的最佳方案。上述三个问题相互间有影响，并非孤立。但也相当复杂，这里假设三者独立，并重点讨论第二个问题。7.1.2 查询处理优化的目标不管在集中式还是分布式环境中，查询执行策略都是根据对各种方案的期望性能进行衡量来选择的。在集中式数据库中，典型的度量方法是计算输入/输出操作的次数以及CPU的使用情况（I/O 次数要尽量少、CPU占用尽量少）。在分布式数据库中，除上述两项外，还必须考虑数据的传输量及延迟。时间，针对考虑的方面不同，主要目标也不同。传输的要求可以依据费用和延迟这两方面来评价。1当考虑费用时，一个应用的性能是用所有传输的费用之和来度量的。2当考虑效率时，一个应用的性能是用此应用从激活到完成所经历的时间来度量的。一次传输的传输费用TC和传输延迟TD可用函数表示为： TC（X） = C0 + X C1 TD（X） = D0 + X D1其中C0、D0、C1、D1是与系统有关的常数，C0相当于在两站点间启动一次传输所需的固定费用；C1是网络范围内统一的单位数据传输费用；D0是建立一个连接所需的固定时间，D1是网络范围内统一的传输单位信息的时间。如果全网各站点可能不均，考虑费用和延迟的更为详细的特性，即每对站点具有不同的系数，一次传输的传输费用TC和传输延迟TD可用函数表示为： TC（X） = C0ij+ X C1ij TD（X） = D0 ij+ X D1ij其中两个上标 I 和 j 分别表示这次传输的源和宿。这里假设是匀质。7.1.3 一种新的查询模型7.1.3.1 数据库的概貌对于段Ri ，其概貌其可由下列信息组成： 1每个段Ri 的元组数目-基数，表示为 Card（A）； 2每个属性A的大小（即字节数），表示为 Size（A）；一个段的大小，表示为Size（Ri），等于其属性大小之和，即Ri的记录长度。 3. 对于每个段Ri中的每个属性A，在Ri中出现的不同的值的数目，表示为Val（ARi）。 对于全局关系的概貌也同样由这三种信息组成。例如： Card(SUPPLY) = 50000 SNUM PNUM DEPTNUM QUAN Size 6 7 2 10 Val 3000 1000 30 500 Card(DEPT) = 30 DEPTNUM NAME AREA MGRNUM Size 2 15 1 7 Val 30 30 2 30 ( a) 全局关系SUPPLY和DEPT的概貌 Card(SUPPLY1) = 30000 Site（SUPLLY1）= 1 SNUM PNUM DEPTNUM QUAN Size 6 7 2 10 Val 1500 1000 30 500 Card(DEPT1) = 10 Site（DEPT1）= 2 DEPTNUM NAME AREA MGRNUM Size 2 15 1 7 val 10 10 2 10 （ b） 段SUPPLY1和DEPT1的概貌 图7. 1 概貌的例子7.1.3.2 代数操作结果的概貌的估算令S表示在关系R上执行一个一元操作的结果，并令T表示对两个关系R和S进行一个二元操作的结果。一、 对R进行的一个选择操作1.基数，对于每个选择我们有一选择度，最简单的选择是：属性 = 值（A = v），可以估计为1/Val（AR），假定这些值是均匀分布的，并且值v出现在R中，则有： Card（S）= Card（R）例：从在座的100个学生中，任给个学号，列出其信息。 这时可以估计为1/Val（AR）=1/100。 列出女同学信息： 这时可以估计为1/Val（AR）=1/2 （假设男女均匀）2大小， 选择操作不影响关系的大小（框架不变）。 Size（S）= Size（R）3不同的值，考虑一不在选择公式中出现的属性B，且均匀分布，则Val（BS）可通过概率统计导出，问题化为：给定 n = Card（R）个物体，均匀分布在m = Val（BR）种颜色中，如果我们只取r = card（S）个物体，可选择到多少不同的颜色C？ 这里给出一个近似解的计算公式： r, 当r = m/2 c(n,m r) = (r + m)/3, 当 m/2 r 2m （7.1） m, 当 r 2m这里，n、m 是R操作前的概貌信息，r可由选择操作后的基数Card（S）=Card（SLF（R）得到。有时候不能假定值是独立且均匀分布的，因而不能使用上面的表达式，特别是对于在选择公式中使用的属性，必须采用完全不同的求值方法，可具体问题具体分析。如：Val（学号S）=1 Val（性别S）=1二、 对R进行的一个投影操作1 基数 投影要影响操作数的基数，因为从结果中消除了重复。可以使用以下三个规则：l 如果投影只包含单个属性A，则Card（S）= Val（AR）l 如果投影只包括R的一个键，则Card（S）= Card（R）l 如果不是上述两种情况，包含了R的一个以上属性，则Card（S）MIN（ Val（AiR），Card（R）/? AiAttr(S）Attr(S）是投影结果属性集。2大小 投影结果的大小为：Size（S）= Size（Attr(S）3不同的值 被投影的属性的不同的值与操作数关系中的相同。三、Group-by 1.基数 给出S的基数的上限： Card（S）MIN（ Val（AiR），Card（R） AiG 2大小 对于在G中出现的全部属性A， Size（S.A）= Size（R.A） S 的大小为G和AF中属性大小之和，即： Size（S）= Size（R.A）+ Size（R.B） B为AF中的属性。 3不同的值 对于在G中出现的全部属性A Val（AS）= Val(AR) 四、 并集 （R S）1 基数Card（T ） Card（R）+ Card（S）2 大小 我们有：Size（T）= Size（R） = Size（S） 因为T、R、S三者为同类关系。 3 不同的值 上限为 Val（AT） Val（AR）+ Val（AS）（要小得多） 五、 差集1基数 Max（0，Card（R）- Card（S）Card（T）Card（R） 如果R S = 则Card（T）= Card（R） 如果R S 则Card（T）= 0 （Card（R）- Card（S）0） 如果S R 则Card（T）= Card（R）- Card（S）2 大小 Size（T）= Size（R）= Size（S） 因为T与R 、S关系。3. 不同的值 上限为： Val（AT） Val（AR） 六、笛卡儿乘积 1 基数 Card（T）= Card（R） Card（S） 2. 大小 Size （T）= Size（R）+ Size（S） 3. 不同的值 属性的不同的值与操作数关系中的相同。七、结合 考虑结合 T = R JNA=B S 。1基数 可给出一个上限 Card（T） Card（R） Card（S）该值一般远高于实际基数。假定R中A的全部值也是S中B的全部值，且反之亦然，即 （Val（AR）= Val（BS），并且这两个属性在R和S的元组上都是均匀分布的，则有： Card（T）= （Card（R） Card（S）/ Val（AR）/? 仍在上述假定之下，如果两个属性之一，例如A是R的一个键，或B是S的一个键,则： Card（T）= Card（S） （因Card（R）= Val（AR）或 Card（T）= Card（R） （因Card（S）= Val（AS） 例： T = S JNS.学号=SC.学号 SC 就是上述的第一种情况。 Card（T）=（Card（S）Card（SC）/ Val（学号AS）2. 大小Size （T）= Size（R）+ Size（S） 对于自然结合，必须从结果的大小中减去重复属性的大小。3. 不同的值 对于一结合操作产生的不同值的数目可给出一上限。如果A是一结合属性，则有： Val（AT） Val（AR）+ Val（BS）如果A不是一结合属性，则有： Val（AT） Val（AR）+ Val（BS）八、 半结合 考虑半结合 T = R SJA=B S 。1 基数 用表示半结合操作的选择度，它是R的元组中被选中的比例，有文献建议： = Val（AS）/Val（dom (A） 式中 Val(dom（A）)表示A域中不同的值的数目，给定，可求Card（T）为： Card（T）=Card（R）2大小 半结合结果的大小与其第一个操作数R的大小相同,即:Size（T）= Size（R）3不同的值 与选择运算类似，对于不在半结合公式中出现的属性B且均匀分布，可用公式(7.1)来计算,其中:n = Card（R），m = Val（AR）及r = Card（T）。 对于在此半结合公式中出现的唯一的属性A，则 Val（AT） =Val（AR）下面通过段的概貌估计讨论运算后的结果概貌。 例: Q1：查：对北部地区的部门供货的供应商号 PJSNUM JNDEPTNUM=DEPTNUM PJSNUM，DEPTNUM PJDEPTNUM SUPPLY1 DEPT1 SUPPLY1 SLAREA=“NORTH“ DEPT1 （a）查询Q1的算符树 （b）查询Q1的优化图 Reducer for SUPPLY1 ； PJSNUM，DEPTNUM (段简化程序) Reducer for DEPT1； PJDEPTNUMSLAREA=NORTH (段简化程序)简化后的段SUPPLY1 与 DEPT1 的概貌； Card（SUPPLY1）=30000 Card（DEPT1）= 10 Site（SUPPLY1）= 1 Site (DEPT1）= 2 SNUM DEPTNUM DEPTNUM Size 6 2 Size 2 Val 1800 20 Val 10 （c）在查询Q1简化后的简化程序和概貌 图7.2 使用简化程序和段的概貌把查询树变换至优化图7.1.3.3 查询优化的一种模型 本节给出一种查询优化的新模型，对查询优化的描述比算符树模型更为方便。它突出重点，只包含对此查询优化问题重要的那些操作，只考虑最常用的查询子集。一元操作不重要，因为它们只能在基数和大小两方面减小操作数而不需要任何数据传输，因此，一元操作必须尽早执行。二元操作是重要的，因为它们涉及了两个操作数的比较，因此，当操作数不在同一站点时就需要数据传输，本章只讨论二元操作的结合和并集。这里引入查询的优化图的新模型，在优化图中节点代表简化的段，“结合”用节点之间的边来表示，图7.2（a）表示完成了第六章的全部变换后查询Q1的算符树，图7.2（b）中表示了同一查询的优化图。该图只包含了用一根边连接起来的两个节点，边就代表了所要求的结合。该查询的两个段的简化程序见图7.2（c）DEPT1 at 2DEPT2 at 3DEPT3 at 5SUPPLY1 at 1SUPPLY2 at 4 DEPTNUM=DEPTNUM （a）查询Q1第一个版本的优化图 PJSNUM JNDEPTNU =DEPTNUM UN UN PJSNUM，DEPTNUM PJSNUM，DEPTNUM PJDEPTNUM PJDEPTNUM PJDEPTNUM SUPPLY1 SUPPLY2 SLAREA=NORTH SLAREA=NORTH SLAREA=NORTH DEPT1 DEPT2 DEPT3 （b） 查询Q1的一个算符数 图7.3 查询Q1的优化图 图7.3（a）表示了一较复杂的优化图例子，它对应于图7.3（b）中的算符树，图7.3（a）的优化图表示了两个并集操作以后再有一结合操作。7.1.4 分布式查询优化中假设的概要1对于每个查询，假设给定一个实质，并且在分配的段上操作。2开始时只考虑传输要求和使传输费用最少（在7.2.1、7.2.2中），在7.2.3中使传输延迟为最小，而在7.2.4中假设了一个更广泛的费用模型。3传输费用不与进行每次传输的两个站点有关（均质）。4为了求出概貌，在需要时可假定值在段的元组上均匀分布，而且全部属性都是独立的。5不考虑包含笛卡儿乘积和差集的查询。6在7.2节中我们考虑结合查询，这种查询的优化图中只包含结合操作而没有并集。7.1.5 分布式数据库中查询优化的重要性 分布式数据库系统效率与查询优化程序的质量密切相关，应用程序员应该有能力在只有较低透明性系统的环境下书写高效的查询程序。 还以Q1为例，查询对比部地区公司供货供应商号；设要求的结果在结点2。分析该查询不同执行策略的传输要求，为简单起见，忽略费用和延迟表达式中的C0和D0 。下面的讨论是根据77页图6.1、80页图6.4（规范化，且用准则12优化）、89页图6.7（用推论优化）、101页图7.1（给出概貌）、104页图7.2（优化后的概貌）和105页图7.3a（第一个版本的优化图） 中所示的该查询的算符树、优化图和概貌来进行的。策略1 把全部段平行进行收集于站点2，并在站点2执行此查询。把按照此查询中表示的次序来执行操作，没有任何简化和优化（见图6.4（a），图7.3（a）表示了这种情况的优化图，图7. 1给出了SUPPLY1和DEPT1的概貌，假定SUPPLY2、DEPT2和DEPT1的概貌是相似的，且card（SUPPLY2）= 20000 ，card（DEPT2）= card（DEPT1）= 10，我们把全部段收集在站点2以便在那里执行此查询，并且令收集是平行进行的，于是，DEPT1不需要传送。SUPPLY1等于30000 25 8 比特 ，SUPPLY2等于20000 25 8 比特 ，而DEPT2和DEPT3等于10 25 8 比特，最后得到的传输费用为10002000C1，传输延迟为6000000D1（相应于传输最大的段SUPPLY1）。如果D1等于10000比特/秒，则该查询执行策略要求10分钟。策略2 对段执行本地处理（即运用段的简化程序）；进行与策略1类似的平行传输，把全部简化的段发送至执行此查询的站点2。具体如下： SUPPLY1：因已经投影操作：S1 = 3000088 SUPPLY2：因已经投影操作：S2 = 2000088 DEPT2 经选择和投影：D2 = 约10个字节 DEPT2 几乎无 总费用：（30000 + 20000）88C1 = 320000C1 需延迟 3000088/10000=1920000/10000 = 192 秒，约3分钟。策略3 采用算符树7.2（a），即图6.7,经过限定关系代数学的优化，这时只需把经简化程序后的SUPPLY1传至站点2即可进行。 总费用为 3000088 = 1920000C1 需延迟 3000088 /D1= 1920000/D1 约为3分钟。 在费用上好于策略2。策略4 先把简化了的段DEPT1送至站点1，在站点1结合,然后把结果送回站点2 。 费用分析： DE