基于自動累加表的查詢優化技術

摘要:商務數據庫中，決策支持相關的查詢變得越來越頻繁。使用什么樣的技術來滿足不斷變化的信息源和快速響應的系統需求是查詢優化要解決的一個重大技術問題。本文提出原子視角的概念，并對區分視角的粒度選擇進行了詳細分析，使用EQGM模型尋找候選自動累加表，然后通過匹配函數和規則進行自動累加表的規劃。通過訪問自動累加表來實現查詢性能的優化和提升。實際項目運行結果表明，查詢性能很大程度上獲得了優化。

關鍵詞:原子視角;自動累加表;自動累加表規劃;數據粒度;匹配函數

1 引言/背景

決策支持系統(Decision Supporting System， DSS)最大的特點和優點就是數據積累[1]，它最基本的兩個組成部分就是數據的輸入和輸出，而報表是數據輸出的主要手段。報表不僅是對業務活動過程的記錄，及時反映企事業各部門的經營狀況，還能從歷史數據中進行數據挖掘歸納總結出有規律的信息，為管理決策層提供準確、直接的數據。

近年來，決策支持相關的查詢有了很大的發展[4]。這些查詢基本上要對海量數據進行多重連接和復雜的聚集操作。這些查詢交互性需求變得越來越普遍，而且要求系統以秒為單位進行快速響應。傳統的優化技術往往不能滿足這些要求。

一般有兩種方法對多重，分布或異構數據庫的數據進行信息整合:虛擬視圖技術和數據倉庫的物化視圖技術。物化視圖是一個定時刷新的預存計算結果的表。當信息源經常變化時，虛擬試圖的方法比較好。當信息源變化不是太頻繁并且需要很快的查詢響應時間時，物化視圖的方法更有效。選擇合適的基本數據的“共享”部分進行物化而不是物化所有的視圖是一種更有效的方法。用戶查詢可以通過獲取物化視圖而不是原數據來優化查詢。

本文提出的自動累加表功能上和物化視圖類似，但是它是實際存在的物理表，將查詢頻率比較高和與業務查詢密切相關的屬性制作成自動累加表，可以同時滿足信息源變化頻繁和快速響應時間的要求。本文首先提出原子視角的概念，它消除了視角之間的函數依賴關系;然后使用EQGM模型工具來對統計查詢進行了分析，從而得到查詢和更新頻率比較高的表以及它們的屬性，并將它們作為候選自動累加表;然后遵循一定的規則和匹配函數，將這些表和屬性制作成自動累加表(Automatic Summary Table，AST)，并對自動累加表的累加程度進行了分析。在統計查詢時就可以查詢這些自動累加表，而不是事實表和維表，來實現查詢性能的提升和優化。

2 相關文獻

報表統計和數據庫系統一般都是息息相關的，數據庫的設計直接影響到報表統計的效率。根據應用系統的需要，有時一張報表與數據庫中數張表相關聯，使得報表統計的查詢語句變的相當復雜，從而影響了報表的查詢效率。報表的查詢優化一般可以歸為三大類:

(1)創建臨時表。當系統應用有多張表關聯的時候，且這些表數據比較龐大，而發現其中的某一張或者某幾張表關聯后得到的結果集非常小并且希望查詢得到這個結果集的速度非常快，可以考慮創建“臨時表”[2]。

(2)分裂大表。分裂大表可以分為臨時分裂和永久分裂兩種[3]。在永久分裂的基礎上加設一個索引表，索引表中存放所有子表的名稱和子表分裂的條件，索引表是該類信息的唯一操作入口。

(3)基于物化視圖的查詢優化。

①自動累加表(Automatic Summary Table， AST)。AST實際上是一種帶有聚集函數的物化視圖，考慮到其優化過程的自動性，所以稱為自動累加表。文獻通過QGM(Query Graph Model)工具，提出了查詢和AST匹配模型，還歸納總結出了4種統一的匹配模式[5];然后通過AST對查詢進行重寫，查詢時直接訪問AST來實現查詢的優化。

