[發(fā)明專利]一種多維區(qū)間查詢方法及系統(tǒng)有效
| 申請?zhí)枺?/td> | 201010205946.3 | 申請日： | 2010-06-12 |
| 公開（公告）號： | CN101866358A | 公開（公告）日： | 2010-10-20 |
| 發(fā)明（設(shè)計）人： | 鄒永強;劉佳;查禮;王世才 | 申請（專利權(quán)）人： | 中國科學(xué)院計算技術(shù)研究所 |
| 主分類號： | G06F17/30 | 分類號： | G06F17/30 |
| 代理公司： | 北京律誠同業(yè)知識產(chǎn)權(quán)代理有限公司 11006 | 代理人： | 祁建國;梁揮 |
| 地址： | 100080 北*** | 國省代碼： | 北京;11 |
| 權(quán)利要求書： | 查看更多 | 說明書： | 查看更多 |
| 摘要： | |||
| 搜索關(guān)鍵詞： | 一種 多維 區(qū)間 查詢 方法 系統(tǒng) | ||
技術(shù)領(lǐng)域
本發(fā)明涉及計算機處理領(lǐng)域，尤其涉及一種多維區(qū)間查詢系統(tǒng)及方法。
背景技術(shù)
資源發(fā)現(xiàn)需要多種條件的查詢，其中多數(shù)查詢可以轉(zhuǎn)換為多維區(qū)間查詢。事實上多維區(qū)間查詢是網(wǎng)絡(luò)應(yīng)用的一個基本需求。簡單的例子是在存儲互聯(lián)網(wǎng)圖片信息的應(yīng)用，設(shè)計者可能需要查詢一段時間內(nèi)點擊數(shù)量最高的前100張圖片，這種查詢就涉及到了時間和點擊量等多個屬性(數(shù)據(jù)表的列，也叫維度、維)區(qū)間。
隨著網(wǎng)絡(luò)應(yīng)用數(shù)據(jù)量的不斷增大，現(xiàn)有方法均難以同時滿足高性能、低存儲開銷和高可靠性的要求。通過對現(xiàn)有數(shù)據(jù)模型進行分類可知，應(yīng)用需要支持多維區(qū)間查詢的新數(shù)據(jù)模型。分布式順序表(Distributed?Ordered?Table，DOT)是一種適用于海量數(shù)據(jù)(TB到PB級)下單個維度(僅僅是主鍵)區(qū)間查詢的數(shù)據(jù)庫系統(tǒng)，最有潛力通過增加索引支持多維區(qū)間查詢。
在分布式順序表上通常使用的索引方法是對需要查詢的列建立二級索引，查詢時先搜索二級索引再定位到數(shù)據(jù)表取出數(shù)據(jù)。這種方法會在檢索數(shù)據(jù)表時產(chǎn)生隨機讀操作，而在分布式順序表中隨機讀操作的速度相比順序掃描(scan)有一個數(shù)量級的下降，所以在這種索引機制下多維區(qū)間查詢的速度緩慢，響應(yīng)時間過長不能滿足目前網(wǎng)絡(luò)應(yīng)用對海量數(shù)據(jù)進行實時檢索的需求。如果不建二級索引，而是為索引列建立聚簇索引以提高查詢性能，則由于底層文件系統(tǒng)副本導(dǎo)致存儲開銷成倍增長。
本發(fā)明基于下述事實：
1、DOT系統(tǒng)中通常有3～5份副本用于提高性能和可靠性，以應(yīng)對超大規(guī)模數(shù)據(jù)量。
2、應(yīng)用使用多維區(qū)間查詢時所需屬性列數(shù)通常不超過5。
通過采集中國國家網(wǎng)格軟件GOS中高性能計算網(wǎng)關(guān)(HPCG)應(yīng)用的實際運行日志，記錄并分析了其29小時時間區(qū)間內(nèi)98.63萬次操作，其中查詢請求有96.1萬次，占97％。這些查詢請求具有如下規(guī)律：①全部的查詢請求可以包括在“＝”，“＜”，“＞”，“＜＝”，“＞＝”，“startswith”及其邏輯關(guān)系組合中，沒有其它復(fù)雜的SQL語法需求；②單獨查詢請求所涉及的字段比較少。所有單獨查詢請求涉及的字段數(shù)量均小于等于5，又其中92％的請求涉及的字段數(shù)量小于等于4；④單獨關(guān)系表涉及的支持查詢的字段數(shù)量均少于等于5。
3、DOT上連續(xù)掃描的吞吐率遠遠高于隨機讀取。
例如Google的BigTable就是典型的DOT系統(tǒng)，其讀寫1KB長度記錄的基本操作性能見表，從中可以看出順序讀是隨機讀的3.7倍，而連續(xù)掃描是隨機讀的12.7倍。
表1BigTable中基本操作性能
發(fā)明內(nèi)容
為了解決上述的技術(shù)問題，本發(fā)明提供了一種多維區(qū)間查詢系統(tǒng)及方法，其目的在于，基于分布式順序表構(gòu)建索引，使其支持多維區(qū)間查詢，并同時滿足高性能、低存儲開銷和高可靠性要求。
本發(fā)明公開了一種多維區(qū)間查詢方法，包括：
該專利技術(shù)資料僅供研究查看技術(shù)是否侵權(quán)等信息，商用須獲得專利權(quán)人授權(quán)。該專利全部權(quán)利屬于中國科學(xué)院計算技術(shù)研究所，未經(jīng)中國科學(xué)院計算技術(shù)研究所許可，擅自商用是侵權(quán)行為。如果您想購買此專利、獲得商業(yè)授權(quán)和技術(shù)合作，請聯(lián)系【客服】
本文鏈接：http://www.szxzyx.cn/pat/books/201010205946.3/2.html，轉(zhuǎn)載請聲明來源鉆瓜專利網(wǎng)。
