A Dynamic Materialized View Selection in a Cloud-Based Data Warehouse.pdf

1、數(shù)據(jù)倉(cāng)庫(kù)是在生產(chǎn)環(huán)境中提供決策支持的系統(tǒng)。傳統(tǒng)的數(shù)據(jù)倉(cāng)庫(kù)管理系統(tǒng)往往通過(guò)提高查詢(xún)性能來(lái)進(jìn)行優(yōu)化。這種優(yōu)化一般通過(guò)使用緩存、索引以及物化視圖而實(shí)現(xiàn)，優(yōu)化過(guò)程中也需要選擇一套最佳的數(shù)據(jù)結(jié)構(gòu)(物化視圖、索引等)。隨著云計(jì)算的快速發(fā)展，決策支持系統(tǒng)脫穎而出，并成為了一種新的挑戰(zhàn)模式，查詢(xún)優(yōu)化則成為云環(huán)境面臨的主要挑戰(zhàn)之一。
　　本文的目標(biāo)是將物化視圖的選擇引入到基于云計(jì)算的架構(gòu)中去。在基于云的數(shù)據(jù)倉(cāng)庫(kù)中，由于云環(huán)境的復(fù)雜性以及其按次計(jì)費(fèi)的

2、模式，導(dǎo)致執(zhí)行物化視圖的選擇頗具挑戰(zhàn)性。因而，在云環(huán)境中，物化視圖的選擇不應(yīng)基于查詢(xún)得到的元組數(shù)或查詢(xún)次數(shù)而完成，而應(yīng)該考慮CPU的消耗、帶寬的使用率、以及存儲(chǔ)空間等。
　　我們可以看到，財(cái)政預(yù)算有限的用戶(hù)只能接受一個(gè)漫長(zhǎng)的查詢(xún)響應(yīng)時(shí)間，但具有較足的預(yù)算的用戶(hù)可以忽略成本，并要求一個(gè)非常快的響應(yīng)時(shí)間。我們可通過(guò)構(gòu)建物化視圖來(lái)完成這一目標(biāo)，這里的挑戰(zhàn)在于如何選擇一組視圖并能在云環(huán)境中得以物化，以提高查詢(xún)處理響應(yīng)時(shí)間和降低云計(jì)算的成本

3、。有如下三種情況需要考慮：
　　有限的預(yù)算：給定一個(gè)預(yù)先的財(cái)務(wù)預(yù)算，這里的關(guān)鍵在于如何選擇正確的數(shù)據(jù)集視圖，并將其在云環(huán)境中進(jìn)行物化以盡量減少查詢(xún)響應(yīng)時(shí)間。
　　響應(yīng)時(shí)間的限制：在有限的響應(yīng)時(shí)間內(nèi)，這里的關(guān)鍵是如何選擇一組物化視圖來(lái)減少財(cái)務(wù)費(fèi)用。
　　預(yù)算和時(shí)間之間的權(quán)衡：在這種情況下，我們必須對(duì)查詢(xún)響應(yīng)時(shí)間和財(cái)務(wù)預(yù)算之間進(jìn)行權(quán)衡。我們的目標(biāo)是選擇一組視圖并將其在云環(huán)境中進(jìn)行物化，并能給出一種最佳方案來(lái)解決查詢(xún)響應(yīng)時(shí)間

4、與財(cái)務(wù)預(yù)算的問(wèn)題。
　　基于上述問(wèn)題，本文的主要研究工作如下：
　　首先，文中定義了一種費(fèi)用模型，該模型適用于云環(huán)境下的按需付費(fèi)模式，并在費(fèi)用預(yù)算限制下，根據(jù)CPU的功耗來(lái)實(shí)現(xiàn)物化視圖的多標(biāo)準(zhǔn)優(yōu)化。
　　其次，本文提出了一種基于費(fèi)用成本的動(dòng)態(tài)物化視圖選擇算法，該算法考慮了計(jì)算復(fù)雜度、存儲(chǔ)開(kāi)銷(xiāo)以及轉(zhuǎn)移成本。通過(guò)使用前述工作中定義的查詢(xún)預(yù)測(cè)，本文提出的算法能動(dòng)態(tài)地選擇最佳物化視圖。
　　費(fèi)用模型是視圖選擇問(wèn)題中的一個(gè)

