[發明專利]一種基于分布式數據庫的半連接查詢計劃選擇算法

在審

• 申請號: 201611138749.8
• 申請日: 2016-12-08
• 公開（公告）號: CN108182192A
• 公開（公告）日: 2018-06-19
• 發明（設計）人: 夏斌;李博涵;秦小麟
• 申請（專利權）人: 南京航空航天大學
• 主分類號: G06F17/30
• 分類號: G06F17/30
• 代理公司: 暫無信息
• 代理人: 暫無信息

本發明的目的是提出一種基于查詢地點不同的分布式半連接代價模型，以解決分布式連接的查詢計劃選擇問題。利用該方法能在查詢正式操作前，利用現有表大小，以及表屬性及元組長度，套用代價模型，確定查詢計劃。提高分布式數據庫系統的查詢效率，采用新的代價模型在執行半連接計劃之前評估和傳輸執行與優化代價。剔除與連接無關的數據，有效減少連接操作關系中的無用數據，選擇執行代價更小的執行方法。首先對分布式數據庫查詢執行代價模型進行分析，然后對半連接中的連接運算方式、連接關系的傳輸方法和執行場地等問題進行研究，并計算其評估方法的執行代價，給出一種可行的查詢計劃選擇算法，最終確定執行的場地、連接的方法和傳輸方法。

技術領域

本發明涉及一種并行式連接算法中針對連接后數據規模的計算，屬于計算機數據庫中的代價模型領域。

背景技術

分布式數據庫系統可以將物理位置分散而又需要不同粒度數據管理的多個集中式數據庫系統組織起來，形成一個具有海量、分布式特征的數據庫系統[1]。分布式數據庫中操作代價較高的連接操作對系統查詢效率直接產生影響。分布式數據庫在體系結構上與集中式數據庫系統差異顯著，提供了一個新的服務平臺，由此帶來與集中式數據庫系統不同的技術問題[2]。查詢優化處理是其中關鍵性問題之一。在集中式數據庫中，由于系統大多運行在單個處理器的計算機上，所以查詢執行總代價為CPU代價+I/O代價；而在分布式數據庫系統中，由于數據的分布和冗余，查詢處理需要考慮站點間代價，所以除了考慮CPU代價和I/O代價外，還應該包括數據在網絡上的傳輸代價，即總代價＝CPU代價+I/O代價+傳輸代價[3]。

分布式數據庫系統的查詢優化追求兩個目標：一是使總代價最小；二是使查詢響應時間最短，這一點在分布式數據庫系統中的意義尤為重要，因為分布式數據庫系統是由多臺計算機組成的，數據的分布和冗余也增加了查詢并行處理的可能性，從而可以縮減查詢處理的響應時間，提高查詢處理速度。

分布式數據庫的查詢優化是云數據管理的研究熱點之一。傳統的分布式連接查詢處理算法[4]以基于樹的查詢執行計劃模型為基礎，輔以Hash表[5]的使用，以達到查詢優化目的。例如分布式空間連接查詢使用的KD樹，需要在數據集上事先建立索引[6]；亦如基于樹型結構的MapReduce并行模型，該模型在Reduce階段建立反向二叉樹來實現有效的結果合并和花間，減少整合查詢結果所花費的代價[7]。然而上述模型在算法執行過程中產生大量的中間結果，從而導致大量的系統開銷，抵消了分布式帶來的效率提高。針對傳統的分布式連接查詢處理算法的不足，提出了基于半連接算法的查詢優化處理，以及基于直接連接算法的查詢優化處理[8][9]。這兩種算法都是以總代價最小為優化準則。具體選擇哪種算法，則需根據系統組成環境來確定。若傳輸代價較大，局部代價可以忽略不計，則采用半連接算法的查詢優化處理；相反，若局部代價較大時，采用直接連接算法比采用半連接算法優越。在實際的應用中，系統組成環境可能比較復雜，應該綜合考慮局部代價和傳輸代價。

基于直接連接算法的查詢優化處理，針對執行場地的不同，針對連接方式的不同，以及針對傳輸方法的不同的查詢優化研究見文獻[10]。其針對直接連接的掃描關系不同，劃分成了兩種算法，嵌套循環法和合并掃描法；并根據查詢地點的不同，劃分成了查詢站點為內關系所在地的Site(I)，查詢站點為外關系所在地的Site(O)，以及查詢站點為其他地點的Site(Other)。而基于半連接算法的查詢優化處理在這三個方面的綜合評估和代價分析研究還較少。因此本文重點研究基于半連接的實現方法，綜合考慮局部代價和傳輸代價的相對費用，計算所有評估方法的執行代價，選擇其中執行代價較小的執行方法，最終確定執行的場地、連接的方法和傳輸的方法。

上文中提到的文獻來源于如下的期刊：

[1]Nishiyama S.DISTRIBUTED DATABASE SYSTEM：US，US 20110010338A1[P].2011.