基于代價的順序查詢優化

【摘 要】 數據流的高速性和無限性以及計算機資源的有限性使得提高數據處理速度成為數據流管理系統（DSMS）的關鍵；本文主要討論了DSMS的核心技術--查詢優化；通過并行查詢處理技術來提高數據流處理速度的新方法。

【關鍵詞】 數據流 并行查詢優化 shared--nothing

1.順序查詢優化的代價指標

一個計劃的代價一般由總工作量和內存消耗兩個要素組成。在單機數據庫系統中，總工作量主要包括CPU占用時間和I/O時間。為了并行化地需要，順序優化的代價計算應當包括計劃的結點間的通信代價。因此總工作量由CPU占用時間、I/O時間和網絡通信時間三部分組成。

2.順序優化的搜索策略

順序優化的關鍵問題是從搜索空間SequenceSpace（操作間的偏序關系、操作算法、數據分片策略）中搜索代價最小的計劃。解決這個問題的標準技術是動態規劃（Dynamic programming）。動態規劃是一種接近窮盡搜索的方法，可以保證找到最優的計劃。雖然從理論上講，動態規劃仍然是指數級的算法，但是在實際的搜索過程中，動態規劃的效率是相當高的。

在動態規劃中，比較兩個子計劃優劣的指標被稱為裁減指標（Pruning Metric）。動態規劃算法的正確性依賴于下述關于裁減指標的兩個假設：

最優化原則：如果兩個計劃中僅有一個子計劃不同，那么具有較優子計劃的計劃較優。

全序原則：所有計劃能夠基于裁減指標全序排列，動態算法依靠這種全序關系來迅速裁減代價較大的計劃，保證對于每一個關系子集只產生一個“最優”的子計劃。

3.并行化

兩階段優化的第二個階段——并行化階段的任務是將順序優化階段得到的順序執行計劃轉化成能在多個結點上并行執行的計劃。并行化階段的主要工作包括：

選擇操作間的執行模式。即決定多個不同操作是串行執行還是并行執行。

決定操作的并行度。即一個操作在執行時生成多少個操作實例，系統需要為每個操作實例分配一個處理集，決定操作的并行度也就相當于確定為該操作分配多少個處理機。

處理機的分配。在SN結構下，還需要指定操作實例的執行結點。

并行化實際上是一個資源分配問題，即決定為每一個執行計劃分配多少CPU、I/O、網絡和內存資源。

3.1 并行化的目標——多資源負載平衡

最優地并行計劃就是相應時間最短地計劃。而并行計劃地響應時間是由資源消耗和并行化程度兩個因素決定的。因此，從另一個角度看，最優并行計劃的衡量標準是：最小的資源消耗＋最充分的并行化。如果一個并行執行計劃既能保證消耗最少的系統資源，又能保證將這些資源占用平均地分攤到系統內地資源單位上，那么該計劃執行的響應時間必定最短。由于兩階段優化的一個基本特征是在順序優化階段對通信代價進行了預先的控制，并行化不會導致資源占用的增加，最優的并行計劃就是負載最均衡的計劃。因此并行化階段的目標就變得非常明確：實現查詢工作量在系統內多種資源上的負載平衡。

3.2 并行化的代價模型

由于并行化的根本目標是多資源的負載平衡，因此并行化的代價指標必然要反映任務的資源負載平衡狀況。為了定量地描述任務地資源負載平衡狀況，我們提出了任務資源向量和任務負載平衡因子兩個概念。

在并行數據庫系統中，資源有多種類型，每類資源又有若干實例，因此一個任務所消耗地各種資源構成了一個多維向量，一般稱其為任務資源向量。任務資源向量可以準確地描述任務的資源占用情況。

任務負載平衡因子是在任務資源向量的基礎上定義的。任務負載平衡因子準確地描述了任務負載在各個資源上地分布情況，任務負載平衡因子的值越小，任務并行化的效果越好。

另外，任務并行化的一個顯而易見的約束是任務主存向量中所有成員的值都小于其對應的主存資源的最大容量，否則任務將因主存不夠而無法執行。如果任務的主存向量滿足這種執行約束，則被稱為有效的任務主存向量。

3.3 縮減并行化搜索空間地啟發式規則

假設系統由m個結點組成，每個結點上有1個處理機，如果可以對操作間地執行模式、操作的并行度，以及操作的處理結點進行任意選擇（但是并行度必須小于處理機數目m），那么對一個包含n個操作的任務，可能的并行化方案數目是：

因此，并行計劃搜索空間隨著結點數目增加而呈指數級增長。SN系統中結點的數目往往比較大，因此我們采用了啟發式規則對并行化搜索空間進行限制。

導致并行計劃搜索空間比較大的主要原因是操作的并行度和處理機分配選擇方案太多，上述公式的前提是并行度和處理機分配的選擇是任意的。但實際上，對并行度和處理機分配的選擇會受到其它一些因素制約。

規則1. Scan操作的并行度和處理機分配方案應當與其對應的表的數據分片策略一致。

根據這一規則，可以自然地決定計劃中所有Scan操作地并行度和處理機分配方案。

規則2. 如果兩個操作之間地數據分片策略為1對1，這兩個操作地并行度和處理機分配應該完全一樣。

與其他并行數據庫相比，規則2是特有地。由于通信代價影響了順序優化時對計劃的選擇，最終得到最優計劃可能是因為通信代價的節約才得以入選，我們必須保證這種節約了的通信代價不會因并行化而重新出現，因此，一旦在順序優化時確定了操作間的數據分片方法是1對1，就不能在并行化時加以改變。否則這兩個操作之間必然會出現通信代價，從而違背了兩階段優化假設。

小結

并行化階段的優化目標非常明確：實現查詢工作量在系統內多種資源上的負載平衡。我們使用任務的資源向量來描述任務的資源占用，然后在此基礎上提出了任務資源負載平衡因子的概念，并將其作為并行化的代價指標。為了縮減并行化的搜索空間，我們提出了四條重要的啟發式規則。

※佳木斯大學科研經費資助項目《數據流上并行優化查詢技術》 項目編號l2009-131

參考文獻：

[1]文繼榮， 陳紅，王珊. 《Shared-nothing并行數據庫系統查詢優化技術》[J]. 計算機學報，Jan 2000，Vol. 23， No. 1

[2]于亞新，王國仁，于戈.《并行XML數據庫系統中數據分片策略的研究》[J]. 計算機研究與發展，Oct. 2003，Vol. 40， No. 10

[3]歐陽旭東，何巍.《并行數據庫的物理實現與應用》[J]. 湖北郵電技術，March 2002， Consecutive No. 61.鄒暉，羅省賢.《機群并行系統與網絡并行計算環境（PVM與MPI比較）》[J]. 物探化探計算技術，Nov. 2001，Vol. 23， No.4

[4]曹陽，方強，王國仁，于戈.《基于遺傳算法的多連接表達式并行查詢優化》[J]. 軟件學報，2002，Vol. 13， No. 2.

[5]都志輝. 《高性能計算之并行編程技術--MPI并行程序設計》[M]. 清華大學出版社. 2001.

作者簡介：周虹（1967--）黑龍江省訥河縣人 教授。

（作者單位：周虹 富春巖，佳木斯大學公共計算機教研部；鄭佳昕，人事處）