5、重要問(wèn)題，在預(yù)算有限的情況下，它有助于實(shí)現(xiàn)物化視圖的多目標(biāo)優(yōu)化（CPU利用率，帶寬消耗和磁盤(pán)分配）。
　　使用物化視圖意味著要修改計(jì)算成本，因?yàn)椴樵?xún)處理可能會(huì)利用物化視圖，而視圖則需要選擇和維護(hù)。通過(guò)使用一組視圖來(lái)響應(yīng)查詢(xún)而產(chǎn)生的計(jì)算成本包括處理成本，物化成本和維護(hù)成本。
　　處理費(fèi)用通常由查詢(xún)負(fù)載Q、物化視圖集V、租用云實(shí)例的配置和查詢(xún)的頻率來(lái)產(chǎn)生。查詢(xún)可能會(huì)使用物化視圖的內(nèi)容，而無(wú)需重新計(jì)算其結(jié)果。對(duì)視圖進(jìn)行物化需要執(zhí)行

6、相關(guān)的查詢(xún)，在云環(huán)境中，這樣的操作是需要付費(fèi)的，而且還會(huì)產(chǎn)生物化成本。如果對(duì)源數(shù)據(jù)集進(jìn)行了大量的修改，那么物化視圖集也需要得到更新。更新或維護(hù)成本與更新物化視圖的時(shí)間和頻率是成正比的。
　　存儲(chǔ)成本是一個(gè)重要的問(wèn)題，尤其是在基于云的架構(gòu)中，任何存儲(chǔ)的數(shù)據(jù)需要按存儲(chǔ)時(shí)間支付。隨著云計(jì)算存儲(chǔ)中的數(shù)據(jù)可以在多個(gè)服務(wù)器和多個(gè)位置進(jìn)行跨越，數(shù)據(jù)的安全性則成為了一個(gè)重要問(wèn)題。因此，使用物化視圖來(lái)提高查詢(xún)的性能意味著要在云中存儲(chǔ)選定的視圖，并支

7、付相應(yīng)的費(fèi)用。數(shù)據(jù)存儲(chǔ)成本和數(shù)據(jù)的大?。ǔ跏紨?shù)據(jù)集和物化視圖）及存儲(chǔ)時(shí)間是成正比的。
　　對(duì)于數(shù)據(jù)處理、存儲(chǔ)和分發(fā)，云計(jì)算已經(jīng)成為一個(gè)可行的、主流的解決方案，但大量數(shù)據(jù)在云中進(jìn)出及 TB級(jí)的數(shù)據(jù)大小是一個(gè)不可逾越的挑戰(zhàn)。因此，數(shù)據(jù)傳輸?shù)某杀緹o(wú)法在我們的成本模型被忽略。
　　數(shù)據(jù)傳輸成本或帶寬消耗成本取決于輸入數(shù)據(jù)的大小、物化視圖的輸出數(shù)據(jù)、物化視圖的整個(gè)數(shù)據(jù)集（初始數(shù)據(jù)集和插入數(shù)據(jù)）以及CSP的原子轉(zhuǎn)移成本。
　　本文

8、提出的物化視圖選擇方法是基于PR_Q系統(tǒng)預(yù)測(cè)的，它能作為一個(gè)完整的視圖管理體系運(yùn)作。它能預(yù)測(cè)下一個(gè)查詢(xún)并為其進(jìn)行視圖的物化。我們的算法對(duì)視圖選擇有兩個(gè)階段：?jiǎn)?dòng)和在線(xiàn)階段。
　　在啟動(dòng)階段，系統(tǒng)通過(guò)輸入的查詢(xún)流開(kāi)始工作，查詢(xún)流（THQ）的閾值由數(shù)據(jù)庫(kù)管理員指定。我們假設(shè)大家對(duì)查詢(xún)流都比較了解。對(duì)查詢(xún)流很熟悉的話(huà)能使我們?yōu)樽约旱乃惴ㄗ鞒鏊璧墓浪恪?dòng)階段包含有兩個(gè)連續(xù)的步驟：兩階段優(yōu)化方法（2PO）和背包0/1優(yōu)化。首先，基于兩階

