補充查詢處理和查詢優(yōu)化

會計學(xué)1補充查詢處理和查詢優(yōu)化2一、查詢處理步驟

查詢處理分為4個階段，在處理過程中，一旦發(fā)現(xiàn)問題，則報告錯誤，中止處理。§1關(guān)系數(shù)據(jù)庫系統(tǒng)的查詢處理查詢處理的任務(wù)：

將用戶提交給RDBMS的查詢語句轉(zhuǎn)換為高效的執(zhí)行計劃（方案）。第1頁/共60頁3

詞法分析：識別出語句中的SQL關(guān)鍵字、屬性名、關(guān)系名、運算符、常量等語言符號。語法分析：檢查語句是否符合SQL語法規(guī)則。(1)查詢分析第2頁/共60頁4語義檢查：根據(jù)數(shù)據(jù)字典，檢查語句中的數(shù)據(jù)庫對象，如屬性名、關(guān)系名等，是否有效。符號名轉(zhuǎn)換：將外部名轉(zhuǎn)換為內(nèi)部名。安全性檢查：檢查用戶是否有請求的存取權(quán)限。完整性檢查：檢查是否違反完整性約束。查詢樹轉(zhuǎn)換：用基于關(guān)系代數(shù)的查詢樹來表示查詢，查詢樹也叫語法分析樹。(2)查詢檢查第3頁/共60頁5(3)查詢優(yōu)化從多個可能的執(zhí)行方案中選擇一個執(zhí)行效率較高的方案。分為兩個層次。第4頁/共60頁6(4)查詢執(zhí)行依據(jù)查詢優(yōu)化得到的結(jié)果，生成執(zhí)行代碼，執(zhí)行之。代數(shù)優(yōu)化：按照一定的規(guī)則，改變代數(shù)表達式中關(guān)系操作的次序和組合，使執(zhí)行效率更高，又稱邏輯優(yōu)化。物理優(yōu)化：依據(jù)事先確定的策略，選擇底層存取路徑和算法。第5頁/共60頁7二、實現(xiàn)查詢操作的算法舉例1.選擇操作的實現(xiàn)Select*fromstudentwhere<條件表達式>；考慮<條件表達式>的幾種情況：C1:無條件；C2:Sno=‘200215121’；C3：Sage>20;C4:Sdept=‘CS’ANDSage>20;第6頁/共60頁8二、實現(xiàn)查詢操作的算法舉例1.選擇操作的實現(xiàn)(1)簡單的全表掃描方法對查詢基本表順序掃描，逐一檢查每個元組是否滿足選擇的條件，對滿足條件的元組作為結(jié)果輸出。對于小表，簡單有效。對于大表，費時。(2)索引或散列掃描方法如果選擇條件中的屬性上有索引（B+樹索引或Hash索引），可以用索引掃描方法。通過索引先找到滿足條件的元組的主碼或元組指針，再通過元組指針直接在查詢的基本表中找到元組。第7頁/共60頁9二、實現(xiàn)查詢操作的算法舉例2.連接操作的實現(xiàn)Select*fromStudent,ScWhereStudent.Sno=SC.sno(1)嵌套循環(huán)方法

對于外層循環(huán)(Student)的每個元組(s),檢索內(nèi)層循環(huán)(SC)中的每個元組(sc)，并檢查這兩個元組在連接屬性(sno)上是否相等。如果滿足連接條件，則串接后作為結(jié)果輸出，直到外層循環(huán)表中的元組處理完為止。第8頁/共60頁10二、實現(xiàn)查詢操作的算法舉例(2)排序-合并方法

①如果連接的表沒有排好序，則將Student和SC表按連接屬性Sno排序；②取Student表中的第一個Sno，依次掃描SC表中具有相同Sno的元組，把它們連接起來；③當(dāng)掃描到Sno不相同的第一個SC元組時，返回Student表掃描下一個元組，再掃描SC表中具有相同Sno的元組，把它們連接起來。重復(fù)上述步驟直到Student表掃描完。第9頁/共60頁11二、實現(xiàn)查詢操作的算法舉例(3)索引連接方法①在SC表上建立屬性Sno的索引，如果原來沒有的話；②對Student表中的每一個元組，由Sno的值通過SC的索引查找相應(yīng)的SC元組；③把這些SC元組和Student元組連接起來。循環(huán)執(zhí)行②、③；直到Student表中的元組處理完為止。第10頁/共60頁12二、實現(xiàn)查詢操作的算法舉例(4)HashJoin方法把連接屬性作為hash碼，用同一個hash函數(shù)把R和S中的元組散列到同一個hash文件中。劃分階段：對包含較少元組的表(比如R)進行一遍處理，把它的元組按hash函數(shù)分散到hash表的桶中；試探階段：對另一個表(S)進行一遍處理，把S的元組散列到適當(dāng)?shù)膆ash桶中，并將元組與桶中所有來自R并與之匹配的元組連接起來。第11頁/共60頁13§2關(guān)系數(shù)據(jù)庫系統(tǒng)的查詢優(yōu)化

