查詢樹的優(yōu)化[優(yōu)質(zhì)分析]

《查詢樹的優(yōu)化[優(yōu)質(zhì)分析]》由會員分享，可在線閱讀，更多相關(guān)《查詢樹的優(yōu)化[優(yōu)質(zhì)分析]（46頁珍藏版）》請?jiān)谘b配圖網(wǎng)上搜索。

1、第四章第四章 查詢優(yōu)化查詢優(yōu)化1嚴(yán)選文書4.1 關(guān)系數(shù)據(jù)庫系統(tǒng)的查詢處理n查詢處理步驟Select student.name from student,scWhere student.sno=sc.sno and o=2;例：選修了例：選修了2號課程的學(xué)生姓名號課程的學(xué)生姓名2嚴(yán)選文書4.1 關(guān)系數(shù)據(jù)庫系統(tǒng)的查詢處理Select student.name from student,scWhere student.sno=sc.sno and o=2;1.查詢分析：識別其中的關(guān)鍵字，屬性名，表名。2.查詢檢查：屬性名是否有效，表名是否有效等。3.查詢優(yōu)化：例如上例中先執(zhí)行連接還是先執(zhí)行 o=2從

2、sc表中進(jìn)行選擇。選用何 種方法進(jìn)行連接。4.查詢執(zhí)行。3嚴(yán)選文書4.1 關(guān)系數(shù)據(jù)庫系統(tǒng)的查詢處理n查詢處理步驟 查詢分析：對查詢語句進(jìn)行掃描、詞法分析和語法分析。 查詢檢查：語義檢查 查詢優(yōu)化：代數(shù)優(yōu)化和物理優(yōu)化 查詢執(zhí)行4嚴(yán)選文書4.1 關(guān)系數(shù)據(jù)庫系統(tǒng)的查詢處理n為什么進(jìn)行代數(shù)優(yōu)化？例：選修了例：選修了2號課程的學(xué)生姓名號課程的學(xué)生姓名snamesname( o=o=2 2 （ SC Student）snamesname( student.sno=sc.sno o=o=2 2 （ SC Student）snamesname( o=o=2 2( (SC) ) Student）5嚴(yán)選文書4.1

3、 關(guān)系數(shù)據(jù)庫系統(tǒng)的查詢處理snamesname( student.sno=sc.sno o=o=2 2 （ SC Student）假設(shè)有假設(shè)有1000個學(xué)生記錄，個學(xué)生記錄，10000個選課記錄，個選課記錄，2號課程的選課記錄為號課程的選課記錄為500個。個。1. 笛卡爾積計算：笛卡爾積計算：1000*10000 2. 選擇：掃描選擇：掃描1000*10000個記錄個記錄3. 投影投影6嚴(yán)選文書4.1 關(guān)系數(shù)據(jù)庫系統(tǒng)的查詢處理假設(shè)有假設(shè)有1000個學(xué)生記錄，個學(xué)生記錄，10000個選課記錄，個選課記錄，2號課程的選課記錄為號課程的選課記錄為500個。個。1. 連接，采用嵌套循環(huán)：連接，采用嵌套

4、循環(huán)：10000*1000 ，得到，得到10000個結(jié)果個結(jié)果2. 選擇：掃描選擇：掃描10000個記錄個記錄3. 投影投影snamesname( o=o=2 2 （ SC Student）7嚴(yán)選文書4.1 關(guān)系數(shù)據(jù)庫系統(tǒng)的查詢處理假設(shè)有假設(shè)有1000個學(xué)生記錄，個學(xué)生記錄，10000個選課記錄，個選課記錄，2號課程的選課記錄為號課程的選課記錄為500個。個。1. 選擇：掃描選擇：掃描10000個記錄個記錄 ，得到，得到500個記錄個記錄2. 連接，采用嵌套循環(huán)：連接，采用嵌套循環(huán)：500*1000次，得到次，得到500個記錄個記錄3. 投影投影snamesname( o=o=2 2( (SC

5、) ) Student）F 選擇操作先做可以提高效率。選擇操作先做可以提高效率。8嚴(yán)選文書4.2 代數(shù)優(yōu)化4.2.1 關(guān)系代數(shù)表達(dá)式等價變換規(guī)則關(guān)系代數(shù)表達(dá)式等價變換規(guī)則F 等價的概念：n若關(guān)系表達(dá)式f（E1，E2，En）的結(jié)果與關(guān)系表達(dá)式g（E1，E2，En）的結(jié)果是同一個關(guān)系，那么稱這兩個表達(dá)式等價。n若關(guān)系表達(dá)式E1和E2是等價的可以記為：12EE9嚴(yán)選文書等價變換規(guī)則1. 連接、笛卡兒積交換率連接、笛卡兒積交換率 設(shè)設(shè)E1和和E2是關(guān)系代數(shù)表達(dá)式，是關(guān)系代數(shù)表達(dá)式，F(xiàn)是連接運(yùn)算的是連接運(yùn)算的條件，則有：條件，則有：1221EEEE1221EEEE1221FFEEEE10嚴(yán)選文書等價變換

6、規(guī)則1. 連接、笛卡兒積的結(jié)合率連接、笛卡兒積的結(jié)合率 設(shè)設(shè)E1，E2，E3是關(guān)系代數(shù)表達(dá)式，是關(guān)系代數(shù)表達(dá)式，F(xiàn)1和和F2是是連接運(yùn)算的條件，則有：連接運(yùn)算的條件，則有：123123()()EEEEEE123123()()EEEEEE1212123123()()FFFFEEEEEE11嚴(yán)選文書等價變換規(guī)則2. 連接、笛卡兒積的結(jié)合率連接、笛卡兒積的結(jié)合率 設(shè)設(shè)E1，E2，E3是關(guān)系代數(shù)表達(dá)式，是關(guān)系代數(shù)表達(dá)式，F(xiàn)1和和F2是是連接運(yùn)算的條件，則有：連接運(yùn)算的條件，則有：Student(SCCourse)StudentSCCourseSC(StudentCourse)StudentSCCour

7、se12嚴(yán)選文書3. 投影的串接定律121212,( ) )( )nmnA AAB BBA AAEE 這里，這里，E是關(guān)系代數(shù)表達(dá)式，是關(guān)系代數(shù)表達(dá)式，Ai（i=1，2，n），），Bj（j=1，2，m）是屬性）是屬性名且名且A1，A2， An 是是B1，B2，Bm 的子集。的子集。等價變換規(guī)則,( )( )SnameSname SageSnameSS13嚴(yán)選文書4. 選擇的串接定律等價變換規(guī)則1919( )( )SdeptISSageSdeptISSageSS求IS系年齡大于歲的學(xué)生：14嚴(yán)選文書4. 選擇的串接定律1212( ) )( )FFFFEEE是關(guān)系代數(shù)表達(dá)式，是關(guān)系代數(shù)表達(dá)式，F(xiàn)1

8、和和F2是選是選擇條件。選擇的串接定律說明選擇條件擇條件。選擇的串接定律說明選擇條件可以合并，這樣一次就可以檢查全部的可以合并，這樣一次就可以檢查全部的條件。條件。等價變換規(guī)則15嚴(yán)選文書等價變換規(guī)則19,19( )( )SageSname SageSname SageSageSS1919,( )( )SnameSageSnameSageSname SageSS16嚴(yán)選文書5. 選擇與投影的交換律 此時，條件此時，條件F只涉及屬性組只涉及屬性組A。若條件中有不屬。若條件中有不屬于于A的屬性組的屬性組B，那么有更一般的規(guī)則：，那么有更一般的規(guī)則：1212,( ) )( ) )nnFA AAA A

9、AFEE12121212,( ) )( ) ) )nnnmA AAFA AAFA AA B BBEE等價變換規(guī)則17嚴(yán)選文書6.選擇與笛卡爾積的交換122112121212()1()()()23()FFFFFFEEEEEEEE（ ）（ ）（ ）（1）F只涉及只涉及E1的屬性。的屬性。（2）F=F1F2，且，且F1只涉及只涉及E1的屬性，的屬性，F(xiàn)2只涉及只涉及E2的屬性。的屬性。（3） F=F1F2，且，且F1只涉及只涉及E1的屬性，而的屬性，而F2涉及涉及E1和和E2的屬性。的屬性。18嚴(yán)選文書11()()cnocnoSSCSCS(1) 實(shí)例：選修實(shí)例：選修1號課程的學(xué)生信息號課程的學(xué)生信息

