基于查詢和相對收益的物化視圖選擇算法

彭 成，佟秋利

（1.清華大學 計算機科學與技術(shù)系，北京100084；2.清華大學 計算機與信息管理中心，北京100084）

0 引 言

在多維聯(lián)機分析系統(tǒng)中，將數(shù)據(jù)進行聚集生成物化視圖預先存儲起來，對一些查詢可以直接給出結(jié)果，而不必進行聚集計算，提高了查詢的效率。物化視圖需要占用空間，對于高維度的數(shù)據(jù)集來說，可以生成的物化視圖的總個數(shù)隨著維度上升成指數(shù)級增長，需要進行物化視圖的選擇。

目前物化視圖選擇的策略較多，但是并沒有得到普遍的最優(yōu)算法，物化視圖選擇調(diào)整問題本身也被證明為NPHard問題［1］。在數(shù)據(jù)倉庫系統(tǒng)運行過程中，對著用戶查詢的不斷變化，已有的選擇策略可能并不能滿足當前的用戶查詢習慣，如何準確地把握用戶查詢類型的分布，并選擇合適的時間段進行調(diào)整，是當前研究的重要問題。

Theodoratos D提出了對物化視圖定期地進行動態(tài)調(diào)整的方法，通過判斷用戶一段時間內(nèi)的查詢情況變化，結(jié)合物化視圖本身的查詢代價綜合考慮，選擇合適的時間進行調(diào)整。除了這種階段性調(diào)整的方式之外還有實時動態(tài)調(diào)整的方式，Cohen E提出了按照查詢請求的變化來實時改變每個物化視圖的優(yōu)先級，進行實時調(diào)整。不過這種方式調(diào)整又過于頻繁，對于查詢請求比較多的情況下不適用，另外視圖集經(jīng)常變化，不夠穩(wěn)定，對于隨機性強的查詢并不是很實用。

本文提出了根據(jù)查詢進行動態(tài)調(diào)整的選擇算法，同時又考慮到視圖的收益和占用空間，而且可以由用戶自行設(shè)定維屬性權(quán)重，不斷調(diào)整出最適合的物化視圖選擇方案。

1 物化視圖概念介紹

為了能夠更快地得到查詢結(jié)果，在多維聯(lián)機分析系統(tǒng)中，也會采用類似于視圖的策略，將數(shù)據(jù)進行聚集處理并預先存儲起來作為中間結(jié)果，當查詢訪問需要利用到其結(jié)果時可以直接給出，而不必進行聚集計算，這個中間結(jié)果便是物化視圖。對于傳統(tǒng)的二維數(shù)據(jù)庫，視圖的存在方便了查詢，但是視圖本身是一個虛表，并不真實存在，只是方便用戶瀏覽的一種形態(tài)，在實際查詢時還是會調(diào)用原始數(shù)據(jù)庫進行計算，在效率上并沒有提高，查詢時也需要重新進行計算。而物化視圖則不同，它是真實存在的中間結(jié)果，可以提高查詢的效率。在OLAP查詢中，有時會遇到很復雜并且需要調(diào)用多個維度，涉及到多種數(shù)據(jù)的查詢，這個時候需要對數(shù)據(jù)進行連接、投影等操作，其對時間的消耗是很大的，如果每次都需要進行重新計算，則滿足不了聯(lián)機分析系統(tǒng)對查詢的快速響應(yīng)要求。物化視圖的出現(xiàn)解決了這一問題，它對可能需要調(diào)用到的結(jié)果事先進行投影、連接、選擇等操作生成中間數(shù)據(jù)并存放起來，是真實地存放在數(shù)據(jù)倉庫中的，每次查詢時可以直接從物化視圖返回結(jié)果，提高了查詢的效率。

2 物化視圖的選擇及調(diào)整

物化視圖的存在使得數(shù)據(jù)倉庫獲得了較快的查詢速度，物化視圖的選擇策略對查詢速度有著決定性的影響。目前物化視圖選擇的策略較多，但是并沒有得到普遍的最優(yōu)算法。完全物化的數(shù)據(jù)集的數(shù)據(jù)量隨著維度數(shù)量而指數(shù)級增長，對于高維度的數(shù)據(jù)倉庫，完全物化并存儲是難以實現(xiàn)的。因此，就需要選擇其中部分的物化視圖來存放，即物化視圖的選擇策略問題，在特定的空間限制條件下，選擇出合適的物化視圖集，使得數(shù)據(jù)倉庫對用戶查詢有著最快的響應(yīng)。