關(guān)系數(shù)據(jù)語言只需用戶提出“做什么”，不必指出“怎么做”，為什么能做到這一點？一個重要原因就是系統(tǒng)能自動進行查詢優(yōu)化。系統(tǒng)自動優(yōu)化比用戶自己優(yōu)化會做得更好，見P267。在集中式數(shù)據(jù)庫中，查詢執(zhí)行的總代價(開銷)為：總代價=I/O代價+CPU代價+內(nèi)存代價三者中，I/O代價是最主要的。查詢優(yōu)化的總目標：選擇有效的策略，求得給定的關(guān)系表達式的值，使得查詢代價較小。第12頁/共60頁14例：求選修了2號課程的學(xué)生姓名。其SQL語句為：SELECT姓名FROMStudent,SCWHEREStudent.學(xué)號=SC.學(xué)號AND課號=‘2’;為什么要進行查詢優(yōu)化？也可用SQL語言如下實現(xiàn):SELECT姓名FROMStudentWHERE學(xué)號IN(SELECT學(xué)號FROMSCWHERE課號=‘2’);第13頁/共60頁15

對于一個復(fù)雜的查詢，不同用戶可能會寫出各種不同的查詢方法。這些方法有的簡單，有的復(fù)雜。它們的執(zhí)行結(jié)果是一樣的，但執(zhí)行效率可能是不一樣的。系統(tǒng)能解決這一問題嗎？第14頁/共60頁16對這一查詢，可以考慮下面幾種實現(xiàn)方式：1、先求Student和SC的笛卡爾積，然后從中選出兩學(xué)號字段值相等、課程號為2的元組，再投影姓名。Q1=姓名(Student.學(xué)號=SC.學(xué)號∧課號=‘2’(StudentSC))2、先做Student和SC的自然連接，然后從中選出課程號為2的元組，再投影姓名。Q2=姓名（課號=‘2’

（Student∞SC））3、先從SC中選出課程號為2的元組，然后將該結(jié)果與Student連接，再投影姓名。Q3=姓名（Student∞課號=‘2’

（SC））第15頁/共60頁17分析三種實現(xiàn)策略的執(zhí)行時間：

設(shè)有1000個學(xué)生記錄，10000個選課記錄，選修2號課程的學(xué)生有50名。1、第一種策略：Q1=姓名(Student.學(xué)號=SC.學(xué)號∧課號=‘2’(StudentSC))（1）計算廣義笛卡爾積StudentSC：

執(zhí)行方式：讀Student若干塊和SC的1塊到內(nèi)存，然后執(zhí)行連接，結(jié)果裝滿1塊后就立即寫入磁盤的臨時文件中，當(dāng)內(nèi)存中的Student記錄與SC記錄全部連接后，再讀入SC的下一塊，繼續(xù)連接，直到SC的所有記錄與內(nèi)存中的Student都連接，再讀入Student的另若干塊，重復(fù)上面的過程。第16頁/共60頁18

設(shè)一塊能裝10個Student記錄或100個SC記錄。則Student的總塊數(shù)為1000/10=100塊，SC的總塊數(shù)為10000/100=100塊若每次在內(nèi)存中裝入5塊Student記錄和1塊SC的記錄，則Student被讀取1遍，SC被讀取100/5=20遍。讀取兩表的總塊數(shù)為

100+10020=2100塊連接結(jié)果為1000*10000=10000000個記錄，若每塊可裝10個結(jié)果記錄，共需寫入磁盤10000000/10=1000000塊。若每秒可讀寫20塊，則讀、寫總時間分別為：

2100/20=105秒1000000/20=50000秒第17頁/共60頁19（2）依次讀入StudentSC的記錄，然后執(zhí)行選擇。讀的時間：1000000/20=50000秒滿足條件的記錄為50個，全部放入內(nèi)存，不再臨時存儲。（3）在上步基礎(chǔ)上執(zhí)行投影得最終結(jié)果（此步時間不計）。第一種策略的總時間為：105+50000+5000010萬秒（近28小時）第18頁/共60頁202、第二種策略（1）計算自然連接讀取Student表和SC表的策略不變，執(zhí)行時間還是2100/20=105秒。因為SC表中的每一個學(xué)號都在Student表中出現(xiàn)，而Student表中無重復(fù)學(xué)號，故連接后的結(jié)果和SC表的行數(shù)一樣，為10000行，將它們臨時存入盤中需（10000/10）塊/20塊/秒=50秒計算自然連接需時：105+50=155秒Q2=姓名（課號=‘2’

