一種改進查詢優化算法的具體應用

張國華

(南京師范大學泰州學院，江蘇 泰州 225300)

一種改進查詢優化算法的具體應用

張國華

(南京師范大學泰州學院，江蘇 泰州 225300)

我國新型農村合作醫療系統(以下簡稱新農合)采用了分布式數據庫系統，即數據分布在不同的主管部門與不同的數據庫服務器上，各個部門對于數據的查詢頻率及數據的反饋速度要求較高，但業務流程中在涉及查詢時的數據來源復雜，傳統的一些查詢算法所消耗的時間代價、空間代價過高。針對上述問題，文中通過對分布式數據庫系統的簡化，建模出代價模型查詢圖，提出基于貪婪的優化算法并給出了數據查詢迭代方案，解決了在分布式數據庫查詢連接優化的問題。實驗結果表明，改進后的優化算法能明顯縮短查詢時間，并通過系統上線測試對比，證明該算法是有效可行的。

新農合；分布式數據庫；連接優化；算法時間代價

0 引 言

新農合的分布式數據庫(DBMS)[1]是把數據分散在網絡的不同服務器上，而總體上屬于相同系統的數據子集，它是數據庫技術與網絡技術結合的產物，提供了一種更高層次的大數據服務。而在新農合系統中參合數據、門診數據、藥品等數據分布在省廳、各縣市乃至各鎮村等醫療衛生服務部門服務器，因此對數據的查詢變得復雜，對查詢反饋的時間要求非常高。因此查詢連接減少算法時間與空間復雜度成為分布式數據庫系統中要解決與優化的一個核心問題。為解決該問題，學者們提出了很多查詢優化算法。其中比較著名的有基于直接連接的查詢優化、基于半連接的查詢優化、基于蟻群算法[2]的智能優化。這些算法大多僅從局部某一方向做了優化。

為了更好地提高新農合系統的整體性能，解決新農合數據連接整合效率，嘗試從新農合的系統總體架構入手，結合分布式數據庫系統特點，文中設計了基于貪婪優化策略[3-5]的查詢的連接優化算法。通過數據計算與模擬，采用多步決策，逐步處理，將新農合系統的查詢節點逐一合并，力求最優。對數據庫查詢問題，采用查詢圖[6]對問題進行空間描述，通過代價估算，檢驗算法的優越性。

1 系統總體優化目標與方案

1.1 系統總體優化目標

新農合分布式數據庫管理系統，數據分散在農村衛生服務站、醫療衛生單位、衛生行政主管單位、保險公司等部門，需要同時對多部門的節點進行數據的協同與并行處理，并采用優化策略分散一些特別負荷大的節點任務，使得系統整體順暢運行，但該優化操作同時也會造成一些額外的通信開銷。因此，系統優化的總體目標是充分發揮優勢，縮減不利影響，從而達到提高新農合分布式數據庫系統整體性能的目的。

結合該系統業務量大、數據分散等特點，主要從以下兩方面進行考慮：

(1)系統最短響應時間[7]：系統響應用戶操作時間最短。

(2)最大吞吐量：系統能同時盡量多地完成的數據處理任務。

因為新農合是一項惠民政策，要求做到即時結算報銷，系統要求實時性強，因此文中主要以縮短系統響應時間作為主要目標來優化。

1.2 確定優化方案

查詢優化方法主要有兩類：一類是靜態優化，另一類是動態規劃。靜態優化主要是依據數據已有目錄中統計數據預先對數據做估計，一般情況下，這種估計不準確，所以這種優化質量較低。而動態規劃的基本原理是按照每一步的中間結果進行逐步優化，優化質量更高，但因其邊執行邊優化，這種做法固然大大提高了優化質量，但其通信開銷卻大幅度增長。

該系統則汲取這兩種方法所長，取折中方案，即先根據靜態優化方法結果來執行，接著計算靜態優化方案中的數據統計結果與實際數據值偏差的絕對值是否在預先設定的范圍內，如超出則調用動態規劃方案來取代之前的靜態優化方案。如何取舍多種執行方案，前人采用了窮舉的方法[8]來對所有方案進行統計對比，但其工作量巨大。文中則創新地先采用啟發式規則對所有方案進行初步篩選，然后再依據消耗代價統計確定最終選擇方案。

