1、數(shù)據(jù)庫系統(tǒng)簡(jiǎn)介An Introduction to Database System第9章關(guān)系查詢處理和查詢優(yōu)化，第9章關(guān)系系統(tǒng)及其查詢優(yōu)化，9.1關(guān)系數(shù)據(jù)庫系統(tǒng)的查詢處理9.2關(guān)系數(shù)據(jù)庫系統(tǒng)的查詢優(yōu)化9.3代數(shù)優(yōu)化9.4物理優(yōu)化9.5小注釋，9.1關(guān)系數(shù)據(jù)庫系統(tǒng)的查詢處理，9.1.1查詢處理步驟9.1.2實(shí)現(xiàn)查詢操作的算法示例語法分析和翻譯2。優(yōu)化3 .執(zhí)行，處理查詢階段(續(xù))，處理查詢階段，1。解析和翻譯程序、查詢處理器必須對(duì)查詢語言中的語句進(jìn)行解析，并將其轉(zhuǎn)換為某種內(nèi)部表示形式。祖懷語言的語法分析與傳統(tǒng)編程語言的語法分析幾乎沒有區(qū)別。語法分析和翻譯過程類似于編程語言編譯器的語法分析過程。也

2、就是說，使用較高級(jí)別的查詢語句(如SQL)作為輸入，并輸出關(guān)系代數(shù)表達(dá)式。2 .查詢優(yōu)化在關(guān)系數(shù)據(jù)庫系統(tǒng)中占有非常重要的位置。關(guān)系數(shù)據(jù)庫系統(tǒng)和非程序SQL語言取得巨大成功的關(guān)鍵在于查詢優(yōu)化技術(shù)的發(fā)展。關(guān)系查詢優(yōu)化是影響RDBMS性能的關(guān)鍵因素。優(yōu)化是關(guān)系系統(tǒng)的挑戰(zhàn)和機(jī)會(huì)。挑戰(zhàn)是，關(guān)系系統(tǒng)必須執(zhí)行查詢優(yōu)化，以獲得用戶可接受的性能。關(guān)系表達(dá)式具有較高的語義級(jí)別，使關(guān)系系統(tǒng)可以在關(guān)系表達(dá)式中分析查詢語義，從而提供執(zhí)行查詢優(yōu)化的可能性。這為關(guān)系系統(tǒng)接近非關(guān)系系統(tǒng)或發(fā)揮更多性能提供了機(jī)會(huì)。2 .查詢優(yōu)化程序，查詢優(yōu)化解決的問題：1，每個(gè)SQL語句可以轉(zhuǎn)換為多個(gè)等價(jià)關(guān)系代數(shù)表達(dá)式。替代關(guān)系代數(shù)表達(dá)式是什么

3、？2，每個(gè)關(guān)系代數(shù)表達(dá)式的關(guān)系運(yùn)算可以用不同的算法實(shí)現(xiàn)，可以使用不同的索引。具體使用什么算法和什么索引？3、整體表達(dá)式評(píng)估是使用管道計(jì)算方法，還是使用實(shí)體化計(jì)算方法？還是使用兩種混合計(jì)算方法？2 .查詢優(yōu)化程序，1，問題中的呈現(xiàn)查詢SQL語句可以用多種方式表示，每個(gè)SQL語句可以轉(zhuǎn)換為多個(gè)等價(jià)關(guān)系代數(shù)表達(dá)式。例如，select balance from account where balance 2500可以轉(zhuǎn)換為兩個(gè)關(guān)系代數(shù)表達(dá)式，其中每個(gè)表達(dá)式的關(guān)系運(yùn)算可以用另一個(gè)算法和索引實(shí)現(xiàn)。因此，查詢優(yōu)化程序的任務(wù)是找到上述表達(dá)式中成本最低的指定查詢的處理進(jìn)程。2 .查詢優(yōu)化程序、2、執(zhí)行計(jì)劃查詢優(yōu)

