數(shù)據(jù)庫(kù)原理9-2

1、第九章第九章 關(guān)系查詢處理和查詢優(yōu)化關(guān)系查詢處理和查詢優(yōu)化授課教師：顧留碗復(fù)習(xí)上節(jié)課內(nèi)容復(fù)習(xí)上節(jié)課內(nèi)容v索引的創(chuàng)建及管理索引的創(chuàng)建及管理 建立索引的必要性 索引的類型 管理索引（創(chuàng)建、查看、修改、刪除）v關(guān)系數(shù)據(jù)庫(kù)系統(tǒng)的查詢處理關(guān)系數(shù)據(jù)庫(kù)系統(tǒng)的查詢處理 查詢分析 查詢檢查 查詢優(yōu)化 查詢執(zhí)行本次課學(xué)習(xí)內(nèi)容本次課學(xué)習(xí)內(nèi)容v關(guān)系數(shù)據(jù)庫(kù)系統(tǒng)的查詢優(yōu)化 v代數(shù)優(yōu)化v物理優(yōu)化 一、關(guān)系數(shù)據(jù)庫(kù)系統(tǒng)的查詢優(yōu)化一、關(guān)系數(shù)據(jù)庫(kù)系統(tǒng)的查詢優(yōu)化 v查詢優(yōu)化在關(guān)系數(shù)據(jù)庫(kù)系統(tǒng)中有著非常重要的地位 v關(guān)系查詢優(yōu)化是影響RDBMS性能的關(guān)鍵因素 v由于關(guān)系表達(dá)式的語(yǔ)義級(jí)別很高，使關(guān)系系統(tǒng)可以從關(guān)系表達(dá)式中分析查詢語(yǔ)義，提供

2、了執(zhí)行查詢優(yōu)化的可能性 v查詢優(yōu)化的優(yōu)點(diǎn)不僅在于用戶不必考慮如何最好地表達(dá)查詢以獲得較好的效率，而且在于系統(tǒng)可以比用戶程序的“優(yōu)化”做得更好 ； （1）優(yōu)化器可以從數(shù)據(jù)字典中獲取許多統(tǒng)計(jì)信息許多統(tǒng)計(jì)信息，而用戶程序則難以獲得這些信息； （2）如果數(shù)據(jù)庫(kù)的物理統(tǒng)計(jì)信息改變了，系統(tǒng)可以自動(dòng)自動(dòng)對(duì)查詢重新優(yōu)化以選擇相適應(yīng)的執(zhí)行計(jì)劃。在非關(guān)系系統(tǒng)中必須重寫(xiě)程序，而重寫(xiě)程序在實(shí)際應(yīng)用中往往是不太可能的。 (3)優(yōu)化器可以考慮數(shù)百種不同的執(zhí)行計(jì)劃考慮數(shù)百種不同的執(zhí)行計(jì)劃，程序員一般只能考慮有限的幾種可能性。 (4)優(yōu)化器中包括了很多復(fù)雜的優(yōu)化技術(shù)，這些優(yōu)化技術(shù)往往只有最好的程序員才能掌握。系統(tǒng)的自動(dòng)優(yōu)化相

3、當(dāng)于使得系統(tǒng)的自動(dòng)優(yōu)化相當(dāng)于使得所有人都擁有這些優(yōu)化技術(shù)。所有人都擁有這些優(yōu)化技術(shù)。vRDBMS通過(guò)某種代價(jià)模型計(jì)算出各種查詢執(zhí)行策略的執(zhí)行代價(jià)，然后選取代價(jià)最小的執(zhí)行方案： 集中式數(shù)據(jù)庫(kù)集中式數(shù)據(jù)庫(kù) 執(zhí)行開(kāi)銷主要包括： 磁盤(pán)存取塊數(shù)磁盤(pán)存取塊數(shù)(I/O代價(jià)代價(jià)) 處理機(jī)時(shí)間處理機(jī)時(shí)間(CPU代價(jià)代價(jià)) 查詢的內(nèi)存開(kāi)銷查詢的內(nèi)存開(kāi)銷 I/O代價(jià)是最主要的 分布式數(shù)據(jù)庫(kù)分布式數(shù)據(jù)庫(kù) 總代價(jià)總代價(jià)=I/O代價(jià)代價(jià)+CPU代價(jià)代價(jià)+內(nèi)存代價(jià)通信代價(jià)內(nèi)存代價(jià)通信代價(jià)v查詢優(yōu)化的總目標(biāo)： 選擇有效的策略； 求得給定關(guān)系表達(dá)式的值； 使得查詢代價(jià)最小(實(shí)際上是較小) ；實(shí)例演示（驗(yàn)證為何需要查詢優(yōu)化？）實(shí)

