连接操作的优化(数据库)

时间：2022-10-30 08:30:01 | 来源：信息时代

时间：2022-10-30 08:30:01 来源：信息时代

    连接操作的优化 : 对两表或多表的各种连接操作符进行优化,选择较优的查询计划。
连接操作是从两个关系的笛卡儿积中选取属性间满足一定条件的元组。在SQL查询中,表现为FROM子句涉及多个表。连接操作包括等值连接、自然连接、非等值连接、自身连接、外连接、复合条件连接等。笛卡儿积也可以看作是一种特殊的连接操作,即无条件的连接操作。连接操作通常是数据库查询中开销最大、最费时的操作,因而也是查询优化的重点操作符。
连接操作的优化主要包括确定多表连接操作的连接顺序(包括内表外表选择)和每个连接操作符的操作算法。
连接顺序的常用表达方式是连接树。通用的连接树形式是浓密树(bushy tree)。浓密树是一个满足下列条件的树:
(1)叶结点表示关系。
(2)每个内结点既表示一个数据操作,也表示操作的结果关系,其子结点所对应的关系是该内结点的操作关系
浓密树可以表达任意数目关系之间的任意连接顺序。图1就是一个五表连接的浓密树示例,它表达的连接顺序是:R₁与R₂连接,R₄与R₅连接,R₃与R₄、R₅的连接结果连接,R₁、R₂的连接结果与R₃、R₄、 R₅的连接结果连接。 即(R₁⋈R₂₎⋈(R₃⋈(R₄⋈R₅₎₎。

图1 浓密树示例

这些连接操作中, 分别由R₁、R₄、R₃、R₁⋈R₂做外关系。当这五个表采用其他连接操作顺序时,会形成不同的浓密树形式。
选择连接顺序的常用优化方法包括动态规划算法和贪心算法。
动态规划算法的基本思想是,采用自底向上搜索,对于一组相同关系的连接操作,仅保留其中最小代价的计划。连接操作的代价可以简单地以中间关系的大小表示(这时优化算法就是选择连接顺序),也可以是所选用的连接算法的代价(这时算法就是选择连接顺序以及连接算法)。例如,对于一个四表连接查询R⋈S⋈T⋈U,如果我们只允许左深连接树,利用动态规划方法优化连接操作的过程是:
(1)考虑单个关系,列出它的大小。不妨假设B(R)<B(S)<B(T)<B(U),则Cost(scan R)<Cost(scan S)<Cost(scan T)<Cost(scan U)。
(2)考虑两个关系的连接,列出两个关系的所有可能的连接组合,共种,即12种,它们是R⋈S, S⋈R, R⋈T, T⋈R, R⋈U, U⋈R, S⋈T,T⋈S, S⋈U, U⋈S, T⋈U, U⋈T。每一个关系对,只保留以较小代价的关系作左变元的连接对,例如,对于R⋈S与S⋈R,因为Cost(scan R)<Cost(scan S),于是保留R⋈S。 这样一共保留6个连接对(R⋈S,R⋈T, R⋈U, S⋈T, S⋈U,T⋈U), 分别计算其连接代价。 不妨假设Cost(T⋈U)<Cost(S⋈T)<Cost(R⋈S)<Cost(R⋈U)<Cost(R⋈T)<Cost(S⋈U)。
(3)考虑三个关系的连接,列出三个关系的所有可能的连接组合,共种, 即24种。对于每一个三关系组,由于只允许左深连接树,因此它一定是两个关系连接后再和第三个关系连接。我们只保留以最小代价的连接关系对作左变元的计划,计算其连接代价及结果关系的大小。例如,对于R、S、T的连接, 由第(2)步知道,Cost(S⋈T)<Cost(R⋈S)<Cost(R⋈T), 因此, 只保留以S⋈T作为左变元的连接计划, 即(S⋈T)⋈R。这样一共保留了4个连接子计划。
(4)考虑四个关系的连接,由于只允许左深连接树,因此,它一定是三个关系连接后再和第四个关系连接,我们仍然只考虑以最小代价的连接计划作左变元,利用第(3)步的结果,最后计算保留下来的连接计划的代价(共4种),从中选出最小代价的计划就是最终的连接顺序。
虽然动态规划算法对于一组相同关系的连接操作,仅保留了其中最小代价的计划,以此缩减了优化连接操作的搜索空间,但当参与连接的关系数目较大时(比如超过了5～6个),其效率依然会较低。一个更高效的优化连接操作的算法是贪心算法,它在优化过程中采用连接顺序试探来缩减搜索空间。贪心算法一次为连接的顺序作一个决定,一旦做出决定便不再重新考虑。
贪心算法以连接代价估算值最小的关系对开始,这对关系的连接成为当前树。然后递归地在所有还没有加入当前树的关系中,寻找与当前树进行连接时代价最小的关系及相应连接算法。以旧的当前树作为左变元,被选中的关系作为右变元来形成新的当前树。
除此之外,连接操作优化时,查询优化器还经常用启发式规则来选择连接顺序和连接算法,以进一步提高优化效率。常用的启发式规则有:
(1)如果参与连接的一个关系在连接属性上有索引,则采用索引连接,且该关系作为内表。
(2)如果参与连接的一个关系是按连接属性排好序的,则采用排序-合并连接比用散列连接好,但不一定比索引连接好。
(3)计算三个或更多的关系的并或交时,先对最小关系进行组合。