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

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

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

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

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

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

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

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

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

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

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

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

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