②重構視圖(Restructured View)[6]。提出了一個可以將普通視圖和重構視圖統一處理的查詢優化框架，適用于SQL的選擇-投影-聯接查詢和有無聚集函數的視圖。作者還對重構視圖進行了可用性分析和查詢重寫的介紹。

③物化視圖的選擇。綜合考慮存儲空間、查詢性能和維護成本等方面要求，提出了物化視圖的兩階段選擇算法MPL和MPL-CV[7]。

④MVPP。提出一個基于Multiple View Processing Plan(MVPP)[8]的啟發式算法，從查詢性能和維護成本因素考慮選擇什么樣的視圖進行物化;還將物化視圖的設計問題映射成0-1整形規劃問題，保證了最優解的存在。

⑤兩階段算法。第一階段負責優化總的查詢響應時間，第二階段在給定的維護時間成本約束下選擇合適的視圖進行物化[4]。

本文從數據粒度角度對原子視角進行了進一步的優化選擇，同時針對自動累加表的規劃過程提出了三條原則和AST的更新原則。

3 相關概念和定義

3.1事實表和維表

度量是數據的實際意義，也稱為事實，即描述數據“是什么”。維是人們觀察數據的特定角度。人們觀察數據的某一維時可能存在細節程度不同，維的這種數據層次結構就是維的層級。一個維通常具有多個層級，例如時間維可以從日期、月份、季度、年等不同層級來進行描述。

事實表[9]是用來描述和存儲多維立方體的度量值及各個維的碼值，用于存放企業大量的事實數據，通常數據量都很大，且非規范化程度很高;維表[9]是用來描述維信息，它是圍繞事實表建立的較小的表。一般用關系數據庫的二維表來表示事實表和維表，也就是用“星形模式”和“雪花模式”來表示多維數據模型。星形模式通常有一個中心表(事實表)和多個維表組成。雪花模式是對星型模式的擴展。雪花模式[9]對星型模式的維表進一步層次化，將原來的各維表進一步的細化，拆分為更詳細的維表，形成一些局部的“層次”區域。如圖1所示的售票表和相關聯的維表的雪花模式圖，白色的表示事實表，灰色的表示維表。

3.2原子視角的規范化

在報表查詢過程中，用戶通過輸入不同的查詢條件進行相應的查詢。系統需要知道從什么角度對用戶需求數據進行篩選統計，然后按一定的排列方式呈現出來，這里引入查詢視角的概念。所謂查詢視角(Query Viewpoint)指的是系統從什么視角什么角度對數據進行篩選查詢。系統會從不同的角度對數據庫中的數據進行查詢統計，用集合來表示一個應用系統的所有查詢視角的集合:。

實際情況下， 的 個查詢視角中，有的視角可能通過其他的視角來進行表示，如售票金額、售票數量和單價，只需要知道其中的兩個，然后根據它們之間的函數關系得到另一個的值。在查詢過程中，只需要知道這些相關聯視角的部分，通過它們的函數關系得到全部的視角數值。為此引入原子視角的概念。所謂原子視角(Atomic Viewpoint)，它實際上是一種特殊的查詢視角集合，它消除了查詢視角中的函數依賴關系，記為，其他的非原子視角記為原子視角滿足以下規則:

因此，。公式1表示，在原子視角集合中，任意的原子視角之間都是獨立正交的，不存在函數依賴，體現了它的原子性。公式2表示，在所有的統計視角中，任意一個視角都可以通過原子視角集合中的元素來進行表示。公式3，4表示，在原子視角集合中，原子視角可以通過一個非原子視角和其他的原子視角來表示，而這個非原子視角也是不可再分的。

