[發(fā)明專利]一種多維區(qū)間查詢方法及系統(tǒng)

有效

• 申請(qǐng)?zhí)枺?/td>: 201010205946.3
• 申請(qǐng)日: 2010-06-12
• 公開（公告）號(hào): CN101866358A
• 公開（公告）日: 2010-10-20
• 發(fā)明（設(shè)計(jì)）人: 鄒永強(qiáng);劉佳;查禮;王世才
• 申請(qǐng)（專利權(quán)）人: 中國科學(xué)院計(jì)算技術(shù)研究所
• 主分類號(hào): G06F17/30
• 分類號(hào): G06F17/30
• 代理公司: 北京律誠同業(yè)知識(shí)產(chǎn)權(quán)代理有限公司 11006
• 代理人: 祁建國;梁揮

1.一種多維區(qū)間查詢方法，其特征在于，包括：

步驟1，將用于備份數(shù)據(jù)的副本組織成為多份互為補(bǔ)充和校驗(yàn)的互補(bǔ)聚簇索引表；互補(bǔ)聚簇索引表以每個(gè)索引列創(chuàng)建一張以列值加原行主鍵加列值長度為新主鍵的順序表，并將原行中其余列的數(shù)據(jù)完整存儲(chǔ)；互補(bǔ)聚簇索引表用于供查詢時(shí)進(jìn)行連續(xù)掃描；

步驟2，將查詢串轉(zhuǎn)換為查詢計(jì)劃樹，進(jìn)行查詢優(yōu)化后完成查詢的執(zhí)行。

2.如權(quán)利要求1所述的多維區(qū)間查詢方法，其特征在于，步驟1中，互補(bǔ)聚簇索引表包含原數(shù)據(jù)表中所有的數(shù)據(jù)；底層文件系統(tǒng)的備份策略處于關(guān)閉的狀態(tài)。

3.如權(quán)利要求1所述的多維區(qū)間查詢方法，其特征在于，步驟2中，查詢優(yōu)化時(shí)，先對(duì)查詢語句進(jìn)行去重合并，然后基于分布式順序表的分片信息對(duì)子查詢結(jié)果集的大小進(jìn)行估算，最后挑選結(jié)果集最小的子查詢執(zhí)行查詢過程。

4.如權(quán)利要求1所述的多維區(qū)間查詢方法，其特征在于，查詢計(jì)劃樹的每個(gè)葉子節(jié)點(diǎn)是能被直接處理的點(diǎn)查詢和單個(gè)維度的區(qū)間查詢，查詢計(jì)劃樹的非葉子節(jié)點(diǎn)表示多個(gè)查詢的邏輯關(guān)系。

5.如權(quán)利要求3所述的多維區(qū)間查詢方法，其特征在于，估算子查詢結(jié)果集的大小具體包括：

步驟21，對(duì)于每個(gè)給定的區(qū)間查詢，由其起始鍵值和結(jié)束鍵值通過對(duì)元信息中數(shù)據(jù)的查找確定此區(qū)間查詢覆蓋的分片數(shù)量；

步驟22，對(duì)于被完全覆蓋的分片，按分片平均大小估算其大小；對(duì)于被部分覆蓋的分片，根據(jù)按照該分片被覆蓋的比例計(jì)算該分片大小；

步驟23，累加全部分片的大小，獲得估算的結(jié)果集大小；

步驟24，當(dāng)兩個(gè)子查詢包含的分片數(shù)相等且結(jié)果集大小相等時(shí)，比較查詢區(qū)間的字符串距離，用所述字符串距離來估算子查詢結(jié)果集的大小。

6.如權(quán)利要求1所述的多維區(qū)間查詢方法，其特征在于，還包括下述步驟：

步驟3，建立互補(bǔ)校驗(yàn)表，互補(bǔ)校驗(yàn)表中按照各個(gè)互補(bǔ)聚簇索引表的主鍵存儲(chǔ)了全部索引列的值，同時(shí)屏蔽底層文件系統(tǒng)的備份策略；當(dāng)互補(bǔ)聚簇索引表發(fā)生數(shù)據(jù)缺失時(shí)通過互補(bǔ)校驗(yàn)表中保存的主鍵對(duì)應(yīng)關(guān)系從其它互補(bǔ)聚簇索引表中恢復(fù)缺失的數(shù)據(jù)。