2 查詢代價構成

2.1 代價構成

無論是集中式數據庫管理系統，還是分布式數據庫管理系統，查詢消耗的代價主要指執行查詢消耗的時間開銷，由三部分組成：外存儲器訪問代價(即I/O代價)；數據處理代價(即CPU代價)；通信代價(即傳輸代價)。分布式數據庫系統中，因其數據分布在網絡的若干節點上，相對而言通信代價在整個查詢執行代價中占比最高，是查詢執行代價應該考慮的主要方面。

2.2 建模查詢圖

設有A,B,C,D四個關系數據庫分布在網絡的若干節點，它們的數據量分別為10,5,20,15，它們之間的拓撲關系及通信距離見圖1。

圖1 建模查詢圖

不同網絡對于查詢的處理機制各不相同。大多情況，數據在網絡上的通信時間要大于內部各節點通信數據處理時間，文中為簡化問題，查詢訪問的I/O代價和CPU處理代價暫不考慮，只從通信代價方面著手研究。

2.3 通信代價模型

在傳輸過程中有兩種影響：費用和延遲。其中費用起決定作用。按傳輸費用衡量是指使通信中的整個傳輸開銷最小，即傳輸的數據量最小。

模型為：

CCOM(X)=C0+C1*X

其中,C0為場地間傳輸數據的啟動所需的固定費用(啟動一次)，簡稱啟動代價；C1為網絡單位傳輸數據費用，簡稱單位傳輸代價；X為需傳輸的數據量。

3 基于查詢圖的貪婪算法

3.1 算法介紹

貪婪算法[9-11]是一種優化的分級事件處理方法，其主要核心是依據要求選擇某種度量法則，將多個輸入按照這種量度法則所規定的順序進行。假如這個輸入與當前構成在這種量度法則意義下的部分最優解加在一起并不能產生可行解，則舍去這個。這種能夠得到在某種量度法則下最優的依次分級處理方法就是貪婪算法。文中借助此方法進一步優化該方案，即在相關部門連接查詢的過程中，采用中間查詢反饋的結果值來虛擬表示當前消耗的通信代價，從而在不同的分布式數據節點連接查詢過程中，不斷找出查詢消耗最小代價的中間結果并將其合并，從而降低系統整體查詢總代價[12]。

3.2 連接算法設計

依據上述的貪婪算法的總體思路，結合圖1，給出具體優化操作步驟：

(1)對相鄰的數據服務器節點連接時，首先找出連接所消耗代價[13]最少的連接運算。因此在圖中，逐次對相鄰節點做連接查詢代價計算結果依次為：

CA∞B=10*5*0.2(關系A數據量*關系B數據量*通信距離)=10

CB∞C=5*20*0.5(關系B數據量*關系C數據量*通信距離)=50

CC∞D=20*15*0.4(關系C數據量*關系D數據量*通信距離)=120

CD∞A=15*10*0.6(關系D數據量*關系A數據量*通信距離)=90

根據計算結果可知,當A,B進行連接時，其查詢通信代價最小，所以將這兩個節點合并，合并結果見圖2。新查詢圖中合并后節點內數值表示當前查詢的中間值。

(2)按照(1)同樣的方法計算。

CAB∞C=10*20*0.5(關系AB數據量*關系C數據量*通信距離)=100

CC∞D=20*15*0.4(關系C數據量*關系D數據量*通信距離)=120

CD∞AB=15*10*0.6(關系D數據量*關系AB數據量*通信距離)=90

由此看出最小的查詢代價為90,應該合并AB與D得出如圖3所示的查詢結構圖。

圖3 ABD合并后查詢圖

(3)最后執行ABD與C的合并，查詢代價為：

CABD∞C=90*20*0.5=900

至此整個系統的查詢近似代價總和為：

CA∞B+CAB∞D+CABD∞C=10+90+900=1 000

其查詢順序因為(((A∞B)∞D)∞C),根據上述過程分步轉換，查詢的優化處理最后得出如圖4所示的查詢樹結構。

3.3 算法對比及實驗對比

