1、分布式數(shù)據(jù)庫(kù)的查詢優(yōu)化,1.分布式查詢優(yōu)化的目標(biāo) 2.分布式查詢優(yōu)化的方法,1,分布式查詢優(yōu)化的目標(biāo),分布式數(shù)據(jù)庫(kù)系統(tǒng)中進(jìn)行查詢優(yōu)化的最終目標(biāo)就是盡量使總代價(jià)最小和使查詢響應(yīng)時(shí)間最短。1.總代價(jià)：在分布式數(shù)據(jù)庫(kù)系統(tǒng)中，除了包括在集中式數(shù)據(jù)庫(kù)中的 CPU 代價(jià)和 I/O 代價(jià)（合稱為局部處理代價(jià)）之外，由于數(shù)據(jù)分布在不同的結(jié)點(diǎn)上，在數(shù)據(jù)查詢處理中還需要考慮到站點(diǎn)間傳輸數(shù)據(jù)的通信代價(jià)，因此，總代價(jià)=CPU 代價(jià)+I/O 代價(jià)+通信代價(jià)。 2.響應(yīng)時(shí)間：指從接收查詢到完成查詢的時(shí)間間隔。在分布式數(shù)據(jù)庫(kù)系統(tǒng)中，響應(yīng)時(shí)間既與通訊時(shí)間有關(guān)，又與局部處理時(shí)間有關(guān)。,2,分布式查詢優(yōu)化的目標(biāo),3,分布式查詢優(yōu)

2、化的方法,1.基于關(guān)系代數(shù)等價(jià)變換的優(yōu)化 首先把查詢內(nèi)容轉(zhuǎn)化為關(guān)系代數(shù)表達(dá)式，經(jīng)過(guò)分析得到查詢樹(shù)，然后將原始查詢樹(shù)經(jīng)過(guò)從全局到片段的變換變成了基于片段的查詢樹(shù)，最后經(jīng)過(guò)一系列的基于關(guān)系代數(shù)等價(jià)變換規(guī)則的優(yōu)化算法的轉(zhuǎn)化，使該查詢樹(shù)中選擇和投影操作盡可能靠近葉結(jié)點(diǎn)，笛卡兒乘積運(yùn)算盡可能遠(yuǎn)離葉結(jié)點(diǎn)，這樣就可以減少操作量和操作次數(shù)，從而達(dá)到查詢優(yōu)化的目的。,4,分布式查詢優(yōu)化的方法,2.基于語(yǔ)義信息的優(yōu)化 語(yǔ)義查詢是利用數(shù)據(jù)庫(kù)的完整性約束定義把初始的查詢轉(zhuǎn)為一個(gè)語(yǔ)義等價(jià)的，但是處理代價(jià)更小的查詢。與一般的查詢處理過(guò)程所不同的是，基于語(yǔ)義信息的查詢處理擴(kuò)展了傳統(tǒng)的數(shù)據(jù)字典，在 IDB（Intellige

3、nt Database）中加入了新的語(yǔ)義信息規(guī)則，增添了語(yǔ)義優(yōu)化過(guò)程。使用這種方法不僅可以提高查詢的效率并且可把一般查詢對(duì)于非索引屬性的檢索轉(zhuǎn)變成為一個(gè)對(duì)索引屬性的檢索。但是又存在著增加處理時(shí)間的不足。在查詢數(shù)據(jù)量較大的分布式數(shù)據(jù)庫(kù)中宜于使用該算法。,5,分布式查詢優(yōu)化的方法,6,分布式查詢優(yōu)化的方法,3.SDD_1 查詢優(yōu)化算法 大致思想是通過(guò)反復(fù)的獲得有益半連接運(yùn)算，減少每個(gè)站點(diǎn)上用于連接運(yùn)算的數(shù)據(jù)，然后將所有站點(diǎn)的數(shù)據(jù)匯集到數(shù)據(jù)量最大的站點(diǎn)做最后裝配。,7,分布式查詢優(yōu)化的方法,處理過(guò)程主要包括三個(gè)步驟： 1.初始化：從全部關(guān)系中的半連接中生成有益的半連接集合； 2.選擇有益的半連接：從