4、化程序使用關(guān)系代數(shù)表達(dá)式作為輸入來輸出查詢執(zhí)行計(jì)劃。什么是查詢執(zhí)行計(jì)劃？2 .查詢優(yōu)化程序，2，執(zhí)行計(jì)劃不僅提供關(guān)系代數(shù)表達(dá)式，還計(jì)算查詢。這些注釋用于說明如何具體實(shí)現(xiàn)每個(gè)任務(wù)。例如，可以描述用于關(guān)系運(yùn)算的算法或要使用的一個(gè)或多個(gè)特定索引。添加了有關(guān)如何執(zhí)行的注釋的這種關(guān)系代數(shù)運(yùn)算稱為執(zhí)行原語，用于計(jì)算一個(gè)查詢的基元序列稱為查詢執(zhí)行計(jì)劃或查詢計(jì)算計(jì)劃。查詢優(yōu)化是為給定查詢選擇最有效的查詢執(zhí)行計(jì)劃的過程，它包括兩個(gè)方面：也就是說，它在關(guān)系代數(shù)級(jí)別進(jìn)行了優(yōu)化，執(zhí)行此操作的目的是找到與給定關(guān)系代數(shù)表達(dá)式相同，但更有效的表達(dá)式。查詢語句處理的詳細(xì)策略的選擇。例如，確定用于執(zhí)行運(yùn)算的特定算法和要使用的特

5、定索引等。2 .查詢優(yōu)化程序，2，執(zhí)行計(jì)劃，2。優(yōu)化程序必須估計(jì)每個(gè)查詢執(zhí)行計(jì)劃的成本，以便查詢優(yōu)化程序、3、查詢優(yōu)化程序可以從許多查詢執(zhí)行計(jì)劃中進(jìn)行選擇。這使用了關(guān)系的統(tǒng)計(jì)數(shù)據(jù)。如何估計(jì)查詢執(zhí)行計(jì)劃的成本？3 .執(zhí)行引擎查詢執(zhí)行引擎允許的輸入是查詢執(zhí)行計(jì)劃，結(jié)果是特定查詢結(jié)果的引擎。，3 .所有數(shù)據(jù)庫系統(tǒng)都運(yùn)行不完全遵循這些步驟的引擎。大多數(shù)數(shù)據(jù)庫系統(tǒng)不使用關(guān)系代數(shù)表達(dá)式來表示查詢。相反，執(zhí)行引擎查詢執(zhí)行引擎允許的輸入是查詢執(zhí)行計(jì)劃，輸出是特定查詢結(jié)果的注釋語法分析樹基于給定的SQL查詢結(jié)構(gòu)。9.1關(guān)系數(shù)據(jù)庫系統(tǒng)中的查詢處理，9.1.1查詢處理步驟實(shí)現(xiàn)9.1.2查詢操作的算法示例，實(shí)現(xiàn)9.1

6、.2查詢操作的算法示例，第一，選擇操作的實(shí)現(xiàn)2，連接操作的實(shí)現(xiàn)，第一，選擇操作的實(shí)現(xiàn)，示例1 select * from student where需要考慮的一些情況：C1:無條件；C2:SnO 200215121；C3:sage 20；C4:sdept cs and sage 20；以選擇實(shí)施作業(yè)(繼續(xù))，然后選擇實(shí)施一般作業(yè)的方法。1.簡(jiǎn)單全表掃描方法在查詢的基礎(chǔ)表順序掃描中，單獨(dú)確定每個(gè)元組是否滿足選擇條件，將滿足條件的元組與結(jié)果輸出匹配到較小的表。不適合大桌子2。索引(或散列)掃描方法首先通過選擇條件的屬性具有索引(例如b樹索引或散列索引)的索引查找符合條件的元組主指針或元組指針，然后

7、通過元組指針直接在查詢的基表中查找元組，選擇操作的實(shí)現(xiàn)(續(xù))；示例1-C2中為C2，Sno200215121，然后在b樹的順序集中，作為起點(diǎn)，sag20的所有元組指針將通過此元組指針在student表中搜索所有大于20的學(xué)生。選擇作業(yè)實(shí)現(xiàn)(續(xù))，示例1-C4，SdeptCS AND Sage20，Sdept和Sage都有索引：分別查找算法1: SdeptCS的一組元組指針和sag20的另一組元組指針。查找從這兩組指針的交集到學(xué)生表的計(jì)算機(jī)系統(tǒng)年齡大于20的學(xué)生搜索算法2: student表的sdepts的元組指針集。通過此元組指針，確保其他選擇條件(如sag20)將滿足條件的元組輸出到結(jié)果，以

