[發明專利]一種基于合并偏差門限的范圍查詢數據分片優化方法

有效

• 申請號: 201810195004.8
• 申請日: 2018-03-09
• 公開（公告）號: CN108460137B
• 公開（公告）日: 2021-07-20
• 發明（設計）人: 葛微;李先賢;王金艷
• 申請（專利權）人: 廣西師范大學
• 主分類號: G06F16/2453
• 分類號: G06F16/2453
• 代理公司: 桂林市華杰專利商標事務所有限責任公司 45112
• 代理人: 劉梅芳

本發明公開了一種基于合并偏差門限的范圍查詢數據分片優化方法，其特征是，包括如下步驟：1)建立范圍查詢負載下的數據訪問概率模型；2)定義最優分片方案；3)切分出第一個數據片；4)試探合并下一段數據片，并計算合并帶來的代價偏差；5)跳轉到步驟4)，循環執行數據片合并，直到剩余數據片個數達到K為止，K是分片的數據片個數。這種方法能降低數據的管理維護開銷、以及數據查詢中的定位尋址代價和傳輸代價、提高查詢效率。

技術領域

本發明涉及面向大數據上范圍查詢的數據分片優化技術，具體是一種基于合并偏差門限的范圍查詢數據分片優化方法。

背景技術

在面對范圍查詢需求時，我們需要感知范圍查詢的訪問模式，并基于此為數據分片，將訪問模式下關聯性強的數據劃分成一個數據片。這個“定制邊界”的數據片在被范圍查詢訪問時會被全部或大比率命中，大大降低數據定位尋址開銷和傳輸開銷，從而提高查詢效率。

為了獲得最優的范圍查詢性能，為數據劃分切片的最優分片位置一定是在范圍查詢的邊界上。因為從來沒有被范圍查詢分割開的相鄰數據，一定會在每次查詢中都被范圍查詢同時命中，那么他們也不應該被數據分片切割開。

發明內容

本發明的目的是針對現有技術的不足，而提供一種基于合并偏差門限的范圍查詢數據分片優化方法。這種方法能降低數據的管理維護開銷、以及數據查詢中的定位尋址代價和傳輸代價、提高查詢效率。

實現本發明的目的的技術方案是：

一種基于合并偏差門限的范圍查詢數據分片優化方法，與現有技術不同的是，包括如下步驟：

1）建立范圍查詢負載下的數據訪問概率模型：定義數據集上范圍查詢的所有邊界組成的集合叫做范圍查詢邊界集，在基于記錄的數據組織方式下，一條數據記錄的查詢累積概率＝數據記錄被查詢負載訪問的次數/總查詢次數，在基于數據片的數據組織方式下，定義第個數據片的長度為，數據片上的查詢累積概率為，由于對數據片上任意記錄的訪問都體現為對數據片的訪問，因此數據片查詢累積概率取值為所含數據記錄的查詢累積概率的最大值，數據片上的查詢代價表示為：

上的查詢代價 ＝ 定位尋址代價 + 數據傳輸代價

＝ 磁盤每次定位尋址代價 ×的查詢累積概率 +數據片的長度 ×每字節數據的傳輸代價 × 的查詢累積概率，由于數據分片后，可能存在查詢“誤命中”的情況，即片內部分數據不是查詢結果集，但會被訪問的情況，這就帶來了額外的傳輸開銷，定義這部分額外的傳輸開銷叫做代價偏差，數據的分片粒度越粗，則數據查詢的定位尋址代價越小，而數據傳輸代價偏差越大，導致數據傳輸代價越大，反之亦然，數據的分片粒度越細，則數據查詢的定位尋址代價越大，數據傳輸代價越小，也就是說，定位尋址代價和數據傳輸代價是兩個互相制約的指標，因此在傾斜范圍查詢工作負載下，數據分片問題是一個最優化問題；

2）定義最優分片方案：有N個關鍵字的數據集X，定義它的最優-分片方案中第分片為，第分片為，因為這樣的劃分方式是最優分片方案，因此，如果調整數據分片的邊界，將中的調整到數據片中，就會增加數據查詢的代價，也就是說，數據在經過最優分片后，分片代價偏差受到相鄰分片的約束，當各分片的代價偏差趨近于相等的時候，總的代價偏差最小。

3）切分出第一個數據片：定義范圍查詢邊界集為，其基數為B，將集合中的元素排序，得到，那么第一個數據片為；

4）試探合并下一段數據片，并計算合并帶來的代價偏差：

（1）將下一個數據初始化為下一個分片，并開始向后循環合并，如果合并后分片帶來的代價偏差大于門限T時，放棄合并，則原分片是最優數據片；

（2）如果合并后分片帶來的代價偏差不大于門限T時，則開始向后循環合并；