關(guān)系查詢(xún)處理和查詢(xún)優(yōu)化(1)課件

1、關(guān)系查詢(xún)處理和查詢(xún)優(yōu)化(1)關(guān)系查詢(xún)處理和查詢(xún)優(yōu)化(1)SQL語(yǔ)句轉(zhuǎn)換為關(guān)系代數(shù)表達(dá)式9.1 RDBMS的查詢(xún)處理查詢(xún)處理的步驟SQL語(yǔ)句轉(zhuǎn)換為關(guān)系代數(shù)表達(dá)式9.1 RDBMS的查詢(xún)處理實(shí)現(xiàn)查詢(xún)操作的算法示例9.1 RDBMS的查詢(xún)處理一、選擇操作的實(shí)現(xiàn)簡(jiǎn)單的全表掃描方法對(duì)查詢(xún)的基本表順序掃描，逐一檢查每個(gè)元組是否滿足選擇條件，把滿足條件的元組作為結(jié)果輸出；適合小表，不適合大表。2. 索引掃描方法如果選擇條件中的屬性上建有索引；通過(guò)索引先找到滿足條件的元組指針，再通過(guò)指針直接在基本表中找到元組。實(shí)現(xiàn)查詢(xún)操作的算法示例9.1 RDBMS的查詢(xún)處理一、選擇實(shí)現(xiàn)查詢(xún)操作的算法示例9.1 RDBMS的

2、查詢(xún)處理二、連接操作的實(shí)現(xiàn)查詢(xún)處理中最耗時(shí)的操作之一；只討論等值連接最常用的實(shí)現(xiàn)算法。例：select * from student, sc where student.sno=sc.sno嵌套循環(huán)法2. 排序合并法3. 索引連接法4. Hash Join法實(shí)現(xiàn)查詢(xún)操作的算法示例9.1 RDBMS的查詢(xún)處理二、連接studentsc排序合并連接方法示意圖studentsc排序合并連接方法示意圖9.2 關(guān)系數(shù)據(jù)庫(kù)系統(tǒng)的查詢(xún)優(yōu)化目標(biāo)：提高關(guān)系數(shù)據(jù)庫(kù)的存取效率實(shí)現(xiàn)策略：RDBMS根據(jù)數(shù)據(jù)字典的統(tǒng)計(jì)信息通過(guò)某種代價(jià)模型估算各種查詢(xún)策略的執(zhí)行代價(jià)，然后選取代價(jià)最小的執(zhí)行方案。e.g. 集中式數(shù)據(jù)庫(kù)執(zhí)行開(kāi)

3、銷(xiāo)包括：磁盤(pán)存取塊數(shù)（I/O代價(jià)）處理機(jī)時(shí)間（CPU代價(jià)）內(nèi)存開(kāi)銷(xiāo)9.2 關(guān)系數(shù)據(jù)庫(kù)系統(tǒng)的查詢(xún)優(yōu)化目標(biāo)：提高關(guān)系數(shù)據(jù)庫(kù)的存取效9.2 關(guān)系數(shù)據(jù)庫(kù)系統(tǒng)的查詢(xún)優(yōu)化實(shí)例：查詢(xún)選修了2號(hào)課程的學(xué)生姓名 SELECT Student.SnameFROM Student, SCWHERE Student.Sno=SC.Sno AND SC.Cno=2思考：該查詢(xún)對(duì)應(yīng)的關(guān)系代數(shù)表達(dá)式；假設(shè)讀寫(xiě)速度為20塊/s, 分析各種查詢(xún)策略的執(zhí)行時(shí)間。總記錄數(shù)內(nèi)存裝載塊數(shù)塊的大小總塊數(shù)Student1000510Sc100001100中間結(jié)果1101071001001069.2 關(guān)系數(shù)據(jù)庫(kù)系統(tǒng)的查詢(xún)優(yōu)化實(shí)例：查詢(xún)選修了

4、2號(hào)課程的學(xué)9.3 代數(shù)優(yōu)化關(guān)系代數(shù)表達(dá)式等價(jià)變換規(guī)則代數(shù)優(yōu)化策略：通過(guò)對(duì)關(guān)系代數(shù)表達(dá)式的等價(jià)變換來(lái)提高查詢(xún)效率。兩個(gè)關(guān)系表達(dá)式E1和E2等價(jià)，可記為E1 E2.常用的等價(jià)變化規(guī)則如下：連接、笛卡兒積交換律 設(shè)E1和E2是關(guān)系代數(shù)表達(dá)式，F(xiàn)是連接運(yùn)算的條件，則有9.3 代數(shù)優(yōu)化關(guān)系代數(shù)表達(dá)式等價(jià)變換規(guī)則2.連接、笛卡爾積的結(jié)合律3. 投影的串接定律4. 選擇的串接定律5. 選擇與投影的交換律2.連接、笛卡爾積的結(jié)合律3. 投影的串接定律4. 選擇的串9.3 代數(shù)優(yōu)化查詢(xún)樹(shù)的啟發(fā)式優(yōu)化9.3 代數(shù)優(yōu)化查詢(xún)樹(shù)的啟發(fā)式優(yōu)化9.3 代數(shù)優(yōu)化代數(shù)優(yōu)化示例9.3 代數(shù)優(yōu)化代數(shù)優(yōu)化示例9.4 物理優(yōu)化代數(shù)優(yōu)化改變查詢(xún)語(yǔ)句中操作的次序和組合，不涉及底層的存取路徑；對(duì)于每一種操作有多種存取路徑，它們的執(zhí)行效率不同，因此僅僅進(jìn)行代數(shù)優(yōu)化是不夠的；物理優(yōu)化就是要選擇高效合理的操作算法和存取路徑，得到優(yōu)化的查詢(xún)計(jì)劃。9.4 物理優(yōu)化代數(shù)優(yōu)化改變查詢(xún)語(yǔ)句中操作的次序和組合，不涉9.4 物理優(yōu)化常用的方法：基于規(guī)則的啟發(fā)式優(yōu)化：大多數(shù)情況都使用的規(guī)則。基于代價(jià)估算的優(yōu)化：估算不同執(zhí)行策略的代