基于蟻群遺傳混合算法改進的連接查詢研究*

張逸風，佟國香，劉 軍，屈亞寧

(1.上海理工大學光電信息與計算機工程學院，上海 200093；2.山東山大華天軟件有限公司，山東 濟南 250000)

1 引言

產品生命周期管理PLM(Product Lifecycle Management)是支持產品信息創建、管理、分發和應用的一系列方案。PLM的核心技術之一是面向產品全生命周期的數據建模技術。目前PLM系統主要以文檔管理為主，很難解決異構平臺、跨單位、跨階段和跨領域開發時的數據交互問題，因此，研發基于模型數據庫的復雜產品全生命周期模型管理原型系統PLMM(Product Lifecycle Management of Model)成為工業4.0時代大趨勢。而產品生命周期中的概念產生、產品設計、采購、生產制造、銷售和服務等各個階段的數據不僅數據量大，且相互關聯錯綜復雜，目前主流的關系型數據庫和數據倉庫都可以作為PLM系統的數據服務支持平臺。由于PLM系統的數據庫結構的復雜度高，數據信息具有多樣性，將數據抽象為模型后，模型之間的關聯關系越來越復雜，耦合性越來越高等諸多因素降低了數據檢索的效率，因此，選擇合適的連接查詢算法[1]尤為重要。

在傳統聯機事務處理OLTP(On-Line Transaction Processing)[2]的多表連接查詢方式中，Hash Join[3]是近些年研究人員改進得最多的連接查詢算法。因為其穩定性和有效性，自誕生以來研究人員就嘗試從各方面對其進行改進。文獻[4]介紹了一種散列合并連接算法HMJ(Hash-Merge Join)。它通過不可預測的、緩慢的或突發的網絡流量處理來自遠程數據源的數據項。算法綜合運用了非阻塞連接算法X-Join和漸進式合并連接算法的優點，得到了更優的結果。文獻[5]提出了一種新的基于NOWs(Network Of Workstations)的散列連接處理的負載共享算法,結合了分塊方法和散列連接來管理當前環境中發生的動態變化，可以用于當前的單連接處理。文獻[6]提出了一種基于列庫的分布式環境中散列連接算法，面向數據的分布式計算模型的設計，引入分區聚合和啟發式優化策略，實現了改進的哈希連接算法。

對于聯機分析處理OLAP(On-Line Analytical Processing)[7]多表連接查詢，由于數據量過于巨大，牽扯的關聯表數量也大幅增加。Ripple Join[8]是主流的估算聚合值方法，輪流在每個表中隨機采樣，將采樣的結果放入內存,對新放入內存的結果和所有現存的結果進行連接查詢。這種方法要求采樣的數據分布具有隨機性，而現代數據庫數據被聚類存放，因此不具有隨機分布的特性。文獻[9]對Ripple Join算法進行了并行性和采樣方面的改進，該方法的局限性是，一旦內存無法再加載數據時，估計結果將不具有統計意義。Chris 等人[10]將sort-merge思想應用到Ripple Join算法中，對內存轉出到外存的數據進行隨機化處理，從而保證估計結果的統計意義，并在引擎DBO(Date Base Owner)上實現了該方法，提升了Ripple Join的部分效率。文獻[11]介紹了Invisible Join，其思想是將表的相關列映射成位圖，對維表主鍵屬性相應的外鍵列建立一個事實表位圖，根據所需要選擇的位圖和屬性獲得相應連接結果。文獻[12]提出的Flash/Five Join是一種基于索引的多路等值的列式數據庫連接算法，對連接列屬性值進行排序，同時索引號隨之變動，再將連接列屬性值物化得到物化后的值，最后對索引號排序得到連接結果。Wander Join[13,14]是一種通過采樣計算聚合值[15]的方法，設計了一個步行計劃選擇器代替隨機采樣，使得采樣更有目的性，效率更高。通過合理應用Wander Join連接查詢，用戶將獲得更高的聚合值返回效率，數據庫系統可以支持更多元的運算。它的問題在于復雜性和適用性，以及對分組查詢的查詢速度不盡如人意。

本文將蟻群遺傳混合算法[16]與Wander Join相結合，提出了優化連接順序的連接查詢算法。該算法通過一個連接選擇器計算出連接表之間的代價，用于連接圖建模時的順序選擇。執行連接圖對應的連接計劃后，使用剪枝策略對樣本多余的節點進行剪枝操作，保留高選擇性的節點，以減少節點的數量，避免重復搜索。最后將提出的混合連接算法在TPC-H(Transaction process Performance Council-H)數據集和TPC-DS(Transaction process Performance Council-DS)數據集[17,18]上分別進行了仿真驗證。