4、例演示（驗(yàn)證為何需要查詢優(yōu)化？）例例1： 求選修了求選修了2號(hào)課程的學(xué)生姓名。號(hào)課程的學(xué)生姓名。假定學(xué)生-課程數(shù)據(jù)庫(kù)中有1000條學(xué)生記錄，10000條選課記錄；其中選修2號(hào)課程的選課記錄為50條； 用SQL表達(dá)： SELECT Student.Sname FROM Student，SC WHERE Student.Sno=SC.Sno AND SC.Cno=2 v系統(tǒng)可以用多種等價(jià)的關(guān)系代數(shù)表達(dá)式關(guān)系代數(shù)表達(dá)式來(lái)完成：Q1=Sname(Student.Sno=SC.SnoSc.Cno=2 (StudentSC)Q2=Sname(Sc.Cno=2 (Student SC)Q3=Sname(St

5、udent Sc.Cno=2(SC)1、第一種情況、第一種情況v 分三個(gè)步驟： 計(jì)算StudentSC花費(fèi)時(shí)間，即計(jì)算笛卡爾積操作時(shí)間； 計(jì)算Student.Sno=SC.SnoSc.Cno=2 花費(fèi)時(shí)間，即計(jì)算選擇操作時(shí)間； 計(jì)算Sname花費(fèi)時(shí)間，即計(jì)算投影操作時(shí)間；1）計(jì)算笛卡爾積時(shí)間）計(jì)算笛卡爾積時(shí)間v把Student和SC的每個(gè)元組連接起來(lái)的做法： 在內(nèi)存中盡可能多地裝入某個(gè)表(如Student表)的若干塊，留出一塊存放另一個(gè)表(如SC表)的元組； 把SC中的每個(gè)元組和Student中每個(gè)元組連接，連接后的元組裝滿一塊后就寫(xiě)到中間文件上； 從SC中讀入一塊和內(nèi)存中的Student元組

6、連接，直到SC表處理完； 再讀入若干塊Student元組，讀入一塊SC元組； 重復(fù)上述處理過(guò)程，直到把Student表處理完；v 設(shè)一個(gè)塊能裝10個(gè)Student元組或100個(gè)SC元組，在內(nèi)存中存放5塊Student元組和1塊SC元組，則讀取總塊數(shù)為： =100 + 20100=2100塊v 若每秒讀寫(xiě)20塊，則總計(jì)要花105s ；v 連接后的元組數(shù)為103104=107；v 設(shè)每塊能裝10個(gè)元組，則寫(xiě)出這些塊要用106/20=5104s ；1010005101000100100002）計(jì)算選擇時(shí)間）計(jì)算選擇時(shí)間v 依次讀入連接后的元組，按照選擇條件選取滿足要求的記錄； v 假定內(nèi)存處理時(shí)間忽

7、略；v 讀取中間文件花費(fèi)的時(shí)間(同寫(xiě)中間文件一樣)需5104s ；v 滿足條件的元組假設(shè)僅50個(gè)，均可放在內(nèi)存； 3）作投影操作）作投影操作v 把第2步的結(jié)果在Sname上作投影輸出，得到最終結(jié)果 ；v 所有內(nèi)存處理時(shí)間均忽略不計(jì)；第一種情況下執(zhí)行查詢的總時(shí)間第一種情況下執(zhí)行查詢的總時(shí)間105 + 25104105s2、第二種情況、第二種情況v 分三個(gè)步驟： 計(jì)算Student SC花費(fèi)時(shí)間，即計(jì)算自然連接操作時(shí)間； 計(jì)算Sc.Cno=2 花費(fèi)時(shí)間，即計(jì)算選擇操作時(shí)間； 計(jì)算Sname花費(fèi)時(shí)間，即計(jì)算投影操作時(shí)間；1）計(jì)算自然連接時(shí)間）計(jì)算自然連接時(shí)間v 讀取Student和SC表的策略不變，

8、總的讀取塊數(shù)仍為2100塊，花費(fèi)105 s ；v 自然連接的結(jié)果比第一種情況大大減少，為104個(gè) ；v 寫(xiě)出這些元組時(shí)間為103/20=50s，為第一種情況的千分之一；2）計(jì)算選擇操作時(shí)間）計(jì)算選擇操作時(shí)間v 讀取中間文件塊，執(zhí)行選擇運(yùn)算，花費(fèi)時(shí)間也為50s；3）計(jì)算選擇操作時(shí)間：）計(jì)算選擇操作時(shí)間：把第2步結(jié)果投影輸出。 第二種情況下執(zhí)行查詢的總時(shí)間第二種情況下執(zhí)行查詢的總時(shí)間105+50+50205s 3、第三種情況、第三種情況v 分三個(gè)步驟： 先對(duì)SC表作選擇運(yùn)算，只需讀一遍SC表，需存取100塊，花費(fèi)時(shí)間為5s，因?yàn)闈M足條件的元組僅50個(gè)，不必使用中間文件。 讀取Student表，把讀

9、入的Student元組和內(nèi)存中的SC元組作連接。也只需讀一遍Student表共100塊，花費(fèi)時(shí)間為5s。 把連接結(jié)果投影輸出；第三種情況下執(zhí)行查詢的總時(shí)間第三種情況下執(zhí)行查詢的總時(shí)間5+5 10sv由Q1變換為Q2、 Q3得出結(jié)論： 即有選擇和連接操作時(shí)，先做選擇操作，這樣參加連接的元組就可以大大減少，這是代數(shù)優(yōu)化代數(shù)優(yōu)化；v在Q3中： SC表的選擇操作算法有全表掃描和索引掃描2種方法，經(jīng)過(guò)初步估算，索引掃描方法較優(yōu) ； 對(duì)于Student和SC表的連接，利用Student表上的索引，采用index join代價(jià)也較小，這就是物理優(yōu)化物理優(yōu)化； 二、代數(shù)優(yōu)化二、代數(shù)優(yōu)化v代數(shù)優(yōu)化策略代數(shù)優(yōu)化策

10、略： 通過(guò)對(duì)關(guān)系代數(shù)表達(dá)式的等價(jià)變換來(lái)提高查詢效率；v關(guān)系代數(shù)表達(dá)式的等價(jià)：指用相同的關(guān)系代替兩個(gè)表達(dá)式中相應(yīng)的關(guān)系所得到的結(jié)果是相同的；v兩個(gè)關(guān)系表達(dá)式E1和E2是等價(jià)的，可記為E1E2 1）連接、笛卡爾積）連接、笛卡爾積交換律交換律 設(shè)E1和E2是關(guān)系代數(shù)表達(dá)式，F(xiàn)是連接運(yùn)算的條件，則有 E1 E2E2 E1 E1 E2E2 E1 E1 E2E2 E12）連接、笛卡爾積的）連接、笛卡爾積的結(jié)合律結(jié)合律 設(shè)E1，E2，E3是關(guān)系代數(shù)表達(dá)式，F(xiàn)1和F2是連接運(yùn)算的條件，則有 (E1 E2) E3E1 (E2 E3) (E1 E2) E3E1 (E2 E3) (E1 E2) E3E1 (E2 E

11、3) 1、常用的等價(jià)變換規(guī)則（、常用的等價(jià)變換規(guī)則（P269）2、查詢樹(shù)的啟發(fā)式優(yōu)化、查詢樹(shù)的啟發(fā)式優(yōu)化v啟發(fā)式規(guī)則：?jiǎn)l(fā)式規(guī)則： 選擇運(yùn)算應(yīng)盡可能先做；選擇運(yùn)算應(yīng)盡可能先做；在優(yōu)化策略中這是最重要、最基本的一條； 把投影運(yùn)算和選擇運(yùn)算同時(shí)進(jìn)行；把投影運(yùn)算和選擇運(yùn)算同時(shí)進(jìn)行； 如有若干投影和選擇運(yùn)算，并且它們都對(duì)同一個(gè)關(guān)系操作，則可以在掃描此關(guān)系的同時(shí)完成所有的這些運(yùn)算以避免重復(fù)掃描關(guān)系； 把投影同其前或其后的雙目運(yùn)算結(jié)合起來(lái)； 把某些選擇同在它前面要執(zhí)行的笛卡爾積結(jié)合起來(lái)成為一個(gè)連接運(yùn)算； 找出公共子表達(dá)式；優(yōu)化關(guān)系表達(dá)式的算法（優(yōu)化關(guān)系表達(dá)式的算法（P271） 算法：關(guān)系表達(dá)式的優(yōu)化；算法

12、：關(guān)系表達(dá)式的優(yōu)化；輸入：一個(gè)關(guān)系表達(dá)式的查詢樹(shù)；輸出：優(yōu)化的查詢樹(shù)；輸入：一個(gè)關(guān)系表達(dá)式的查詢樹(shù)；輸出：優(yōu)化的查詢樹(shù)；方法：方法：1）利用等價(jià)變換規(guī)則4把形如F1F2Fn(E)變換為F1(F2(Fn(E)；2）對(duì)每一個(gè)選擇，利用等價(jià)變換規(guī)則49盡可能把它移到樹(shù)的葉端；3）對(duì)每一個(gè)投影利用等價(jià)變換規(guī)則3，5，10，11中的一般形式盡可能把它移向樹(shù)的葉端；4）利用等價(jià)變換規(guī)則35把選擇和投影的串接合并成單個(gè)選擇、單個(gè)投影或一個(gè)選擇后跟一個(gè)投影；5) 把上述得到的語(yǔ)法樹(shù)的內(nèi)節(jié)點(diǎn)分組。v例：將例例：將例1的的SQL語(yǔ)句的代數(shù)優(yōu)化；語(yǔ)句的代數(shù)優(yōu)化； 關(guān)系代數(shù)語(yǔ)法樹(shù) 三、物理優(yōu)化三、物理優(yōu)化v 代數(shù)優(yōu)化

13、改變查詢語(yǔ)句中操作的次序和組合，不涉及底層的存取路徑；對(duì)于一個(gè)查詢語(yǔ)句有許多存取方案，它們的執(zhí)行效率不同， 僅僅進(jìn)行代數(shù)優(yōu)化是不夠的 ；v 物理優(yōu)化就是要選擇高效合理的操作算法或存取路徑，求得優(yōu)化的查詢計(jì)劃 ；v 選擇的方法： 基于規(guī)則的啟發(fā)式優(yōu)化 基于代價(jià)估算的優(yōu)化 兩者結(jié)合的優(yōu)化方法1、基于啟發(fā)式規(guī)則的存取路徑選擇優(yōu)化、基于啟發(fā)式規(guī)則的存取路徑選擇優(yōu)化P2731） 選擇操作的啟發(fā)式規(guī)則: 對(duì)于小關(guān)系，使用全表順序掃描，即使選擇列上有索引 對(duì)于大關(guān)系，啟發(fā)式規(guī)則有： 對(duì)于選擇條件是主碼值的查詢； 查詢結(jié)果最多是一個(gè)元組，可以選擇主碼索引； 一般的RDBMS會(huì)自動(dòng)建立主碼索引； 對(duì)于選擇條件是

14、非主屬性值的查詢，并且選擇列上有索引 要估算查詢結(jié)果的元組數(shù)目 如果比例較小(10%)可以使用索引掃描方法 否則還是使用全表順序掃描2） 連接操作的啟發(fā)式規(guī)則： 如果2個(gè)表都已經(jīng)按照連接屬性排序 選用排序-合并方法 如果一個(gè)表在連接屬性上有索引 選用索引連接方法 如果上面2個(gè)規(guī)則都不適用，其中一個(gè)表較小 選用Hash join方法 可以選用嵌套循環(huán)方法，并選擇其中較小的表，確切地講是占用的塊數(shù)(b)較少的表，作為外表(外循環(huán)的表) 。2、基于代價(jià)的優(yōu)化、基于代價(jià)的優(yōu)化P274v基于代價(jià)的優(yōu)化方法要計(jì)算各種操作算法的執(zhí)行代價(jià)，與數(shù)據(jù)庫(kù)的狀態(tài)密切相關(guān) ；v數(shù)據(jù)字典中存儲(chǔ)的優(yōu)化器需要的統(tǒng)計(jì)信息： 1）對(duì)每個(gè)基本表n該表的元組總數(shù)(N)n元組長(zhǎng)度(l)n占用的塊數(shù)(B)n占用的溢出塊數(shù)(BO)2）對(duì)基表的每個(gè)列3）對(duì)索引(如B+樹(shù)索引)代價(jià)估算示例代價(jià)估算示例 1）全表掃描算法的代價(jià)估算公式 如果基本表大小為B塊，全表掃描算法的代價(jià) costB 如果選擇