物化視圖的選擇策略一般由3個方面因素決定：存儲空間占用，維護代價以及生成物化視圖帶來的收益。

（1）存儲空間占用：由于物化視圖的大小各不相同，維度包含的越多，數(shù)據(jù)劃分的越精細的物化視圖一般占用的空間較多，即使它可以為用戶節(jié)省很多的時間，但是有時將空間節(jié)省下來存放更多的占用空間較少的物化視圖更為劃算。從本質(zhì)上來說，物化視圖的存在是用空間交換時間的技術(shù)，物化視圖的個數(shù)是受到約束的。

（2）維護代價：即當原始數(shù)據(jù)庫中的數(shù)據(jù)發(fā)生變化時，物化視圖作為實際存在的數(shù)據(jù)，也是需要同步更新來保持數(shù)據(jù)一致。對于較大的數(shù)據(jù)倉庫來說，更新數(shù)據(jù)的耗時會比較長，如果與之相關(guān)的物化視圖比較多，那么更新的代價就很大，這時需要減少物化視圖的數(shù)量以得到平衡。對于空間限制比較寬松的情況，物化視圖過多的話會影響到更新時的速度，所以如何尋找平衡點也是物化視圖選擇中一個重要的考慮因素。

（3）物化視圖帶來的收益：指不生成某個物化視圖和生成此物化視圖對查詢速度的貢獻，對于生成了物化視圖的情況，相應(yīng)的查詢可以直接得到結(jié)果，未生成物化視圖的查詢時間計算需要考慮到選擇、連接、聚集等幾個方面的運算速度。收益分為相對收益和絕對收益，相對收益是生成物化視圖對現(xiàn)有視圖集的效率改進。而絕對收益就是物化視圖對原始數(shù)據(jù)集的效率改進。一般進行收益計算時，采用的是相對收益，其更能反映實際的收益效果。

本文采用的方式是定期更新與根據(jù)查詢效率更新相結(jié)合的方式，一方面對每次查詢請求判斷是否生成相應(yīng)的物化視圖，通過一個閾值來作為是否生成的評判標準；另一方面設(shè)定一個固定時間進行全局性的物化視圖集的更新，主要是按照每個物化視圖集的權(quán)重進行排序并將靠前的物化視圖生成。當然已經(jīng)存在的不需要生成，只需要生成那些新出現(xiàn)的物化視圖。

3 數(shù)據(jù)立方體格結(jié)構(gòu)圖

對于物化視圖，每種維度有聚集和不聚集兩種選擇，共有2＾n個可能的物化視圖。如果一個物化視圖A的所有維度都在另一個物化視圖B中出現(xiàn)，即B將數(shù)據(jù)集劃分得更為精細，同時劃分方式是包括A的所有劃分方式的，此時B和A是一種偏序關(guān)系，記做A≦B，所有的可以由A計算的查詢都可以由B來計算得到。對于物化視圖的集合｛V1，V2，V3……Vn｝，它們之間以視圖之間的偏序關(guān)系作為箭頭，視圖本身作為結(jié)點形成的圖就叫做數(shù)據(jù)立方體的格圖。

例如，對一個有4個維度的數(shù)據(jù)集，4個維度分別為部門（A），科目（B），項目（C），年份（D），那么其可能的物化視圖共有2＾4＝16個，按照維度數(shù)量可以分組如下：

（1）（A，B，C，D），即數(shù)據(jù)集本身

（2）（A，B，C），（A，B，D），（A，C，D），（B，C，D）

（3）（A，B），（A，C），（A，D），（B，C），（B，D），（C，D）

（4）（A），（B），（C），（D）

（5）none，即不劃分的數(shù)據(jù)