(1)算法對比。

根據圖1所示的查詢圖，采用不同的連接方案，所消耗的查詢代價也各不相同。表1給出了通過計算所有不同連接方案所消耗的查詢代價[14]。

圖4 優化查詢樹

序號連接順序依次代價總代價1((A∞B)∞C)∞D10,100,100011102(A∞B)∞(C∞D)10,120,100011303(A∞D)∞(B∞C)90,50,100011404((A∞B)∞D)∞C10,90,100011005(A∞(B∞C))∞D50,100,100011506A∞((B∞C)∞D)50,300,100013507A∞((C∞D)∞B)120,300,100014208((A∞D)∞B)∞C90,90,10001180

從表中可以看出，對于任何一種查詢連接它的最后一步的中間查詢代價都為1 000，對于各種不同的連接順序，其中間消耗的查詢代價都不相同，從而引起查詢消耗總代價也有區別。表1數據表明，采用文中優化的查詢算法的方案4的總代價為1 100，是所有方案中消耗查詢總代價最小的。

(2)實驗分析與測試。

此次實驗利用方案4所不同地點的服務器分別為A,B,C,D。服務器的操作系統均為Windows2003Server，CPU主頻為2.4GHz,內存為4GB,數據庫管理系統均為SQLServer2005版本。

A服務器為基層農民參保信息采集點數據庫，其存儲了農民參保采集信息表(農保編號,姓名,性別,出生年月……)，數據量為100 000條元組。

B服務器為某醫院HIS數據庫[14]，其存儲了農民門診住院記錄(農保編號,姓名,性別,醫療費用……)，數據量為50 000條元組。

C服務器為衛生行政主管部門數據庫，其存儲了新農合數據統計信息表(農保編號，姓名，費用，報銷總計……)，數據量為200 000條元組。

D服務器為負責新農合報銷的保險公司結算中心數據庫，其存儲了新農合報銷記錄表(農保編號，姓名，費用，報銷時間……)，數據量為150 000條元組。

A-B節點的通信距離為20，B-C節點的通信距離為50，C-D的通信距離為40，A-D之間的通信距離為60。

通過檢索命令，按照表1的連接方法連接檢索數據得到的實驗結果見表2。

表2 實驗結果表 s

上述8種情況考慮了所有的連接情況，并且方法4是采用文中算法的連接方案。實驗證明，該連接算法能顯著縮短查詢總時間，提高查詢效率。

4 結束語

在傳統的分布式數據查詢技術處理的基礎上，文中給出了一種能在分布式數據庫系統提升查詢效率的方法。通過理論分析及實驗對比，均能顯著提升查詢效率。在新農合系統分布式數據的使用中，表明其能進一步縮短數據檢索響應時間，提高新農合相關單位的工作效率。

[1] 徐濟惠．嵌入式數據庫多連接查詢優化算法的研究[J].寧波大學學報：理工版，2008，21(2)：206-210．

[2] 謝文兵，戴塔根，徐祖明．基于GRWSM協議的分布式空間數據處理技術[J]．計算機測量與控制，2011，19(4)：981-983．

[3] 微軟公司．QueryingMicrosoftSQLServer2000WithTransact-SQL[M]．北京：清華大學出版社，2001.

[4] 張小波，成良玉，鐘閏祿.建立動態群組的多Agent協同模型及應用[J]．計算機應用，2004，24：52-53.

[5] 李瑞軒，霍曉麗，文珠穆，等．多數據庫系統中的全局查詢轉換方法研究[J]．計算機工程，2005，31(16)：4-6.

[6] 姜愛福，李長云．分布式查詢優化的技術實現[J]．計算技術與自動化，2005，24(1)：72-73.

[7] 陳 波，高秀娥，陳來杰．基于等價變換的分布式查詢優化方法研究[J]．計算機工程與設計，2006，27(3)：390-392．

[8] 趙鵬軍，劉三陽．求解復雜函數優化問題的混合蛙跳算法[J]．計算機應用研究，2009，26(7)：2435-2437．

[9] 陳 靜，向隆剛，朱欣焰．分布式異構柵格數據的集成管理研究[J]．武漢大學學報：信息科學版，2011，36(9)：1094-1096．

