資源描述：
《查詢(xún)優(yōu)化及索引》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫(kù)。
1、第十章查詢(xún)優(yōu)化及索引瓊州學(xué)院電子信息工程學(xué)院第十章查詢(xún)優(yōu)化及索引10.1關(guān)系數(shù)據(jù)庫(kù)系統(tǒng)的查詢(xún)處理10.2關(guān)系數(shù)據(jù)庫(kù)系統(tǒng)的查詢(xún)優(yōu)化10.3代數(shù)優(yōu)化10.4物理優(yōu)化10.5小結(jié)10.6索引、全文索引與優(yōu)化瓊州學(xué)院電子信息工程學(xué)院查詢(xún)優(yōu)化及索引本章目的：RDBMS的查詢(xún)處理步驟查詢(xún)優(yōu)化的概念基本方法和技術(shù)查詢(xún)優(yōu)化分類(lèi)：代數(shù)優(yōu)化物理優(yōu)化瓊州學(xué)院電子信息工程學(xué)院10.1關(guān)系數(shù)據(jù)庫(kù)系統(tǒng)的查詢(xún)處理10.1.1查詢(xún)處理步驟10.1.2實(shí)現(xiàn)查詢(xún)操作的算法示例瓊州學(xué)院電子信息工程學(xué)院10.1.1查詢(xún)處理步驟RDBMS查詢(xún)處理階段：1.查詢(xún)分析2.查詢(xún)檢
2、查3.查詢(xún)優(yōu)化4.查詢(xún)執(zhí)行瓊州學(xué)院電子信息工程學(xué)院查詢(xún)處理步驟（續(xù)）查詢(xún)處理步驟瓊州學(xué)院電子信息工程學(xué)院1.查詢(xún)分析對(duì)查詢(xún)語(yǔ)句進(jìn)行掃描、詞法分析和語(yǔ)法分析從查詢(xún)語(yǔ)句中識(shí)別出語(yǔ)言符號(hào)進(jìn)行語(yǔ)法檢查和語(yǔ)法分析瓊州學(xué)院電子信息工程學(xué)院2.查詢(xún)檢查根據(jù)數(shù)據(jù)字典對(duì)合法的查詢(xún)語(yǔ)句進(jìn)行語(yǔ)義檢查根據(jù)數(shù)據(jù)字典中的用戶權(quán)限和完整性約束定義對(duì)用戶的存取權(quán)限進(jìn)行檢查檢查通過(guò)后把SQL查詢(xún)語(yǔ)句轉(zhuǎn)換成等價(jià)的關(guān)系代數(shù)表達(dá)式RDBMS一般都用查詢(xún)樹(shù)(語(yǔ)法分析樹(shù))來(lái)表示擴(kuò)展的關(guān)系代數(shù)表達(dá)式把數(shù)據(jù)庫(kù)對(duì)象的外部名稱(chēng)轉(zhuǎn)換為內(nèi)部表示瓊州學(xué)院電子信息工程學(xué)院3.查詢(xún)優(yōu)化查詢(xún)優(yōu)化
3、：選擇一個(gè)高效執(zhí)行的查詢(xún)處理策略查詢(xún)優(yōu)化分類(lèi)：代數(shù)優(yōu)化：指關(guān)系代數(shù)表達(dá)式的優(yōu)化物理優(yōu)化：指存取路徑和底層操作算法的選擇查詢(xún)優(yōu)化方法選擇的依據(jù)：基于規(guī)則(rulebased)基于代價(jià)(costbased)基于語(yǔ)義(semanticbased)瓊州學(xué)院電子信息工程學(xué)院4.查詢(xún)執(zhí)行依據(jù)優(yōu)化器得到的執(zhí)行策略生成查詢(xún)計(jì)劃代碼生成器(codegenerator)生成執(zhí)行查詢(xún)計(jì)劃的代碼瓊州學(xué)院電子信息工程學(xué)院10.1關(guān)系數(shù)據(jù)庫(kù)系統(tǒng)的查詢(xún)處理10.1.1查詢(xún)處理步驟10.1.2實(shí)現(xiàn)查詢(xún)操作的算法示例瓊州學(xué)院電子信息工程學(xué)院10.1.2實(shí)現(xiàn)查詢(xún)操作的
4、算法示例一、選擇操作的實(shí)現(xiàn)二、連接操作的實(shí)現(xiàn)瓊州學(xué)院電子信息工程學(xué)院一、選擇操作的實(shí)現(xiàn)［例1］Select*fromstudentwhere<條件表達(dá)式>；考慮<條件表達(dá)式>的幾種情況：C1：無(wú)條件；C2：Sno＝'200215121'；C3：Sage>20；C4：Sdept＝'CS'ANDSage>20；瓊州學(xué)院電子信息工程學(xué)院選擇操作的實(shí)現(xiàn)（續(xù)）選擇操作典型實(shí)現(xiàn)方法：1.簡(jiǎn)單的全表掃描方法對(duì)查詢(xún)的基本表順序掃描，逐一檢查每個(gè)元組是否滿足選擇條件，把滿足條件的元組作為結(jié)果輸出適合小表，不適合大表2.索引(或散列)掃描方法適合選擇條
5、件中的屬性上有索引(例如B+樹(shù)索引或Hash索引)通過(guò)索引先找到滿足條件的元組主碼或元組指針，再通過(guò)元組指針直接在查詢(xún)的基本表中找到元組瓊州學(xué)院電子信息工程學(xué)院選擇操作的實(shí)現(xiàn)（續(xù)）［例1-C2］以C2為例，Sno＝‘200215121’，并且Sno上有索引(或Sno是散列碼)使用索引(或散列)得到Sno為‘200215121’元組的指針通過(guò)元組指針在student表中檢索到該學(xué)生［例1-C3］以C3為例，Sage>20，并且Sage上有B+樹(shù)索引使用B+樹(shù)索引找到Sage＝20的索引項(xiàng)，以此為入口點(diǎn)在B+樹(shù)的順序集上得到Sage>2
6、0的所有元組指針通過(guò)這些元組指針到student表中檢索到所有年齡大于20的學(xué)生。瓊州學(xué)院電子信息工程學(xué)院選擇操作的實(shí)現(xiàn)（續(xù)）［例1-C4］以C4為例，Sdept＝‘CS’ANDSage>20，如果Sdept和Sage上都有索引：算法一：分別用上面兩種方法分別找到Sdept＝‘CS’的一組元組指針和Sage>20的另一組元組指針求這2組指針的交集到student表中檢索得到計(jì)算機(jī)系年齡大于20的學(xué)生算法二：找到Sdept＝‘CS’的一組元組指針，通過(guò)這些元組指針到student表中檢索對(duì)得到的元組檢查另一些選擇條件(如Sage>20
7、)是否滿足把滿足條件的元組作為結(jié)果輸出。瓊州學(xué)院電子信息工程學(xué)院二、連接操作的實(shí)現(xiàn)連接操作是查詢(xún)處理中最耗時(shí)的操作之一本節(jié)只討論等值連接(或自然連接)最常用的實(shí)現(xiàn)算法［例2］SELECT*FROMStudent，SCWHEREStudent.Sno=SC.Sno；瓊州學(xué)院電子信息工程學(xué)院連接操作的實(shí)現(xiàn)（續(xù)）1.嵌套循環(huán)方法(nestedloop)2.排序-合并方法(sort-mergejoin或mergejoin)3.索引連接(indexjoin)方法4.HashJoin方法瓊州學(xué)院電子信息工程學(xué)院連接操作的實(shí)現(xiàn)（續(xù)）嵌套循環(huán)方法(
8、nestedloop)對(duì)外層循環(huán)(Student)的每一個(gè)元組(s)，檢索內(nèi)層循環(huán)(SC)中的每一個(gè)元組(sc)檢查這兩個(gè)元組在連接屬性(sno)上是否相等如果滿足連接條件，則串接后作為結(jié)果輸出，直到外層循環(huán)表中的元組處理完為止瓊州學(xué)