這些物化視圖按照維度的包含關(guān)系可以生成格結(jié)構(gòu)圖，維度的包含關(guān)系也表明了對于相應(yīng)查詢的包含關(guān)系，即若一個物化視圖是包含另一個的，那么它可以進行另一個物化視圖能夠進行的所有查詢。上面的物化視圖集能夠形成的數(shù)據(jù)立方體格結(jié)構(gòu)圖如圖1所示。

其中的邊是從上往下的單向邊，上面是父結(jié)點，下面是子結(jié)點，每個結(jié)點表示一個物化視圖，結(jié)點的內(nèi)容即物化視圖中包含的維度。例如（A，B）表示按照部門和科目分類形成的物化視圖。（A，B，C，D），（A，B，C），（A，B，D）都存在流向（A，B）的通路，表明（A，B）這一物化視圖可以被它們生成，能從（A，B）得到結(jié)果的查詢都可以從上面3個物化視圖中任意一個通過聚集計算得到。

圖1 數(shù)據(jù)立方體格結(jié)構(gòu)

4 BWCC權(quán)重及相對收益計算模型

本文采用基于用戶查詢習慣和物化視圖加權(quán)相對收益的動態(tài)選擇算法。其考慮了視圖的大小，視圖的相對收益，另外還考慮了物化視圖所包含的每項屬性的權(quán)重，即特定的某項維度被查詢的可能性，另外系統(tǒng)根據(jù)用戶的查詢輸入進行學習，根據(jù)查詢頻率動態(tài)調(diào)整，保持提供最適合的物化視圖選擇方案。

影響選擇方案的核心因素有幾個：查詢頻率，特定維度的權(quán)重，視圖大小以及物化視圖帶來的相對收益。用Vq來表示視圖q的價值，并采用查詢驅(qū)動機制，每次查詢涉及到的視圖的價值相應(yīng)增大，不定期地更新物化視圖以滿足不斷變化的查詢需求。

（1）維度權(quán)重用來表示每項維度被查詢到的可能性的大小，初始化均為1，可由用戶自行定義更改，對于特定的物化視圖q，其維度權(quán)重Weight（q）為所有維度項權(quán)重的平均值。

（2）物化視圖q的相對收益Ben（q）表示物化視圖q給已有的物化視圖集帶來的查詢效率的改進，B（q，s）＝∑v≤qBv，其中v為在格結(jié)構(gòu)圖中q的子結(jié)點，Bv為q對于v帶來的查詢效率的改進。定義w為v的父結(jié)點中已經(jīng)生成物化視圖并且具有最少的元組數(shù)的節(jié)點，如果C（v）＜C（w），則Bv＝C（w）－C（v），否則Bv＝0。

（3）查詢頻率Count（q）表示視圖q被查詢到的次數(shù)，每個查詢都可以對應(yīng)到與查詢條件含有同樣維度條件的物化視圖q。

（4）物化視圖q的占用空間的大小是衡量其價值的另一因素，其與物化視圖包含的元組數(shù)C（q）成正比，在計算價值時可以直接用C（q）表示。對于具有一定稀疏度的多維數(shù)據(jù)集，實際生成的物化視圖尺寸往往會小一些。假定原始多維數(shù)據(jù)集的稀疏度為k，物化視圖較原數(shù)據(jù)集對n個維度進行了聚集，每個維度包含的屬性項數(shù)為d1，d2，……dn，原始數(shù)據(jù)集元組數(shù)量為a，則新物化視圖的元組數(shù)量C（q）估計值為

本文采用的算法對物化視圖價值Value（q）計算的公式 為Value（q）＝Ben（q）＊Weight（q）＊Count（q）2／C（q）。從上式可以看出，本文的算法中物化視圖q的價值Value（q）與其相對收益Ben（q）和視圖權(quán)重Weight（q）成正比，收益和維度權(quán)重越大，視圖價值越高；Value（q）與查詢到的次數(shù)Count（q）的平方成正比，查詢到的次數(shù)越多，視圖價值越高，同時在一段時間內(nèi)查詢到的次數(shù)越多，價值增長越快；Value（q）與視圖的元組數(shù)個數(shù)成反比，表示視圖越大，占用空間越多，其價值越低。

5 BWCC算法實現(xiàn)