[10] 邵佩英．分布式數據庫系統及其應用[M]．北京：科學出版社，2003．

[11]GilbertS，LynchN．Brewer’sconjectureandthefeasibilityofconsistent，available，partition-tolerantwebsen，ices[J]．SigactNewsletter，2002，33(2)：51-59．

[12]BacaR，KratkyM．TJDewey-ontheefficientpathlabelingschemeholisticapproach[M]//Databasesystemsforadvancedapplications.[s.l.]:[s.n.],2009．

[13]VogelsW．Eventuallyconsistent[J]．Queue，2008，6(6)：14-19．

[14]ElmasriR,NavatheSB.Fundamentalsofdatabasesystems[M].4thed.Beijing:ChinaMachinePress,2009.

A Specific Application for Improved Query Optimization Algorithm

ZHANG Guo-hua

(Taizhou College of Nanjing Normal University,Taizhou 225300,China)

China’s New Rural Cooperative Medical System (NRCMS) adopts the distributed database system.Data distribution in different authorities with different database servers,each department for the query frequency and data feedback speed has higher requirements,which involves complicated data resources in the working process,but the traditional query algorithm costs too much time and space.Aiming at these problems,through a distributed database system simplification,modeling query image of cost model,an optimization algorithm based on the greedy is proposed and the iterative scheme for data query is given,which solves the problem of connection in a distributed database query optimization.The experiments show that the improved optimization algorithm can significantly shorten the query time,and the on-line system test comparison demonstrates the algorithm is effective and feasible.

NCMS；distributed database;connection optimization;algorithm time cost

2014-12-10

2015-05-13

時間：2016-06-22

教育部Google2014年產學合作專業綜合改革項目(PO640068)；泰州市軟科學研究計劃項目(SRK20160005)

張國華(1981-)，男，講師，研究方向為分布式數據庫。

http://www.cnki.net/kcms/detail/61.1450.TP.20160621.1701.002.html

TP311

A

1673-629X(2016)07-0112-04

10.3969/j.issn.1673-629X.2016.07.024

[3] 洪妍妍．手指靜脈識別原型系統的設計與實現[D]．濟南：山東大學，2011．

[4] 余成波，秦華鋒．生物特征識別技術手指靜脈識別技術[M]．北京：清華大學出版社，2009．

[5] 高 嵩．手指靜脈圖像采集裝置設計[D]．長春：長春理工大學，2009．

[6] 袁 智．手指靜脈識別技術研究[D]．哈爾濱：哈爾濱工程大學，2007．

[7] 管鳳旭．基于流行學習及可拓分類器的手指靜脈識別研究[D]．哈爾濱：哈爾濱工程大學，2010．

[8]CrisanS,TarnovanIG,CrisanTE.Radiationoptimizationandimageprocessingalgorithmsintheidentificationofhandveinpatterns[J].ComputerStandards&Interfaces,2010,32(3):130-140.

[9]WuXiangqian,GaoEnying,TangYoubao,etal.Anovelbiometricsystembasedonhandvein[C]//Proceedingsofthe2010fifthinternationalconferenceonfrontierofcomputerscienceandtechnology.[s.l.]:[s.n.],2010:522-526.

[10]ChenHaifen,LuGuangming,WangRui.AnewpalmveinmatchingmethodbasedonICPalgorithm[C]//Proceedingsofthe2ndinternationalconferenceoninteractionsciences:informationtechnology,cultureandhuman.Seoul,Korea:IEEE,2009:1207-1211.

[11] 馬文科,王 玲,何 浩.一種指紋圖像的局部閾值分割算法[J].計算機工程與應用,2009,45(34):177-179.

[12] 苑瑋琦，王 楠．基于局部灰度極小值的掌脈圖像分割方法[J]．光電子·激光，2011，22(7)：1091-1096.

[13] 苑瑋琦,咸 陽.非接觸成像手指節紋檢測算法[J].計算機系統應用,2014,23(8):144-149.

[14]YuanWeiqi,ZhangTianwen.Valleytypeedgedetectionmethodbasedonlogicjudgment[J].JournalofImageandGraphics,2001,6(6):577-581.