【正文】 數(shù)表達(dá)式的等價(jià)變換來提高查詢效率 v關(guān)系代數(shù)表達(dá)式的等價(jià)：指用相同的關(guān)系代替兩個(gè)表達(dá)式中相應(yīng)的關(guān)系所得到的結(jié)果是相同的v兩個(gè)關(guān)系表達(dá)式 E1和 E2是等價(jià)的，可記為 E1≡E2 An Introduction to Database System關(guān)系代數(shù)表達(dá)式等價(jià)變換規(guī)則（續(xù)）v 常用的等價(jià)變換規(guī)則：1. 連接、笛卡爾積交換律 設(shè) E1和 E2是關(guān)系代數(shù)表達(dá)式， F是連接運(yùn)算的條件，則有 E1 E2≡E2 E1 E1 E2≡E2 E1 E1 E2≡E2 E12. 連接、笛卡爾積的結(jié)合律 設(shè) E1， E2， E3是關(guān)系代數(shù)表達(dá)式， F1和 F2是連接運(yùn)算的條件，則有 (E1 E2) E3≡E1 (E2 E3) (E1 E2) E3≡E1 (E2 E3) (E1 E2) E3≡E1 (E2 E3) An Introduction to Database System關(guān)系代數(shù)表達(dá)式等價(jià)變換規(guī)則（續(xù)）3. 投影的串接定律 ( (E))≡ (E)這里， E是關(guān)系代數(shù)表達(dá)式， Ai(i=1， 2， … ， n)， Bj(j=1， 2， … ，m)是屬性名且 {A1， A2， … ， An}構(gòu)成 {B1， B2， … ， Bm}的子集。 即有選擇和連接操作時(shí)，先做選擇操作，這樣參加連接的元組就可以大大減少，這是代數(shù)優(yōu)化v在 Q3中167。 因?yàn)闈M足條件的 SC記錄僅 50個(gè)，涉及最多 50個(gè) Student記錄167。 存取的索引塊和 SC中滿足條件的數(shù)據(jù)塊大約總共 3～ 4塊v 若 Student表在 Sno上也有索引167。3. 把連接結(jié)果投影輸出 第三種情況總的執(zhí)行時(shí)間 ≈5+5≈10s An Introduction to Database System一個(gè)實(shí)例（續(xù)）v 假如 SC表的 Cno字段上有索引167。2. 讀取 Student表，把讀入的 Student元組和內(nèi)存中的SC元組作連接。239。3. 把第 2步結(jié)果投影輸出。自然連接的結(jié)果比第一種情況大大減少，為 104個(gè) 216。 (Student SC))1. 計(jì)算自然連接 216。 所有內(nèi)存處理時(shí)間均忽略不計(jì) An Introduction to Database System一個(gè)實(shí)例（續(xù)）v二、 第二種情況 Q2=πSname(=39。 把第 2步的結(jié)果在 Sname上作投影輸出，得到最終結(jié)果 167。讀取中間文件花費(fèi)的時(shí)間 (同寫中間文件一樣 )需 5104s 167。 依次讀入連接后的元組，按照選擇條件選取滿足要求的記錄 167。若每秒讀寫 20塊，則總計(jì)要花 105s v 連接后的元組數(shù)為 103104=107。 重復(fù)上述處理過程，直到把 Student表處理完An Introduction to Database System一個(gè)實(shí)例（續(xù)）v 設(shè)一個(gè)塊能裝 10個(gè) Student元組或 100個(gè) SC元組，在內(nèi)存中存放 5塊 Student元組和 1塊 SC元組，則讀取總塊數(shù)為 ＋ =100+20100=2100塊v 其中，讀 Student表 100塊。167。 把 SC中的每個(gè)元組和 Student中每個(gè)元組連接，連接后的元組裝滿一塊后就寫到中間文件上167。 在內(nèi)存中盡可能多地裝入某個(gè)表 (如 Student表 )的若干塊，留出一塊存放另一個(gè)表 (如 SC表 )的元組。239。239。239。239。 使得查詢代價(jià)最小 (實(shí)際上是較小 ) An Introduction to Database System 關(guān)系數(shù)據(jù)庫系統(tǒng)的查詢優(yōu)化 查詢優(yōu)化概述 一個(gè)實(shí)例 An Introduction to Database System 一個(gè)實(shí)例[例 3] 求選修了 2號課程的學(xué)生姓名。 選擇有效的策略167。 分布式數(shù)據(jù)庫216。執(zhí)行開銷主要包括：– 磁盤存取塊數(shù) (I/O代價(jià) )– 處理機(jī)時(shí)間 (CPU代價(jià) )– 查詢的內(nèi)存開銷 216。系統(tǒng)的自動優(yōu)化相當(dāng)于使得所有人都擁有這些優(yōu)化技術(shù)An Introduction to Database System查詢優(yōu)化概述（續(xù)）v RDBMS通過某種代價(jià)模型計(jì)算出各種查詢執(zhí)行策略的執(zhí)行代價(jià)，然后選取代價(jià)最小的執(zhí)行方案167。167。 An Introduction to Database System查詢優(yōu)化概述（續(xù)）167。 (2)如果數(shù)據(jù)庫的物理統(tǒng)計(jì)信息改變了，系統(tǒng)可以自動對查詢重新優(yōu)化以選擇相適應(yīng)的執(zhí)行計(jì)劃。 步驟：? 劃分階段 (partitioning phase)：– 對包含較少元組的表 (比如 R)進(jìn)行一遍處理– 把它的元組按 hash函數(shù)分散到 hash表的桶中? 試探階段 (probing phase)：也稱為連接階段 (join phase) – 對另一個(gè)表 (S)進(jìn)行一遍處理– 把 S的元組散列到適當(dāng)?shù)?hash桶中– 把元組與桶中所有來自 R并與之相匹配的元組連接起來 An Introduction to Database System連接操作的實(shí)現(xiàn)（續(xù)）v上面 hash join算法前提：假設(shè)兩個(gè)表中較小的表在第一階段后可以完全放入內(nèi)存的 hash桶中 v以上的算法思想可以推廣到更加一般的多個(gè)表的連接算法上 An Introduction to Database System第九章 關(guān)系系統(tǒng)及其查詢優(yōu)化 關(guān)系數(shù)據(jù)庫系統(tǒng)的查詢處理 關(guān)系數(shù)據(jù)庫系統(tǒng)的查詢優(yōu)化 代 數(shù) 優(yōu) 化 物 理 優(yōu) 化 小 結(jié) An Introduction to Database System 關(guān)系數(shù)據(jù)庫系統(tǒng)的查詢優(yōu)化v查詢優(yōu)化在關(guān)系數(shù)據(jù)庫系統(tǒng)中有著非常重要的地位 v關(guān)系查詢優(yōu)化是影響 RDBMS性能的關(guān)鍵因素 v由于關(guān)系表達(dá)式的語義級別很高，使關(guān)系系統(tǒng)可以從關(guān)系表達(dá)式中分析查詢語義，提供了執(zhí)行查詢優(yōu)化的可能性 An Introduction to Database System 關(guān)系數(shù)據(jù)庫系統(tǒng)的查詢優(yōu)化 查詢優(yōu)化概述 一個(gè)實(shí)例 An Introduction to Database System 查詢優(yōu)化概述v關(guān)系系統(tǒng)的查詢優(yōu)化v非關(guān)系系統(tǒng)An Introduction to Database System查詢優(yōu)化概述（續(xù)）v 查詢優(yōu)化的優(yōu)點(diǎn)不僅在于用戶不必考慮如何最好地表達(dá)查詢以獲得較好的效率，而且在于系統(tǒng)可以比用戶程序的 “優(yōu)化 ”做得更好 167。重復(fù)上述步驟直到 Student 表掃描完An Introduction to Database System連接操作的實(shí)現(xiàn)（續(xù)）v Student表和 SC表都只要掃描一遍v 如果 2個(gè)