關(guān)系查詢處理和查詢優(yōu)化

第九章關(guān)系查詢處理和查詢優(yōu)化查詢處理與優(yōu)化如何以有效的方式處理用戶查詢是RDBMS有效實現(xiàn)的關(guān)鍵問題之一數(shù)據(jù)庫的更新運(yùn)算要么是簡單的（如插入一個元組），要么與一個復(fù)雜的更新條件相關(guān)聯(lián)（如刪除滿足某些條件的元組）復(fù)雜的更新首先需要找到要更新的元組，然后才能進(jìn)行更新。因此，只有能夠有效地處理查詢，才能有效地實現(xiàn)更新查詢處理的中心任務(wù)是把使用諸如SQL這樣的說明性語言表達(dá)的用戶查詢轉(zhuǎn)換成一系列能夠在物理文件上執(zhí)行的操作，并執(zhí)行這些操作得到查詢結(jié)果查詢優(yōu)化是查詢處理的關(guān)鍵步驟，它從眾多的查詢執(zhí)行方案中選擇最有效的執(zhí)行方案關(guān)系查詢處理和查詢優(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小結(jié)9.1關(guān)系數(shù)據(jù)庫系統(tǒng)的查詢處理9.1.1查詢處理步驟9.1.2實現(xiàn)查詢操作的算法示例9.1.1查詢處理步驟RDBMS查詢處理過程查詢分析查詢檢查查詢優(yōu)化查詢執(zhí)行圖9.1查詢處理步驟9.1.1查詢處理步驟（續(xù)）查詢分析：

進(jìn)行詞法分析、語法分析和語義分析詞法分析從查詢語句中識別出語言符號，如SQL的保留字、關(guān)系名、屬性名和各種運(yùn)算符等其他符號語法分析檢查用戶查詢語句的語法格式，確保查詢語句語法上的正確性語義分析可以與語法分析同時進(jìn)行，將查詢轉(zhuǎn)換成更適合進(jìn)一步處理的內(nèi)部表示9.1.1查詢處理步驟（續(xù)）查詢檢查根據(jù)數(shù)據(jù)字典對合法的查詢語句進(jìn)行語義檢查根據(jù)數(shù)據(jù)字典中的用戶權(quán)限和完整性約束定義對用戶的存取權(quán)限進(jìn)行檢查檢查通過后把SQL查詢語句轉(zhuǎn)換成等價的關(guān)系代數(shù)RDBMS一般都用查詢樹，也稱語法分析樹，來表示擴(kuò)展的關(guān)系代數(shù)表達(dá)式把數(shù)據(jù)庫對象的外部名稱轉(zhuǎn)換成內(nèi)部表示9.1.1查詢處理步驟（續(xù)）查詢檢查——查詢樹例9.1找出提供了P001號零件的供應(yīng)商名稱SELECTSnameFROMSuppliers,SPWHERESuppliers.Sno=SP.SnoANDPno=‘P001’;轉(zhuǎn)換成下圖9.2所示的語法樹，或者轉(zhuǎn)換成如下關(guān)系代數(shù)表達(dá)式：Q1：πSname(Suppliers.Sno=SP.SnoPno='P001'(Suppliers×SP))Suppliers.Sno=SP.Sno

Pno=‘P001’SuppliersSPSname圖9.2一棵語法分析樹9.1.1查詢處理步驟（續(xù)）查詢優(yōu)化一個給定的查詢有多種可能的執(zhí)行策略例如，例9.1的查詢也可以用如下關(guān)系代數(shù)表達(dá)式計算：Q2：πSname(

Pno='P001'(SuppliersSP))Q3：πSname(SuppliersPno='P001'(SP))每個基本運(yùn)算也可以有多種不同的實現(xiàn)算法一個查詢執(zhí)行計劃包括計算查詢的關(guān)系代數(shù)表達(dá)式和其中每個基本運(yùn)算的實現(xiàn)算法查詢優(yōu)化就是從多種可能的查詢執(zhí)行方案中選擇一種最有效執(zhí)行的查詢執(zhí)行計劃的過程對于相同的查詢，不同的查詢執(zhí)行計劃的時間開銷可能相差幾個數(shù)量級例如，使用Q1計算例9.1的查詢的I/O開銷大約是使用Q3的2000倍9.1.1查詢處理步驟（續(xù)）按照優(yōu)化層次分為代數(shù)優(yōu)化和物理優(yōu)化代數(shù)優(yōu)化vs物理優(yōu)化代數(shù)優(yōu)化：找到一個與給定的查詢表達(dá)式等價、但執(zhí)行起來更加有效的關(guān)系代數(shù)表達(dá)式物理優(yōu)化：為關(guān)系代數(shù)表達(dá)式選擇一個詳細(xì)的策略，包括為特定的操作選擇可用的算法（底層操作算法），選擇可用的索引（存取路徑）等基于規(guī)則的優(yōu)化vs基于代價的優(yōu)化基于規(guī)則的優(yōu)化：根據(jù)某些啟發(fā)式規(guī)則，通過關(guān)系代數(shù)的等價變換，得到更有效的關(guān)系代數(shù)表達(dá)式；或者根據(jù)某些啟發(fā)式規(guī)則選擇實現(xiàn)基本運(yùn)算的算法基于代價的優(yōu)化：利用元數(shù)據(jù)中的統(tǒng)計信息，估計不同的查詢執(zhí)行計劃的開銷，從中選擇最優(yōu)方案9.1.1查詢處理步驟（續(xù)）

查詢執(zhí)行執(zhí)行引擎依據(jù)優(yōu)化器得到的查詢執(zhí)行計劃生成執(zhí)行查詢計劃的代碼，執(zhí)行該代碼產(chǎn)生查詢結(jié)果，并以適當(dāng)?shù)男问教峤挥脩舨樵儓?zhí)行之前還要進(jìn)行安全性檢查，確保執(zhí)行查詢的用戶必須具有相應(yīng)的訪問權(quán)限。任何違反安全性限制的查詢都將被拒絕對于數(shù)據(jù)庫的更新操作，除了安全性檢查之外，還需要進(jìn)行完整性檢查9.1.1查詢處理步驟（續(xù)）查詢代價的估計為了優(yōu)化查詢，優(yōu)化器必須知道每個基本運(yùn)算的代價，進(jìn)而估計查詢執(zhí)行計劃的代價精確地估計代價是困難的，但是粗略的估計是可能的，并且這種粗略估計可以很好地反映不同查詢計劃的相對優(yōu)劣查詢代價包括CPU代價、I/O代價和內(nèi)存代價在分布式數(shù)據(jù)庫系統(tǒng)或并行數(shù)據(jù)庫系統(tǒng)中，查詢代價還包括通信代價本章，我們只考慮集中式系統(tǒng)內(nèi)存代價用查詢處理所需的內(nèi)存量度量最壞的情況：內(nèi)存緩沖區(qū)只能容納數(shù)目不多的數(shù)據(jù)塊——大約每個關(guān)系一塊或幾塊9.1.1查詢處理步驟（續(xù)）CPU代價用查詢所需的CPU時間度量磁盤存取比內(nèi)存操作慢，并且隨著硬件技術(shù)的發(fā)展，CPU速度的提高也比磁盤速度的提高快得多因此磁盤I/O一直是制約查詢處理速度提高的瓶頸通常，I/O代價被認(rèn)為是估計查詢處理代價的合理度量I/O代價包括磁盤尋道時間、旋轉(zhuǎn)延遲時間和實際的數(shù)據(jù)傳輸時間磁盤尋道時間和旋轉(zhuǎn)延遲時間依賴于磁頭的當(dāng)前位置，難以精確估計可以假定每個磁盤塊的讀寫大致需要相同的平均尋道時間和旋轉(zhuǎn)延遲時間I/O代價可以用磁盤讀寫塊數(shù)近似地估計9.1.1查詢處理步驟（續(xù)）表達(dá)式計算代價評估的統(tǒng)計信息DBMS的數(shù)據(jù)字典中存儲并維護(hù)了關(guān)于數(shù)據(jù)庫關(guān)系的如下統(tǒng)計信息nr：關(guān)系r的元組數(shù)br：包含關(guān)系r的塊數(shù)lr：關(guān)系r的元組長度（字節(jié)數(shù)）V(r,A)：關(guān)系r在屬性A上的不同值數(shù)目在查詢中經(jīng)常同時出現(xiàn)的屬性集上，也有類似的統(tǒng)計量fr：關(guān)系r的塊因子，即一塊能夠容納關(guān)系r的元組數(shù)當(dāng)r存儲在一個物理文件中時，br=nr/fr關(guān)系r的哪些屬性（集）上建立了索引，哪種索引（B+樹索引、Hash索引、聚集索引B+樹索引包括屬性A上B+樹高度h(r,A)B+樹葉節(jié)點(diǎn)數(shù)l(r,A)等信息9.1關(guān)系數(shù)據(jù)庫系統(tǒng)的查詢處理9.1.1查詢處理步驟9.1.2實現(xiàn)查詢操作的算法示例9.核1.懇2斃實現(xiàn)拋查詢劉操作姨的算幕法示漿例查詢稠最常晚用的抹運(yùn)算版是選柴擇、哀投影固和連閥接投影烏運(yùn)算紫的實堤現(xiàn)是歐簡單番的通常紀(jì)投影服可以殃并入舅其他拾步驟重點(diǎn)臂討論選擇與連接選擇技操作劑的實苦現(xiàn)[例呆1]既se板le裹c(diǎn)t鼓*寇f孟ro映m坦st花ud稻en堡t伴wh撞er對e岸<條叼件表勿達(dá)式榜>：考慮賢<條升件表勞達(dá)式生>的關(guān)幾種栗情況錄：C1垂：無扔條件晶；C2僵：s矩no奏='吃20汽02跡15鼓12壺1'改；C3頓：s憲ag慎e>挨20南;C4邊:影sd摟ep役t=染'C開S'抓A社ND俱s恐ag剃e>擺20選擇爭操作憶的實突現(xiàn)（懲續(xù)）選擇南操作包典型鉗的實耗現(xiàn)方器法1.界簡單項的全隱表掃犬描方后法對查婦詢的沾基本番表順孤序掃矛描，因逐一吩檢查籍每個基元組園是否肆滿足篇選擇建條件字，把段滿足期條件等的元械祖作右為結(jié)擋果輸昏出適合斧小表償，或真者滿足哪選擇窩條件杠的元踩組所丘占比遠(yuǎn)例較是大2.逢索引壯（散證列）絡(luò)掃描志方法適合然選擇賤條件茂中屬逆性有戶索引持（例偵如B低+樹脆索引扮或者陵ha而sh唉索引榨）通過兼索引否先找擴(kuò)到滿嫂足條食件的扭元組財主碼晉或元筆組指壩針，握再通樹過元辦組指禮針直談接在伏查詢譯的基惕本表賀中找喬到元測組選擇酷操作羊的實顆現(xiàn)（堤續(xù)）[例薄1-召C2槳]以煎C2忙為例胖，s舊no拔='私20攜02多15功12往1'后，并華且在億sn類o上尸有索耀引（這或s迷no捎是散誰列碼抽），宣則可輪以使眾用索衣引（郊或散解列碼拒）得帆到s袍no嗎為'形20甲02扛15體12湊1'陪元組謙的指蕩針，驅(qū)然后少通過巨元組輩指針憤在s銀tu盜de智nt注表中坐檢索眠到該邀學(xué)生[例茅1-跪C3戚]以趴C3唯為例拖，s先ag按e>嘆20物，并脅且在瞧sa鈔ge宮上有抽B+足樹索燦引，明則可溪以使聾用B廚+樹袖索引態(tài)找到靠sa刪ge同=2液0的調(diào)索引魯項，惹以此良為入泰口點(diǎn)繭在B種+樹如的順去序集勒上得炸到s描ag沉e>哨20遠(yuǎn)的所溫有元援組指致針，宋然后引通過臭這些堡元組耗指針斷到s崗tu姑de燈nt被表中被檢索測到所望有年纖齡大珠于2捐0的炭學(xué)生[例破1-芳C4木]以謝C4灶為例我，s欠de牽pt攔='產(chǎn)CS旋'a梳nd損s挽ag漢e>疲20坐，如賤果s蒼de我pt諸和s四ag賤e上糧都有臨索引緩，那炒么其盈中一子種算聚法是必：分甩別用潔上面丘兩種植方法攀分別荒找到啊sd非ep討t=聲'C栽S'巖的一仙組元參組指孕針和當(dāng)sa匹ge招>2磁0的貍另一重組元替組指鳳針，違求這敘2組獸指針權(quán)的交的集，經(jīng)再到緣瑞st香ud革en泥t表石中檢畜索，舟就得貼到計紫算機(jī)尼系年興齡大容于2列0的執(zhí)學(xué)生牙；另冊一種鴿算法廟：找背到s味de啄pt偵='杠CS句'的悶一組秧元組取指針雖，通嗓過這庫些元別組指抱針到芳st慕ud告en猛t表吉中檢槽索，女并對棵得到撞的元涌組檢醫(yī)查另赤一些毫選擇潮條件固（如旅sa井ge奴>2蔥0）轉(zhuǎn)是否家滿足天，將彩滿足蟻條件住的元尚組作芝為結(jié)欄果輸表出連接芽操作謙的實晚現(xiàn)連接川操作齊是查乳詢處網(wǎng)理中讀最耗哥時的五操作灶之一本章帝只討授論等嶼值連默接（舌或自踢然連異接）每最常頑用的揉實現(xiàn)派算法[例另2]帆S架EL早EC濱T跳*純FR述OM向S矩tu頁de晴nt扣,S繡CWH被ER親E抱St釘ud路en因t.氧Sn底o(hù)=稿SC集.S倘no1.蘇嵌套率循環(huán)蜂方法目（n西es薪te羨d法lo戀op送）2.度排序扣-合數(shù)并方滑法（僵so魚rt印-m館er監(jiān)ge怕j昆oi避n或舒me誼rg鉤e集jo撿in蘇）3.齡索引貢連接星（i護(hù)nd智ex鏟j匠oi待n）游方法4.余Ha橫sh氣J燙oi狠n方穗法連接堡操作恢的實堆現(xiàn)（偷續(xù)）1.求嵌套主循環(huán)點(diǎn)方法對外膨?qū)友矇郗h(huán)（挪St怕ud昆en精t）孔的每礎(chǔ)一個艘元組阻（s遙），著檢索諒內(nèi)層娘循環(huán)?。⊿琴C）傾中的捎沒一迷個元夾組（扮sc曬）檢查從這兩墾個元彼組在潮連接危屬性趕（s僚no體）上析是否遠(yuǎn)相等如果膝滿足而連接督條件填，則刷串接萍后作脾為結(jié)泊果輸膀出，吩直到振外層獎循環(huán)偵表中愉的元改組處局理完困為止連接印操作靜的實乘現(xiàn)（帝續(xù)）2.犧排序戴-合場并方松法（輔so溉rt妹-m參er削ge芹j潮oi骨n或滔me最rg奧e耀jo祖in鵝）如果資進(jìn)行燙連接辮的兩脖個關(guān)愉系r和s在連版接屬驅(qū)性上帳是有賓序的饞，則英可以踩使用策歸并岔連接與兩割個有享序文好件歸警并類霸似排序妙-合寶并連肉接方盲法的磁步驟幅：1.駕如果傷連接海的表席沒有漸排好意序，遲首先吵對S桿tu售de串nt肆表和說SC殃表按本連接基屬性壤Sn應(yīng)o排講序2.夏取S散tu始de孟nt殖表中旬第一合個S出no溜，依仿次掃妻描S逼C表常中具撇有相堪同的織Sn荷o的望元組樣；把枝它們密連接翅起來篩（如農(nóng)圖所束示）3.培當(dāng)掃躲描到事Sn渣o不屠同的斤第一腔個S濃C元月組時跡，返個回S反tu昆de誤nt犯表掃避描它石的下筆一個假元組什，再伶掃描狼SC沃表中伍具有晚相同奇的S凝no拖元組瞧，把木它們飽連接掌起來重復(fù)弱上述鏟步驟釋直到違St鍋ud順en閉t表塑掃描朋完連接皺操作芝的實孩現(xiàn)（鉗續(xù)）200215121200215122200215123200215124...200215121192200215121285200215121388200215122290200215122380...排序-合并連接方法示意圖連接裕操作怠的實動現(xiàn)（寬續(xù)）St墾ud插en溫t表鈴和S刻C表有都只習(xí)需要蹈掃描嘗一遍如果變2個置表原原來無傘序，氣執(zhí)行事時間衰要加郊上對淹兩個窩表的域排序墊時間對于忌兩個般大表訓(xùn)，先蛾排序善后使匪用s蒙or盆t-爬m(xù)e語rg輕e緞jo黨in話方法夸執(zhí)行皮連接勞，總戚的執(zhí)雕行時銹間一件般仍半會大失大地鬼減少連接圓操作兼的實娃現(xiàn)（科續(xù)）3.侍索引宰連接寇（i拌nd配ex售j激oi逆n）中方法步驟慎：1.子在S舞C表鹽上建膛立屬晚性S模no聚索引裹，如肅果原羊來沒但有的使話2.銜對S翠tu義de伯nt踢中每贏一個拾元組眠，由朵Sn瓣o值燙通過瓶SC嗓的索輛引查已找相忘應(yīng)的巖SC菊元組3.駝把這劑些S殿C元鴨組和浮St疤ud鳳en度t連錢接起鄰來循環(huán)帳執(zhí)行載2、慢3步讀，直艇到S以tu良de農(nóng)nt輔表中抱的元濁組處般理完信為止連接票操作裂的實珍現(xiàn)（同續(xù)）4.描Ha斃sh會J洽oi孩n方個法把連情接屬撓性作冊為h狀as偷h碼奮，用舟同一指個h優(yōu)as火h函握數(shù)把鬧R和污S中雪的元掙組散周列到奧同一因個h朝as胳h文障件中步驟朝：劃分吹階段匪（p射ar舒ti球ti矮on超in完g押ph絕as規(guī)e）矛：對包框含較語少元口組的弄表（脅比如變R）那進(jìn)行理一遍登處理把它聽的元犧組按哈ha貍sh秧函數(shù)創(chuàng)分散昂到h泡as載h表府的桶孔中試探楊階段儲（p影ro騾bi本ng牧p賊ha桐se社）：報也稱旦為連懶接階默段（藝jo趁in撇p摩ha缺se潛）對另襲一個手表（息S）薦進(jìn)行村一遍叛處理把S如的元冒組散知列到歲適當(dāng)季ha折sh憐桶中并把岔元組氣與桶翻中所光有來子自R襖并與輪之相蓋匹配餃的元窯組連稿接起鬼來該算頭法的外前提遼是假的設(shè)這平兩個廢表中膽較小眉的表距在第鉤一階紙段后烏可以賀完全劫放入階內(nèi)存上的h弦as電h桶暈中該算款法思填想可杜以推蠢廣到菊更加焰一般勿的多避個表違的連汁接算廚法上關(guān)系酷查詢恐處理烈和查伯詢優(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俘小結(jié)9.拴2焰關(guān)系緊數(shù)據(jù)存庫系親統(tǒng)的喜查詢辮優(yōu)化查詢淘優(yōu)化矩在關(guān)范系數(shù)團(tuán)據(jù)庫刃系統(tǒng)圣中有密著非庭常重庫要的緒地位盞，是催影響遙RD綿BM灑S性漠能的史關(guān)鍵絨因素非關(guān)蔬系系墾統(tǒng)用戶剖使用離過程炒化的掩語言鴿表達(dá)奪查詢無要求執(zhí)行妖何種持操作帳，以濤及操射作的匯序列與都是戒由用顆戶來盟決定握的系統(tǒng)頌為用們戶提毯供選外擇存呆取路顯徑的峽手段育，而目用戶膏必須職了解繁存取門路徑端，為畏自己估的查揀詢選扶擇合聚適的傲存取麥路徑對于救關(guān)系慘數(shù)據(jù)嶺庫系記統(tǒng)，悲查詢屋優(yōu)化皺是機(jī)沉遇，眉也是烏挑戰(zhàn)用戶墨只需煉要說心明做釋什么店，而鬧不必廈說明徑怎么荒做。味這就廁為查毀詢優(yōu)素化提日供了域更大荷的空突間，鑼使得縣系統(tǒng)篩可以住分析冷查詢穴語義邀，選活擇最極佳的平查詢振處理蹲方案為了耽使查擋詢處件理速超度達(dá)允到用沈戶可銷以接標(biāo)受的夜水平床，R誼DB族MS堆必須析使用炭優(yōu)化世技術(shù)弄，并豪且為液查詢碗選擇鄉(xiāng)豐一種撐最佳嘉的執(zhí)鳥行方湊案也設(shè)并非駐一件永易事9.騎2密關(guān)系改數(shù)據(jù)衛(wèi)庫系板統(tǒng)的領(lǐng)查詢江優(yōu)化莊（續(xù)醋）9.避2.像1熔查詢犁優(yōu)化臟概述9.鄉(xiāng)豐2.籠2羞一個冶實例9.弓2.粒1掙查詢捏優(yōu)化嘆概述查詢枕優(yōu)化鐵的優(yōu)掘點(diǎn)不灶僅在忍于用扣戶不衡必考典慮如始何最熔好地咱表達(dá)殖查詢衡以獲雄得較妙好的剩效率講，而算且在謎于系膏統(tǒng)可帖以比慨用戶露程序藥的“懇優(yōu)化彈”做際的更盆好，蘋原因種：1.艙優(yōu)化賤器可湊以從廈數(shù)據(jù)妙字典腔中獲制取許砍多統(tǒng)浸計信貞息，輔例如傘：每椒個關(guān)鑒系表愧中的女元組傘數(shù)、制關(guān)系榮中每繼個屬知性值厲的分瓜布情謠況、辱哪些餓屬性脊上已潛經(jīng)建趙立了撫索引喝等。靈優(yōu)化秒器可礎(chǔ)以根勺據(jù)這口些信清息作屢出正即確的慨估算游，選中擇高槽效的叢執(zhí)行墻計劃彼，而日用戶曬程序宇則難榜以獲僻得這同些信拋息2.豈如果債數(shù)據(jù)侮庫的羽物理堆統(tǒng)計垃信息恩改變仰了，沾系統(tǒng)投可以誕自動娛對查撓詢進(jìn)黎行重炊新優(yōu)者化以筆選擇曠相適妹應(yīng)的獨(dú)執(zhí)行隆計劃張。在降非關(guān)置系系唉統(tǒng)中恐必須冒重寫信程序幅，而元重寫抗程序溜在實宵際應(yīng)賀用中追往往釋是不蝕太可阿能的9.可2.佩1米查詢園優(yōu)化海概述逢（續(xù)新）3.巧優(yōu)化極器可跪以考溪慮數(shù)箭百種蝴不同合的執(zhí)夫行計握劃，厘而程交序員鼻一般尖只能羨考慮離有限鑄的幾趣種可撇能性4.違優(yōu)化頑器中老包括孕了很舍多復(fù)粉雜的宅優(yōu)化漠技術(shù)越，這貨些優(yōu)烘化技冒術(shù)往搏往只慚有最已好的角程序避員才征能掌片握。袖系統(tǒng)螞的自渣動優(yōu)勾化相崖當(dāng)于脆使得匹所有折人都凝擁有蒜這些澤優(yōu)化桌技術(shù)查詢境優(yōu)化圣的總櫻目標(biāo)辦：選擇艘有效振的策賴略求得棄給定趨關(guān)系漠表達(dá)傍式的嚴(yán)值使得餓查詢否代價博最小險（實若際上紅是較啟小）9.控2鞠關(guān)系講數(shù)據(jù)祥庫系面統(tǒng)的嗚查詢饑優(yōu)化址（續(xù)街）9.介2.以1猶查詢兼優(yōu)化窮概述9.耳2.腸2放一個機(jī)實例9.既2.端2黑一個波實例[例千3]句求選瓶修2饅號課介程的敞學(xué)生守姓名秤，用全SQ負(fù)L表洪達(dá)：SE領(lǐng)LE著CT富S抱tu硬de泳nt殼.S須na劣meFR豆OM數(shù)S從tu當(dāng)de稅nt鋪，S咸CWH光ER蝕E票St疤ud神en動t.域Sn件o=片SC染.S餅no瞧A鐵ND外S冒C.藏Cn參o=最'2玩'假定厘學(xué)生達(dá)-課漠程數(shù)勸據(jù)庫殖中有拍10雄00西個學(xué)崖生記停錄，瞞10航00謹(jǐn)0個術(shù)選課間記錄其中寨選修箭2號供課程論的選嫌課記件錄為寬50川個9.百2.方2萄一個關(guān)實例咳(續(xù)鄉(xiāng)豐)系統(tǒng)崗可以玩用多形種等璃價的拖關(guān)系薯代數(shù)雷表達(dá)筑式完懂成這聽一查習(xí)詢Q1=πSn遣am淋e(σSt詠ud踏en揪t.廉Sn垂o=響SC除.S潮no秋∧S濱c.弱Cn若o=攻'2約'(S返tu連de止nt貸×S縫C)吼)Q2=πSn催am矩e(σSc斬.C挨no泛='受2'(S怎tu例de匪nt柿S雹C)辜)Q3=πSn即am桑e(S飾tu刪de劣ntσSc泰.C曬no政='穗2'(S肌C)背)9.墓2.死2秩一個叔實例莖(續(xù)坡)一、梳第一反種情優(yōu)況Q1=πSn黃am股e(σSt萍ud攔en拖t.型Sn蛙o=加SC尚.S欠no夫∧S伯c.鞋Cn毯o=跡'2倘'St潤ud浮en嫂t×愁SC涼))1.榆計算栗廣義伍笛卡吹爾積把S懇tu臉de攪nt津和S枕C的內(nèi)每個繩元組位連接鼠起來甩的做彼法是己：在內(nèi)挑存中祖盡可豈能多選地裝針入某迷個表姥(如店St螺ud茫en高t表鍋)的毫若干嘩塊，呀留出芳一塊久存放沸另一低個表早(如清SC郊表)華的元捆組把S壺C中危的每莖個元示組和鴿St振ud錦en痛t中熱每個彎元組癢連接優(yōu)，連神接后支的元舍組裝藥滿一怒塊后括就寫疼到中凝間文漢件上從S俗C中戀讀入去一塊這和內(nèi)養(yǎng)存中侮的S詞tu攀de蒜nt故元組舞連接允，直牢到S血C表乞處理錘完再讀烘入若絲式干塊田St鈴ud眾en酒t元糊組，劣讀入旺一塊燈SC判元組重復(fù)尿上述箭處理敘過程徹，直叔到把元St渡ud野en柿t表捐處理淋完9.芹2.驗2穗一個繳實例鑼(續(xù)示)設(shè)一具個塊代能裝蠶10租個S稻tu翅de散nt疾元組稼或1德00克個S屯C元榴組，度在內(nèi)喝存中應(yīng)存放似5塊厚St商ud您en列t元訂組和跌1塊饅SC館元組倚，則員讀取銷總塊鹽數(shù)為讀取謊總塊閱數(shù)=讀St貫ud塊en黑t表塊搜數(shù)+讀SC表遍腐數(shù)*遠(yuǎn)每遍窗塊數(shù)其中熔，讀恨St椒ud穗en笑t表話10腫0塊像。讀吹SC倒表2雖0遍單，每倘遍1衛(wèi)00續(xù)塊。奏若每宿秒讀瘦寫2秩0塊降，則禍總計托要花則10六5s連接餡后的坦元組甲數(shù)為證103×1怨04=1貝07。設(shè)劍每塊特能裝辦10儲個元坡組，夕則寫繡出這快些塊殼要用催106/2譽(yù)0=狹5×隆104s9.炸2.弓2器一個暑實例嚷(續(xù)誕)2.弦作選革擇操看作依次賤讀入恥連接慘后的予元組尖，按泳照選哄擇條偽件選饞取滿般足要能求的薯記錄假定皂內(nèi)存稱處理嶼時間計忽略壇。讀蕩取中史間文橫件花沙費(fèi)的窄時間裳(同圖寫中寸間文填件一恥樣)催需5歉×1條04s滿足五條件秘的元堡組假作設(shè)僅顧50身個，統(tǒng)均可疊放在栗內(nèi)存3.遠(yuǎn)作投泉影操企作把第菜2步胃的結(jié)描果在毅Sn閣am腦e上渣作投含影輸臺出，率得到睛最終帖結(jié)果第一兵種情余況下盛執(zhí)行垃查詢否的總浙時間樹≈1側(cè)05李+2方×5構(gòu)×1煌04≈1顯05s所有詳內(nèi)存攀處理便時間獎均忽敗略不迅計9.賓2.慎2腸一個湖實例趟(續(xù)彎)二、湊第二灶種情子況Q2=πSn貌am俯e(σSc符.C子no究='見2'(S留tu班de咽nt蚊S喬C)鹽)1.潮計六算自蘆然連慎接執(zhí)行吵自然介連接并，讀瞧取S挎tu餡de某nt庸和S展C表慶的策敞略不劈燕變，飾總的案讀取急塊數(shù)崗仍為救21戀00屬塊花腫費(fèi)1罰05號s自然師連接激的結(jié)舟果比偵第一善種情惰況大貿(mào)大減祥少，葬為1輔04個寫出且這些振元組幸時間咽為1群04/1垮0/臭20售=5輛0s補(bǔ)，為村第一度種情命況的赴千分壯之一2.犬讀筑取中婆間文謀件塊，執(zhí)譽(yù)行選慣擇運(yùn)跪算，喜花費(fèi)鵝時間乖也為距50稻s。3.勸把走第2足步結(jié)奪果投粱影輸磚出。第二營種情姻況總窯的執(zhí)牛行時牲間≈狗10弊5+至50慚+5遷0≈厘20猾5s9.旬2.越2粒一個夢實例瞇(續(xù)煙)三、跳第盡三種劉情況Q3=πSn現(xiàn)am爽e(S會tu被de尊nt惑σSc煉.C陵no底='磁2'(S艦C)覺)1.先對腥SC來表作膀選擇雜運(yùn)算，只儲需讀黑一遍陳SC效表，元存取躁10觸0塊裙花費(fèi)劣時間塞為5結(jié)s，乎因為掘滿足厚條件驚的元啟組僅礙50暖個，哄不必贏使用吸中間扣文件添。2.讀取褲St飛ud模en辜t表，把輪讀入啄的S牙tu侍de泳nt勺元組佩和內(nèi)膨存中的的S針C元桃組作斗連接遇。也沈只需建讀一子遍S學(xué)tu際de襯nt桶表共蹈10棄0塊佛，花她費(fèi)時糊間為5s。3.把連愁接結(jié)固果投筐影輸儉出第三攜種情猾況總姿的執(zhí)淡行時灰間≈嚼5+材5≈10詞s9.四2.份2送一個遵實例巨(續(xù)濁)假如哥SC維表的蠻Cn臥o字甲段上飄有索去引第一靈步就羅不必售讀取院所有鋪的S先C元逆組而憶只需講讀取鞏Cn柜o=侮‘2凈’的桶那些翁元組蕉(5恭0個芽)存取木的索憂引塊找和S玻C中詳滿足禽條件康的數(shù)者據(jù)塊汽大約糖總共設(shè)3～遙4塊若S閱tu煮de懇nt殊表在拔Sn疏o上愿也有合索引第二棉步也就不必羞讀取搜所有壯的S峰tu良de雁nt悄元組因為聲滿足曲條件找的S第C記鼠錄僅竭50既個，澆涉及馬最多凍50廟個S勞tu背de鹽nt誦記錄讀取連St約ud鍛en酷t(yī)表串的塊浸數(shù)也邀可大曉大減扛少總的傍存取戶時間鬼將進(jìn)粱一步澡減少惜到數(shù)素秒9.供2.李2買一個妄實例木(續(xù)到)把代乎數(shù)表賺達(dá)式Q1變換除為Q2、Q3，即有浴選擇肆和連良接操漿作時嚼，先做處選擇挺操作，這栗樣參似加連毅接的乳元組倡就可渣以大棚大減向少，返這是翼代數(shù)猛優(yōu)化在Q3中SC襲表的超選擇索操作陳算法吸有全曾表掃急描和遞索引獲掃描深2種煤方法恩，經(jīng)巖過初叛步估幸算，貌索引穗掃描托方法倚較優(yōu)對于妻St替ud打en肢t和梳SC栽表的脖連接企，利州用S惕tu淋de戚nt通表上虛的索蘋引，厭采用肝in拆de崗x白jo表in次代價住也較絮小，陶這就免是物駐理優(yōu)眼化關(guān)系恰查詢摩處理窩和查榜詢優(yōu)誓化9.如1舊關(guān)系堡數(shù)據(jù)橫庫系獨(dú)統(tǒng)的值查詢誓處理9.抄2昨關(guān)系愁數(shù)據(jù)帆庫系姻統(tǒng)的晨查詢海優(yōu)化9.滿3抽代數(shù)士優(yōu)化9.咐4派物理繪優(yōu)化9.文5駛小結(jié)9.圍3代數(shù)灘優(yōu)化9.扛3.茂1裹關(guān)系摩代數(shù)籮表達(dá)倡式等神價變疼換規(guī)疾則9.處3.陡2查趣詢樹找的啟暢發(fā)式背優(yōu)化9.夫3.讀1菌關(guān)系缺代數(shù)陷表達(dá)排式等削價變教化規(guī)回則代數(shù)卻優(yōu)化呈策略妻：通羊過對極關(guān)系攻代數(shù)鐮表達(dá)業(yè)式的籌等價禿變換恩來提掩高查棵詢效范率關(guān)系巡壽代數(shù)嗚表達(dá)烈式的矛等價使：指歡用相毒同的臂關(guān)系須代替擊兩個飲表達(dá)飯式中循相應(yīng)高的關(guān)絲式系所恒得到業(yè)的結(jié)嬌果是曠相同蓋的兩個刺關(guān)系而表達(dá)區(qū)式E1和E2是等爭價的叫，可登記為E1≡E29.捎3.齡1雪關(guān)系也代數(shù)未表達(dá)叛式等逗價變浪化規(guī)脫則（澡續(xù)）常用唐的等脅價變限換規(guī)嶺則：1.嬌連接丹、笛壩卡爾腫積交吹換律2.桃連行接、娘笛卡敗爾積半的結(jié)醉合律3.焰投墊影的禿串接粥定律4.奴選終擇的稼串接春定律5.驚選您擇與建投影亮操作源的交娃換律6.罵選淋擇與趕笛卡棋爾積留的交粱換律7.岡選待擇與何并的強(qiáng)分配娛律8.姜選游擇與技差運(yùn)火算的騙分配根律9.矛選斬?fù)駥弊匀粻t連接錯的分?jǐn)∨渎?0哭.內(nèi)投影桶與笛筒卡爾板積的迅分配這律11什.糖投影再與并助的分份配律9.繞3.左2準(zhǔn)查詢漿樹的吸啟發(fā)屆式優(yōu)訂化典型執(zhí)的啟乖發(fā)式日規(guī)則廉：1.讓選平擇運(yùn)糠算應(yīng)戰(zhàn)盡可效能先茅做。在餅優(yōu)化坐策略發(fā)中這逆是最跪重要獄、最率基本么的一壁條。它搭常常榜可使桑執(zhí)行查時節(jié)驅(qū)約幾叨個數(shù)灣量級樣，因赴為選腿擇運(yùn)犁算一傻般使葉計算碰的中災(zāi)間結(jié)克果大絕大變吼小2.釣把瀉投影明運(yùn)算慨和選森擇運(yùn)盞算同眼時進(jìn)累行。如有胖若干焦投影炮和選獨(dú)擇操蓮作，擴(kuò)并且毯它們煎都對黎同一搬個關(guān)隨系操圍作，戶則可些以在櫻掃描絕此關(guān)進(jìn)系的呢同時怒完成疲所有販的這蜻些運(yùn)兔算以題避免廟重復(fù)游掃描其關(guān)系3.荒把評投影裳同其失前或張其后窮的雙正目運(yùn)爸算結(jié)腹合起世來，沒們有必星要為柳了去錢掉某她些字晝段而盟掃描吼一遍宮關(guān)系4.疾把宋某些聯(lián)選擇礎(chǔ)同在拋它前六面要融執(zhí)行擾的笛牌卡爾鐵積結(jié)握合起菜來成瘡為一夕個連勞接運(yùn)辭算，連芝接特陶別是來等值按連接交運(yùn)算刊要比特同樣斜關(guān)系打上的滿笛卡世爾積柜節(jié)省具很多賞時間5.無找恐出公址共子雄表達(dá)底式。如鄙果這左種重議復(fù)出疲現(xiàn)的召子表贊達(dá)式五的結(jié)焦果不傻是很束大的盒關(guān)系轟，并枝且從啟外存扔中讀楊入這矮個關(guān)言系比會計算廊該子近表達(dá)回式的鳥時間傭少得某多，喘則先覺計算弄一次蒸公共拉子表心達(dá)式罷并把侵結(jié)果榮寫入滔中間陽文件亡是合龜算的叛。當(dāng)勵查詢嚼的是隨視圖拉時，盈定義展視圖萍的表承達(dá)式始就是帆公共徹子表膝達(dá)式爪的情勞況9.拉3.緒2呼查詢弄樹的似啟發(fā)淹式優(yōu)臘化（狀續(xù)）［例偷4］舊下面畝給出伴［例療3］輝中殿SQ競L語燦句的胃代數(shù)襯優(yōu)化擋示例娃。(1被)說把S之QL旗語句攝轉(zhuǎn)換嶼成查腹詢樹吧，如浩下圖光所示圖9嚴(yán).3奏查詢衰樹9.側(cè)3.拍2抹查詢翼樹的煩啟發(fā)養(yǎng)式優(yōu)蹦化（溫續(xù)）為了淺使用抽關(guān)系使代數(shù)稈表達(dá)銜式的余優(yōu)化藥法，備假設(shè)鳳內(nèi)部帳表示芒是關(guān)技系代夢數(shù)語砌法樹袖，則兩上面曉的查飼詢樹妻如下沃圖所金示。

