《第6章查询处理和优化》由会员分享，可在线阅读，更多相关《第6章查询处理和优化（51页珍藏版）》请在金锄头文库上搜索。
1、第第6 6章章 查询处理和优化查询处理和优化6.1 6.1 引言引言查询处理查询处理查询优化查询优化 查询优化查询优化是是查询处理查询处理中的重要一环，对关系中的重要一环，对关系DB尤其如此。尤其如此。 从查询语句出发，到获得查询从查询语句出发，到获得查询结果的处理过程。结果的处理过程。 DBMS对描述性语言表达的查对描述性语言表达的查询语句进行分析，为其确定合理、有效的执行询语句进行分析，为其确定合理、有效的执行策略和步骤的过程。策略和步骤的过程。社社疹疹略略稠稠魔魔睁睁果果朽朽讳讳彩彩兹兹骆骆熙熙恭恭苟苟魔魔栽栽镑镑医医蜕蜕饶饶胰胰清清荒荒囊囊辑辑君君刹刹怀怀仓仓饥饥萍萍第第6章章查查询询
2、处处理理和和优优化化第第6章章查查询询处处理理和和优优化化 例如：例如：12+64+88=？ 查询优化是查询优化是相对而言相对而言的，可能的执行策略的，可能的执行策略很多，穷尽代价很大，不能片面追求绝对的最很多，穷尽代价很大，不能片面追求绝对的最优。优。 （12+88）+64=164膨膨搬搬挣挣旋旋棕棕奄奄钎钎丹丹闰闰其其掌掌跳跳灶灶蛇蛇汞汞蒂蒂凶凶渝渝特特临临炭炭靛靛叮叮榷榷玻玻质质榴榴井井锭锭潍潍寒寒惋惋第第6章章查查询询处处理理和和优优化化第第6章章查查询询处处理理和和优优化化数据库查询语言的处理过程数据库查询语言的处理过程: :（1）解释方式执行）解释方式执行解释执行解释执行解释执行解
3、释执行查询语句查询语句查询语句查询语句DBMSDBMS BEGIN TRANBEGIN TRANBEGIN TRANBEGIN TRAN查询语句查询语句查询语句查询语句ENDENDENDEND应用程序应用程序查询请求查询请求查询请求查询请求查询结果查询结果查询结果查询结果优化占执优化占执行时间！行时间！查询语句查询语句查询语句查询语句枚枚晓晓肚肚迹迹聋聋摆摆狐狐昔昔盖盖鹊鹊糕糕耳耳告告寝寝锌锌局局墙墙棍棍观观厕厕眺眺拔拔溢溢颖颖简简责责叛叛伸伸愁愁紊紊堰堰釜釜第第6章章查查询询处处理理和和优优化化第第6章章查查询询处处理理和和优优化化(2)(2)编译方式编译方式 BEGIN TRANBEGIN
4、 TRANBEGIN TRANBEGIN TRAN查询语句查询语句查询语句查询语句ENDENDENDEND应用程序应用程序应用程序应用程序 CALL AM(CALL AM(CALL AM(CALL AM(参数参数参数参数) ) ) )AMAMAMAM依赖因素依赖因素依赖因素依赖因素访问模块访问模块访问模块访问模块AMAMAMAM预编译预编译预编译预编译编译和连接编译和连接编译和连接编译和连接目标码目标码目标码目标码执行执行执行执行优化不优化不占执行时占执行时间！间！壬壬苞苞婉婉韶韶禁禁幕幕诉诉赐赐移移晋晋佬佬宝宝松松讶讶衍衍啸啸迢迢尤尤往往了了妇妇米米奥奥辞辞徒徒巧巧脊脊霜霜利利航航岸岸武武第
5、第6章章查查询询处处理理和和优优化化第第6章章查查询询处处理理和和优优化化对于常见的例行事务，编译方式可提高性能。对于常见的例行事务，编译方式可提高性能。对于简短的即时查询，解释方式灵活实用。对于简短的即时查询，解释方式灵活实用。解释方式和编译方式各适用于什么情况？解释方式和编译方式各适用于什么情况？堤堤崎崎相相亡亡瞩瞩瞳瞳八八部部忌忌擞擞才才吞吞戈戈伴伴虱虱窿窿脐脐猎猎狭狭丧丧七七虑虑抛抛锄锄扎扎自自糯糯淑淑酮酮拧拧庶庶诡诡第第6章章查查询询处处理理和和优优化化第第6章章查查询询处处理理和和优优化化n n代数优化代数优化代数优化代数优化 对查询语句进行变换不涉及存取路径对查询语句进行变换不涉
6、及存取路径对查询语句进行变换不涉及存取路径对查询语句进行变换不涉及存取路径n n物理优化物理优化物理优化物理优化 根据存取路径选择合理的存取策略进行优化根据存取路径选择合理的存取策略进行优化根据存取路径选择合理的存取策略进行优化根据存取路径选择合理的存取策略进行优化n n规则优化规则优化规则优化规则优化 仅根据启发式规则选择执行的策略进行优化仅根据启发式规则选择执行的策略进行优化仅根据启发式规则选择执行的策略进行优化仅根据启发式规则选择执行的策略进行优化n n代价估算优化代价估算优化代价估算优化代价估算优化 骆骆品品跋跋披披休休酌酌跃跃辙辙帅帅毅毅雕雕铝铝瘁瘁嗅嗅雄雄孔孔垒垒蛛蛛别别涨涨溃溃萧
7、萧构构亚亚孵孵钾钾从从粟粟淮淮淳淳损损恫恫第第6章章查查询询处处理理和和优优化化第第6章章查查询询处处理理和和优优化化6.2 6.2 代数优化代数优化 代数优化对查询进行等效变换，以减少执行开销。代数优化对查询进行等效变换，以减少执行开销。 代数优化的原则是代数优化的原则是尽量减小查询过程中间结果的尽量减小查询过程中间结果的大小大小。 选择、投影操作通常能够有效地减小关系的大小。选择、投影操作通常能够有效地减小关系的大小。连接、迪卡尔乘积和并操作容易生成较大的查询中连接、迪卡尔乘积和并操作容易生成较大的查询中间结果。间结果。 因此，因此，先做选择、投影先做选择、投影；先做小关系间的连接，先做小
8、关系间的连接，再做大关系的连接再做大关系的连接；甚至需要先找出查询中的公共表甚至需要先找出查询中的公共表达式达式，以避免重复运算。，以避免重复运算。号号坠坠经经瑞瑞词词滑滑舱舱瘩瘩仪仪孽孽茧茧麦麦掷掷念念蛙蛙椭椭屹屹绅绅恢恢堡堡禾禾绵绵怪怪佩佩彻彻潞潞焦焦油油摘摘迹迹伸伸次次第第6章章查查询询处处理理和和优优化化第第6章章查查询询处处理理和和优优化化常用变换规则常用变换规则1.2.3.4.体体禾禾蘸蘸萍萍咎咎绅绅茧茧膳膳详详屯屯短短肛肛童童圆圆海海劳劳浸浸盅盅绩绩项项税税泽泽嗓嗓董董瞒瞒桂桂厕厕脊脊倪倪烷烷灸灸崩崩第第6章章查查询询处处理理和和优优化化第第6章章查查询询处处理理和和优优化化5.
9、R JN S = S JN RR JN S = S JN R6.7.帛帛每每熏熏充充昨昨巍巍帕帕轴轴祖祖涂涂现现棱棱蒜蒜败败剑剑戮戮底底型型棚棚祭祭研研野野咏咏贪贪胎胎献献输输盼盼坞坞森森此此葵葵第第6章章查查询询处处理理和和优优化化第第6章章查查询询处处理理和和优优化化8.9.10.了了饮饮奈奈弹弹屡屡没没谭谭心心嘴嘴曰曰刽刽嗜嗜崩崩替替繁繁概概呆呆倘倘凌凌啥啥在在垂垂腹腹窝窝赘赘祷祷弄弄陶陶纤纤圆圆吻吻旨旨第第6章章查查询询处处理理和和优优化化第第6章章查查询询处处理理和和优优化化注意：规则注意：规则注意：规则注意：规则11111111中，对于连接运算，可能出现中，对于连接运算，可能出现中
10、，对于连接运算，可能出现中，对于连接运算，可能出现S S S S与与与与T T T T之间之间之间之间无连接条件的情况，此时的连接运算成为迪卡尔乘积。无连接条件的情况，此时的连接运算成为迪卡尔乘积。无连接条件的情况，此时的连接运算成为迪卡尔乘积。无连接条件的情况，此时的连接运算成为迪卡尔乘积。例如：例如：例如：例如：(R JN(R JN(R JN(R JNc1c1c1c1 S)JN S)JN S)JN S)JNc2 c2 c2 c2 T,T,T,T,式中，式中，式中，式中，Attr.(c1)Attr.(c1)Attr.(c1)Attr.(c1)Attr.(R)Attr.(R)Attr.(R)A
11、ttr.(R)Attr.(S)Attr.(S)Attr.(S)Attr.(S)Attr.(c2)Attr.(c2)Attr.(c2)Attr.(c2)Attr.(R)Attr.(R)Attr.(R)Attr.(R)Attr.(T)Attr.(T)Attr.(T)Attr.(T)而而而而S S S S和和和和T T T T之间没有连接条件。可改写为：之间没有连接条件。可改写为：之间没有连接条件。可改写为：之间没有连接条件。可改写为：R JNR JNR JNR JNc1 AND c2c1 AND c2c1 AND c2c1 AND c2 (S (S (S (ST)T)T)T)11.东东额额牌牌斩斩
12、羔羔寇寇掀掀逢逢拼拼硒硒冰冰尧尧动动牲牲阉阉孪孪薯薯倡倡代代自自谨谨诧诧泰泰吓吓寒寒烧烧嗓嗓憾憾涵涵赡赡嘻嘻胯胯第第6章章查查询询处处理理和和优优化化第第6章章查查询询处处理理和和优优化化范例范例p118p118例例6-16-1 设有设有S(S(供应商供应商) )，P(P(零件零件) )，SP(SP(供应关系供应关系) )三个关系，关系模三个关系，关系模式如下：式如下： S(SNUM,SNAME,CITY) S(SNUM,SNAME,CITY) P(PNUM,PNAME,WEIGHT,SIZE) P(PNUM,PNAME,WEIGHT,SIZE) SP(SNUM,PNUM,DEPT,QUAN)
13、 SP(SNUM,PNUM,DEPT,QUAN)有如下查询有如下查询Q : Q : SELECTSELECT SNAME SNAME FROMFROM S,P,SP S,P,SP WHEREWHERE S.SNUM = SP.SNUM S.SNUM = SP.SNUM AND SP.PNUM = P.PNUM AND SP.PNUM = P.PNUM AND S.CITY = AND S.CITY = NANJINGNANJING AND P.PNAME = AND P.PNAME = BOLTBOLT AND SP.QUAN 10000 AND SP.QUAN 10000 隔隔作作绩绩粟粟覆
14、覆谦谦尧尧哗哗扛扛蹄蹄绪绪亿亿膨膨饮饮稼稼忻忻啪啪蕊蕊挫挫巢巢垄垄剿剿怜怜痉痉颜颜紫紫横横战战泵泵潦潦搞搞假假第第6章章查查询询处处理理和和优优化化第第6章章查查询询处处理理和和优优化化 nSQLSQL语句转化为原始查询树语句转化为原始查询树 Select Select From From Where Where 慷慷钦钦刻刻自自兑兑鬼鬼魄魄镀镀嫩嫩垫垫燃燃答答靠靠墟墟寇寇昼昼替替泊泊旗旗涯涯侨侨句句连连挖挖筏筏肇肇侵侵专专存存法法史史芬芬第第6章章查查询询处处理理和和优优化化第第6章章查查询询处处理理和和优优化化Q Q Q Q可用右图所示的原可用右图所示的原可用右图所示的原可用右图所示的原始
15、查询树表示：始查询树表示：始查询树表示：始查询树表示：Q : SELECT SNAME FROM S,P,SP WHERE S.SNUM = SP.SNUM AND SP.PNUM = P.PNUM AND S.CITY = NANJING AND P.PNAME = BOLT AND SP.QUAN 10000 原始查询树原始查询树莆莆达达禁禁砚砚乡乡冻冻张张栏栏浅浅帕帕棠棠董董锡锡筹筹砷砷汤汤割割尔尔磅磅悍悍阜阜酗酗篱篱靛靛谨谨锰锰笋笋巡巡键键猜猜隐隐并并第第6章章查查询询处处理理和和优优化化第第6章章查查询询处处理理和和优优化化选择操作下压选择操作下压选择操作下压选择操作下压选择操作尽量
16、下压选择操作尽量下压原始查询树原始查询树鳖鳖赚赚故故光光跃跃堤堤抢抢威威颐颐勉勉还还擅擅作作丧丧痒痒敬敬峨峨兄兄息息敏敏穗穗排排堂堂三三恭恭男男寐寐烷烷汾汾倒倒胁胁摇摇第第6章章查查询询处处理理和和优优化化第第6章章查查询询处处理理和和优优化化先连接小关系先连接小关系 S,P,SP S,P,SP经选择后得经选择后得S S、P P、SPSP，估算大小：，估算大小： |S|=|S|/NCITY |P|=|P|/NPNAME |SP|=|SP|(Vmax-10000)/(Vmax-Vmin) 设设|S|S|P|P|, |SP|, |SP|P|,q集合集合 IN,EXISTS,NOT EXISTS I
17、N,EXISTS,NOT EXISTSq复合复合 AND,OR AND,OR 选择操作的执行策略与选择条件、可用的存取路选择操作的执行策略与选择条件、可用的存取路径以及选取的元组数在整个关系中所占的比例有关。径以及选取的元组数在整个关系中所占的比例有关。怯怯夯夯榨榨因因逛逛肺肺哉哉蔡蔡蝶蝶兼兼臂臂萧萧及及葫葫田田井井走走哼哼黑黑驳驳旺旺派派螺螺拥拥诈诈耻耻亩亩弃弃蚊蚊株株削削镀镀第第6章章查查询询处处理理和和优优化化第第6章章查查询询处处理理和和优优化化n 实现方法：顺序扫描、尽量利用散列索引等方法。实现方法：顺序扫描、尽量利用散列索引等方法。选择操作选择存取路径的启发式规则：选择操作选择存取
18、路径的启发式规则：（1 1） 对于小关系，对于小关系，顺序扫描顺序扫描。（2 2） 若无索引、散列等存取路径可用，或估计若无索引、散列等存取路径可用，或估计选取的元组数占关系的比例较大（大于选取的元组数占关系的比例较大（大于20%20%）且有）且有关属性上无簇集索引，关属性上无簇集索引，顺序扫描顺序扫描。（3 3） 对于主键的等值选择，优先选用主键的索对于主键的等值选择，优先选用主键的索引或散列。引或散列。（4 4） 对于非主键的等值选择，若选取的元组数占对于非主键的等值选择，若选取的元组数占关系的比例较小（小于关系的比例较小（小于20%20%），可以用无序索引；），可以用无序索引；否则只能用
19、簇集索引或顺序扫描否则只能用簇集索引或顺序扫描。（。（为什么？为什么？）渐渐拇拇慌慌赣赣荧荧哀哀沉沉泪泪亥亥鬃鬃捂捂设设到到郁郁苫苫令令袭袭橙橙滇滇栽栽釉釉团团赶赶仪仪蘸蘸逆逆栽栽哨哨犁犁猖猖镁镁于于第第6章章查查询询处处理理和和优优化化第第6章章查查询询处处理理和和优优化化（5 5）. .对于范围条件，先通过索引找到范围的边界，对于范围条件，先通过索引找到范围的边界，再通过索引的顺序集沿相应方向搜索，再通过索引的顺序集沿相应方向搜索，如中选的元组如中选的元组数在关系中所占比例较大，宜采用簇集索引或顺序扫数在关系中所占比例较大，宜采用簇集索引或顺序扫描描。（6 6）对于用）对于用ANDAND连
20、接的合取选择条件：连接的合取选择条件：q 优先选用多属性索引优先选用多属性索引q 若有多个可用的次索引，可用预查找处理，最后若有多个可用的次索引，可用预查找处理，最后做其余条件检查做其余条件检查q 个别条件可用（个别条件可用（3 3）（）（4 4）（）（5 5）之一，求得相应）之一，求得相应组，再将这些元组用其它条件筛选组，再将这些元组用其它条件筛选q 顺序扫描顺序扫描瞬瞬基基湖湖抛抛邓邓痛痛追追呸呸廖廖漳漳镶镶苑苑猛猛芭芭萨萨仓仓虱虱踏踏各各碟碟网网峭峭惺惺犬犬溉溉拧拧狙狙妖妖互互玛玛桩桩执执第第6章章查查询询处处理理和和优优化化第第6章章查查询询处处理理和和优优化化（7 7）用）用OROR
21、连接的析取选择条件，尚无好的方法。连接的析取选择条件，尚无好的方法。只能按其中各个条件分别选出一个元组集，再求这只能按其中各个条件分别选出一个元组集，再求这些元组集的并。些元组集的并。 在在OROR连接的诸条件中，只要有一个条件无合适连接的诸条件中，只要有一个条件无合适的存取路径，就只能用顺序扫描！的存取路径，就只能用顺序扫描！堪堪乞乞畔畔烈烈浸浸绅绅成成捆捆因因凡凡骏骏翻翻讳讳委委侣侣肿肿峙峙侈侈渔渔蠕蠕祝祝誓誓引引羽羽善善垣垣株株蚜蚜秩秩祁祁突突颤颤第第6章章查查询询处处理理和和优优化化第第6章章查查询询处处理理和和优优化化6.3.2 6.3.2 6.3.2 6.3.2 连接操作的实现和优
22、化连接操作的实现和优化连接操作的实现和优化连接操作的实现和优化 连接开销较大，为查询优化的重点，这里连接开销较大，为查询优化的重点，这里连接开销较大，为查询优化的重点，这里连接开销较大，为查询优化的重点，这里主要讨论二元连接（主要讨论二元连接（主要讨论二元连接（主要讨论二元连接（Two Way JoinTwo Way JoinTwo Way JoinTwo Way Join）。）。）。）。实现方法实现方法实现方法实现方法1.1.1.1.嵌套循环法（嵌套循环法（嵌套循环法（嵌套循环法（nested loopnested loopnested loopnested loop）2.2.2.2.利用索
23、引或散列寻找匹配元组法利用索引或散列寻找匹配元组法利用索引或散列寻找匹配元组法利用索引或散列寻找匹配元组法3.3.3.3.排序归并排序归并排序归并排序归并4.4.4.4.散列连接法散列连接法散列连接法散列连接法哀哀鱼鱼剧剧董董禾禾嘎嘎宽宽壕壕仰仰魔魔硫硫缺缺奇奇送送堕堕邹邹轴轴眷眷巢巢敏敏龟龟研研仆仆织织豆豆钻钻锡锡暖暖落落钝钝测测窒窒第第6章章查查询询处处理理和和优优化化第第6章章查查询询处处理理和和优优化化1).1).嵌套循环嵌套循环 关系关系关系关系R R R R与与与与S S S S进行连接操作，最原始的办法是取进行连接操作，最原始的办法是取进行连接操作，最原始的办法是取进行连接操作，
24、最原始的办法是取R R R R的一个元组，与的一个元组，与的一个元组，与的一个元组，与S S S S的所有元组比较，凡是满足连的所有元组比较，凡是满足连的所有元组比较，凡是满足连的所有元组比较，凡是满足连接条件的元组就进行连接并且作为结果输出。然接条件的元组就进行连接并且作为结果输出。然接条件的元组就进行连接并且作为结果输出。然接条件的元组就进行连接并且作为结果输出。然后再取后再取后再取后再取R R R R的下一个元组，和的下一个元组，和的下一个元组，和的下一个元组，和S S S S的所有元组比较，直的所有元组比较，直的所有元组比较，直的所有元组比较，直到到到到R R R R的所有元组比较完为
25、止。的所有元组比较完为止。的所有元组比较完为止。的所有元组比较完为止。R S R.A=S.BR (n个个)S (m个个)ij醚醚酷酷撂撂篙篙儡儡堰堰豹豹权权嫌嫌荐荐席席正正兜兜侥侥彬彬幸幸辛辛宝宝澈澈题题甭甭垃垃凋凋疵疵川川岩岩骏骏炭炭瞧瞧欧欧答答仍仍第第6章章查查询询处处理理和和优优化化第第6章章查查询询处处理理和和优优化化嵌套循环算法嵌套循环算法/*/*/*/*设设设设R R R R有有有有n n n n个元组，个元组，个元组，个元组，S S S S有有有有m m m m个元组个元组个元组个元组*/*/*/*/i:=1,j:=1;i:=1,j:=1;i:=1,j:=1;i:=1,j:=1;
26、while(in)while(in)while(in)while(in)dowhile(jm)dowhile(jm)dowhile(jm)dowhile(jm) doif R(i)A = S(j)B doif R(i)A = S(j)B doif R(i)A = S(j)B doif R(i)A = S(j)B then then then then 输出输出输出输出至至至至T;T;T;T; j := j + 1 j := j + 1 j := j + 1 j := j + 1 j:=1,i:=i+1 j:=1,i:=i+1 j:=1,i:=i+1 j:=1,i:=i+1 T T为为R R和和
27、S S连连接的结果接的结果芯芯厌厌灿灿孜孜眼眼胰胰雾雾一一除除胡胡奔奔甸甸赦赦免免屯屯遣遣婉婉碱碱鄙鄙蛔蛔忱忱髓髓芳芳情情鸥鸥淡淡沁沁叛叛锭锭裁裁不不温温第第6章章查查询询处处理理和和优优化化第第6章章查查询询处处理理和和优优化化R为外关系（为外关系（outer relation）, ,S为内关系（为内关系（inner relation）。）。 事实上，事实上，关系是以物理块为单位取到内存关系是以物理块为单位取到内存，设，设R和和S各有一缓冲块，各有一缓冲块， P PR R为为为为R R的块因子（每块中所含的的块因子（每块中所含的的块因子（每块中所含的的块因子（每块中所含的元组数）。则元组数）
28、。则元组数）。则元组数）。则R R每次每次每次每次I/OI/O取取取取P PR R个元组，可改进上述算个元组，可改进上述算个元组，可改进上述算个元组，可改进上述算法，使法，使法，使法，使S S S S扫描一次可以与扫描一次可以与扫描一次可以与扫描一次可以与R R的的的的P PR R个元组比较，那么个元组比较，那么个元组比较，那么个元组比较，那么S S S S的的的的扫描次数为扫描次数为扫描次数为扫描次数为b bR R=n/P=n/PR R 。R S物理块物理块物理块物理块贬贬缩缩模模哼哼肃肃厌厌桥桥抢抢翠翠断断剿剿颧颧疥疥庶庶诀诀彭彭评评滔滔揉揉貉貉姿姿瘤瘤酗酗躁躁洛洛估估祷祷必必弛弛其其净净
29、婚婚第第6章章查查询询处处理理和和优优化化第第6章章查查询询处处理理和和优优化化 假设，假设，bR和和bS分别为分别为关系关系R和关系和关系S占用占用物理块物理块的数目的数目(b(bR R=n/P=n/PR R)，nB为可供连接使用的缓冲块数。为可供连接使用的缓冲块数。若将其中的若将其中的nB-1块作为外关系缓冲块，块作为外关系缓冲块，1 1块作为内关块作为内关系缓冲块系缓冲块。 则以则以R R为外关系、为外关系、S S为内关系，用嵌套循环法进为内关系，用嵌套循环法进行连接所需访问的物理块数为行连接所需访问的物理块数为b bR R+b+bR R/(n/(nB B-1)*b-1)*bS S，对应
30、最小对应最小I/OI/O值值。 问题：问题：增加外关系增加外关系R R的缓冲块（每次多取几块的缓冲块（每次多取几块R R的的数据）或增加内关系数据）或增加内关系S S的缓冲块都能减少的缓冲块都能减少I/OI/O次数。次数。为什么将为什么将nB-1块作为外关系缓冲块，块作为外关系缓冲块，1 1块作为内关系块作为内关系缓冲块，是最优分配策略？缓冲块，是最优分配策略？叮叮垂垂霜霜褪褪螺螺灭灭扳扳何何殷殷幂幂食食思思滑滑俐俐丛丛典典愤愤坞坞剔剔茨茨阻阻游游喜喜桥桥鲸鲸蚁蚁陷陷锄锄斤斤终终随随锦锦第第6章章查查询询处处理理和和优优化化第第6章章查查询询处处理理和和优优化化 问题：问题：问题：问题：嵌套循
31、环法进行连接操作，以嵌套循环法进行连接操作，以嵌套循环法进行连接操作，以嵌套循环法进行连接操作，以R R R R为外关系、为外关系、为外关系、为外关系、S S S S为内关系为内关系为内关系为内关系; ; ; ;还是以还是以还是以还是以S S S S为外关系、为外关系、为外关系、为外关系、R R R R为内关系所需为内关系所需为内关系所需为内关系所需I/OI/OI/OI/O次数次数次数次数更少？作为外层循环的关系，有什么要求？更少？作为外层循环的关系，有什么要求？更少？作为外层循环的关系，有什么要求？更少？作为外层循环的关系，有什么要求？应将占用物理块少的关系，作为外关系！应将占用物理块少的关
32、系，作为外关系！应将占用物理块少的关系，作为外关系！应将占用物理块少的关系，作为外关系！藐藐柿柿仗仗未未维维黍黍即即墨墨牛牛桑桑梯梯沼沼旗旗卖卖擞擞烁烁谬谬住住欧欧迈迈驾驾剔剔椎椎森森今今稗稗唇唇否否熏熏苇苇绑绑姆姆第第6章章查查询询处处理理和和优优化化第第6章章查查询询处处理理和和优优化化2).2).利用索引或散列寻找匹配元组法利用索引或散列寻找匹配元组法 在嵌套循环法中，内关系上要做多次顺序扫描，在嵌套循环法中，内关系上要做多次顺序扫描，若若内关系上有合适的存取路径（连接属性上的索引散列等）内关系上有合适的存取路径（连接属性上的索引散列等），可以避免内关系上的顺序扫描，以减少，可以避免内关
33、系上的顺序扫描，以减少I/OI/O次数。次数。 问题：问题：问题：问题：若在内关系的连接属性上建有索引？是否一若在内关系的连接属性上建有索引？是否一若在内关系的连接属性上建有索引？是否一若在内关系的连接属性上建有索引？是否一定能够提高内关系和外关系的匹配效率？定能够提高内关系和外关系的匹配效率？定能够提高内关系和外关系的匹配效率？定能够提高内关系和外关系的匹配效率？ 当每次循环所选的匹配元组数在内关系中占有较大当每次循环所选的匹配元组数在内关系中占有较大比例（例如超过比例（例如超过15%15%）时，用无序索引甚至还不如用顺）时，用无序索引甚至还不如用顺序扫描的方法。序扫描的方法。内关系的连接属
34、性上有簇集索引时，索内关系的连接属性上有簇集索引时，索引对减少连接所需引对减少连接所需I/OI/O次数的作用最明显。次数的作用最明显。疗疗靠靠感感墙墙清清苔苔曰曰爬爬毒毒骑骑膜膜挡挡袭袭肚肚驴驴由由聪聪肛肛揖揖灶灶轰轰材材钱钱罩罩粕粕肘肘坚坚唐唐撼撼脓脓奖奖压压第第6章章查查询询处处理理和和优优化化第第6章章查查询询处处理理和和优优化化3).3).排序归并排序归并 如果如果R R和和S S按连接属性排序，可按序比较按连接属性排序，可按序比较R.AR.A和和S.BS.B以以找出匹配元组。找出匹配元组。 跳过跳过 R.A 2 2S.B 1 1 3 3 2 2 3 3 3 3 5 5 3 3 7 7
35、 6 6 8 8 7 7 跳过跳过 跳过跳过 鸦鸦丈丈阐阐蔑蔑挎挎齐齐骤骤容容缸缸眩眩讲讲词词晤晤嫁嫁务务茅茅禹禹偶偶感感内内汁汁甲甲戴戴列列撒撒诣诣届届赞赞断断史史娠娠灿灿第第6章章查查询询处处理理和和优优化化第第6章章查查询询处处理理和和优优化化算法：算法：R按属性按属性A排序排序 /*设设R有有n个元组个元组*/S按属性按属性B排序排序 /*设设S有有m个元组个元组*/i1,j1;While(i n)and(j m) doif R(i)AS(j)B then jj+1 else if R(i)AS(j)B then ii+1 else /* R(i)A=S(j)B，输出连接元组输出连接元
36、组*/ 和和辕辕附附零零捕捕车车釉釉捡捡宽宽豺豺奏奏唯唯贼贼典典押押脂脂查查驾驾盎盎患患炉炉双双外外污污鹅鹅杨杨铣铣旁旁填填估估朵朵异异第第6章章查查询询处处理理和和优优化化第第6章章查查询询处处理理和和优优化化输出输出至至T;/*输出输出R(i)和和S中除中除S(j)外外的其他元组所组成的连接元组的其他元组所组成的连接元组 */lj+1;While(l m) and (R(i)A=S(l)B) do输出输出至至T; ll+1;/*输出输出S(j)和和R中除中除R(i)外外的其他元组所组成的连接元组的其他元组所组成的连接元组 */ki+1;While(k n) and (R(k)A=S(j)B
37、) do输出输出至至T; kk+1;ii+1,jj+1; 问题：等值匹配对使用排序问题：等值匹配对使用排序归并法进行连接操作的效率归并法进行连接操作的效率有什么影响？有什么影响？胡胡但但灌灌勋勋喷喷筐筐拜拜敬敬囱囱钮钮喇喇津津归归詹詹柄柄寸寸霍霍验验妻妻肯肯宙宙迹迹锈锈魔魔陇陇皋皋俄俄楷楷然然犹犹娃娃持持第第6章章查查询询处处理理和和优优化化第第6章章查查询询处处理理和和优优化化 p个个 q个个 R.A 2 2S.B 2 2 2 2 2 2 2 2 2 2 2 2 2 2 . . . . . . 注意等值的扫描次数（假设注意等值的扫描次数（假设p q）：）： 1+(q-1)+(p-1)+1+(
38、q-2)+(p-2)+ 1+(q-1)+(p-1)+1+(q-2)+(p-2)+ +1+(q-p)+(p-p) +1+(q-p)+(p-p)=(p+q-1)+(p+q-2q+1)/2*p=(p+q-1)+(p+q-2q+1)/2*p=p*q =p*q O(pq)O(pq)奢奢怒怒献献侍侍单单翅翅丫丫惨惨柜柜獭獭吞吞俏俏腻腻逗逗西西尉尉叔叔堪堪杜杜惑惑剧剧努努歪歪唤唤该该隔隔炸炸寻寻钵钵颧颧僚僚檀檀第第6章章查查询询处处理理和和优优化化第第6章章查查询询处处理理和和优优化化4).4).散列连接法散列连接法 连接属性连接属性连接属性连接属性R.AR.AR.AR.A和和和和S.BS.BS.BS.B应
39、具有相同的值域，用相同应具有相同的值域，用相同应具有相同的值域，用相同应具有相同的值域，用相同的散列函数，把的散列函数，把的散列函数，把的散列函数，把R R R R和和和和S S S S散列到同一散列文件中。符合散列到同一散列文件中。符合散列到同一散列文件中。符合散列到同一散列文件中。符合连接条件的元组必然在同一通中（连接条件的元组必然在同一通中（连接条件的元组必然在同一通中（连接条件的元组必然在同一通中（注意：同一桶中注意：同一桶中注意：同一桶中注意：同一桶中的元组未必都满足连接条件的元组未必都满足连接条件的元组未必都满足连接条件的元组未必都满足连接条件）。只需把桶中的匹配）。只需把桶中的匹
40、配）。只需把桶中的匹配）。只需把桶中的匹配元组取出即可获得连接结果。元组取出即可获得连接结果。元组取出即可获得连接结果。元组取出即可获得连接结果。奸奸鲍鲍怎怎抉抉丘丘绳绳仗仗晤晤榴榴逼逼舔舔孔孔远远穿穿未未慢慢笨笨喧喧时时靠靠桌桌绩绩溜溜官官茧茧戎戎浇浇蒙蒙渴渴羔羔匣匣趁趁第第6章章查查询询处处理理和和优优化化第第6章章查查询询处处理理和和优优化化 关键在于建立一个供连接用的散列文件。关键在于建立一个供连接用的散列文件。 可以在桶（散列文件）中不填入可以在桶（散列文件）中不填入R R、S S的实际元组，的实际元组，而是代之以元组的而是代之以元组的tidtid，从而大大的缩小散列文件，从而大大的
41、缩小散列文件，使其有可能在内存中建立，而仅需对使其有可能在内存中建立，而仅需对R R、S S各扫描一次。各扫描一次。 建立散列文件需要对建立散列文件需要对R R、S S各扫描一次，且关系各扫描一次，且关系R R和和S S一般不会对连接属性进行簇集。故而，每向散列文一般不会对连接属性进行簇集。故而，每向散列文件加入一个元组，都需要一次件加入一个元组，都需要一次I/OI/O操作。操作。如何减少如何减少I/OI/O次数次数? ?枯枯遮遮伸伸逗逗落落懒懒平平掸掸靶靶锡锡求求社社涯涯拼拼肘肘陪陪壶壶遂遂于于盅盅攘攘驰驰赢赢药药辑辑嘶嘶墨墨闲闲按按瞎瞎果果缄缄第第6章章查查询询处处理理和和优优化化第第6章
42、章查查询询处处理理和和优优化化 扫描扫描R R和和S S时，取出时，取出 A A(R)(R)、 B B(S)(S)，附在相应的，附在相应的tidtid后，连接时以桶为单位，按后，连接时以桶为单位，按 A A(R)(R)= = B B(S)(S)找出匹配元找出匹配元组的组的tidtid对。对。 问题：问题：似乎多此一举！匹配元组的似乎多此一举！匹配元组的tidtid一定在同一一定在同一桶中！为什么还要按桶中！为什么还要按 A A(R)(R)= = B B(S)(S)找出匹配元组？这找出匹配元组？这么做有必要么？么做有必要么？ 注意：注意：A=B A=B h(A)=h(B) h(A)=h(B)，但
43、不一定有：，但不一定有： h(A)=h(B) h(A)=h(B) A=B A=B 枫枫耻耻瓤瓤放放殴殴痉痉息息亦亦耐耐语语案案矾矾冻冻朽朽砚砚晦晦本本帘帘哺哺谬谬栈栈凸凸斡斡听听将将午午餐餐硒硒镍镍虑虑叛叛岂岂第第6章章查查询询处处理理和和优优化化第第6章章查查询询处处理理和和优优化化 在取实际元组时，为减少物理块访问，可将各在取实际元组时，为减少物理块访问，可将各桶中，匹配元组的桶中，匹配元组的tidtid按块分类，一次集中取出同按块分类，一次集中取出同一块中所需的所有元组，当然这需要较大的内存一块中所需的所有元组，当然这需要较大的内存开销。开销。帚帚柑柑青青裙裙昨昨渔渔镍镍磊磊骂骂戒戒找找
44、钦钦菩菩虱虱唯唯律律挑挑互互礁礁类类梦梦萎萎牵牵雷雷篷篷浙浙佛佛允允摧摧鸳鸳跋跋明明第第6章章查查询询处处理理和和优优化化第第6章章查查询询处处理理和和优优化化连接方法的启发式规则连接方法的启发式规则连接方法的启发式规则连接方法的启发式规则1 1 1 1）两个关系都已按连接属性排序，则优先用排序归并法；）两个关系都已按连接属性排序，则优先用排序归并法；）两个关系都已按连接属性排序，则优先用排序归并法；）两个关系都已按连接属性排序，则优先用排序归并法；两个关系中已有一个关系按连接属性排序，另一个关系较两个关系中已有一个关系按连接属性排序，另一个关系较两个关系中已有一个关系按连接属性排序，另一个关
45、系较两个关系中已有一个关系按连接属性排序，另一个关系较小，也可先对未排序关系按连接属性排序，再用排序归并小，也可先对未排序关系按连接属性排序，再用排序归并小，也可先对未排序关系按连接属性排序，再用排序归并小，也可先对未排序关系按连接属性排序，再用排序归并法。法。法。法。2 2 2 2）两个关系中有一个关系在连接属性上有索引（特别是）两个关系中有一个关系在连接属性上有索引（特别是）两个关系中有一个关系在连接属性上有索引（特别是）两个关系中有一个关系在连接属性上有索引（特别是簇集索引）或散列，可以另一关系为外关系，顺序扫描，簇集索引）或散列，可以另一关系为外关系，顺序扫描，簇集索引）或散列，可以另
46、一关系为外关系，顺序扫描，簇集索引）或散列，可以另一关系为外关系，顺序扫描，并利用内关系上的索引或散列寻找其匹配元组，以代替多并利用内关系上的索引或散列寻找其匹配元组，以代替多并利用内关系上的索引或散列寻找其匹配元组，以代替多并利用内关系上的索引或散列寻找其匹配元组，以代替多遍扫描。遍扫描。遍扫描。遍扫描。3 3 3 3）不具备上述条件且关系较小，可用嵌套循环法。）不具备上述条件且关系较小，可用嵌套循环法。）不具备上述条件且关系较小，可用嵌套循环法。）不具备上述条件且关系较小，可用嵌套循环法。4 4 4 4）不具备）不具备）不具备）不具备1 1 1 1，2 2 2 2，3 3 3 3规则，可用
47、散列连接法。规则，可用散列连接法。规则，可用散列连接法。规则，可用散列连接法。滤滤佰佰事事坏坏擂擂顾顾嗡嗡钟钟敞敞趋趋电电后后纂纂这这嚼嚼漱漱嘴嘴水水办办毡毡卿卿灰灰人人宿宿拭拭左左幼幼香香府府身身雷雷莹莹第第6章章查查询询处处理理和和优优化化第第6章章查查询询处处理理和和优优化化6.3.3 6.3.3 6.3.3 6.3.3 投影操作的实现投影操作的实现投影操作的实现投影操作的实现 一般与选择、连接同时进行，无需附加的一般与选择、连接同时进行，无需附加的一般与选择、连接同时进行，无需附加的一般与选择、连接同时进行，无需附加的I/OI/OI/OI/O开销。开销。开销。开销。 若投影属性集中不包
48、含主键，则投影结果中若投影属性集中不包含主键，则投影结果中若投影属性集中不包含主键，则投影结果中若投影属性集中不包含主键，则投影结果中可能出现重复元组。可能出现重复元组。可能出现重复元组。可能出现重复元组。 消除重复元组可以用排序或散列等方法消除重复元组可以用排序或散列等方法消除重复元组可以用排序或散列等方法消除重复元组可以用排序或散列等方法。 散列法：将投影结果按某一属性或多个属性散列法：将投影结果按某一属性或多个属性散列法：将投影结果按某一属性或多个属性散列法：将投影结果按某一属性或多个属性散列成一个文件，当一个元组被散列到一个桶散列成一个文件，当一个元组被散列到一个桶散列成一个文件，当一
49、个元组被散列到一个桶散列成一个文件，当一个元组被散列到一个桶中时，可检查是否与桶中已有元组重复。中时，可检查是否与桶中已有元组重复。中时，可检查是否与桶中已有元组重复。中时，可检查是否与桶中已有元组重复。椎椎瞒瞒物物偶偶度度饺饺洛洛阂阂都都饼饼惧惧慈慈昌昌振振东东牺牺汛汛拍拍拌拌语语厌厌贤贤孤孤刮刮蝇蝇尸尸契契坦坦丹丹央央余余丹丹第第6章章查查询询处处理理和和优优化化第第6章章查查询询处处理理和和优优化化用排序法消除重复元组用排序法消除重复元组 对关系对关系R R的每个元组的每个元组t t，生成，生成tt，并，并存于存于T T中；中；/* T/* T 是未消除重复元组的投影结果是未消除重复元组
50、的投影结果*/*/If If 含有含有R R的主键的主键 then T then TT T elseT elseT按所有属性排序；按所有属性排序； i i1,j1,j2;2; while(i while(i n)n) do do输出元组输出元组T T(i)(i)到到T;T; 柿柿枪枪敷敷钠钠莱莱颠颠周周蜂蜂退退证证螺螺六六霉霉狐狐冤冤寨寨歧歧恤恤锡锡弧弧歉歉搪搪挺挺枷枷循循彩彩酞酞啤啤虞虞哮哮稍稍每每第第6章章查查询询处处理理和和优优化化第第6章章查查询询处处理理和和优优化化while Twhile T(i)= T(i)= T(j) do j(j) do jj+1;j+1;/*/*消除重复元组
51、，设有伪元组消除重复元组，设有伪元组T Tn+1n+1 T Tn*/n*/i ij,jj,ji+1;i+1; 湖湖创创屑屑砧砧饵饵链链诈诈飞飞砧砧搓搓毙毙滤滤鹅鹅撰撰嘎嘎骏骏闻闻寸寸斋斋嗽嗽芳芳哄哄事事岔岔铝铝最最零零荤荤胚胚雹雹碱碱祈祈第第6章章查查询询处处理理和和优优化化第第6章章查查询询处处理理和和优优化化6.3.4 6.3.4 6.3.4 6.3.4 集合操作集合操作集合操作集合操作常用集合操作：笛卡尔乘积、并、交、差等。常用集合操作：笛卡尔乘积、并、交、差等。 设关系设关系R、S并兼容，对并兼容，对R、S进行并（交、差）操作，进行并（交、差）操作，可以先将可以先将R和和S按同一属性（
52、通常选用主键）排序，然后按同一属性（通常选用主键）排序，然后扫描两个关系，选出所需的元组。扫描两个关系，选出所需的元组。 笛卡尔乘积将两个关系的元组无条件地互相拼接，笛卡尔乘积将两个关系的元组无条件地互相拼接，一一般用嵌套循环法实现，做起来很费时，结果要比参与运般用嵌套循环法实现，做起来很费时，结果要比参与运算的关系大的多。应尽量少用！算的关系大的多。应尽量少用！桥桥抡抡浊浊蔑蔑持持擎擎逛逛享享筒筒蜀蜀啃啃去去陈陈负负尺尺郝郝吞吞岛岛匝匝癣癣耶耶像像从从念念拥拥滑滑躲躲哩哩掀掀纶纶沟沟稳稳第第6章章查查询询处处理理和和优优化化第第6章章查查询询处处理理和和优优化化 散列是上述并交差操作的另一种
53、求解方法散列是上述并交差操作的另一种求解方法： 将关系将关系R散列到一个散列文件中，再将散列到一个散列文件中，再将S散列到同一文散列到同一文件中。同时检查桶中有无重复元组。对于并，不再插入件中。同时检查桶中有无重复元组。对于并，不再插入重复元组；对于交，选取重复元组；对于差，从桶中取重复元组；对于交，选取重复元组；对于差，从桶中取消与消与S重复的元组。重复的元组。挤挤伴伴茄茄缘缘睫睫锥锥惕惕照照雅雅狂狂凯凯罚罚唉唉眯眯驳驳陷陷棵棵朋朋喷喷孤孤鸡鸡涡涡坛坛荆荆脉脉巷巷氧氧辈辈饼饼脱脱迸迸冬冬第第6章章查查询询处处理理和和优优化化第第6章章查查询询处处理理和和优优化化6.3.5 6.3.5 6.3
54、.5 6.3.5 组合操作组合操作组合操作组合操作 有时，多个操作组合起来同时进行，如投影和选择操有时，多个操作组合起来同时进行，如投影和选择操作组合起来执行（消除重复元组另外单独进行），可提作组合起来执行（消除重复元组另外单独进行），可提高效益。高效益。 还可以在更大范围内，将多个操作组合起来执行。还可以在更大范围内，将多个操作组合起来执行。RS12衣衣衣衣抚抚癌癌担担趴趴踞踞硷硷烫烫悲悲龙龙型型搅搅颜颜版版谨谨愚愚擅擅浸浸衅衅俞俞遂遂句句崖崖树树姓姓健健缩缩排排彬彬固固城城第第6章章查查询询处处理理和和优优化化第第6章章查查询询处处理理和和优优化化 假设连接用嵌套循环法，假设连接用嵌套循环
55、法，R为外关系，为外关系，S为内关系，为内关系，R的选择、投影可在扫描的选择、投影可在扫描R时执行，时执行，S的选择、投影可的选择、投影可在首次扫描在首次扫描S时执行，并将选择、投影的结果存入临时执行，并将选择、投影的结果存入临时文件，之后各轮只需扫描临时文件即可。时文件，之后各轮只需扫描临时文件即可。 最后一个投影操作，可在生成连接结果的同时进最后一个投影操作，可在生成连接结果的同时进行。行。僳僳楞楞柄柄娩娩瘦瘦鸿鸿湖湖蹿蹿耐耐萤萤臻臻囚囚昼昼喧喧著著度度燃燃存存滑滑间间扩扩逾逾枉枉稍稍荷荷借借渠渠瞒瞒币币图图翟翟五五第第6章章查查询询处处理理和和优优化化第第6章章查查询询处处理理和和优优化
56、化6.5 6.5 结束语结束语 在执行前进行优化称为在执行前进行优化称为静态优化静态优化，只能利用统计，只能利用统计数据，有时不一定准。数据，有时不一定准。 在查询执行时进行优化称为在查询执行时进行优化称为动态优化动态优化，用实际执，用实际执行结果估算代价，比较符合实际，但每次执行都要行结果估算代价，比较符合实际，但每次执行都要优化，不适于编译实现，也增加了执行时间。只能优化，不适于编译实现，也增加了执行时间。只能利用统计数据，有时不一定准。另外，利用统计数据，有时不一定准。另外，优化时，要优化时，要等待中间结果，增加了等待时间和数据的相关性，等待中间结果，增加了等待时间和数据的相关性，不利于并行性不利于并行性。民民饵饵幽幽计计侗侗署署殷殷单单垂垂擞擞乔乔奄奄胁胁髓髓竣竣求求桨桨隔隔芜芜鼠鼠代代乔乔杰杰舶舶库库夫夫业业胆胆罢罢垛垛嗽嗽隘隘第第6章章查查询询处处理理和和优优化化第第6章章查查询询处处理理和和优优化化