在原子視角中，根據它們功能的不同分為兩類:區分視角(Differentiation Perspective)和聚集視角(Aggregation Perspective)。所謂區分視角，指系統通過這些視角來篩選數據庫中所需要的屬性，對應于維表中的主碼。一般用在查詢中的選擇-投影-連接運算中，但是不包含聚集函數，記為。聚集視角是查詢中用于聚集函數中的屬性，負責分組和聚集函數的計算，記為。因此，原子視角還可以表示為:。對于一個具體的區分視角來講，還存在一個數據粒度[10]問題。即當某個維度存在不同層級時，應選擇某維的哪個層級作為區分視角才會使查詢更有效率。如果選擇的維的層級太高，查詢效率很高，但可以響應的查詢就會受到限制;如果選擇的維的層級太低，雖然可以響應大部分的查詢，但是查詢效率低下，而且操作復雜。因此，選擇維的哪個層級作為區分視角要綜合考慮數據粒度的利弊。圖2是一個事實表和它的維的層級結構。

以財務款項流動這個維度即“售票員-售票窗口-港口-船務公司”來說明如何在某維度上選擇合適的粒度。用維度上層級為的查詢成本來表示，，其中表示第個查詢的查詢頻率，表示第個查詢消耗的系統資源，系統消耗的系統資源和需要處理的數據量成正比，所以可以用要處理的數據量作為表示。目標就是選擇某一維度上最小的層級作為該維度上的區分視角。如果相同維度下存在兩個相同的查詢成本或者存在兩個查詢成本，值很接近，但明顯大于其余層級的查詢成本時，可以將這個維度的兩個層級拆分為兩個維度，分別都作為區分視角。

3.3EQGM(Extendable Query Graph Model)

EQGM是QGM(Query Graph Model)[5]的擴展形式，惟一的不同是QGM的葉節點是表，而EQGM在葉節點上添加了查詢用到的屬性。在EQGM中，查詢通過一個非環形有向圖來表示，其中葉節點表示帶有屬性的基本表，中間節點表示對表的操作，而邊表示從子節點到父節點的記錄流。每個非葉節點通過對輸入數據的操作之后會產生一個關系表，輸入數據也是一系列的關系表。EQGM的根結點返回最終的查詢結果。

EQGM中的中間節點通過它們的操作類型來劃分。最常見的兩種類型為SELECT節點和GROUP-BY節點。SELECT節點代表查詢的選擇-投影-連接部分，通過使用WHERE或HAVING謂詞來計算所有的出現在SELECT和GROUP-BY語句中的標量表達式。GROUP-BY節點執行分組并計算聚集函數。如圖3中底部的SELECT節點通過SaleWindow-key(售票窗口編碼)=Window-key(窗口編碼)實現了window和Ticketselling表的連接，通過選擇謂詞WindowName(售票窗口名稱)=Yantai01篩選售票窗口為yantan01的記錄。GROUP-BY節點通過SaleID(售票人編碼)，SaleWindow-key進行分組，并計算SUM(price)的值。最后，頂部的SELECT節點通過HAVING謂詞sm>10，000輸出最終查詢結果。

4. 統計匹配模型

4.1 匹配函數和自動累加表的規劃

所有的統計(Statistics)集合記為，根據查詢視角和原子視角的定義得知，一個具體的統計 可以表示為:

考慮到一般的統計視角都可以通過原子視角來進行表示，所以在實際分析統計查詢的時候，可以將統計簡化為。對于一些不包含聚集函數的查詢統計，查詢結果只需要調用數據庫中維表的明細信息即可，相對來說操作不是很復雜，在這里不作考慮。因此，如果中為空，。每一個統計都是對表的一系列操作，本節使用EQGM模型工具來對統計查詢進行分析，得到查詢和更新頻率比較高的表以及它們的屬性，并將它們作為候選自動累加表;然后遵循一定的規則和匹配函數，將這些表和屬性制作成自動累加表(Automatic Summary Table，AST)，并從查詢性能和維護成本等方面對自動累加表的累加程度進行了分析。在統計查詢時就可以查詢這些自動累加表，而不是事實表和維表，來實現查詢性能的提升和優化。