圖9.4關(guān)系代數(shù)語法樹9.豆3.稀2新查詢蛇樹的采啟發(fā)柄式優(yōu)膨化（暮續(xù)）(2倘)領(lǐng)對查匹詢樹構(gòu)進(jìn)行造優(yōu)化利用井規(guī)則扒4、教6把胳選擇鄭σSC維.C夠no=‘壤2’秘移到游葉端蚊，查暢詢樹銅便轉(zhuǎn)薪換成桐下圖爽所示澡的優(yōu)還化的趣查詢膏樹。犯這就脆是9譯.2準(zhǔn).2脫節(jié)中Q3的查蠶詢樹渴表示圖9浮.4旬優(yōu)忘化后粒的查厚詢樹關(guān)系職查詢廁處理頸和查桿詢優(yōu)哥化9.傘1虹關(guān)系宇數(shù)據(jù)港庫系獲統(tǒng)的竭查詢易處理9.亞2籍關(guān)系皇數(shù)據(jù)版庫系京統(tǒng)的電查詢另優(yōu)化9.修3護(hù)代數(shù)屈優(yōu)化9.篇4際物理島優(yōu)化9.男5葛小結(jié)9.盤4增物理挎優(yōu)化代數(shù)細(xì)優(yōu)化申改變僻查詢座語句綱中操術(shù)作的吵次序企和組雹合，添不涉業(yè)及底治層的覆存取東路徑對于六一個陣查詢筒語句胃有許朝多存捕取方鮮案，云它們抽的執(zhí)系行效宅率不品同，融僅勝僅進(jìn)聽行代博數(shù)優(yōu)堤化是固不夠揮的物理銷優(yōu)化刃就是穿要選吵擇高收效合非理的肌操作頃算法莖或存只取路啄徑，拖求得墓優(yōu)化亡的查標(biāo)詢計作劃選擇餃的方避法可詞以是盲：基于知規(guī)則臺的啟揀發(fā)式息優(yōu)化根；基于捉代價希估算環(huán)的優(yōu)朗化；兩者秤結(jié)合9.數(shù)4炭物理錫優(yōu)化9.濾4.親1夠基于過啟發(fā)據(jù)式規(guī)械則存耀取路冒徑選稈擇優(yōu)贈化9.蜘4.滴2博基于小代價爹的優(yōu)場化9.陽4.鹽1夫基于抓啟發(fā)先式規(guī)紛則的抓存取銳路徑炊選擇題優(yōu)化一、窯選擇擁操作呼的啟陽發(fā)式排規(guī)則脫有：1.憲對于小關(guān)系棋，使煩用全表資順序打掃描，即淚使選川擇列股上有岡索引對于囑大關(guān)石系，牙啟發(fā)繞式規(guī)仔則有尚：2.毒對于米選擇皇條件休是主挎碼=匙值的桑查詢傻，查該詢結(jié)朽果最偷多是歷一個城元組境，可潑以選鑒擇主柏碼索規(guī)引，流一般加的R導(dǎo)DB紋MS剖會自豈動建就立主躁碼索企引3.婆對于拖選擇販條件羅是非努主屬狗性=閥值的碼查詢憶，并案且選口擇列餅上有園索引闊，則稼要估暮算查提詢結(jié)謊果的連元組錢數(shù)目融，如恥果比翻例較惠小（畝<1獲0%廢）可轉(zhuǎn)以使次用索滅引掃壇描方邊法，亡否則渠還是麻使用呢全表零順序梳掃描9.閣4.傅1岡基于獄啟發(fā)艷式規(guī)中則的窮存取乘路徑壞選擇扁優(yōu)化惠（續(xù)纖）4.殘對于膀選擇卡條件皆是屬穗性上澆的非盞等值密查詢研或者鉛范圍乒查詢塘，并炊且選響擇列團(tuán)上有除索引牙，同歪樣要溪估算確查詢暢結(jié)果尤的元流組數(shù)抖目，盛如果鋸比例腐較小費(fèi)（<熄10鼻%）逮可以涉使用爬索引椅掃描逐方法款，否斃則還塞是使艇用全誰表順潑序掃餓描5.做對于厲用A店ND箏連接香的合油取選旗擇條嚷件，賄如果伸涉及蝴這些謙屬性首的組果合索敢引，時則優(yōu)刺先采經(jīng)用組蜂合索布引掃穿描方擠法；毯如果賠某些域?qū)傩运缴嫌懈兑话愀坏乃饔埔?，慈則可減以使像用[貢例1瞧-C磁4]仰中介避紹的福索引狡掃描贏方法謝，否芹則使六用全逆表順告序掃快描6.運(yùn)對于贊用O駁R連傭接的騾析取踐選擇偷條件撓，一冷般使蜂用全膨表順長序掃添描9.虛4.拿1演基于捐啟發(fā)找式規(guī)壘則的禮存取奶路徑超選擇裳優(yōu)化昆（續(xù)犬）全表掃描索引掃描小關(guān)系有索引全表掃描無索引全表掃描大關(guān)系主碼=值主碼索引非主屬性=值，有索引結(jié)果少索引掃描結(jié)果多全表掃描非等值或范圍有索引結(jié)果少索引掃描結(jié)果多全表掃描AND連接的合取組合索引組合索引掃描一般索引索引掃描無索引全表掃描OR連接的析取全表掃描9.駛4.熄1灑基于軌啟發(fā)債式規(guī)阿則的楊存取邀路徑毛選擇子優(yōu)化煮（續(xù)狹）二、子連接發(fā)操作乎的啟予發(fā)式餡規(guī)則1.濫如果副2個搏表都設(shè)已經(jīng)姐按照疫連接顧屬性排序，則搶選用析排序傘-合漲并方料法2.戴如果替一個汗表在外連接識屬性允上有索肯引，則東可以殼選用竄索引柱連接功方法3.御如果回上面承2個午規(guī)則市都不碎適用趟，其捐中一論個表較小，則塌可以胃選用刺Ha戶sh言j糧oi寨n方廉法4.黎最后情可以攤選用嵌套墓循環(huán)的方傻法，界并選默擇其睡中較賺小的零表，獲確切就地講潤是占葡用的蛇塊數(shù)烏（b疼）較難少的稼表，露作為現(xiàn)外表因（外央循環(huán)逮的表案）。琴理由械如下聲：設(shè)連慘接表屠R與棚S分牲別占勺用的盛塊數(shù)西為B自r與磨Bs法，連晴接操替作使允用的酷內(nèi)存芬緩沖勢區(qū)塊樂數(shù)為防K，很分配露K-姐1塊珠給外仿表。隊如果臥R為弱外表兼，則淺嵌套穴循環(huán)驚法存乓取的死塊數(shù)惑為B扛r+其（B苗r/氣K-修1）墾Bs柿，顯槳然應(yīng)頭該選繼塊數(shù)墾小的弟表作卵為外滋表9.嚷4.粱2汪基于資代價伏的優(yōu)蛋化啟發(fā)傷式規(guī)醒則優(yōu)崗化是項定性唐的選柏?fù)?，?yīng)比較貫粗糙青，但嗎是實插現(xiàn)簡漫單而糾且優(yōu)饒化本亡身的桐代價卻較小斯，適譽(yù)合解湊釋執(zhí)慨行的謀系統(tǒng)在編掙譯執(zhí)氧行的泄系統(tǒng)透中，糠一次脫編譯買優(yōu)化綢，多質(zhì)次執(zhí)棗行，劑查詢男優(yōu)化雄和查坑詢執(zhí)柴行是通分開史的，晝因此無適合但采用喚精細(xì)辨復(fù)雜醒的基禾于代娃價的播優(yōu)化嗎方法9.唉4.專2癥基于識代價坊的優(yōu)趣化（培續(xù)）一、躬統(tǒng)計伶信息基于留代價伴的優(yōu)際化方廟法主匪要計植算各這種操做作算速法的液執(zhí)行粘代價蒙，它宅與數(shù)皇據(jù)庫扒的狀債態(tài)密握切相棄關(guān)。鍋為此蜂在數(shù)貌據(jù)字尸典中水存儲查了優(yōu)邪化器怖需要過的統(tǒng)蝕計信敘息（浮da圍ta張ba曾se凳s米ta減ti掃st波ic堪s）閉，主掙要包佩括以內(nèi)下幾饒個方專面：1.橋?qū)γ空€基寒本表詞，該搏表的腹元組密總數(shù)灘（N茂）、柱元組刃長度疼（l睜）、潑占用功塊數(shù)蠻（B邁）、城占用叢的溢劑出塊通數(shù)（令BO仗）；2.怎對基童本表遵的每神個列太，該桑列不客同值干的個杜數(shù)（常m）般、選緒擇率那（f絡(luò)）（賞如果雨不同酸值的糊分布概是均秘勻的宿，f旦=l鉗/m瘋；否臘則，廳每個斬值的地選擇扣率=唯具有獎該值垃的元旬組個壯數(shù)l呼/N拴）、庭該列弱最大擠值、陡最小來值，需該列椒上是葛否已臉經(jīng)建后立了鉆索引努，是良哪種擋索引戰(zhàn)（B狂+樹纖索引白、H真as澤h索志引、巷聚集停索引干）3.怠對索雄引，巨例如還B+購樹索兄引，童該索熔引的傻層數(shù)允（L無）、便不同材索引垂值的遍個數(shù)善、索饞引的泥選擇躲基數(shù)禁S（膏有S桿個元愉組具瞧有某兼?zhèn)€索噸引值去）、向索引登的葉稀節(jié)點(diǎn)想數(shù)（蠟Y）9.墻4.司2橋基于剃代價票的優(yōu)猛化（媽續(xù)）二、低代息價估熊算示伍例1.魚全表