查詢樹的優(yōu)化

會(huì)計(jì)學(xué)1查詢樹的優(yōu)化4.1關(guān)系數(shù)據(jù)庫系統(tǒng)的查詢處理查詢處理步驟Sfromstudent,scWherestudent.sno=o=2;例：選修了2號課程的學(xué)生姓名第1頁/共46頁4.1關(guān)系數(shù)據(jù)庫系統(tǒng)的查詢處理Sfromstudent,scWherestudent.sno=o=2;1.查詢分析：識別其中的關(guān)鍵字，屬性名，表名。2.查詢檢查：屬性名是否有效，表名是否有效等。3.查詢優(yōu)化：例如上例中先執(zhí)行連接還是先執(zhí)行

o=2從sc表中進(jìn)行選擇。選用何種方法進(jìn)行連接。4.查詢執(zhí)行。第2頁/共46頁4.1關(guān)系數(shù)據(jù)庫系統(tǒng)的查詢處理查詢處理步驟查詢分析：對查詢語句進(jìn)行掃描、詞法分析和語法分析。查詢檢查：語義檢查查詢優(yōu)化：代數(shù)優(yōu)化和物理優(yōu)化查詢執(zhí)行第3頁/共46頁4.1關(guān)系數(shù)據(jù)庫系統(tǒng)的查詢處理為什么進(jìn)行代數(shù)優(yōu)化？例：選修了2號課程的學(xué)生姓名Πsname(o=‘2’

（SC

Student））Πsname(student.sno=sc.snoΛ

o=‘2’

（SCХStudent））Πsname(o=‘2’(SC)

Student））第4頁/共46頁4.1關(guān)系數(shù)據(jù)庫系統(tǒng)的查詢處理Πsname(student.sno=sc.snoΛ

o=‘2’

（SCХStudent））假設(shè)有1000個(gè)學(xué)生記錄，10000個(gè)選課記錄，2號課程的選課記錄為500個(gè)。1.笛卡爾積計(jì)算：1000*100002.選擇：掃描1000*10000個(gè)記錄3.投影第5頁/共46頁4.1關(guān)系數(shù)據(jù)庫系統(tǒng)的查詢處理假設(shè)有1000個(gè)學(xué)生記錄，10000個(gè)選課記錄，2號課程的選課記錄為500個(gè)。1.連接，采用嵌套循環(huán)：10000*1000，得到10000個(gè)結(jié)果2.選擇：掃描10000個(gè)記錄3.投影Πsname(o=‘2’

（SC

Student））第6頁/共46頁4.1關(guān)系數(shù)據(jù)庫系統(tǒng)的查詢處理假設(shè)有1000個(gè)學(xué)生記錄，10000個(gè)選課記錄，2號課程的選課記錄為500個(gè)。1.選擇：掃描10000個(gè)記錄，得到500個(gè)記錄2.連接，采用嵌套循環(huán)：500*1000次，得到500個(gè)記錄3.投影Πsname(o=‘2’(SC)

Student）

選擇操作先做可以提高效率。第7頁/共46頁4.2代數(shù)優(yōu)化4.2.1關(guān)系代數(shù)表達(dá)式等價(jià)變換規(guī)則

等價(jià)的概念：若關(guān)系表達(dá)式f（E1，E2，…，En）的結(jié)果與關(guān)系表達(dá)式g（E1，E2，…，En）的結(jié)果是同一個(gè)關(guān)系，那么稱這兩個(gè)表達(dá)式等價(jià)。若關(guān)系表達(dá)式E1和E2是等價(jià)的可以記為：第8頁/共46頁等價(jià)變換規(guī)則1.連接、笛卡兒積交換率設(shè)E1和E2是關(guān)系代數(shù)表達(dá)式，F(xiàn)是連接運(yùn)算的條件，則有：第9頁/共46頁等價(jià)變換規(guī)則1.連接、笛卡兒積的結(jié)合率設(shè)E1，E2，E3是關(guān)系代數(shù)表達(dá)式，F(xiàn)1和F2是連接運(yùn)算的條件，則有：第10頁/共46頁等價(jià)變換規(guī)則2.連接、笛卡兒積的結(jié)合率設(shè)E1，E2，E3是關(guān)系代數(shù)表達(dá)式，F(xiàn)1和F2是連接運(yùn)算的條件，則有：≡Student(SCCourse)StudentSCCourseSC(StudentCourse)≡StudentSCCourse第11頁/共46頁3.投影的串接定律

這里，E是關(guān)系代數(shù)表達(dá)式，Ai（i=1，2，…，n），Bj（j=1，2，…，m）是屬性名且{A1，A2，…An}是{B1，B2，…，Bm}的子集。等價(jià)變換規(guī)則第12頁/共46頁4.選擇的串接定律等價(jià)變換規(guī)則求IS系年齡大于１９歲的學(xué)生：第13頁/共46頁4.選擇的串接定律

E是關(guān)系代數(shù)表達(dá)式，F(xiàn)1和F2是選擇條件。選擇的串接定律說明選擇條件可以合并，這樣一次就可以檢查全部的條件。等價(jià)變換規(guī)則第14頁/共46頁等價(jià)變換規(guī)則第15頁/共46頁5.選擇與投影的交換律

此時(shí)，條件F只涉及屬性組A。若條件中有不屬于A的屬性組B，那么有更一般的規(guī)則：等價(jià)變換規(guī)則第16頁/共46頁6.選擇與笛卡爾積的交換（1）F只涉及E1的屬性。（2）F=F1∧F2，且F1只涉及E1的屬性，F(xiàn)2只涉及E2的屬性。（3）F=F1∧F2，且F1只涉及E1的屬性，而F2涉及E1和E2的屬性。第17頁/共46頁(1)實(shí)例：選修1號課程的學(xué)生信息等價(jià)變換規(guī)則(2)實(shí)例：信息系選修1號課程的學(xué)生信息第18頁/共46頁7.選擇與并的分配率設(shè)E=E1∪E2，E1和E2有相同的屬性名，則：注：先做選擇可以減少讀取寫入的數(shù)據(jù)，因此減少磁盤IO量，從而提高了效率。等價(jià)變換規(guī)則第19頁/共46頁設(shè)S1是計(jì)科041的學(xué)生關(guān)系表，S2是計(jì)科042的學(xué)生關(guān)系表：等價(jià)變換規(guī)則第20頁/共46頁8.選擇與差運(yùn)算的分配率設(shè)E1和E2有相同的屬性名，則：注：先做選擇可以減少讀取寫入的數(shù)據(jù)，因此減少磁盤IO量，從而提高了效率。等價(jià)變換規(guī)則第21頁/共46頁設(shè)S1是計(jì)科041的學(xué)生關(guān)系表，S3是計(jì)科專業(yè)的學(xué)生關(guān)系表：等價(jià)變換規(guī)則第22頁/共46頁9.選擇對自然連接的分配率F只涉及E1和E2的公共屬性。注：先做選擇可以減少做笛卡兒積的數(shù)據(jù)，結(jié)果關(guān)系的數(shù)據(jù)量也同步減少，因此減少磁盤IO量，提高了效率。等價(jià)變換規(guī)則第23頁/共46頁等價(jià)變換規(guī)則第24頁/共46頁10.投影與笛卡爾積的分配律

設(shè)E1和E2是兩個(gè)關(guān)系表達(dá)式，A是E1的屬性組，B是E2的屬性組。則：注：先做投影可以減少讀取寫入的數(shù)據(jù)，因此減少磁盤IO量，從而提高了效率。等價(jià)變換規(guī)則第25頁/共46頁查找所有學(xué)生可能的選課對：等價(jià)變換規(guī)則第26頁/共46頁11.投影與并的分配律設(shè)E1和E2有相同的屬性名，則：注：先做投影可以減少讀取寫入的數(shù)據(jù)，因此減少磁盤IO量，從而提高了效率。等價(jià)變換規(guī)則第27頁/共46頁設(shè)S1是計(jì)科041的學(xué)生關(guān)系表，S2是計(jì)科042的學(xué)生關(guān)系表：查找計(jì)科041、042的學(xué)生姓名：等價(jià)變換規(guī)則第28頁/共46頁優(yōu)化規(guī)則：選擇運(yùn)算盡可能先做。投影運(yùn)算和選擇運(yùn)算同時(shí)進(jìn)行。把投影運(yùn)算同其前后的雙目運(yùn)算結(jié)合執(zhí)行。選擇運(yùn)算和笛卡兒積運(yùn)算結(jié)合成連接運(yùn)算。找出公共子表達(dá)式，避免重復(fù)運(yùn)算。第29頁/共46頁4.2.2查詢樹的優(yōu)化4.2代數(shù)優(yōu)化1.查詢樹××SCSC第30頁/共46頁4.2.2優(yōu)化算法1.利用規(guī)則4分解選擇運(yùn)算。2.利用規(guī)則4~9把選擇運(yùn)算盡量移到葉端。3.利用規(guī)則3，5，10，11把投影運(yùn)算盡量移到葉端。4.利用規(guī)則3~5把選擇和投影的串接合并成單個(gè)選擇、單個(gè)投影或一個(gè)選擇后跟一個(gè)投影的形式。使盡可能多的選擇和投影同時(shí)執(zhí)行。5.分組。雙目運(yùn)算和他的直系祖先為一組；雙目運(yùn)算后代直道葉子全是單目運(yùn)算時(shí)并入改組。笛卡兒積的后面若不是與之可以合并的自然連接的等值選擇時(shí)，其后代單獨(dú)分為一組。第31頁/共46頁優(yōu)化實(shí)例例：查詢至少選修了一門先行課號為5號課程的學(xué)生姓名。其中，C是課程表，S是學(xué)生表，SC是學(xué)生選課表。在優(yōu)化規(guī)則中沒有對自然連接的直接優(yōu)化，我們把自然連接分解為笛卡兒積和選擇。第32頁/共46頁分解后的關(guān)系代數(shù)表達(dá)式××SCSC第33頁/共46頁第一步：利用規(guī)則4分解選擇運(yùn)算××SCSC第34頁/共46頁第二步：盡量下放選擇運(yùn)算××SCSC第35頁/共46頁××SCSC第二步（2）：下放完成后：第36頁/共46頁第三步：盡量下放投影運(yùn)算××SCSCE第37頁/共46頁第三步：盡量下放投影運(yùn)算××SCSC第38頁/共46頁第三步（2）：第一次下放后：××SCSC第39頁/共46頁