（Student∞SC））第19頁/共60頁21（2）執(zhí)行選擇運算將存儲在磁盤上臨時文件中的自然連接結(jié)果，讀入內(nèi)存進行選擇，結(jié)果為50個記錄，不再臨時存儲。主要為讀取自然連接結(jié)果的時間：為50秒（3）把上一步結(jié)果投影，時間忽略不計第二種策略的總時間為：155+50=205秒第20頁/共60頁223、第三種策略（1）先對SC表作選擇只需讀一遍SC表，需時100塊

/20塊/秒=5秒中間結(jié)果只有50個記錄，不需使用中間文件（2）作自然連接只需讀一遍Student表，邊讀邊和內(nèi)存中的中間結(jié)果連接，結(jié)果仍為50個元組，需時5秒Q3=姓名（Student∞課號=‘2’

（SC））（3）把上一步結(jié)果投影，時間忽略不計第三種策略的總時間為：5+5=10秒結(jié)論：不同的查詢策略其執(zhí)行時間可能差別很大第21頁/共60頁23說明：剛才使用的是全表掃描的方法，比較費時，如果在選擇字段和連接字段上建立了適當(dāng)?shù)乃饕?，就可以減少記錄的讀取量，從而降低查詢開銷。這就是存取路徑選擇問題，由物理優(yōu)化解決。第22頁/共60頁24總結(jié)：通過剛才的例子可知，前兩種策略的中間結(jié)果集（笛卡爾積和自然連接）包含了許多對查詢結(jié)果無用的記錄，造成結(jié)果集太大，不得不進行磁盤緩存處理，從而使得花費時間較多。由此啟發(fā)我們，在查詢處理時，應(yīng)盡可能早地去掉對查詢結(jié)果沒有用的數(shù)據(jù)（記錄或字段），以降低中間結(jié)果集的規(guī)模，這可通過優(yōu)先執(zhí)行一元運算（選擇和投影）來實現(xiàn)，象第三種策略那樣。第23頁/共60頁25§3代數(shù)優(yōu)化一、關(guān)系代數(shù)表達式等價變換規(guī)則

設(shè)E1、E2是關(guān)系代數(shù)表達式。若用相同的關(guān)系代替E1、E2中相應(yīng)的關(guān)系所得到的結(jié)果相同，則稱E1、E2等價，記作E1

E2。1、投影的串接定律（冪等律）A1,A2,…,An(B1,B2,…,Bm(E))A1,A2,…,An(E)

其中{A1,A2,…,An}{B1,B2,…,Bm}例：姓名

(學(xué)號，姓名

(Student))姓名

(Student)第24頁/共60頁262、選擇的串接定律（冪等律）F1

（F2

（E））F1F2

（E）性別=‘男’

(年齡>20(Student))性別=‘男’年齡>20(Student)第25頁/共60頁273、連接、笛卡爾積的交換律笛卡爾積：E1E2E2E1自然連接：E1∞E2E2∞E1一般連接：E1∞E2E2∞E1FF4、連接、笛卡爾積的結(jié)合律笛卡爾積：(E1E2)E3E1(E2E3)自然連接：(E1∞E2)

∞E3E1∞(E2∞E3)一般連接：(E1∞E2)

∞E3E1∞(E2∞E3)F1F2F1F2第26頁/共60頁285、選擇與投影的交換律F(A1,A2,…,An(E))A1,A2,…,An(F(E))其中F只涉及A1,A2,…,An中的屬性例：性別=‘男’

(學(xué)號，姓名，性別

(Student))學(xué)號，姓名，性別

(性別=‘男’

(Student))若F中有不屬于A1,A2,…,An的屬性B1,B2,…,Bm，則A1,A2,…,An(F(E))A1,A2,…,An(A1,A2,…,An,B1,B2,…,Bm(F(E)))A1,A2,…,An(F(A1,A2,…,An,B1,B2,…,Bm(E)))第27頁/共60頁29例：學(xué)號，姓名(性別=‘男’

(Student))學(xué)號，姓名性別=‘男’

(學(xué)號，姓名，性別

(Student))第28頁/共60頁306、選擇與笛卡爾積的交換律（分配律）