10、等價變換規(guī)則11()()()cnosdeptIScnosdeptISSSCSCS(2) 實(shí)例：信息系選修實(shí)例：信息系選修1號課程的學(xué)生信息號課程的學(xué)生信息19嚴(yán)選文書7. 選擇與并的分配率設(shè)設(shè)E=E1E2，E1和和E2有相同的屬性名，則：有相同的屬性名，則：1212()()()FFFEEEE注：先做選擇可以減少讀取寫入的數(shù)據(jù)，因此減少磁盤注：先做選擇可以減少讀取寫入的數(shù)據(jù)，因此減少磁盤IO量，從而提高了效率。量，從而提高了效率。等價變換規(guī)則20嚴(yán)選文書設(shè)設(shè)S1是計科是計科041的學(xué)生關(guān)系表，的學(xué)生關(guān)系表，S2是計科是計科042的學(xué)生關(guān)系表：的學(xué)生關(guān)系表：1912191192()()()Sage

11、SageSageSSSS等價變換規(guī)則21嚴(yán)選文書8. 選擇與差運(yùn)算的分配率設(shè)設(shè)E1和和E2有相同的屬性名，則：有相同的屬性名，則：1212()()()FFFEEEE注：先做選擇可以減少讀取寫入的數(shù)據(jù)，因此減少磁盤注：先做選擇可以減少讀取寫入的數(shù)據(jù)，因此減少磁盤IO量，從而提高了效率。量，從而提高了效率。等價變換規(guī)則22嚴(yán)選文書設(shè)設(shè)S1是計科是計科041的學(xué)生關(guān)系表，的學(xué)生關(guān)系表，S3是計科專業(yè)的學(xué)生關(guān)系表：是計科專業(yè)的學(xué)生關(guān)系表：1931193191()()()SageSageSageSSSS等價變換規(guī)則23嚴(yán)選文書9. 選擇對自然連接的分配率F只涉及只涉及E1和和E2的公共屬性。的公共屬性。

