处理一个给定的查询,尤其是复杂查询,通常有很多策略。查询优化就是从许多策略中找出最有效的查询执行计划的处理过程。我们期望系统能够构造一个最小化查询执行代价的查询执行计划。
优化一方面在关系代数级别发生,即系统尝试找出一个与给出的表达式等价,但执行更为高效的表达式。另一方面为处理查询选择一个详细的测了。
给定一个关系代数表达式,查询优化器的任务是产生一个查询执行计划,该计划能获得与原关系表达式相同的结果,并且得到结果集的执行代价最小。
为了找到最小代价查询执行计划,该计划能获得与原关系表达式相同的结果,并且得到结果集的执行代价最小。
为了找到最小执行代价查询执行计划,查询优化器需要产生一些能和给定表达式得到相同结果的候选计划,并选择代价最小的一个。查询执行计划的产生:
要完成第一步,查询优化器需要产生与给定表达式等价的表达式,通过等价规则来进行。等价规则说明了如何将一个表达式转换成逻辑上等价的另一个表达式。通过估计一个查询计划的每个操作的结果集的统计大小来估计出单个操作的代价,把这些单个操作的代价合起来就确定了执行给定关系表达式的代价估计。
选择一个查询执行计划可以是基于执行计划的代价。这种优化称为就代价的优化。
物化视图能够帮助加速某些查询的处理。
如果两个关系代数表达式在所有有效数据库实例中都会产生相同的元组集,则我们称它们是等价的。元组的顺序是无关紧要的。
在SQL语言中,输入和输出都是元组的多重集合,关系代数的一个多重集合版本用于计算SQL表达式。若对于所有有效的数据库,两个表达式产生相同的多重集合,则称多重集合版本的这两个关系代数表达式是等价的。
等价规则指出了两种不同形式的表达式是等价的。
关系表达式的一些通用等价规则:
还有很多。
若一组等价规则中任一条规则都不能由其他规则联合起来导出,称这组等价规则集为最小的等价规则集。
一个好的连接运算次序对于减少临时结果的大小是很重要的
查询优化器使用等价规则系统地产生与给定表达式等价的表达式。
使用等价规则把表达式E2转换成E1,则E1和E2在结构上类似,并且具有一些相同的子表达式。采用一些表达式表示技术,使两个表达式指向共享的子表达式,可以明显减少对空间的需求。此外,不必总是用等价规则产生所有可以产生的表达式。
一个操作的代价依赖于它的输入的大小和其他统计信息。首先列出一些有关存储在数据库系统目录中的数据库关系的统计信息,然后使用这些统计信息去估计不同关系操作运算结果的统计信息。具有最小代价估计的计划通常等于或接近于实际最小执行计划。
DBMS目录存储了有关数据库关系的下列统计信息:
关于索引的统计信息,比如B+树索引的高度和索引中叶结点的页数,也保存在目录中。
如果希望维护准确的统计信息,则每次关系修改时,必须同时更新这些统计信息。这样更新导致一定量的额外开销。因此,可以当系统处于轻负载时进行更新。
当一个选择运算的结果大小的估计依赖于选择谓词。首先考虑一个单独的等值谓词,其次考虑一个单独的比较谓词,最后考虑谓词联合。
σA=a(r):如果假设取值是均匀分布的,并假设关系r的某个记录的属性A中的取值为a,则可选择结果有Nr/V(A,r)个元组。
σA<=v(r):如果进行代价估计时,用于修改比较操作的值(v)已知,可做更精确的估计。属性A的最小值min(A,r)和最大值max(A,r)可存储到目录中。假设值是均匀分布的,我们可以对满足条件A<=v的记录数进行估计:若v<min(A,r),则为0;若v>=max(A,r),则为Nr;否则,为Nr*(v-min(A,r)/(max(A,r)-min(A,r))
复杂选择:
合取:选择σi(r)的大小,记为Si。关系中的一个元组满足选择条件n的概率为Si/Nr。上述概率称为选择σi(r)的中选率。满足全部条件的元组数量为Nr(S1S2S3……Sn)/((Nr)^n)
析取:元组满足整个析取式的概率为1减去元组不满足任何一个条件的概率。
取反:选择σ-i(r)的结果集就是不在σi(r)的关系人的元组集。
笛卡尔积r×s包含Nr*Ns个元组。r×s中的每个元组占用Lr+Ls个字节。
当我们用等价规则得到较优的关系代数式后,我们需要选择一个较好的算法来执行。
每个关系运算可以用不同的算法,有多个可选的执行计划。另外,还要决定是否采用流水线技术。
最简单是为每个运算选择一个代价最小的算法。只要保证表达式树中层次较低的运算比层次较高的运算先执行,可选择任意的运算执行顺序。
然后总体上最佳的算法可能单个运算不是最优。所以,我们必须为表达式每个运算考虑可选的算法。用类似等价规则的规则来定义每个操作可用的算法,以及决定结果是否流水线化或者是否实体化。
两大类方法:
基于代价的优化器通过使用等价规则从给定的查询语句产生一系列查询执行计划,并选择代价最小的一个。
我们设计一个动态规划算法来寻找最佳连接算法。动态规划算法能够存储计算结果并将其重用,可大大减少执行时间。
若某个具体的元组排序顺序对后面的元素很有用的话,我们称该特定的顺序是一个感兴趣的排序顺序。还有其他几项技术来减少在大量计划中搜索的代价:
上述的查询优化方法主要集中在连接操作的顺序优化。
一些数据库系统使用的查询优化器是基于等价规则的,器易于扩展查询优化器以适应新规则。
基于代价的优化的缺点在于优化本身的代价。查询优化器可以使用启发式方法减少优化代价。启发式规则的例子:
多数现实中的查询优化器有更多的启发式规则来减少代价。如,许System R优化器,只对特殊类型的连接次序搜索,仅考虑右操作对象是原始关系的连接顺序,这称为左深连接顺序。
某些版本的Oracle系统最初采用减少连接顺序选择代价的启发式优化方法。有些采用基于SQL嵌套块概念的一个层次化过程。还有基于代价的优化技术独立地应用到每个查询块上。许多应用都会反复执行相同的查询,不过查询中的参数不一样,作为启发式方法,可以只对查询进行一次优化并缓存该查询执行计划。
即使使用启发式方法,基于代价的查询优化仍给查询处理带来不少开销。然而,增加的开销通常小于查询执行时间的节省,查询执行时间主要在慢速的磁盘存取上。
SQL概念上讲位于where子句中嵌套子查询处理称传入参数并且返回一个单独值或一个值的集合的函数。参数是嵌套子查询中用到的外层查询的变量。概念上,子查询视为一个函数,它获得一个参数并返回结果集。这种执行称为相关执行,效率不高,因为子查询对外层查询的每一个元组都进行单独运算,导致大量的I/O操作。
SQL优化器尽可能将嵌套子查询转换成连接形式。有效的连接算法避免了昂贵的随机I/O操作。
复杂嵌套子查询的优化是一个困难的工作,许多优化器仅作少量的去除相关工作,最好避免使用复杂嵌套子查询。
一个其内容已计算并存储的视图。物化视图引起了冗余数据。在许多情况下,读一个物化视图的内容比通过执行定义该视图的查询得到该视图的内容代价低得多。
物化视图的数据必须同原始数据一致,必须进行更新,这样的任务称为视图维护。
视图可以通过人工手写代码维护。也可以对视图定义中每一个关系的插入,删除和更新操作定义触发器。一个更好的方法是对物化视图受影响部分进行修改,称为增量的视图维护。
导致一个物化视图过时的改变关系的操作包括插入、删除和更新。可以将更新一个元组操作为删除该元组再插入一个更新的元组操作。对一个关系或表达式的改变称作它的一个变化量。
连接操作:考虑物化视图r⋈s。假设对关系r插入一个元组集Ir的改变。可以将插入一个元组集的物化视图的更新表达式重写为V(new)=V(old) U (Ir⋈s),r的原值记为r(old),新值记为r(new)。删除一个元组集Dr是:V(new)=V(old)-(Dr⋈s)。
选择和投影操作:记视图为V=σx(r),插入元组集Ir:V(new)=V(old) U σx(Ir),删除元组集Dr:V(new)=V(old) – σx(Dr).投影是一个更困难的操作,考虑视图V=IIA(r)。对投影的每个元组,将保留一个计数,当关系r中删除一个元组集Dr时,对Dr中对每个元组t:令t.A表示t在属性A的投影。我们在物化视图中找到(t.A),然后对其中存储的计数减一。如果计数变为0,则删除(t.A),插入则相应加一,如果没有,则插入。
聚集操作
count:与投影类似,当从关系r中删除一个元组集Dr时,作投影的操作。
sum:大致如上。
avg:大致如上。
min,max:插入处理直截了当,删除时还需查看关系r的其他元组是否有最小值。
表达式的处理
可以从最新的子表达式开始,推导出用于计算每一个子表达式结果的增量变化表达式。
重写查询以利用物化视图
将使用物化视图的地方替换成它的定义
物化视图的选择必须基于系统的工作负载,类似于索引的选择,在数据库应用系统性能调整中介绍
如果觉得我的文章对您有用,请点赞。您的支持将鼓励我继续创作!
赞0
添加新评论0 条评论