對于一個統計查詢，它的EQGM圖4可以統一的表達為如圖所示的形式。

首先要定義幾個概念。如圖4，在EQGM中最底層的GROUP-BY節點稱為，最底層的葉節點稱為，非最底層的葉節點稱為，通常是維表。由于本文討論的是非空的統計查詢，所以圖中至少有一個GROUP-BY節點，即一定存在。將及其以下的sub-EQGM所使用的表和表中的屬性記錄下來作為候選的自動累加表(Candidate Automatic Summary Table，)。在中只包含SELCT和GROUP-BY節點操作使用到的屬性，不記錄表中其他不相關的屬性。在篩選的時候，應遵循以下幾個規則:

● 多層原則。 將操作盡可能的分為多個層次，這樣每個層次要處理的數據量就很少了。類似了數據的“分流”操作。 事實表盡量作為 輸入，維表盡量作為 輸入。

● 下拉原則。帶有聚集函數的操作盡可能底層化。合適粒度的區分視角的謂詞盡可能的下拉。

● 上拉原則。聚集視角的謂詞盡可能的上拉。

下拉原則是為了將具有相同原子視角的數據進行壓縮匯總，減少要處理的數據量。將聚集視角的謂詞上拉是為了保證候選自動累加表可以具備一個“共享”的數據操作集合。換句話說，就是為了盡可能的使候選自動累加表可以滿足所有的查詢請求。

帶有聚集函數的查詢統計都會有這樣的一個，接下來討論如何對這些進行進一步的優化。對帶有聚集函數的統計的候選自動累加表進行比較時會出現一下4種情況:

當和兩者相同時，直接將或作為自動累加表;

當和兩者為包含關系時，將包含原子視角多的作為自動累加表;

當和兩者相離即沒有公共交集時，將和分別作為自動累加表;

當和兩者相交時，將作為自動累加表。

匹配過程如下:

步驟1:根據業務功能或邏輯將候選自動累加表進行職能分類;步驟2:然后對其各個邏輯模塊中任意的兩個之間進行按照以上的匹配規則進行判定;步驟3:將各個邏輯模塊生成的自動累加表繼續進行匹配，轉到步驟2，直到該邏輯模塊不再產生新的自動累加表為止;步驟4:將各個邏輯模塊生成的自動累加表再逐一匹配，然后生成最終的自動累加表。

經過上述處理得到的自動累加表實際上是一種輕度綜合數據，但相對于細節數據庫(事實表和維表)中的數據量少得多。系統還可以根據業務的需求，在輕度綜合數據(自動累加表)的基礎上生成高度綜合數據表，來進一步方便決策分析。對于所有統計來說，凡是涉及決策分析和統計聚集操作的查詢都可以通過訪問自動累加表得到快速響應;至于涉及一些細節數據的信息查詢，還是要依賴細節數據庫。

4.2 自動累加表的更新維護

每一項業務操作會對數據庫中的數據產生影響。每執行一次業務操作，會同時在事實表和自動累加表中進行數據更新操作。不同的是，事實表只負責記錄這個業務操作的詳細信息，不對數據進行聚集操作;自動累加表會在業務操作所涉及的原子視角上進行數據的聚集操作。