8、獲取到student表的結(jié)果元組結(jié)果。第二，連接操作的實(shí)現(xiàn)，這是查詢處理中最耗時(shí)的任務(wù)之一，在本節(jié)中，對(duì)等連接(或自然連接)最常用的實(shí)現(xiàn)算法示例2 SELECT * FROM Student，SC WHERE Student。Sno=SC。Sno；實(shí)施連接操作(續(xù))，1 .巢狀回圈方法2。(nested loop method)。排序-合并方法(sort-merge join或merge join) 3。索引聯(lián)合方法4。Hash Join方法、連接操作的實(shí)現(xiàn)(續(xù))、嵌套循環(huán)方法(nested loop)通過為外部循環(huán)(Student)中的每個(gè)元組(s)檢索內(nèi)部循環(huán)(sc)中的每個(gè)元組(SC)來

9、實(shí)現(xiàn)這兩個(gè)元組如果滿足連接條件，線程將輸出到結(jié)果，直到處理了外部循環(huán)表的元組(續(xù))，2。排序-如果已排序連接的表(sort-merge join或merge join)，則排序合并連接方法的步驟：如果已連接的表未排序，則首先按連接屬性Sno對(duì)Student表和SC表排序，然后掃描SC表中具有相同Sno的元組。實(shí)施連接操作(繼續(xù))、實(shí)施連接操作(繼續(xù))、排列連接方法(繼續(xù)):當(dāng)Sno掃描另一個(gè)SC元組時(shí)，返回到Student表，掃描下一個(gè)元組，然后掃描SC表中具有相同Sno的元組，重復(fù)以上步驟，直到Student表掃描完成(繼續(xù))、實(shí)施連接操作索引聯(lián)接方法步驟：在SC表中為屬性Sno創(chuàng)建索引，如

10、果原始Student中的每個(gè)元組沒有索引，則Sno值將通過SC的索引查找相應(yīng)的SC元組，然后循環(huán)瀏覽相應(yīng)的SC元組和Student元組，直到處理了Student表中的元組，從而實(shí)現(xiàn)連接操作(續(xù))，4 .Hash Join方法將連接屬性用作Hash代碼。將r和s的元組以相同散列函數(shù)散列到相同散列文件的步驟：拆分步驟：包含較少元組的表的迭代處理hash函數(shù)，散列表的桶導(dǎo)航步驟(probing phase):又處理另一個(gè)表(s)(也稱為組合步驟)時(shí)，s的元組會(huì)散列到相應(yīng)的hash桶中。其中，hash join算法的工作方式是連接與r中的所有元組匹配的元組，假設(shè)兩個(gè)表中的較小表在第一步之后可以完全放在

11、內(nèi)存中hash桶的上面。第九章關(guān)系系統(tǒng)和查詢優(yōu)化，9.1關(guān)系數(shù)據(jù)庫系統(tǒng)的查詢處理9.2關(guān)系數(shù)據(jù)庫系統(tǒng)的查詢優(yōu)化9.3代關(guān)系數(shù)據(jù)庫系統(tǒng)的查詢優(yōu)化9.4對(duì)象優(yōu)化9.5小節(jié)點(diǎn)，9.2關(guān)系數(shù)據(jù)庫系統(tǒng)的查詢優(yōu)化，查詢優(yōu)化在關(guān)系數(shù)據(jù)庫系統(tǒng)中提供了非常重要的狀態(tài)關(guān)系查詢優(yōu)化，這是影響RDBMS性能的關(guān)鍵因素。關(guān)系系統(tǒng)允許分析關(guān)系表達(dá)式中的查詢語義，從而提供了執(zhí)行查詢優(yōu)化的可能性。查詢優(yōu)化概覽(續(xù))，查詢優(yōu)化的優(yōu)點(diǎn)在于，用戶不必考慮如何最好地表示查詢以獲得更好的效率，如果系統(tǒng)比用戶程序的優(yōu)化更好，(1)優(yōu)化程序可以從數(shù)據(jù)字典中獲取很多統(tǒng)計(jì)信息，但是用戶程序很難獲取這些信息，(2)數(shù)據(jù)庫的物理統(tǒng)計(jì)信息發(fā)生變化時(shí)