9、段優(yōu)化方法，它執(zhí)行了靜態(tài)視圖選擇。兩階段優(yōu)化方法結(jié)合了迭代優(yōu)化算法（II）和模擬退火優(yōu)化算法（SA）。
　　在許多改進(jìn)算法中，該迭代改進(jìn)算法通過(guò)一系列的迭代來(lái)優(yōu)化初始解。通過(guò)使用眾所周知的爬山算法，該迭代改進(jìn)是基于局部?jī)?yōu)化的。該算法開(kāi)始時(shí)，選擇一個(gè)隨機(jī)的初始狀態(tài)。接著它隨機(jī)選擇一些鄰值，并對(duì)它進(jìn)行分析。該算法隨機(jī)執(zhí)行一系列變動(dòng)，并且僅接受下坡移動(dòng)，直到它到達(dá)一個(gè)局部最小值。
　　找到一個(gè)局部最小值后，將會(huì)隨機(jī)生成一個(gè)新的狀態(tài)

10、，該算法將在這一狀態(tài)不停地執(zhí)行直到滿(mǎn)足停止的條件。
　　模擬退火源于統(tǒng)計(jì)力學(xué)，模擬退火技術(shù)最先用于視圖選擇問(wèn)題，該算法模仿固體的退火原理，將固體加溫至充分高，再讓其徐徐冷卻，加溫時(shí)，固體內(nèi)部粒子隨溫升變?yōu)闊o(wú)序狀，內(nèi)能增大，而徐徐冷卻時(shí)粒子漸趨有序，在每個(gè)溫度都達(dá)到平衡態(tài)，最后在常溫時(shí)達(dá)到基態(tài)，內(nèi)能減為最小。與迭代優(yōu)化算法類(lèi)似，達(dá)到某種概率的話(huà)，模擬退火技術(shù)將接受上坡移動(dòng)。該算法的每個(gè)步驟中的概率值都會(huì)下降，并最終只接受下坡移動(dòng)。這

11、種技術(shù)使得模擬退火技術(shù)比迭代改進(jìn)更加優(yōu)化。
　　接受上坡移動(dòng)的原因是，一些局部極小值相互逼近，需要通過(guò)少量的上坡移動(dòng)來(lái)分離。如果算法只執(zhí)行下坡移動(dòng)，即進(jìn)行迭代優(yōu)化，它會(huì)停留在第一個(gè)訪(fǎng)問(wèn)到的局部最小值。
　　在基于云計(jì)算的架構(gòu)中，視圖選擇問(wèn)題實(shí)質(zhì)上是貨幣成本的優(yōu)化問(wèn)題，我們發(fā)現(xiàn)有必要在我們的算法中集成一個(gè)優(yōu)化的過(guò)程，該過(guò)程需要考慮到用戶(hù)的財(cái)務(wù)預(yù)算（本文算法中的BL變量）。在我們的例子中，我們只考慮到預(yù)算有限的情況，即預(yù)先給定一

12、個(gè)財(cái)務(wù)預(yù)算，關(guān)鍵在于選擇一組能在云環(huán)境中進(jìn)行物化的視圖，在預(yù)算受限制的情況下減少查詢(xún)響應(yīng)時(shí)間。為解決這一問(wèn)題，我們選擇了一種動(dòng)態(tài)編程方法來(lái)引用0/1背包優(yōu)化。
　　在線(xiàn)階段是系統(tǒng)的運(yùn)行時(shí)階段。在這一階段，系統(tǒng)對(duì)預(yù)測(cè)的視圖進(jìn)行物化，此外，系統(tǒng)能識(shí)別出一些沒(méi)有意義的視圖并將其刪除。
　　在線(xiàn)視圖選擇問(wèn)題可以定義如下：給定一個(gè)已經(jīng)物化的視圖集和一個(gè)查詢(xún)負(fù)載，接著按照資源受限情況，基于對(duì)查詢(xún)的預(yù)測(cè)重新選擇一組物化視圖。
　　未