12、1212()()()FFFEEEE注：先做選擇可以減少做笛卡兒積的數(shù)據(jù)，結(jié)果關(guān)系的數(shù)注：先做選擇可以減少做笛卡兒積的數(shù)據(jù)，結(jié)果關(guān)系的數(shù)據(jù)量也同步減少，因此減少磁盤據(jù)量也同步減少，因此減少磁盤IO量，提高了效率。量，提高了效率。等價變換規(guī)則24嚴(yán)選文書等價變換規(guī)則25嚴(yán)選文書10. 投影與笛卡爾積的分配律 設(shè)設(shè)E1和和E2是兩個關(guān)系表達(dá)式，是兩個關(guān)系表達(dá)式，A是是E1的屬性組，的屬性組，B是是E2的屬性組。則：的屬性組。則：12121212,12,1,2()()()nmnmA AA B BBA AAB BBEEEE注：先做投影可以減少讀取寫入的數(shù)據(jù)，因此減少磁盤注：先做投影可以減少讀取寫入的數(shù)據(jù)

13、，因此減少磁盤IO量，從而提高了效率。量，從而提高了效率。等價變換規(guī)則26嚴(yán)選文書,()( )( )Sname CnameSnameCnameSCSC查找所有學(xué)生可能的選課對：等價變換規(guī)則27嚴(yán)選文書11. 投影與并的分配律設(shè)設(shè)E1和和E2有相同的屬性名，則：有相同的屬性名，則：121212,12,1,2()()()nnnA AAA AAA AAEEEE注：先做投影可以減少讀取寫入的數(shù)據(jù)，因此減少磁盤注：先做投影可以減少讀取寫入的數(shù)據(jù)，因此減少磁盤IO量，從而提高了效率。量，從而提高了效率。等價變換規(guī)則28嚴(yán)選文書設(shè)設(shè)S1是計科是計科041的學(xué)生關(guān)系表，的學(xué)生關(guān)系表，S2是計科是計科042的學(xué)

