基于代价的查询优化(数据库)

时间：2022-12-27 22:30:01 | 来源：信息时代

时间：2022-12-27 22:30:01 来源：信息时代

    基于代价的查询优化 : 物理查询优化的一种重要方法。对关系查询进行物理查询优化的主要任务,是为逻辑查询计划选择高效合理的操作算法或存取路径,求得优化的查询计划,达到查询优化的目标。物理优化手段包括基于代价、基于规则、基于语义以及同时基于代价和规则的几种策略。其中基于代价的查询优化是根据数据字典中记载的各种统计信息,估算各种执行策略的代价,并从中选择一个系统认为是“较好”的执行策略。
鉴于数据库应用是I/O密集型操作,I/O开销远远大于CPU开销,因此,估算执行策略的代价时可以用所执行的磁盘I/O数近似,而忽略CPU时间。同时,由于我们仅仅需要比较两个不同策略的相对代价,因此,可以简单地用一个操作需要输入和输出的关系大小来近似操作本身的代价。
基本关系的大小可以直接从统计信息中获得,中间关系的大小需要根据统计信息进行估算,每个操作符都有常用的估算公式。
估算中间结果需要的统计信息包括:
T(R): 关系R的元组数Card(R)。
S(R):关系R每条元组的字节数Length(R.A)。
B(R):关系R占用的数据块数Page(R)。
V(R,A):关系R中属性A的不同取值个数Dom(R.A)。
Omax(R.A): 属性A在其值域范围内的最大值。
Omin(R.A): 属性A在其值域范围内的最小值。
这些统计信息一般被保存在数据字典、数据结构、相应属性的B树索引或统计直方图之中,由DBMS获取和维护。其中统计直方图可以比较方便地表达一个关系表的属性分布情况。最常见的统计直方图包括等高直方图和等宽直方图。
假设属性A的值域被划分为如下n个区间:(A₀,A₁,…,A_n-1)＝([a₀,a₁),[a₁,a₂₎,…,[a_n-1,a_n]),a₀和a_n为最大值和最小值,每个区间中的元组数被记为T(Range(R.A_i))＝T([a_i,a_i+1)),i=0,1,…,n-1。每个区间中属性A的基数被记为T(Odom(R.A_i))。等宽直方图的定义为:T(Odom(R.A_i))＝T(Odom(R.A_j))0≤i,j≤n-1,i≠j。即一个属性的等宽直方图是把该属性的取值范围分成相等大小的若干个区间,分别统计取值落在各个区间的元组数的多少,如图1所示。
等高直方图的定义为:T(Range(R.A_i))＝T(Range(R.A_j)),0≤i,j≤n-1,i≠j。即一个属性的等高直方图是调整区间的分界,使得落入每个区间的元组数相等,如图2所示。由于等高直方图可以比较好地解决数据偏斜(Data Skew)问题,因此在大多数系统中都采用这种直方图。

图1 等宽直方图

图2 等高直方图

依据这些统计信息估算中间结果大小的方法如下:
(1)投影操作符: 令U=π_a,b(R)。如果投影操作符不去除投影中的重复结果,其大小是可计算的,即有T(U)=T(R),S(U)为属性A和属性B的长度之和。如果去除投影中的重复结果,则T(U)为V(R,a)*V(R,b)。
(2)选择操作符: 选择操作的结果大小估计公式为:T(δ_p(R))=Selectivity_p(R)*T(R)。其中,Selectivity_p(R)是谓词p在R上的选择率。
(3)笛卡儿积操作符:R₁和R₂的笛卡儿积可以按如下公式估算:T(R₁×R₂₎＝T(R₁)×T(R₂₎;S(R₁×R₂₎＝S(R₁₎+S(R₂₎。
(4)非等值连接操作符:对于,可以用笛卡儿积加选择操作符来估算,即T(U)=T(σ_R1.a>R2.b(R₁×R₂₎₎。
(5) 自然连接操作符和等值连接操作符: 自然连接结果大小的估算基于两个关于值集的简化假设: 针对连接属性的值集包含假设和针对非连接属性的值集保持假设。
对于R(X,Y)⋈S(Y,Z), 值集包含假设是指, 如果V(R,Y)≤V(S,Y),则R中连接属性Y的每个取值都将出现在S的连接属性Y值中;如果V(R,Y)≥V(S,Y),则S中连接属性Y的每个取值都将出现在R的连接属性Y值中。值集保持假设是指,非连接属性X和Z的每个取值都会出现在连接结果集中,即V(R⋈S,X)=V(R,X),V(R⋈S,Y)=V(R,Y)。
基于这两个假设,R和S的连接结果集大小可以用下面公式估算:
令U=R(X,Y)⋈S(Y,Z), 则:

该估算公式可以类推到多属性自然连接上。假设R与S有任意多个公共属性y₁,y₂,…,y_n,则:

该估算公式也可以类推到多表连接上。令U=R₁⋈R₂⋈…⋈R_n,T(U)的估算规则是, 从每个关系中元组数的积出发,然后对于至少出现两次的属性A,除以除了V(R_i,A)中最小值之外的所有值。
等值连接结果的估算与自然连接类似,区别仅仅在于S的估算上,R和S等值连接结果的元组大小等于R和S的元组大小之和。
(6) 并操作符: 对于U=R∪S,T(U)的上限是R和S两个关系的元组数之和,下限是R和S中最大元组数,因此,T(U)通常用平均值来估算,即:

T(U)=((T(R)+T(S)+max(T(R),T(S)))/2;
S(U)=S(R)=S(S)。

(7)交操作符: 对于U=R∩S,T(U)的上限是R和S两个关系中最小元组数,下限是0,因此T(U)通常用平均值来估算,即:

T(U)=(0+min(T(R)),T(S)))/2=min(T(R),T(S))/2;
S(U)=S(R)=S(S)。

(8)差操作符: 对于U=R-S:

T(U)=(T(R)+(T(R)-T(S)))/2=T(R)-T(S)/2;
S(U)=S(R)=S(S)。

有了单个操作符的操作结果大小估算公式后,就可以估算不同操作算法的代价和内存需求了。代价估算方法就是根据计算相应操作算法从磁盘上读入关系的大小加上写出到磁盘上的关系大小,这些关系可能是基本表,也可能是上述操作符的输出结果。例如,对于投影和选择操作,它们只需要扫描一次关系,因此其代价为B(R),最小内存需求为1块。嵌套循环连接算法的代价为B(R)B(S)/M,最小内存需求M为2块。一趟散列连接的代价为B(R)+B(S),最小内存需求为min(B(R),B(S))+1。两趟散列连接算法的代价为3*(B(R)+B(S)),最小内存需求为

不同操作算法的代价估算和内存需求估算是基于代价优化方法选取优化物理计划的依据,选取优化物理计划的具体方法包括穷举法、启发式方法、分支界定计划枚举方法、爬山法、动态规划方法、Selinger风格优化等方法。其中除穷举法遍历了全部搜索空间,其他方法都可以看作是运用启发式规则缩减了搜索空间。
穷举法是对所有可能的选择(连接的次序、操作符的物理实现等)加以组合,对每个可能的物理计划估算代价,选择具有最小代价的一个计划。其优点是针对给定的逻辑查询计划,可以为之找到最优的物理计划,缺点是代价过于高昂。
启发式方法的基本思想是: 用启发式规则裁剪一部分可能不太好的物理计划。其优点是物理优化的搜索空间显著减小,缺点是可能丢失最优计划。
分支界定计划枚举方法的基本思想是: 首先通过启发式规则为整个逻辑查询计划找到一个好的物理计划,令其代价为C; 然后当考虑子计划的其他计划时,除去那些代价大于C的计划;如果代价C较小,则终止搜索并获得目前为止最优的计划。以该计划作为最终执行计划,以避免搜索更好的计划所花费的代价大于所获得的收益。
爬山法的基本思想是: 依据启发式规则选定一个的查询计划,以此作为开始,通过对计划作小的修改,找到具有较低代价的“邻近”计划,当小的修改已经找不到更好的计划时,搜索结束。
动态规划方法的基本思想是: 采用自底向上的方式进行搜索,对于每个子表达式,仅保留当前最小代价的计划。
Selinger风格优化是动态规划方法的改进。它不仅记录了每个子表达式的最小代价的计划,而且也记录了那些虽然具有较高代价,但按此计划执行,所生成中间结果集的元组顺序对表达式树中较高层操作符很有用的计划。