12、，可以自動(dòng)重新調(diào)整查詢，選擇合適的執(zhí)行計(jì)劃。在鄭智薰關(guān)系系統(tǒng)中，程序需要重寫，而重寫程序在實(shí)際應(yīng)用程序中的可能性往往很小。查詢優(yōu)化概述(續(xù))，(3)優(yōu)化程序可以考慮數(shù)百種不同的執(zhí)行計(jì)劃，程序員通常只能考慮一些可能性。(4)優(yōu)化程序往往包含很多復(fù)雜的優(yōu)化技術(shù)，只有最好的程序員才能掌握。系統(tǒng)的自動(dòng)優(yōu)化相當(dāng)于讓每個(gè)人都查看查詢優(yōu)化概覽(繼續(xù))，RDBMS通過某種成本模型計(jì)算各種查詢執(zhí)行策略的執(zhí)行成本。然后選擇最低成本的執(zhí)行方案中央數(shù)據(jù)庫執(zhí)行開銷主要是磁盤訪問塊數(shù)(I/O成本)處理器時(shí)間(CPU成本)查詢的內(nèi)存開銷I/O成本最重要的分布式數(shù)據(jù)庫的總成本=I/O成本CPU成本內(nèi)存成本通信成本、查詢優(yōu)化概

13、覽(續(xù))、查詢優(yōu)化的總目標(biāo)：通過選擇有效策略給出的關(guān)系用SQL表示：SELECT Student。Sname FROM Student，sc where Student . SnO=sc . SnO and sc . cno=2；學(xué)生-假定學(xué)科課程數(shù)據(jù)庫中有1，000個(gè)學(xué)生記錄，1，000個(gè)選項(xiàng)記錄中選項(xiàng)2的選項(xiàng)記錄為50個(gè)(續(xù))，Q1=sname(student . SnO=sc . snosc . cn o=2(student sc)計(jì)算廣泛的笛卡爾乘積如何連接student和sc的每個(gè)元組。從內(nèi)存中加載一個(gè)表(如student表)的多個(gè)塊，并保留另一個(gè)表(如sc表)的一個(gè)元組。在處理SC

14、表之前，將SC中的每個(gè)元組和Student中的每個(gè)元組連接填充一片，然后從SC中讀取一片和內(nèi)存中的Student元組連接。在處理Student表之前，讀取多個(gè)Student元組；一個(gè)實(shí)例(續(xù))、一個(gè)塊可以包含10個(gè)Student元組或100個(gè)SC元組；讀取SC元組直到內(nèi)存包含5個(gè)Student元組和1個(gè)SC元組，因此總塊數(shù)為=100 20100=2100塊其中讀取Student表100塊。讀20次SC表，每次讀100個(gè)。每秒讀取和寫入20塊時(shí)，使用連接到105s的元組數(shù)，直到10304=107。每個(gè)設(shè)置可以安裝10個(gè)元組，106/20=5104s，讀取表，寫入文件，實(shí)例(續(xù))，2。為選擇操作依

15、次讀取相關(guān)聯(lián)的元組，根據(jù)選擇條件，假定滿足要求的記錄選擇會(huì)忽略內(nèi)存處理時(shí)間。讀取中間文件所用的時(shí)間(相當(dāng)于寫入中間文件)假定5104s只有50個(gè)元組符合條件，一個(gè)實(shí)例(繼續(xù))，3 .投影操作將步驟2中的結(jié)果投影到Sname，在最終結(jié)果第一種情況下運(yùn)行查詢所用的總時(shí)間105 25104105s所有內(nèi)存處理時(shí)間都將被忽略，無論一個(gè)實(shí)例是什么。第二，在第二種情況下，Q2=Sname(Sc .cno=2(Student SC)1。計(jì)算自然連接、執(zhí)行自然連接和讀取Student和SC表的策略保持不變，使用105 s自然連接(總讀取塊數(shù)仍為2100塊)的結(jié)果比第一種情況明顯減少。寫入這些元組中的104個(gè)時(shí)，使用104/10/20=50s，第一個(gè)時(shí)的千分之一2。讀取中間文件塊和執(zhí)行選擇操作所需的時(shí)間為50s。將步驟2的結(jié)果投影到輸出。第二個(gè)方案的總運(yùn)行時(shí)間105 50 505050505005s，一個(gè)實(shí)例(續(xù))，第三個(gè)，第三個(gè)方案的Q