14、生關(guān)系表：的學(xué)生關(guān)系表：1212()()()SnameSnameSnameSSSS查找計科查找計科041、042的學(xué)生姓名：的學(xué)生姓名：等價變換規(guī)則29嚴(yán)選文書優(yōu)化規(guī)則：n選擇運(yùn)算盡可能先做。選擇運(yùn)算盡可能先做。n投影運(yùn)算和選擇運(yùn)算同時進(jìn)行。投影運(yùn)算和選擇運(yùn)算同時進(jìn)行。n把投影運(yùn)算同其前后的把投影運(yùn)算同其前后的 雙目運(yùn)算結(jié)合執(zhí)行。雙目運(yùn)算結(jié)合執(zhí)行。n選擇運(yùn)算和笛卡兒積運(yùn)算結(jié)合成連接運(yùn)算。選擇運(yùn)算和笛卡兒積運(yùn)算結(jié)合成連接運(yùn)算。n找出公共子表達(dá)式，避免重復(fù)運(yùn)算。找出公共子表達(dá)式，避免重復(fù)運(yùn)算。30嚴(yán)選文書4.2.2 4.2.2 查詢樹的優(yōu)化查詢樹的優(yōu)化4.2 代數(shù)優(yōu)化1.1.查詢樹查詢樹5()Sn

15、ameCpnoCSCSSname5CpnoSCSC31嚴(yán)選文書4.2.2 優(yōu)化算法1.1.利用規(guī)則利用規(guī)則4 4分解選擇運(yùn)算。分解選擇運(yùn)算。2.2.利用規(guī)則利用規(guī)則4949把選擇運(yùn)算盡量移到葉端。把選擇運(yùn)算盡量移到葉端。3.3.利用規(guī)則利用規(guī)則3 3，5 5，1010，1111把投影運(yùn)算盡量移到葉端。把投影運(yùn)算盡量移到葉端。4.4.利用規(guī)則利用規(guī)則3535把選擇和投影的串接合并成單個選把選擇和投影的串接合并成單個選擇、單個投影或一個選擇后跟一個投影的形式。使擇、單個投影或一個選擇后跟一個投影的形式。使盡可能多的選擇和投影同時執(zhí)行。盡可能多的選擇和投影同時執(zhí)行。5.5.分組。雙目運(yùn)算和他的直系祖

16、先為一組；雙目運(yùn)分組。雙目運(yùn)算和他的直系祖先為一組；雙目運(yùn)算后代直道葉子全是單目運(yùn)算時并入改組。笛卡兒算后代直道葉子全是單目運(yùn)算時并入改組。笛卡兒積的后面若不是與之可以合并的自然連接的等值選積的后面若不是與之可以合并的自然連接的等值選擇時，其后代單獨(dú)分為一組。擇時，其后代單獨(dú)分為一組。32嚴(yán)選文書優(yōu)化實(shí)例例：查詢至少選修了一門先行課號為例：查詢至少選修了一門先行課號為5號課程的號課程的學(xué)生姓名。其中，學(xué)生姓名。其中，C是課程表，是課程表，S是學(xué)生表，是學(xué)生表，SC是學(xué)生選課表。是學(xué)生選課表。5()SnameCpnoCSCS在優(yōu)化規(guī)則中沒有對自然連接的直接優(yōu)化，在優(yōu)化規(guī)則中沒有對自然連接的直接優(yōu)

