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

彭 成，佟秋利

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

0 引 言

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

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

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

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

1 物化視圖概念介紹

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

2 物化視圖的選擇及調整

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

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

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

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

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

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

3 數據立方體格結構圖

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

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

（1）（A，B，C，D），即數據集本身

（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，即不劃分的數據

這些物化視圖按照維度的包含關系可以生成格結構圖，維度的包含關系也表明了對于相應查詢的包含關系，即若一個物化視圖是包含另一個的，那么它可以進行另一個物化視圖能夠進行的所有查詢。上面的物化視圖集能夠形成的數據立方體格結構圖如圖1所示。

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

圖1 數據立方體格結構

4 BWCC權重及相對收益計算模型

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

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

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

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

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

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

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

5 BWCC算法實現

在借鑒已有的算法基礎上，本文給出了基于查詢習慣和加權相對收益的動態選擇及調整算法，算法的流程圖如圖2所示。

圖2 BWCC算法流程

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

算法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；

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

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

算法2：物化視圖集調整算法

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

輸出：物化視圖集MV

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

由q來回答a；

｝

else從原始多維數據集聚集計算回答a；

Count（q）＋＋；／／a對應的視圖計數增加

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

Count＿all＋＋；／／全局更新計數增加

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

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

調用局部更新的算法；

｝

else｛調用全局更新算法；｝

Return MV；

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

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

輸入：查詢對應的視圖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；

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

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

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

輸出：物化視圖集MV

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

for each q in V｛

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

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

Count（q）＝0；／／清零查詢計數

｝

對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），與排序算法相同。在系統運行過程中，隨著用戶查詢的到來，還會進行局部更新和全局更新，局部更新的時間復雜度與視圖數量無關，耗時較少；全局更新的時間復雜度和初始選擇相同，也是O（nlogn）。

6 實驗分析

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

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

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

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

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

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

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

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

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

7 結束語

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

［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技術在生產評價中的應用［J］.計算技術與自動化，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的企業數據倉庫分析模型設計與實現［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的高校教學協同決策［J］.計算機應用，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的數據挖掘模型的研究與應用［J］.機械設計與制造，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.