2 Wander Join查詢算法

Wander Join查詢算法使采樣過程更加集中，避免了盲目地從每個表中抽取樣本進行連接操作，只從其中一個表中隨機抽取一個元組，從該元組開始進行隨機遍歷，在隨機遍歷的每一步中，只考慮當前已采樣元組及其相鄰元組。與Ripple Join連接算法的“盲目搜索”相比，它是一種引導探索。

具體方法是將表之間的連接建模為連接圖，然后在該連接圖中執行隨機遍歷。由于可以用不同的順序對相同的連接執行隨機遍歷，所以Wander Join查詢算法設計了一個優化器來選擇最優的遍歷計劃。由于每一條路徑被選擇的概率不相同，易導致采樣不均勻，為了判斷遍歷計劃的優劣，Wander Join引入HT(Horvitz-Thompson)估計量，用式(1)來估算樣本總體的期望值[19]：

(1)

其中,n表示采樣數目，XIi表示采樣這個Ii得到的值，πIi表示出現采樣的概率。而選擇概率如式(2)所示：

(2)

其中,γ表示不同時刻，Rλ(1)表示第1個表里總記錄的條數，dλ(i)(tp(i))表示從第i-1個表的某條記錄連接到第i個表的邊的數目。

在給定的時間內，最終估計量的方差與Var[X1]E[T]/T成正比，如式(3)所示：

(3)

其中,W表示游走總步數，Xi表示第i個隨機游走的估計值，E[T]表示隨機游走中查找的索引條目的平均值，T表示總運行時間，最終估計量的方差越小，越接近最優的游走方案。

3 改進的連接查詢算法

本文引入蟻群遺傳混合算法和裁剪搜索空間對Wander Join算法進行優化，算法流程如算法1和圖1所示。

算法1改進的連接查詢算法

Step1表節點建模：將N個表上的連接建模為連接圖;

Step2連接順序確定：引入蟻群遺傳混合算法確定表連接順序;

Step3執行選擇計劃：根據新的連接順序執行計劃;

Step4樣本選擇：采用剪枝策略縮小選擇范圍;

Step5完成連接查詢。

Figure 1 Flow chart of improved algorithm 圖1 改進算法流程圖

3.1 表節點建模

數據庫連接查詢優化問題與傳統的旅行商問題類似，目標是尋求一條代價最小的路徑。本文提出的改進算法將需要進行連接查詢的數據表建模成連接圖，以最小代價提供連接查詢路徑，流程如下所示：

Step1初始化節點:每個表被建模為一個節點ci，i=1,2,…,N;

Step2節點連接:若2表之間存在連接條件，則2表之間形成一條邊;

Step3形成連接圖:整合節點和邊形成連接圖G(V,E)，其中V={ci|i=1,2,…,N},E為所有邊組成的集合。

3.2 連接順序確定

實體和群體的能力描述代表了它們執行任務的能力，是進行任務規劃的根本依據。能力描述還將組織任務的可完成性判斷轉化成了描述任務邏輯的定理證明。另外，群體中成員的變更可能導致組織能力的變化，能力描述也能自然地將這種變化表現出來。

由于模擬生物或自然界的不確定算法易陷入局部最優，而基于啟發式的確定算法存在收斂速度慢等問題，本文算法將蟻群算法與遺傳算法相結合，將蟻群算法每次迭代的結果作為遺傳算法的初始種群，用遺傳算法產生的結果更新蟻群算法的信息素。同時，引入2種新的交叉算子，后期使用兩元素優化(2-opt)算法，避免了算法過早陷入局部最優解，加快了算法的收斂速度，流程如下所示：

Step1生成初始種群。

(1)定義啟發式信息素因子α，啟發式期望值因子β，表節點連接代價d，信息素τ，啟發式信息η，信息素強度q，交叉概率pe，變異概率pm，信息素揮發系數ρ等。

(2)禁忌表初始化為空。

(3)將螞蟻釋放在N個表節點上。

(4)狀態及轉移方向初始化，如式(4)所示：

(4)

(5)將表節點按照被遍歷的順序組成編碼，把蟻群算法中所有螞蟻遍歷一次后的完整路徑作為遺傳算法的初始種群。

Step2執行選擇。

按照1∶1的比例，采用輪盤賭方法和最優個體保存法對種群中的個體進行選擇。第k個個體適應度被選擇的概率pk和前k個個體被選擇的累計概率qk如式(5)和式(6)所示：