設(shè)F=F1∧F2∧F3，其中F1只涉及E1中的屬性，F(xiàn)2只涉及E2中的屬性，F(xiàn)3涉及E1和E2兩者中的屬性，則F(E1×E2)F3(F1E1×F2E2)如果某個Fi不存在，則去掉相應(yīng)的Fi。例：Student.學(xué)號=SC.學(xué)號∧成績<60(Student×SC)Student.學(xué)號=SC.學(xué)號(Student

×成績<60SC)第29頁/共60頁317、選擇對自然連接的分配律

設(shè)F=F1∧F2，其中F1只涉及E1的屬性，F(xiàn)2只涉及E2的屬性，則F(E1∞E2)F1E1∞F2E2例：性別=‘男’∧成績>=90(Student

∞SC)性別=‘男’

Student

∞成績>=90SC8、選擇對并、交、差的分配律F(E1∪E2)FE1∪FE2F(E1∩E2)FE1∩FE2F(E1-E2)FE1-FE2第30頁/共60頁329、投影對笛卡爾積的分配律

設(shè)A1,A2,…，An是E1的屬性，B1,B2,…，Bm是E2的屬性，則A1,A2,…,An,B1,B2,…,Bm(E1×E2)A1,A2,…,AnE1×B1,B2,…,BmE210、投影對并、交、差的分配律A(E1∪E2)AE1∪AE2A(E1∩E2)AE1∩AE2A(E1-E2)AE1-AE2第31頁/共60頁33二、查詢樹的啟發(fā)式優(yōu)化1、啟發(fā)式規(guī)則（1）一元運算應(yīng)盡可能先做。這樣可及時丟掉對查詢結(jié)果無用的記錄或字段，極大地減小中間結(jié)果集。（2）將選擇、投影及其前后的笛卡爾積、連接運算同時進行。這樣可減少對關(guān)系的掃描遍數(shù)和中間結(jié)果的存儲量。（3）找出公共子表達式，將計算結(jié)果臨時保存，再遇到該表達式時，不再計算，直接使用保存的結(jié)果。第32頁/共60頁342、關(guān)系代數(shù)語法樹

用來表示關(guān)系代數(shù)表達式的一棵樹，其內(nèi)結(jié)點表示一種運算，葉結(jié)點表示一個關(guān)系。如：

SELECT姓名

FROMStudent，SCWHEREStudent.學(xué)號=SC.學(xué)號AND課號=‘2’；姓名Student.學(xué)號=SC.學(xué)號

∧課號=‘2’×StudentSC方法：將目標列轉(zhuǎn)換為投影，將WHERE中的條件轉(zhuǎn)換為選擇，將FROM后的表用笛卡爾積連接起來。也可轉(zhuǎn)換為自然連接?！拚n號=‘2’第33頁/共60頁353、關(guān)系代數(shù)表達式的優(yōu)化算法輸入：一棵關(guān)系代數(shù)表達式的語法樹輸出：優(yōu)化的語法樹

利用選擇的串接定律，把形如F1F2Fn

（E）的式子變換為F1(F2((Fn(E)))（1）分解選擇第34頁/共60頁36

對每一個選擇，利用“選擇的串接定律、選擇與投影的交換律、選擇對笛卡爾積的分配律、選擇對自然連接的分配律、選擇對并、交、差的分配律”盡可能把它移到樹的葉端。（2）選擇下移第35頁/共60頁37

對每一個投影，利用“投影的串接定律、選擇與投影的交換律、投影對笛卡爾積的分配律、投影對并、交、差的分配律”盡可能把它移到樹的葉端。（3）投影下移（1）分解選擇（2）選擇下移第36頁/共60頁38

利用“投影的串接定律、選擇的串接定律、選擇與投影的交換律”把選擇和投影合并成單個選擇、單個投影、或選擇后跟投影等三種情況，使多個選擇和/或投影能同時執(zhí)行、或在一次掃描中完成。（4）選擇、投影合并（3）投影下移（1）分解選擇（2）選擇下移第37頁/共60頁39

把上面得到的語法樹分組：每個二元運算和它的一元直接祖先為一組。若它的后代直到葉子全是一元運算，則也將它們并入該組。（5）按點分組（每組只有一個二元運算）不超過別的二元運算結(jié)點

但對于笛卡爾積，若后面（父結(jié)點）是不能與它結(jié)合為等值連接的選擇運算時，其一直到葉子的一元運算結(jié)點需單獨算一組。

第38頁/共60頁40例：考慮由以下關(guān)系組成的圖書館數(shù)據(jù)庫BOOKS（書名，作者，出版社，編號）BORROWERS（姓名，單位，證號）LOANS（證號，編號，借閱日期）找出2007年12月01日前借出書籍的書名和借閱人姓名。用SQL語言可表達如下：

SELECT書名，姓名

FROMBOOKS，BORROWERS，LOANSWHEREBOOKS.編號=LOANS.編號ANDBORROWERS.證號=LOANS.證號AND

借閱日期<{2007-12-01};第39頁/共60頁41上述SQL語句可轉(zhuǎn)化為如下關(guān)系代數(shù)表達式：書名，姓名(借閱日期<{2007-12-01}

(BOOKS∞（BORROWERS∞LOANS)))或書名，姓名(借閱日期<{2007-12-01}∧BOOKS.編號=LOANS.編號∧

BORROWERS.證號=LOANS.證號

(BOOKS×(BORROWERS×LOANS)))