在借鑒已有的算法基礎(chǔ)上，本文給出了基于查詢習慣和加權(quán)相對收益的動態(tài)選擇及調(diào)整算法，算法的流程圖如圖2所示。

圖2 BWCC算法流程

對于物化視圖的初始選擇，可以由用戶指定，也可以由系統(tǒng)根據(jù)設(shè)置的維度權(quán)重和視圖占用空間大小進行自行選擇，算法具體描述如下：

算法1：初始選擇物化視圖集算法

輸入：空間限制S，視圖集V

輸出：物化視圖集MV

／／初始化視圖集V中每個視圖q的價值Value＿begin（q）

for each q in V

Value＿begin（q）＝Weight（q）／Size（q）；

對所有q按照Value＿begin（q）從大到小進行排序；

while（S＞0）｛

for each q in V｛／／遍歷視圖集

／／選擇視圖加入物化視圖集

if（S－Size（q）＞0）｛

MV＝MV＋ ｛q｝；／／將視圖q加入物化視圖集

S＝S－Size（q）；／／減少剩余空間

｝｝｝

return MV；

對于物化視圖的初始選擇，可以由用戶指定，也可以由系統(tǒng)根據(jù)設(shè)置的維度權(quán)重和視圖占用空間大小進行自行選擇，Size（q）表示物化視圖q占用的空間大小，初始時的視圖價值是通過該視圖所包含的維度權(quán)重的平均數(shù)以及視圖大小綜合考慮的。維度權(quán)重的平均數(shù)越大，視圖包含的維度越容易被查詢到，其價值就越高，而視圖的占用空間越大，其價值就越低。

隨著用戶查詢的輸入，算法會根據(jù)查詢的頻率調(diào)整各個視圖的價值，并判斷是否需要進行物化視圖集的局部更新和全局更新。對于查詢輸入a，視圖調(diào)整的算法步驟如下：

算法2：物化視圖集調(diào)整算法

輸入：查詢a，物化視圖集MV

輸出：物化視圖集MV

if（MV中存在視圖q，a對應(yīng)的視圖＜＝q，且C（q）最?。?/p>

由q來回答a；

｝

else從原始多維數(shù)據(jù)集聚集計算回答a；

Count（q）＋＋；／／a對應(yīng)的視圖計數(shù)增加

Value（q）＝Ben（q）＊ Weight（q）＊ Count（q）＊Count（q）／C（q）；／／更新視圖q的價值

Count＿all＋＋；／／全局更新計數(shù)增加

／／當查詢未命中而且q價值增加較多時，調(diào)用局部更新的算法

if（Count＿all＜time ＆ ＆ 查詢未命中 ＆ ＆ Value（q）－Value＿old（q）＞val）｛

調(diào)用局部更新的算法；

｝

else｛調(diào)用全局更新算法；｝

Return MV；

每次查詢時，都會對相對應(yīng)的視圖的計數(shù)進行增加，不斷更新視圖的價值。更新后會計算視圖新的價值與舊的價值之差，當差值高于一定值時，說明此視圖最近比較常用，并且在這段時間內(nèi)可能會經(jīng)常用到，需要進行物化，以便提高之后的查詢效率和命中率。視圖局部更新的方法為先判斷當前空間限制是否足夠容納q，如果不足，則刪去價值最小的視圖，直到空間足夠，最后將q加入物化視圖集。

算法3：物化視圖集局部更新算法

輸入：查詢對應(yīng)的視圖q，物化視圖集MV，空間限制S

輸出：物化視圖集MV

if（S－Size（q）＞0）｛／／剩余空間滿足條件時，直接添加q進入物化視圖集

MV＝MV＋ ｛q｝；／／添加q到物化視圖集

S＝S－Size（q）；／／更新空間限制

｝else｛

／／空間不夠時，刪除物化視圖以騰出空間

while（S－Size（q）＜0）｛

獲得價值最小的物化視圖q′

MV＝MV－q′；／／將其刪除

S＝S＋Size（q′）；／／更新空間限制

｝

MV＝MV＋ ｛q｝；／／添加q到物化視圖集

S＝S－Size（q）；／／更新空間限制

｝

return MV；

