关 闭

新闻中心

EEPW首页 > 工控自动化 > 设计应用 > 关系代数与SQL查询优化的研究

关系代数与SQL查询优化的研究

作者:时间:2009-09-25来源:网络收藏

假设关系E1有106个元组,关系E2有103个元组。那么执行E1xE2,则有109个元组。若条件F只与E1有关,且满足F的选择性为0.1%,则意味着只有103个元组满足条件,而另外的1O9-103个元组都不满足条件。因此将σF(E1xE2)等价变换为σF(E1)xE2后,其中间结果σF (E1)的规模仅103元组。若1个物理块可允许存放100个E1元组,10个E2元组,而主存中可允许存放10块E1元组,1块E2元组,以下估计分析等价变换前后的代价。
2.2.1 等价变换前代价估计分析
等价变换前代价是指采用σF(E1)xE2方式所需花费的查询代价。下面分别从E1×E2和σF两个方面分析:
(1)E1×E2代价估计E1xE2代价估计主要是从磁盘读块和中间结果写盘的时间考虑,而对主存中数据的处理时间忽略不计。
E1xE2读块总数=E1的块数+E2的块数×读E2的遍数=104+100x103=110 000块。若每秒可以读50块,读块时间为2 200 s(约0.6 h)。连接后的元组数为109,若每块可存放10个元组,那么写中间结果需要的时间是108/50=2x1 06 s。故E1xE2花费的时间为2×106 s+2.2×103s≈556.2 h。
(2)σF代价估计 σF运算时需将E1xE2的中间结果依次读入内存进行运算,凶此需要108/50=2×106s;满足条件的103个元组,共需100个块写回磁盘,需2 s。故σF花费的时间为2x106s+2.2x103s≈556.2 h。
2.2.2 等价变换后查询代价估计分析
等价变换后查询代价是指采用σF(E1)xE2方式所需花费的查询代价。σF(E1)代价估计约为200 s,读E2的时间为2 s。又由于读E1进行选择的同时将满足条件的元组与E2连接,形成的中间结果有103全部可以放在主存,故无需写盘时间。从分析可知,等价变换后查询代价约为202 s。
2.3 关系代数表达式的优化规则
由上述分析可知,一个关系代数表达式可以有多种查询方案,每个方案的代价相差几个数量级,特别是当查询非常复杂的时候。因此生成一个好的查询方案非常重要。
但需要看到,生成每个可能的方案和测算代价需花费大量的时间,而生成的却可能是即将被抛弃的方案。解决办法是定义一般的优化规则,从而避免DBMS查询优化器枚举出一些差的方案。针对给定的查询问题,通常有以下优化规则:
规则1:尽量将选择和投影运算提前,以减少元组数和关系大小。
规则2:把某些选择运算和笛卡尔积相结合,即将选择运算附加在连接运算上,可减少中间结果保存以备后用的时间代价。
规则3:对同一关系上的多个选择和投影运算同时进行,以避免重复扫描同一关系。
规则4:把投影操作和连接运算结合起来执行。

本文引用地址:http://www.eepw.com.cn/article/202639.htm


3 查询优化
查询优化是为查询选择最有效的查询计划过程。查询优化一方面是在关系代数级进行优化,目的是力图找出与给定查询等价,但执行效率更高的一个表达式。
3.1 等价变换策略
查询优化的另一方面涉及查询语句处理的详细策略的选择,例如选择执行运算所采用的具体算法以及将使用的特定索引等。事实RDBMS优化器的查询优化从给定的查询开始,转换查询形式,直至所得到的形式依据某些规则是最优的。选择与投影等价变换策略有:
策略1:对同一关系的多个选择可以转换为一个用and连接的选择操作。例如:Select A1,…,AnFrom E where F1=
(Select A1 From E where F2)XXXXXXXXXXXXXXXXXXXXXSelect A1,…,AnFrom E where F1and F2。原始的查询意味着要对E进行2次扫描,而变换后只需要1次。



关键词: SQL 查询

评论


相关推荐

技术专区

关闭