通常先轉(zhuǎn)化為后一種形式，在優(yōu)化的后期會將笛卡爾積轉(zhuǎn)換為自然連接。第40頁/共60頁42書名，姓名借閱日期<{2007-12-01}∧BOOKS.編號=LOANS.編號∧

BORROWERS.證號=LOANS.證號上述表達式的語法樹LOANSBOOKSBORROWERS根據(jù)算法第1步，分解該選擇第41頁/共60頁43第1步優(yōu)化（分解選擇）后的語法樹書名，姓名LOANSBOOKSBORROWERS借閱日期<{2005-10-01}∧BOOKS.編號=LOANS.編號∧

BORROWERS.證號=LOANS.證號借閱日期<{2007-12-01}

BOOKS.編號=LOANS.編號BORROWERS.證號=LOANS.證號

分解之后根據(jù)算法第2步，該選擇可下移第42頁/共60頁44書名，姓名LOANSBOOKSBORROWERS借閱日期<{2007-12-01}BOOKS.編號=LOANS.編號BORROWERS.證號=LOANS.證號

第43頁/共60頁45書名，姓名LOANSBOOKSBORROWERS借閱日期<{2007-12-01}BOOKS.編號=LOANS.編號BORROWERS.證號=LOANS.證號

該選擇已不能下移該選擇也不能下移將該選擇下移交換第44頁/共60頁46書名，姓名LOANSBOOKSBORROWERS借閱日期<{2007-12-01}BOOKS.編號=LOANS.編號BORROWERS.證號=LOANS.證號

交換后繼續(xù)下移第45頁/共60頁47書名，姓名LOANSBOOKSBORROWERS借閱日期<{2007-12-01}BOOKS.編號=LOANS.編號BORROWERS.證號=LOANS.證號

交換第46頁/共60頁48書名，姓名LOANSBOOKSBORROWERS借閱日期<{2007-12-01}BOOKS.編號=LOANS.編號BORROWERS.證號=LOANS.證號

繼續(xù)下移第47頁/共60頁49書名，姓名LOANSBOOKSBORROWERS借閱日期<{2007-12-01}BOOKS.編號=LOANS.編號BORROWERS.證號=LOANS.證號

OK第2步優(yōu)化（選擇下移）后的語法樹該投影能否與選擇交換？不能！怎么辦？利用投影的冪等律插入一個投影算法第3步，投影下移第48頁/共60頁50書名，姓名LOANSBOOKSBORROWERS借閱日期<{2007-12-01}BOOKS.編號=LOANS.編號BORROWERS.證號=LOANS.證號

書名，姓名，BOOKS.編號，LOANS.編號交換第49頁/共60頁51書名，姓名LOANSBOOKSBORROWERS借閱日期<{2007-12-01}BOOKS.編號=LOANS.編號BORROWERS.證號=LOANS.證號

書名，姓名，BOOKS.編號，LOANS.編號對笛卡爾分配第50頁/共60頁52書名，BOOKS.編號書名，姓名LOANSBOOKSBORROWERS借閱日期<{2007-12-01}BOOKS.編號=LOANS.編號BORROWERS.證號=LOANS.證號

姓名，LOANS.編號OK還需下移第51頁/共60頁53書名，BOOKS.編號書名，姓名LOANSBOOKSBORROWERS借閱日期<{2007-12-01}BOOKS.編號=LOANS.編號BORROWERS.證號=LOANS.證號

姓名，LOANS.編號插入一個投影姓名，LOANS.編號，

BORROWERS.證號，LOANS.證號

下移第52頁/共60頁54書名，BOOKS.編號書名，姓名LOANSBOOKSBORROWERS借閱日期<{2007-12-01}BOOKS.編號=LOANS.編號BORROWERS.證號=LOANS.證號

姓名，LOANS.編號姓名，LOANS.編號，

BORROWERS.證號，LOANS.證號

對笛卡爾分配第53頁/共60頁55LOANS.編號，

LOANS.證號

姓名，

BORROWERS.