(5)

(6)

其中，f(k)為適應度函數。

計算個體適應度在整個種群適應度中被選擇概率和累計概率，最后通過0～1的隨機數r與累計概率qk來決定被保留的個體。

適應度的計算采用目標函數和適應度函數，目標函數如式(7)所示：

(7)

其中，d(ci,cj)表示表節點ci到表節點cj的距離,Lk則代表螞蟻k在一次迭代中走過的路徑長度。

適應度函數選取目標函數f(Lk)的倒數，如式(8)所示：

(8)

可知，路徑長度影響適應度，路徑越長適應度越小。

Step3執行交叉。

按照交叉概率進行交叉操作。從種群中隨機確定個體a和個體b作為子代路徑的父個體，隨機確定一個交叉節點rc作為子代路徑的起始節點。計算父個體a和b路徑中節點rc與其下一個節點ca1和cb1之間的距離da1和db1，計算節點rc與ca2和cb2之間的距離da2和db2，如果da1+db2*r≤da2+db2*r,0

Step4執行變異。

對交叉后得到的結果采用對換變異，將隨機選取的若干基因按照變異概率pm互換，初始概率選擇較大的值，以便在更大范圍內搜索，盡可能減小丟失最優解的概率。根據進化代數令變異概率pm遞減，最終鎖定最優解。

Step52元素優化(2-opt)。

從當前解中任意選擇2條路徑，拆成2個部分。在不構成環路的前提下，將第1部分的路徑反接回另一條路徑，比較產生的路徑與原路徑的長度，并保留路徑相對較短的解。針對不同的路徑重復進行2-opt，最終得到局部優化后的解。

Step6用式(9)更新信息素：

(9)

(10)

Step7若迭代次數大于最大循環次數或遺傳算法的結果滿足當前要求的最優解，輸出最優連接路徑結果P(x1,x2,…,xn)。

3.3 執行選擇計劃

根據3.2節中得到的新的查詢連接順序P(x1,x2,…,xn)，執行新的選擇計劃。

以圖2為例，如果按照原始的查詢順序A→B→C，連接一次成功率為3/5，但是在優化連接順序后，新的選擇計劃的查詢順序為C→B→A，則連接的一次成功率為4/5，達到了優化效果。

Figure 2 Data connection diagram圖2 數據連接示意圖

3.4 樣本選擇優化

刪除未通過篩選的節點可以對高選擇性查詢樣本進行優化，防止查詢節點失敗，使用更少的節點進行查詢，以加快查詢速度。優化過程如下所示：

Step1初始化權重。

在實踐中，當發出過濾查詢時，統一設置每個節點的權重。

Step2更新權重。

在進行抽樣時，如果遇到一個節點未能通過篩選，將該節點的權值設置為0，并將此節點視為查詢失敗。通過將權值設置為0，保證不再對這個失敗的節點采樣。

Step3裁剪。

如圖3所示，對于3張表A、B、C，可以看到2條可能的采樣路徑是A1→B1→C2和A1→B2→C2。如果連接選擇了A1，B1，而節點C2沒有通過篩選，則將C2的權重置為0，并裁剪。這樣不僅消除了A1→B1→C2這條可能的路徑，也消除了A1→B2→C2路徑。刪除沒有通過篩選的節點，防止了任何路徑對該節點進行再次采樣。

Figure 3 Node clipping diagram圖3 節點裁剪示意圖

Step4輸出裁剪后結果。如果再次執行同一查詢計劃，查詢正確率將有所提升。

4 實驗及結果討論

本文實驗環境為Python 3.6.5，實驗數據集為TPC-H與TPC-DS。

實驗參數設置：蟻群遺傳混和算法種群規模M(k)=25,啟發式信息素因子α=2,啟發式期望值因子β=3,信息素揮發系數ρ=0.7,釋放的信息素總量q=100,交叉概率pe=0.75,變異概率pm=0.05,遺傳算法進化代數設為20，混合算法的總迭代次數達到100代時輸出結果。

基于相對錯誤率、置信區間寬度、平均權重和執行時間對算法性能進行評估，并將蟻群遺傳混合算法+剪枝策略+Wander Join改進的算法(本文算法，記作S-WJ-P)分別與蟻群遺傳混合算法+Wander Join改進的算法(記作S-WJ)以及Wander Join算法(記作WJ)進行了對比實驗。

相對錯誤率如式(11)所示：

(11)

其中,v表示方差，Ns表示抽樣個數。

置信區間的左右值分別用L-int和R-int表示，半寬度(ε-width)公式為：

(12)

