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

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

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

2、sc表中進(jìn)行選擇。選用何 種方法進(jìn)行連接。4.查詢執(zhí)行。3嚴(yán)選文書(shū)4.1 關(guān)系數(shù)據(jù)庫(kù)系統(tǒng)的查詢處理n查詢處理步驟 查詢分析：對(duì)查詢語(yǔ)句進(jìn)行掃描、詞法分析和語(yǔ)法分析。 查詢檢查：語(yǔ)義檢查 查詢優(yōu)化：代數(shù)優(yōu)化和物理優(yōu)化 查詢執(zhí)行4嚴(yán)選文書(shū)4.1 關(guān)系數(shù)據(jù)庫(kù)系統(tǒng)的查詢處理n為什么進(jìn)行代數(shù)優(yōu)化？例：選修了例：選修了2號(hào)課程的學(xué)生姓名號(hào)課程的學(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)選文書(shū)4.1

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

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

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

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)選文書(shū)等價(jià)變換規(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)選文書(shū)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 的子集。的子集。等價(jià)變換規(guī)則,( )( )SnameSname SageSnameSS13嚴(yán)選文書(shū)4. 選擇的串接定律等價(jià)變換規(guī)則1919( )( )SdeptISSageSdeptISSageSS求IS系年齡大于歲的學(xué)生：14嚴(yán)選文書(shū)4. 選擇的串接定律1212( ) )( )FFFFEEE是關(guān)系代數(shù)表達(dá)式，是關(guān)系代數(shù)表達(dá)式，F(xiàn)1

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

9、AFEE12121212,( ) )( ) ) )nnnmA AAFA AAFA AA B BBEE等價(jià)變換規(guī)則17嚴(yán)選文書(shū)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)選文書(shū)11()()cnocnoSSCSCS(1) 實(shí)例：選修實(shí)例：選修1號(hào)課程的學(xué)生信息號(hào)課程的學(xué)生信息

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

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

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

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

14、生關(guān)系表：的學(xué)生關(guān)系表：1212()()()SnameSnameSnameSSSS查找計(jì)科查找計(jì)科041、042的學(xué)生姓名：的學(xué)生姓名：等價(jià)變換規(guī)則29嚴(yán)選文書(shū)優(yōu)化規(guī)則：n選擇運(yùn)算盡可能先做。選擇運(yùn)算盡可能先做。n投影運(yùn)算和選擇運(yùn)算同時(shí)進(jìn)行。投影運(yùn)算和選擇運(yùn)算同時(shí)進(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)選文書(shū)4.2.2 4.2.2 查詢樹(shù)的優(yōu)化查詢樹(shù)的優(yōu)化4.2 代數(shù)優(yōu)化1.1.查詢樹(shù)查詢樹(shù)5()Sn

15、ameCpnoCSCSSname5CpnoSCSC31嚴(yán)選文書(shū)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把選擇和投影的串接合并成單個(gè)選把選擇和投影的串接合并成單個(gè)選擇、單個(gè)投影或一個(gè)選擇后跟一個(gè)投影的形式。使擇、單個(gè)投影或一個(gè)選擇后跟一個(gè)投影的形式。使盡可能多的選擇和投影同時(shí)執(zhí)行。盡可能多的選擇和投影同時(shí)執(zhí)行。5.5.分組。雙目運(yùn)算和他的直系祖

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

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

18、o.C Cno SC Cno1212()()FFEEEE36嚴(yán)選文書(shū)Sname.SC Sno S SnoSCSC5Cpno.C Cno SC Cno第二步（第二步（2）：下放完成后：）：下放完成后：37嚴(yán)選文書(shū)第三步：盡量下放投影運(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)選文書(shū)第三步：盡量下放投影運(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)選文書(shū)第三步（第三步（2）：第一次下放后：）：第一次下放后：.SC Sno S SnoSCSC5Cpno.C Cno SC CnoSname., .S Sname S Sno.SC Sno40嚴(yán)選文書(shū)第三步（第三步（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)選文書(shū)第三步（第三步（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)選文書(shū)第三步（第三步（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)選文書(shū).SC Sno S SnoSCSC5Cpno.C Cno SC CnoSname.SC Sno.,.SC Sno SC Cno.C Cno第四步：盡量把選擇和投影靠在一起第四步：盡量把選擇和投影靠在一起., .S Sname S Sno44嚴(yán)選文書(shū)第五步：分組第五步：分組.SC Sno S SnoSCSC5Cpno.C Cno SC CnoSname.SC Sno.,.SC Sno SC Cno.C Cno., .S Sname S Sno45嚴(yán)選文書(shū)作業(yè)：nP275第第2題。題。即優(yōu)化表達(dá)式：即優(yōu)化表達(dá)式：()CnameSdeptISSSCC46嚴(yán)選文書(shū)