4、有益的半連接集合中找出最有益的半連接，將其添加到執(zhí)行策略中，并相應(yīng)地修改被影響關(guān)系的統(tǒng)計(jì)值(選擇因子，關(guān)系的大小等)； 3.選擇組裝場(chǎng)地：重復(fù)第一步，直到所有有益的半連接加入到執(zhí)行策略中，關(guān)系經(jīng)上面步驟縮減后，選擇存儲(chǔ)數(shù)據(jù)量最大的站點(diǎn)為組裝場(chǎng)地；,8,分布式查詢優(yōu)化的方法,4.基于查詢圖的貪婪算法 貪婪算法實(shí)際上是一種自底向上的啟發(fā)式查詢優(yōu)化算法，在選擇連接順序時(shí)，總是使用一種簡(jiǎn)單而嚴(yán)格的選擇方法，每次都是選取當(dāng)前代價(jià)最小的一個(gè)連接，這樣便可使整個(gè)系統(tǒng)最終查詢的總代價(jià)達(dá)到最小 。 基于查詢圖的貪婪查詢實(shí)際上是一種動(dòng)態(tài)優(yōu)化方案，在具體查詢過(guò)程中，可以用中間查詢結(jié)果的大小近似地表示當(dāng)前通信代價(jià)的大

5、小，因此，對(duì)于不同結(jié)點(diǎn)之間進(jìn)行查詢連接時(shí)，應(yīng)當(dāng)選取查詢運(yùn)算最小的中間結(jié)果，從而降低當(dāng)前查詢代價(jià)，達(dá)到局部最優(yōu)。,9,分布式查詢優(yōu)化的方法,算法設(shè)計(jì)： 1.對(duì)于相鄰的結(jié)點(diǎn)進(jìn)行連接查詢時(shí)，首先需要找出中間結(jié)果最小的連接運(yùn)算。然后把這兩個(gè)相鄰節(jié)點(diǎn)合并成一個(gè)節(jié)點(diǎn)。 2.采用與1中同樣的方法繼續(xù)在查詢圖中尋找最小的連接運(yùn)算，把相鄰的節(jié)點(diǎn)合并，如果合并的過(guò)程中查詢圖出現(xiàn)線段合并，線段上的值為原先兩條線段值的成績(jī)。 3.最后執(zhí)行剩余兩個(gè)節(jié)點(diǎn)的連接。,10,以下通過(guò)一個(gè)例子對(duì)該算法做扼要介紹:,分布式查詢優(yōu)化的方法,11,圖 3.8 中，圓圈內(nèi)的數(shù)字表示站點(diǎn)號(hào)，圓圈外的數(shù)字表示該站點(diǎn)的數(shù)據(jù)大小，直線上的數(shù)字表

6、示該直線所連接的兩個(gè)站點(diǎn)的選擇因子。 1.貪婪算法首先找出中間結(jié)果最小的連接運(yùn)算。該圖中，站點(diǎn)1和站點(diǎn)2做連接運(yùn)算產(chǎn)生的中間結(jié)果最小，為 10*10*0.2=20。將圖 3.8 中的站點(diǎn)1和站點(diǎn)2進(jìn)行合并，變?yōu)閳D 3.9,分布式查詢優(yōu)化的方法,12,分布式查詢優(yōu)化的方法,圖 3.9 中，站點(diǎn) 3 和站點(diǎn) 4 做連接運(yùn)算的中間結(jié)果最小，為 10*10*0.330。將圖 3.9 中的站點(diǎn) 3 和站點(diǎn) 4 進(jìn)行合并，變?yōu)閳D 3.10。,13,分布式查詢優(yōu)化的方法,將圖 3.10 中的 12 和 34 進(jìn)行合并就可以得出連接策略了，其中間結(jié)果大小 為 20+30+20*30*0.06=86。,14,連接策略可以通過(guò)圖 3.11 所示的二叉樹(shù)表示。即(12)(34)。,分布式查詢優(yōu)化的方法,15, 當(dāng)兩個(gè)站點(diǎn)合