[發(fā)明專利]面向海量分布式數(shù)據(jù)庫的嵌套查詢方法

有效

• 申請?zhí)枺?/td>: 201410333217.4
• 申請日: 2014-07-14
• 公開（公告）號: CN104090962B
• 公開（公告）日: 2017-03-29
• 發(fā)明（設計）人: 劉文潔;裴歐亞;李戰(zhàn)懷;田征
• 申請（專利權）人: 西北工業(yè)大學
• 主分類號: G06F17/30
• 分類號: G06F17/30
• 代理公司: 西北工業(yè)大學專利中心61204
• 代理人: 王鮮凱

1.一種面向海量分布式數(shù)據(jù)庫的嵌套查詢方法，其特征在于包括以下步驟：

步驟一、采用關系型數(shù)據(jù)庫的SQL語句解析結果構建查詢樹：

查詢樹的節(jié)點數(shù)據(jù)結構如下：

其中，phy內保存子節(jié)點執(zhí)行結果填充位置標記；phy內的位置標記與next_child一一對應；

步驟二、為查詢樹構建執(zhí)行引擎；根據(jù)查詢樹的特性，采用從葉節(jié)點到根節(jié)點的遞歸計算算法；

遞歸算法如下：

串行執(zhí)行每個節(jié)點；除根節(jié)點外，每個節(jié)點執(zhí)行結束，將本節(jié)點從查詢樹移除，以確保查詢樹的正確執(zhí)行；

算法中的threshold控制著是否啟用HashMap和Bloomfilter；threshold為可變參數(shù)，可變化范圍為(0，511]；

當子查詢結果集不大于threshold時，直接將子查詢結果集寫入主查詢的物理計劃內，接下來的物理計劃執(zhí)行等處理遵循OceanBase現(xiàn)有的查詢處理；當子查詢結果集大于threshold時，將主查詢的物理計劃同子查詢結果集生成的Bloomfilter一起發(fā)送至Chunkserver處理，MergeServer利用子查詢結果集生成的HashMap過濾獲取的結果集；

步驟三、首先ChunkServer進行非嚴格的BloomFiter過濾，獲得最終結果集的超集；其次MergeServer進行嚴格的HashMap過濾，獲得最終結果集；

I、BloomFilter過濾；

分布式架構下，將作為主查詢過濾條件的超大的子查詢結果集分發(fā)至不同的數(shù)據(jù)節(jié)點的方案會占用大量傳輸帶寬；為了降低帶寬占用率且加速查找，采用多哈希函數(shù)映射的快速查找數(shù)據(jù)結構--布隆過濾器：BloomFilter；

策略所構建的BloomFilter采用如下的公式：

k＝-ln(p)÷ln(2)

m＝(n*k)÷ln(2)

式中，p是誤判率，m是位數(shù)組大小，n是總數(shù)據(jù)數(shù)目，k是所需哈希函數(shù)數(shù)目；

BloomFilter的構建由MergeServer負責，構建算法如下：

Input：子查詢結果集S//S代表子查詢結果集

①依據(jù)上述公式及S、默認誤報率p，計算BloomFilter所需位數(shù)組大小m，所需哈希函數(shù)數(shù)目k；

②讀取S的一條記錄R，如果R為NULL，轉⑤；//R代表結果集中的一條記錄，NULL代表一條空記錄；

③將R依次帶入k個哈希函數(shù)H1(R)，...，Hk(R)得到k個值V1，...,Vk；

//H1(R)，...H1(K)代表k個哈希函數(shù)，V1，...Vk代表k個哈希函數(shù)的值；

④將BloomFilter的位數(shù)組的V1，...,Vk位設置為True，轉②；

⑤構建結束，返回BloomFilter；

BloomFilter的查找算法如下：

①讀入一條記錄R

②將R依次帶入k個哈希函數(shù)H1(R)，...，Hk(R)得到k個值V1，...,Vk；

③比對BloomFilter的位數(shù)組的V1，...，Vk位；如果k個位全為True，則返回查找成功，否則返回查找失敗；

II、HashMap過濾；

MergeServer嚴格的數(shù)據(jù)過濾條件是海量的子查詢結果集，采用全內存的HashMap存儲子查詢結果集；

HashMap的高效查找依賴于哈希函數(shù)的均勻散列和低沖突率；均勻散列保證每一個桶內的數(shù)據(jù)檢索時間大致相同；低沖突率保證快速定位，采用鏈表法解決地址沖突；鏈表的每一個節(jié)點的只有key；

MergeServer負責構建HashMap，且利用構建的HashMap進行嚴格的數(shù)據(jù)過濾；

HashMap的構建算法如下：

Input：子查詢結果集S

①初始化HashMap，分配哈希桶空間；

②讀取S的一條記錄R，如果R為NULL，轉⑤；

③將R帶入哈希函數(shù)H(R)，依據(jù)得到的哈希值確定待插入的哈希桶BUCKET?BT；

④將R以鏈表的形式掛在BT的鏈表末尾，轉②；

⑤構建結束，返回HashMap；

HashMap的查找算法如下：

①讀入一條記錄R

②將R帶入哈希函數(shù)H(R)，依據(jù)得到的哈希值確定待查詢的哈希桶BUCKET?BT；//BT代表一個哈希桶；

③遍歷BT內的鏈表節(jié)點，逐個比對；如果相同則返回查找成功，否者返回查找失敗；

查詢樹的每一個非葉子節(jié)點的執(zhí)行都需要兩階段數(shù)據(jù)過濾，即首先根據(jù)孩子節(jié)點的結果集構建HashMap和BloomFilter，接著將BloomFilter同本節(jié)點的物理計劃分發(fā)至數(shù)據(jù)節(jié)點，數(shù)據(jù)節(jié)點依據(jù)物理計劃及過濾條件BloomFilter，將最終結果集的超集返回給MergeServer,最后MergeServer利用HashMap執(zhí)行最后的嚴格的數(shù)據(jù)過濾，獲得最終結果集。