當過了一定長度的時間后，用戶的習慣可能已經(jīng)發(fā)生了變化，此時需要對物化視圖進行全局的更新，利用歷史價值信息以及視圖本身的價值進行綜合判斷，選擇合適的視圖進行物化完成全局更新的操作。全局更新的方法與初始選擇類似，不同的是對于視圖價值的計算，全局更新是對當前視圖價值乘以歷史系數(shù)Value（q）＝Value（q）＊v＿his，其值在0到1之間，可以參考用戶習慣的延續(xù)性進行設(shè)定。

算法4：物化視圖集全局更新算法

輸入：物化視圖集MV，空間限制S，歷史系數(shù)v＿his

輸出：物化視圖集MV

／／對V中每個視圖q計算價值

for each q in V｛

Value（q）＝Value（q）＊v＿his；／／計算時乘以歷史系數(shù)v＿his

Value＿old（q）＝Value（q）；／／更新 Value＿old的值

Count（q）＝0；／／清零查詢計數(shù)

｝

對V中的所有視圖按照價值從大到小進行排序；

／／從大到小加入物化視圖集

While（S＞0）｛

for（each q in V）｛

if（S－Size（q）＞0）｛／／空間足夠時添加q到物化視圖集

MV＝MV＋ ｛q｝；／／加入物化視圖集

S＝S－Size（q）；／／更新空間限制

｝｝｝

return MV；

本文中的BWCC算法的在初始選擇時的復雜度是O（nlogn），與排序算法相同。在系統(tǒng)運行過程中，隨著用戶查詢的到來，還會進行局部更新和全局更新，局部更新的時間復雜度與視圖數(shù)量無關(guān)，耗時較少；全局更新的時間復雜度和初始選擇相同，也是O（nlogn）。

6 實驗分析

本文將BWCC算法與貪心算法和排序算法進行對比，分析了其時間復雜度，測試了其查詢命中率和總體收益。本文在CPU 類型為 Genuine Intel（R）T2050 1.60GHz，1.60GHz的計算機中進行測試，測試對象為一個維度層次項個數(shù)為10，每項對應(yīng)的屬性值個數(shù)為5，事實項個數(shù)為2的多維數(shù)據(jù)集，空間限制為10%。

測試分為兩組數(shù)據(jù)進行，第一組數(shù)據(jù)為完全隨機生成的1000個查詢，每個維度屬性在查詢中出現(xiàn)的概率相同，均為0.5。第二組分為3個階段，每階段1000個查詢，并讓其中指定的10個維度屬性在查詢中出現(xiàn)的概率增至0.8，其余40個維度屬性的出現(xiàn)概率更改為0.2。對于不同的階段，更換指定的10個維度，用以表現(xiàn)用戶習慣的歷史延續(xù)性。

第一組查詢命中率比較如圖3所示。

圖3 第一組查詢命中率比較

對于第一組查詢，由于查詢是完全隨機的，所以3種算法在命中率上差別并不大。對于靜態(tài)的貪心算法和排序算法來講，在初始選擇物化視圖集后就不作變化，其命中率也只和初始的選擇有關(guān)。對于BWCC算法，它的動態(tài)調(diào)整機制對于完全隨機的查詢沒有意義，其初始選擇算法和排序算法相同，也是按照尺寸大小進行排序，因此其命中率也和排序算法接近?？傮w來講，3種算法在對于完全隨機的用戶查詢，其命中率是大體接近的。

第二組查詢命中率比較如圖4所示。

對于具有一定規(guī)律的用戶查詢，查詢的結(jié)果走勢大致分為三段，每段對應(yīng)1000個查詢。對于貪心算法和排序算法來說，物化視圖在初始確定之后就不變了，命中率取決于被賦予高出現(xiàn)概率的維度屬性是否有其物化視圖在初始時被生成。排序算法和貪心算法的命中率隨著維度屬性出現(xiàn)概率的分布變化而變化，時高時低，呈現(xiàn)隨波逐流的態(tài)勢，而不能保持一個相對穩(wěn)定的命中率。

圖4 第二組查詢命中率比較

