资源描述:
《第6章查询处理和优化》由会员上传分享,免费在线阅读,更多相关内容在学术论文-天天文库。
1、第6章查询处理和优化6.1引言查询处理查询优化查询优化是查询处理中的重要一环,对关系DB尤其如此。——从查询语句出发,到获得查询结果的处理过程。——DBMS对描述性语言表达的查询语句进行分析,为其确定合理、有效的执行策略和步骤的过程。例如:12+64+88=?查询优化是相对而言的,可能的执行策略很多,穷尽代价很大,不能片面追求绝对的最优。(12+88)+64=164数据库查询语言的处理过程:(1)解释方式执行解释执行查询语句DBMSBEGINTRAN查询语句END应用程序查询请求查询结果优化占执行时间!
2、!查询语句(2)编译方式BEGINTRAN查询语句END应用程序…CALLAM(参数)…AM依赖因素访问模块AM预编译编译和连接目标码执行优化不占执行时间!!对于常见的例行事务,编译方式可提高性能。对于简短的即时查询,解释方式灵活实用。解释方式和编译方式各适用于什么情况?代数优化对查询语句进行变换不涉及存取路径物理优化根据存取路径选择合理的存取策略进行优化规则优化仅根据启发式规则选择执行的策略进行优化代价估算优化6.2代数优化代数优化对查询进行等效变换,以减少执行开销。代数优化的原则是尽量减小查询过程中
3、间结果的大小。选择、投影操作通常能够有效地减小关系的大小。连接、迪卡尔乘积和并操作容易生成较大的查询中间结果。因此,先做选择、投影;先做小关系间的连接,再做大关系的连接;甚至需要先找出查询中的公共表达式,以避免重复运算。常用变换规则1.2.3.4.5.RJNS=SJNR6.7.8.9.10.注意:规则11中,对于连接运算,可能出现S与T之间无连接条件的情况,此时的连接运算成为迪卡尔乘积。例如:(RJNc1S)JNc2T,式中,Attr.(c1)Attr.(R)Attr.(S)Attr.(c2)Attr.
4、(R)Attr.(T)而S和T之间没有连接条件。可改写为:RJNc1ANDc2(ST)11.范例p118例6-1设有S(供应商),P(零件),SP(供应关系)三个关系,关系模式如下:S(SNUM,SNAME,CITY)P(PNUM,PNAME,WEIGHT,SIZE)SP(SNUM,PNUM,DEPT,QUAN)有如下查询Q:SELECTSNAMEFROMS,P,SPWHERES.SNUM=SP.SNUMANDSP.PNUM=P.PNUMANDS.CITY=‘NANJING’ANDP.PNAME=‘BO
5、LT’ANDSP.QUAN>10000SQL语句转化为原始查询树SelectFromWhereQ可用右图所示的原始查询树表示:Q:SELECTSNAMEFROMS,P,SPWHERES.SNUM=SP.SNUMANDSP.PNUM=P.PNUMANDS.CITY=‘NANJING’ANDP.PNAME=‘BOLT’ANDSP.QUAN>10000原始查询树选择操作下压选择操作尽量下压原始查询树先连接小关系S,P,SP经选择后得S’、P’、SP’,估算大小:
6、S’
7、=
8、S
9、/NCITY
10、P’
11、=
12、P
13、/N
14、PNAME
15、SP’
16、=
17、SP
18、×(Vmax-10000)/(Vmax-Vmin)设
19、S’
20、<
21、P’
22、,
23、SP’
24、<
25、P’
26、消除对查询无用的属性消除对查询无用的属性代数优化的基本步骤:1.以SELECT子句对应投影操作,以FROM字句对应迪卡尔乘积,以WHERE子句对应选择操作,生成原始查询树。2.应用变换规则2)、6)、7)、9)、10),尽可能将选择条件移向树叶方向。3.应用连接、迪卡尔乘积的结合律,按照小关系优先做的原则,重新安排连接(笛卡尔乘积)的顺序。4.如果笛卡尔乘积后还须按连接条件进行选择操
27、作可将两者组合成连接操作。5.对每个叶节点加必要的投影操作,以消除对查询无用的属性。以上所讨论的都是非嵌套查询。嵌套查询比较复杂,分如下两种情况:1.嵌入的查询块与上层查询无关从最低层查询开始,用上述步骤和规则,逐层计算各查询快所等效的关系,直至求出查询结果。2.嵌入的查询块与上层查询有关一般用代入法。例如:SELECTA1FROMR1WHERER1.A2比较符CONST1ANDR1.A3IN(SELECTA4FROMR2WHERER2.A5比较符R1.A1)将第一层查询所涉及R1表中的每条记录,代入虚
28、线框所标出查询体,此时R1.A1为一个常量值,判断该记录是否满足查询条件。存在什么问题?能否再进行优化?注意:采用代入法时,尽可能作“部分选择”!SELECTA1FROMR1WHERER1.A2比较符CONST1ANDR1.A3IN(SELECTA4FROMR2WHERER2.A5比较符R1.A1)FROMR1WHERER1.A2比较符CONST1ANDFROMR1’WHERER1’.A3看作临时表R1’将R1’的每个元组逐个代入,检查限制