17、化，我們把自然連接分解為笛卡兒積和選擇。我們把自然連接分解為笛卡兒積和選擇。33嚴(yán)選文書分解后的關(guān)系代數(shù)表達(dá)式5.()SnameCpnoC Cno SC Cno SC Sno S SnoCSCSSname5.CpnoC Cno SC Cno SC Sno S SnoSCSC34嚴(yán)選文書第一步：利用規(guī)則第一步：利用規(guī)則4分解選擇運(yùn)算分解選擇運(yùn)算Sname.SC Sno S SnoSCSC5Cpno.C Cno SC Cno1212( )( )FFFFEE1212( )( )FFFFEE35嚴(yán)選文書第二步：盡量下放選擇運(yùn)算第二步：盡量下放選擇運(yùn)算Sname.SC Sno S SnoSCSC5Cpn

18、o.C Cno SC Cno1212()()FFEEEE36嚴(yán)選文書Sname.SC Sno S SnoSCSC5Cpno.C Cno SC Cno第二步（第二步（2）：下放完成后：）：下放完成后：37嚴(yán)選文書第三步：盡量下放投影運(yùn)算第三步：盡量下放投影運(yùn)算Sname.SC Sno S SnoSCSC5Cpno.C Cno SC Cno., .,( )( )SnameSC Sno S SnoSnameSC Sno S SnoSC Sno S Sno SnameEEE38嚴(yán)選文書第三步：盡量下放投影運(yùn)算第三步：盡量下放投影運(yùn)算Sname.SC Sno S SnoSCSC5Cpno.C Cno S

19、C Cno., .,SC Sno S Sno Sname12121212,12,1,2()()()nmnmA AA B BBA AAB BBEEEE39嚴(yán)選文書第三步（第三步（2）：第一次下放后：）：第一次下放后：.SC Sno S SnoSCSC5Cpno.C Cno SC CnoSname., .S Sname S Sno.SC Sno40嚴(yán)選文書第三步（第三步（3）：第二次下放：）：第二次下放：.SC Sno S SnoSCSC5Cpno.C Cno SC CnoSname.SC Sno.,.,.( )( )SC SnoC Cno SC CnoSC SnoC Cno SC CnoC Cn

20、o SC Sno SC CnoEE., .S Sname S Sno41嚴(yán)選文書第三步（第三步（3）：第二次下放：）：第二次下放：.SC Sno S SnoSCSC5Cpno.C Cno SC CnoSname.SC Sno., .S Sname S Sno.,.,.C Cno SC Sno SC Cno12121212,12,1,2()()()nmnmA AA B BBA AAB BBEEEE42嚴(yán)選文書第三步（第三步（4）：第二次下放后：）：第二次下放后：.SC Sno S SnoSCSC5Cpno.C Cno SC CnoSname.SC Sno.,.SC Sno SC Cno.C Cn

21、o., .S Sname S Sno43嚴(yán)選文書.SC Sno S SnoSCSC5Cpno.C Cno SC CnoSname.SC Sno.,.SC Sno SC Cno.C Cno第四步：盡量把選擇和投影靠在一起第四步：盡量把選擇和投影靠在一起., .S Sname S Sno44嚴(yán)選文書第五步：分組第五步：分組.SC Sno S SnoSCSC5Cpno.C Cno SC CnoSname.SC Sno.,.SC Sno SC Cno.C Cno., .S Sname S Sno45嚴(yán)選文書作業(yè)：nP275第第2題。題。即優(yōu)化表達(dá)式：即優(yōu)化表達(dá)式：()CnameSdeptISSSCC46嚴(yán)選文書