對于BWCC算法，在上面的實驗中，大體分為3個階段。每個階段的命中率都是開始較低，而后逐漸升高。逐漸升高的原因是它隨著用戶查詢不斷調(diào)整自己的物化視圖集。而每當查詢偏好變化時，由于其之前生成的物化視圖集與新的查詢習慣不一定匹配，所以命中率會出現(xiàn)一定的下降，隨著時間的推移，其自我調(diào)整的機制又將命中率不斷提高?？梢钥闯觯槍@種有一定側(cè)重的查詢集合，BWCC算法的命中率要高于貪心算法和排序算法，對于查詢偏好的變更也有較好的處理能力，本文中的BWCC算法在命中率上具有較大優(yōu)勢。

7 結(jié)束語

本文對數(shù)據(jù)倉庫系統(tǒng)中的物化視圖選擇問題進行了研究，提出了基于習慣和加權(quán)相對收益的動態(tài)選擇及調(diào)整算法BWCC，此算法考慮了視圖的相對收益、視圖尺寸、維屬性權(quán)重以及用戶查詢習慣，可以根據(jù)查詢的偏好進行動態(tài)的調(diào)整，提高了命中率。另外用戶也可以給不同的維度屬性賦予不同的權(quán)重來表示其被查詢到的可能性大小，權(quán)重也會影響到系統(tǒng)對于物化視圖集的選擇，可以更好地對用戶偏好做出改變?？傮w來說，這一算法的命中率高于傳統(tǒng)選擇算法，還可以根據(jù)用戶習慣進行動態(tài)調(diào)整，時間復雜度與傳統(tǒng)選擇算法差別不大，相對于傳統(tǒng)算法有較大的優(yōu)勢。

［1］PMark Whitehorn，PRobert Zare，Mosha Pazusmansky.Problem solving for MDX for SQL Server 2005［M］.New York：Springer－Verlag，2007：105－131.

［2］LI Caihua.Application of OLAP technology in production evaluation［J］.Computing Technology and Automation，2009，28（4）：133－137（in Chinese）.［李才華.OLAP技術(shù)在生產(chǎn)評價中的應(yīng)用［J］.計算技術(shù)與自動化，2009，28（4）：133－137.］

［3］LAN Jian，JIN Hongmei.The design and realization of OLAP based data warehouse analysis model in enterprises［J］.Process Automation Instrumentation，2006，27（5）：9－12（in Chinese）.［藍箭，金紅梅.基于OLAP的企業(yè)數(shù)據(jù)倉庫分析模型設(shè)計與實現(xiàn)［J］.自動化儀表，2006，27（5）：9－12.］

［4］CHEN Qimai，HE Chaobo，LIU Hai.OLAP－based collaborative educational decision［J］.Computer Applications，2009，29（1）：304－305（in Chinese）.［陳啟買，賀超波，劉海.基于OLAP的高校教學協(xié)同決策［J］.計算機應(yīng)用，2009，29（1）：304－305.］

［5］Themis Palpanas，Nick Koudas，Alberto O Mendelzon.On space constrained set selection problems［M］.England：Data Knowl，2008：200－218.

［6］JIANG Nan，GAO Wei，ZHANG Liqiu.Research and application of data mining model based on analysis services［J］.Machinery Design ＆ Manufacture，2007（4）：83－85（in Chi－nese）.［姜楠，高巍，張麗秋.基于Analysis Services的數(shù)據(jù)挖掘模型的研究與應(yīng)用［J］.機械設(shè)計與制造，2007（4）：83－85.］

［7］Kobra Etminani，Prof M Naghibzadeh.A min－min max－min selective algorithm for grid task scheduling［C］／／Uzbekistan：3rd IEEE／IFIP International Conference in Central Asia，2007：1－7.

［8］Dong F，Akl S G.Scheduling algorithms for grid computing：state of the art and open problems［R］.Technical Report，2006.

［9］Tang Zhaohui，Jamie MacLennan.Data mining with SQL server 2005［M］.Beijing：Tsinghua University Press，2007：45－53（in Chinese）.［Tang Zhaohui，Jamie MacLennan.Data mining with SQL server 2005［M］.北京：清華大學出版社，2007：45－53.］

［10］Gupta H，Mumick I S.Selection of views to materialize under a maintenance cost constraint［C］／／ICDT，1999：453－470.