平均權重如式(13)所示：

(13)

其中,n為樣本數量，wi為權重。

4.1 模擬多表連接順序優化

把每個表節點映射為一個二維數組后，基于TPC-H數據集和本文算法獲得的優化表連接路徑如圖4所示。

Figure 4 Minimum cost path of table join圖4 表連接最小代價路徑

為了驗證在更大數量表連接時算法的可行性，模擬實驗了20和50個表連接的情況，本文算法獲得的優化表連接路徑如圖5所示。

Figure 5 Minimal cost path for a large number of table join圖5 大量表連接最小代價路徑

由圖4和圖5可見，表節點數量越多，路徑選擇就越多，本文算法容易找到相對最優解進行連接，從而減少連接的相對錯誤率。

4.2 實驗結果分析

將置信度設置為95%，分別在樣本數量為10 000和100 000的條件下，測試了3種算法在6個檔次選擇率情況下的相對錯誤率、執行時間、平均權重和置信區間寬度,結果如表1和表2所示。

對比表1和表2，在不同選擇概率ch下，WJ的相對錯誤率波動較大，這是因為3.2節中提到的WJ的隨機游走會導致路徑不同，從而影響選擇成功率，而S-WJ和S-WJ-P的相對錯誤率波動較小，說明改進的算法具有良好的魯棒性。S-WJ-P和S-WJ的置信區間寬度與平均權重也均小于WJ的。以上實驗結果表明，本文算法達到95%置信區間的收斂速度比WJ快，換言之，達到相同置信區間所需的樣本數量比WJ的少。此外，由于剪枝策略的加入，裁剪了大量沒有遍歷的節點，因此在低選擇率條件下獲得了更好的優化效果，從而本文算法的估算結果更精確。

圖6～圖9給出了不同樣本數量時的算法對比情況。從圖6和圖7給出的相對錯誤率的對比情況來看，在2種不同樣本數量條件下，S-WJ-P在大部分選擇率區間內的相對錯誤率均低于WJ和S-WJ的，只有在低選擇率區間內S-WJ的相對錯誤率略低。3種算法的執行效率如圖8和圖9所示，S-WJ-P和S-WJ的執行時間均高于WJ的。這是因為引入的蟻群遺傳混合算法和剪枝策略增加了算法的計算時間，但在樣本數量大幅度增加后,由于剪枝策略有效減少了表節點數量，3種算法時間趨于一致，因此犧牲部分時間減少20%～70%的相對錯誤率是值得的。樣本數量較少時的效率問題仍是后續改進算法的方向。

Table 1 Comparison of partial experimental results of 10 000 samples表1 10 000個樣本部分實驗結果對比

Table 2 Comparison of partial experimental results of 100 000 samples表2 100 000個樣本部分實驗結果對比

Figure 6 Comparison of relative error rate of 10 000 samples圖6 10 000個樣本相對錯誤率對比

Figure 7 Comparison of relative error rate of 100 000 samples圖7 100 000個樣本相對錯誤率對比

Figure 8 Execution time of 10 000 samples圖8 10 000個樣本執行時間

Figure 9 Execution time of 100 000 samples圖9 100 000個樣本執行時間

為了驗證改進算法的普適性，基于TPC-DS數據集再次驗證，從圖10、圖11與圖6、圖7中相對錯誤率的對比情況來看，在相同樣本數量條件下，S-WJ-P在大部分選擇率區間內的相對錯誤率均低于WJ和S-WJ的。實驗結果表明，改進算法具有更高的正確率和更好的魯棒性。

Figure 10 Comparison of relative error rates of 10 000 samples on TPC-DS圖10 TPC-DS上10 000個樣本相對錯誤率對比圖

Figure 11 Comparison of relative error rates of 100 000 samples on TPC-DS圖11 TPC-DS上100 000個樣本相對錯誤率對比

5 結束語

本文提出了一種基于Wander Join改進的數據庫連接查詢算法，利用蟻群遺傳混合算法優化表連接的路徑選擇，結合Wander Join算法，使連接查詢得到部分優化。按照新的連接順序進行連接后，引入剪枝策略，減少連接節點數量。實驗表明，算法在控制相對錯誤率和控制樣本數量方面取得了較好的效果。選擇率為10%左右時，改進算法表現最佳，相對錯誤率只有Wander Join算法的1/5。改進算法在數據庫更新操作時會破環剪枝的效果，加上蟻群算法的處理時間，導致執行時間增加。今后的研究可以嘗試連接算法的并行化，或與其它啟發式算法結合，引入強化學習算法全面提升其性能。