7.一種多維區(qū)間查詢系統(tǒng)，其特征在于，包括：

存儲(chǔ)節(jié)點(diǎn)，用于將用于備份數(shù)據(jù)的副本組織成為多份互為補(bǔ)充和校驗(yàn)的互補(bǔ)聚簇索引表；互補(bǔ)聚簇索引表以每個(gè)索引列創(chuàng)建一張以列值加原行主鍵加列值長度為新主鍵的順序表，并將原行中其余列的數(shù)據(jù)完整存儲(chǔ)；互補(bǔ)聚簇索引表用于供查詢時(shí)進(jìn)行連續(xù)掃描；存儲(chǔ)節(jié)點(diǎn)將互補(bǔ)聚簇索引表的分片在物理上分布式的存儲(chǔ)；

客戶端，用于將查詢串轉(zhuǎn)換為查詢計(jì)劃樹，進(jìn)行查詢優(yōu)化后完成查詢的執(zhí)行。

8.如權(quán)利要求7所述的多維區(qū)間查詢系統(tǒng)，其特征在于，

所述互補(bǔ)聚簇索引表包含原數(shù)據(jù)表中所有的數(shù)據(jù)；底層文件系統(tǒng)的備份策略處于關(guān)閉的狀態(tài)。

9.如權(quán)利要求7所述的多維區(qū)間查詢系統(tǒng)，其特征在于，

所述系統(tǒng)還包括服務(wù)節(jié)點(diǎn)，所述服務(wù)節(jié)點(diǎn)用于存儲(chǔ)分布式順序表的元信息，元信息中包含分片與存儲(chǔ)節(jié)點(diǎn)的對(duì)應(yīng)關(guān)系，

所述客戶端在查詢優(yōu)化時(shí)進(jìn)一步用于先對(duì)查詢語句進(jìn)行去重合并，然后基于所述分布式順序表的分片信息對(duì)子查詢結(jié)果集的大小進(jìn)行估算，最后挑選結(jié)果集最小的子查詢請(qǐng)求存儲(chǔ)節(jié)點(diǎn)執(zhí)行查詢過程。

10.如權(quán)利要求7所述的多維區(qū)間查詢系統(tǒng)，其特征在于，

查詢計(jì)劃樹的每個(gè)葉子節(jié)點(diǎn)是能被存儲(chǔ)節(jié)點(diǎn)直接處理的點(diǎn)查詢和單個(gè)維度的區(qū)間查詢，查詢計(jì)劃樹的非葉子節(jié)點(diǎn)表示多個(gè)查詢的邏輯關(guān)系。

11.如權(quán)利要求9所述的多維區(qū)間查詢系統(tǒng)，其特征在于，

所述客戶端在估算子查詢結(jié)果集的大小時(shí)進(jìn)一步用于對(duì)于每個(gè)給定的區(qū)間查詢，由其起始鍵值和結(jié)束鍵值通過對(duì)元信息中數(shù)據(jù)的查找確定此區(qū)間查詢覆蓋的分片數(shù)量；對(duì)于被完全覆蓋的分片，按分片平均大小估算其大小；對(duì)于被部分覆蓋的分片，根據(jù)按照該分片被覆蓋的比例計(jì)算該分片大小；累加全部分片的大小，獲得估算的結(jié)果集大小；當(dāng)兩個(gè)子查詢包含的分片數(shù)相等且結(jié)果集大小相等時(shí)，比較查詢區(qū)間的字符串距離，用所述字符串距離來估算子查詢結(jié)果集的大小。

12.如權(quán)利要求7所述的多維區(qū)間查詢系統(tǒng)，其特征在于，

所述存儲(chǔ)節(jié)點(diǎn)還用于建立互補(bǔ)校驗(yàn)表，互補(bǔ)校驗(yàn)表中按照各個(gè)互補(bǔ)聚簇索引表的主鍵存儲(chǔ)了全部索引列的值，同時(shí)屏蔽底層文件系統(tǒng)的備份策略；當(dāng)發(fā)現(xiàn)互補(bǔ)聚簇索引表發(fā)生數(shù)據(jù)缺失時(shí)通過互補(bǔ)校驗(yàn)表中保存的主鍵對(duì)應(yīng)關(guān)系從其它互補(bǔ)聚簇索引表中恢復(fù)缺失的數(shù)據(jù)。