當數據操作執行時，假設業務操作涉及個原子視角，業務操作所產生的數據在個原子視角下有各自的投影映射值，記為表示數據操作對應的原子視角下的數值;如果數據操作在對應原子視角下沒有投影，則記為1。該業務操作同時會影響相關的自動累加表中數據的變化。假設受影響的自動累加表集合(Automatic Summary Table Operated，

由于業務操作對自動累加表的原理是類似的，只需對其中某一自動累加表進行分析即可。以自動累加表為例，假設此自動累加表中包含的原子視角為，集合表示對應的數值集合，表示自動累加表中原子視角下對應的值。執行業務操作后，變為:

，“+”表示值的更新，更新過程通過觸發器來實現，更新時需要遵循以下規則:

(1)對應的原子視角為聚集視角，“+”表示按照業務操作的邏輯規則進行數據的累加或算術減操作。例如售票系統中，如果業務操作為售票，則在售票金額則在原來基礎上進行累加;如果為退票，則在原來的基礎上進行算術減操作。

(2)如果對應的原子視角為區分視角，需要遵循以下規則:

若區分視角下的值，它所對應的某一聚集視角為。用一個整形變量來統計該區分視角對應的某一具體聚集視角下記錄的數量，

即 。

若，表示自動累加表中，已存在的值為的歷史記錄。此時，只需更新該區分視角對應的聚集視角即可，此時的仍為。

若，表示自動累加表中，在區分視角的值為時，沒有歷史記錄。此時，需要在自動累加表中下寫入一條新的記錄，來實現區分視角值的更新。即就更新為。

5結束語

A港售票系統是一個具有售票、退票和改簽功能的集成售票系統。

系統數據庫中記錄售票相關業務的事實表和維表為50多個，經過業務需求分析和匹配函數后，系統只需要八個自動累加表(表1為其中的一個自動累加表)就可以滿足幾乎全部的財務報表查詢(業務數據的明細記錄報表查詢除外)，且每月需要處理的數據量只有幾千條數據左右。每月月底生成月度報表時，使用原子視角技術前，需要對基本數據進行分組匯總，消耗大量系統資源，一個月結報表的查詢往往需要20分鐘，有時還可能造成系統崩潰。現在只需要十幾秒，報表查詢的效率得到了質的提高。

6 結論

和傳統優化技術相比，本文論述了自動累加表是如何進行規劃的，是一種在數據庫設計階段對查詢性能做得優化;而且所設計的自動累加表把查詢所需要的時間分攤到數據操作時，在原子視角上進行數據的累加。而操作時這種視角上的數據累加所消耗的時間成本是可以忽略的。自動累加表技術是一種以少量空間換取大量時間的查詢優化技術，并在實際的大型滾裝船售票系統的報表查詢中得到了充分運用，有效解決了對超大容量數據庫報表查詢快速響應的問題。

參考文獻:

[1]郭榮，楊穎. PC服務器實現海量數據存取的方法[J].廣西科學院學報，2009，25(1):33-35.

[2]黃艷，譚同德 等. 管理信息系統的報表統計策略[J].南陽師范學院學報(自然科學版)，2003(12):52-54。

[3]尚展壘，陳慧，宋宇偉. 一種改進的查詢優化技術——分裂大表[J].鄭州輕工業學院學報，2002(9):61-63.

[4]W. Liang， H. Wang， M.E. Orlowska. Materialized view selection under the maintenance time constraint， Data Knowledge Engineering 2001(37):203-216.

[5]M. Zaharioudakis， R. Cochrane， G. Lapis， H. Pirahesh， M. Ursta. Answering Complex SQL Queries Using Automatic Summary Tables， in: Proceedings of ACM SIGMOD International Conference on Management of Data，2000:40-49.

[6]Dongfeng Chen， R. Chirkova， F. Sadri. Query optimization using restructured views: Theory and experiments. Information Systems[J]， 2009:353-370.

[7]Ming-Chuan Hung， Man-Lin Huang， Don-Lin Yang，etc. Efficient approaches for materialized views selection in a data warehouse. Information Sciences[J]， 2007:1333-1348.

[8]Jian Yang， K. Karlapalem， Qing Li. Algorithms for Materialized View Design in Data Warehousing Environment. Proceedings of the 23rd VLDB Conference Athens， Greece， 1997:136-145.

[9]李澤海. 數據倉庫中多維數據處理與查詢相關技術的研究[J]，吉林大學，2005(10):11-26.

[10]W.H.Inmon，王志海. 數據倉庫[M].北京:機械工業出版社，2000.