列存儲數(shù)據(jù)庫關(guān)鍵技術(shù)綜述

1、Vol. 37 No. 12Dec 2010第37卷第12期2010年12月計算機(jī)科學(xué)Computer ScienceVol. 37 No. 12Dec 2010Vol. 37 No. 12Dec 2010列存儲數(shù)據(jù)庫關(guān)鍵技術(shù)綜述李超張明博邢春曉胡勁松（清華大學(xué)信息技術(shù)研究院北京100084）摘要隨著互聯(lián)網(wǎng)技術(shù)的發(fā)展、硬件的不斷更新、企業(yè)及政府信息化的不斷深入，應(yīng)用的復(fù)雜性要求越來越高，推動 著數(shù)據(jù)存儲技術(shù)向著海量數(shù)據(jù)、分析數(shù)據(jù)、智能數(shù)據(jù)的方向發(fā)展，以便為數(shù)據(jù)倉庫、在線分析提供高效實時的技術(shù)支 持?；谛写鎯Φ臄?shù)據(jù)庫技術(shù)面臨新的問題 ，已經(jīng)岀現(xiàn)了技術(shù)瓶頸。近些年來，一種新的數(shù)據(jù)存儲 理念，即基

2、于列存 儲的關(guān)系型數(shù)據(jù)庫（簡稱列數(shù)據(jù)庫，下同）應(yīng)運而生。列數(shù)據(jù)庫能夠快 速發(fā)展，主要原因是其復(fù)雜查詢效率 高,讀磁盤 少,存儲空間少，以及由此帶來的技術(shù)、管理和應(yīng)用優(yōu)勢。對列數(shù)據(jù)庫 技術(shù)的基本現(xiàn)狀、關(guān)鍵支撐技術(shù)以及應(yīng)用 優(yōu)勢進(jìn) 行了介紹和分析。關(guān)鍵詞 列數(shù)據(jù)庫，列存儲，數(shù)據(jù)壓縮，延時物化，成組迭代，不可見連接，數(shù)據(jù)倉庫，商業(yè)智能，T PCH 中圖法分類號TP391文獻(xiàn)標(biāo)識碼 ASurvey and Review on Key Tech no logies of Column Orien ted Database SystemsL I Chao ZH A NG M ing bo XIN G Ch

3、un xiao H U Jin song(Research In stitute of Inform ati on Tech no logy, Tsin ghua U ni vers ity, Beiji ng 100084, China)Abstract Column oriented database is a kind of new databasestorage technology that stores data according to column (not traditio nally row). T he databasepioneers such as Dr. M ich

4、ael Stonebraker are advocating and explor ing the new theory and techno logy for column oriented database.The main features of it are good query efficiency, less disk access, less storage, and significant impro vement of databaseperfo rmance. Column oriented databaseis an ideal archit ecture for dat

5、a warehouse natively, and thus shows a good potential in suppo rting highly efficient business intellig ence applica t ions. This new technolo gy is promising in both academic and business, therefore attracting lots of high tech corpora t ions and research institutes to devote in it. This paper intr

6、 oducedand analysed the main features,key technologies and current R& D situat ions of column oriented database.Keywords Column oriented database, Compression, Block iteration, Late materialization, Invisible join, D ata warehouse, Business intellig ence, TPCHVol. 37 No. 12Dec 2010Vol. 37 No. 12

7、Dec 2010到稿日期：2010 01 08 返修日期：2010 03 22 本文 受國家863計劃（編號2009AA01Z143）,鐵道部 清華大 學(xué)科技 研究基金（編號:J2008X 009）資助。李 超（1978-）,女,博士，講師，主要研究方向為存儲技術(shù)、數(shù)據(jù)庫技術(shù)等，E mail: li chaotsi nghua. edu. cn;張明博（1982-）,男,工程師,主要研究方向為 Web信息管理、數(shù)據(jù)庫技術(shù)等；邢春曉（1967-）,男，博士 ,教授，主要研究方向為數(shù)據(jù)庫技術(shù)、數(shù)字圖書館等。111 C'liitti Academic Journal kJiLCtranic

8、PiihlKhiil氐 I 心】2 Allw-.旦一http'.VvAr.Cchl!1引言列數(shù)據(jù)庫是基于列存儲 的、主要面向企業(yè)決策分析領(lǐng)域 的關(guān)系型數(shù) 據(jù)庫。在 SIGMOD85,論文 A Decomposition Storage Model 1提出了一種新的存儲概念，簡稱DSM ,這 就是列數(shù)據(jù)庫的雛形，但是這種技術(shù)在當(dāng)時并沒有得到足夠 的重視。近些年來在以 Michael Stonebraker, Daniel J. Abadi, Peter Boncz為首的一批專家的大力提倡 下,列數(shù)據(jù)庫相關(guān)技 術(shù)及應(yīng)用快速發(fā)展，在企業(yè)決策領(lǐng)域已經(jīng)開辟了一條新道路（參考網(wǎng)址 www. dat

9、abasecolumn. com）。這種技 術(shù)的特 點是 復(fù)雜數(shù)據(jù)查詢效率高，讀磁盤少，存儲空間少。這些特點使其 成為構(gòu)建數(shù)據(jù)倉庫的理想架構(gòu)，因而引起數(shù)據(jù)庫學(xué)術(shù)前沿和 相關(guān)高新科技企業(yè)投入大量的人力和物力研發(fā)。1. 1列數(shù)據(jù)庫基本概念列數(shù)據(jù)庫是對應(yīng)并區(qū)別于行數(shù)據(jù)庫的概念。行數(shù)據(jù)庫就 是我們所熟知的傳統(tǒng)關(guān)系型數(shù)據(jù)庫，即數(shù)據(jù)按記錄存儲，每一 條記錄的所有屬性都存儲 在一起，如果要查詢一條記 錄的一 個屬性值，需要先讀取 整條記錄的數(shù)據(jù)。而列數(shù)據(jù)庫是按數(shù) 據(jù)庫記錄的列來組織和存 儲數(shù)據(jù)的，數(shù)據(jù)庫中每個表 由一組 頁鏈的集合組 成,每條頁鏈對應(yīng)表中的一個存儲列，而該頁鏈 中每一頁存儲的是該列的一個或多

10、個值。1.2列數(shù)據(jù)庫的學(xué)術(shù)價值與應(yīng)用價值列數(shù)據(jù)庫技術(shù)有它獨有的 學(xué)術(shù)價值，近些年來在國際一 流的數(shù)據(jù)庫會議上頻頻有關(guān)于這個領(lǐng)域的優(yōu)秀論文岀 現(xiàn)13,517，他們主要圍繞 其商業(yè)價值以及主要 關(guān)鍵技術(shù)，包括 基于其主要存 儲原理的存 儲壓縮、延時物化、成組疊代、查詢 優(yōu)化、索引、及加密等進(jìn)行研發(fā)。列數(shù)據(jù)庫的應(yīng)用價 值來自它對復(fù)雜查詢的靈活快速以及 壓縮所帶來的存儲優(yōu)勢，這使其在數(shù)據(jù)倉庫和商務(wù)智 能方面 具有良好的發(fā)展前景。已經(jīng)有許多列數(shù)據(jù)庫在企業(yè)決策分析領(lǐng)域的成功案例。VERT ICA已經(jīng)在美國擁有了許多客戶， SYBASE IQ更是已經(jīng)進(jìn)入了中國市場。1.3主要的開源列數(shù)據(jù)庫和商業(yè)列數(shù)據(jù)庫1.

11、 3. 1 C StoreC Store是一款開源 的、運行于Linux系統(tǒng)的列數(shù)據(jù)庫, 是耶魯大學(xué)、麻省理工大學(xué)、布朗大學(xué)等聯(lián)合協(xié)作開發(fā)的軟 件,于2006年10月發(fā)布。它是 一種適合做學(xué)術(shù)研究的列數(shù) 據(jù)庫，目前主要的學(xué)術(shù)研究都是利用它來做的 ，在學(xué)術(shù)界比較 流行。它同時 是商業(yè)列數(shù)據(jù)庫產(chǎn)品VERTICA的原型(ht tp:/db. csail. mit. edu/projects/cstore/# people)。1. 3. 2 MonetDBMonetDB是一款運行 于L inux和 Window s系統(tǒng)上 的高 性能開源列數(shù)據(jù)庫(http: / /monetdb. cwi.nl/),同

12、時是一款內(nèi) 存數(shù)據(jù)庫。它可應(yīng)用于數(shù)據(jù)挖掘、OLAP、GIS、XML查詢、文本和多媒體檢 索。它支 持SQL?99,SQL?03核 心標(biāo)準(zhǔn)，支持 持久存儲、觸發(fā)器。用戶可用C編寫所需功能。它還支持 OPEN GIS標(biāo)準(zhǔn)和SQL/ XM L的大部分標(biāo)準(zhǔn)。它基于內(nèi)存文 件存儲，可對數(shù)據(jù)庫進(jìn) 行升級，支持32位和64位平臺，能對 查詢進(jìn)行有效的優(yōu)化14。1. 3. 3 MonetDB/X100MonetDB/ X100同MonetDB都是一個組織 開發(fā)的，主要 區(qū)別是X100不是內(nèi)存數(shù)據(jù)庫，而其技術(shù)也更加成熟一些,查 詢效率也 更加優(yōu)秀。MonetDB/X100同樣運行于Linux和 Window s

13、系統(tǒng)上，同樣由C編寫。1. 3. 4 RasdamanRasdaman是一款運行在Linux系統(tǒng)上的商業(yè)列數(shù) 據(jù)庫, 由不萊梅大學(xué)和Rasdaman公司合作開發(fā)(www. rasdaman. com), 2008年9月宣布開源版本(),全名 為raster data manager。它是一款快速、靈活、價廉的列數(shù) 據(jù)庫,其開發(fā)語 言是C/C+ +以及JAVA,支持大部分SQL 標(biāo)準(zhǔn)。1. 3. 5 Sybase IQSYBASE IQ是Sybase公司專為分析 型應(yīng)用與 數(shù)據(jù)倉庫 而設(shè)計的，是唯個由傳統(tǒng)基于行存儲的關(guān)系型數(shù)據(jù)庫廠 商開發(fā)的列數(shù)據(jù)庫產(chǎn)品。Sybas

14、eIQ是擁有列式存儲、專利索 弓I、查詢優(yōu)化等技術(shù)的數(shù)據(jù)倉庫引擎，帶來的查詢速度將比傳 統(tǒng)數(shù)據(jù)庫提升10 100倍。1. 3. 6 ParA ccelParAccel分析數(shù)據(jù) 庫PADB是一個專門開發(fā)的數(shù)據(jù)倉 庫和分析型數(shù)據(jù)庫管理系統(tǒng)，ParA ccel具有可擴(kuò)展性、簡單的 數(shù)據(jù)倉庫的安裝和操作、成本可接受性、高效解析查詢處理等 特點。除此之夕卜,還有 Vertica, X100/ VectorWise, K ickFire, SAP Business Accelerator, Infobright, Exasol 等開源列數(shù)據(jù) 庫以及商業(yè)列數(shù)據(jù)庫?？梢钥吹?，列數(shù)據(jù)庫已經(jīng)從 SIGM OD85

15、上不為大眾所關(guān) 注的DSM雛形發(fā)展到了今天初具規(guī)模的局面。無論是在學(xué) 術(shù)前沿研究、系統(tǒng)技術(shù) 研發(fā),還是在數(shù)據(jù)倉庫、數(shù)據(jù)分析及決 策支持等應(yīng)用領(lǐng)域，列數(shù)據(jù)庫都是一個蓬勃發(fā)展的熱點和新 的增長點。本文從3個方面分析列數(shù)據(jù)庫相對于行數(shù)據(jù)庫的優(yōu)勢; 然后介紹列數(shù)據(jù)庫的幾 大關(guān)鍵技 術(shù),包括壓縮、延時物化、成 組迭代、不可見連接，這既是當(dāng)前的一些研究前沿和熱點，又 是不同列數(shù)據(jù)庫系統(tǒng)之間的主要技術(shù)區(qū)別所在;接下來，介紹 用于評價 數(shù)據(jù)庫系統(tǒng)性能的 TPCH測試,以為相關(guān)研究提供 參考，并引用TPCH官方測試結(jié)果進(jìn)一步說明列 數(shù)據(jù)庫的優(yōu) 勢;最后總結(jié)全文。2列數(shù)據(jù)庫的優(yōu)勢列數(shù)據(jù)庫在數(shù)據(jù)倉庫、商務(wù)智能領(lǐng)域應(yīng)

16、用中有著先天的 優(yōu)勢:獨特的存儲方式，能夠迅速地執(zhí)行復(fù)雜查詢；列數(shù)據(jù)庫 的壓縮技術(shù)，更是能為數(shù)據(jù)倉庫、商務(wù)智能應(yīng)用中巨大的數(shù)據(jù) 量節(jié)約存儲成 本;列數(shù)據(jù)庫先進(jìn) 的索引技 術(shù)也大大提 高了數(shù) 據(jù)庫的管理。2. 1列數(shù)據(jù)庫存儲方式帶來的技術(shù)優(yōu)勢因為列數(shù)據(jù)庫和行數(shù)據(jù)庫 都是關(guān)系型數(shù)據(jù)庫，因此列數(shù) 據(jù)庫在邏輯上與行數(shù)據(jù)庫沒有區(qū)別，用戶處理和操作 的都是 一行一行的記 錄、一個一個的表。兩者的本質(zhì)區(qū)別在于其物 理存儲是基于列存儲還是基于行存儲。列數(shù)據(jù)庫按列存儲的 結(jié)構(gòu)，便于在列上對數(shù)據(jù)進(jìn)行輕量級的壓縮，列上多個相同的 值只需要存儲一份。壓縮能夠大量地降低存儲成本。按列存儲和壓縮的特點，也為列數(shù)據(jù)庫在查詢

17、方面帶來 先天優(yōu)勢，因為若能將更多的數(shù)據(jù)壓縮在一起 ，則在每次讀取 時就可以獲得 更多的數(shù)據(jù)。很顯然，每次讀取操作獲取更多 的數(shù)據(jù)就意味 著更快的處 理速度。同 時，列數(shù)據(jù)庫的存儲特 點有利于迅速查詢所需要的列。行存儲雖然可以比較輕松地 添加修改記錄，但是會增加許多不必要的讀取；而列存儲只需 要讀取相關(guān)數(shù) 據(jù),并且可以從多個入口寫入數(shù)據(jù)。2. 2列數(shù)據(jù)庫在數(shù)據(jù)管理方面的便捷優(yōu)勢在數(shù)據(jù)管理方面，行數(shù)據(jù)庫采用的是稠密索引，即當(dāng)數(shù)據(jù) 庫文件中的記錄不按照 關(guān)鍵碼的順序排列時(比如按照加入 的順序排列),需要對每一個記錄 建立一個索引項。這有兩方 面的缺點：一是增加所用的存儲空間，二是增加數(shù)據(jù)更新時的

18、 代價。正是由于這兩 方面的問題,在基于行存儲的關(guān)系型數(shù) 據(jù)庫中，為表的所有列 都建立索引就不太現(xiàn)實。這樣就岀現(xiàn) 了下面的問題：如果一個查詢語 句是基于一個未加索 引的列 查詢，系統(tǒng)就不 得不做全表掃描，導(dǎo)致數(shù)據(jù)庫的查詢效率不 高。因此，考慮在哪些列加索引并根據(jù)應(yīng)用的需求適時調(diào)整,就成為數(shù)據(jù)庫管理員的一項繁重工作。而列數(shù)據(jù)庫因為各條 記錄在磁盤中是按照關(guān)鍵碼值壓縮順序存放的，所以采用的 是稀疏索引，即把連續(xù)的若干記錄分成組(塊),對一組(塊)記 錄建立一個索 引項。列數(shù)據(jù) 庫可以為所有列建立稀疏索引, 事實上也都是 這么做的。這是因為每個列的值都已被壓縮順 序存儲，索引只需建立到數(shù)據(jù)塊級，因此

19、索引的存儲空間很 小,維護(hù)費用很低，使得可以以很小的代價給所有的列建立索 引。當(dāng)查詢通過索引 定位到某一數(shù)據(jù)塊后，就可以使用二分 法查找。這樣，數(shù)據(jù)查詢在任何情況下都不會導(dǎo)致全表掃描,從而提高了數(shù)據(jù)庫的查詢性能。在列數(shù)據(jù)庫中，后臺程序默 認(rèn)地自動為所 有的列維護(hù) 稀疏索引，因此為數(shù)據(jù)庫管 理員卸 下了建立、管理和維護(hù)索引的繁重工作。此外，無論是在行數(shù)據(jù)庫還是列數(shù)據(jù)庫中，在刪除一條記 錄時，都會岀現(xiàn)一個物 理存儲空間上不連續(xù)的空洞。在行數(shù) 據(jù)庫中，隨著一段時間的 增刪操作,這些空洞會越來越多，越 來越大。這一方面會 導(dǎo)致物理存儲空間的閑置和浪費,另一方面會使得訪問數(shù)據(jù)庫 的效率下降。因此，行數(shù)據(jù)

20、庫管理員 為了填補(bǔ)這些空洞、消除空洞帶來的負(fù)面影響，經(jīng)常在維護(hù)時 要做的事情是把數(shù)據(jù)全 部導(dǎo)岀來,再重新導(dǎo)回去。而列 數(shù)據(jù) 庫因為在每一列上都采 用了輕量的稀疏索引，在插入刪除數(shù) 據(jù)時,利用這些索引可以把空洞盡量減小，免除了數(shù)據(jù)庫管理員的大量導(dǎo)入、導(dǎo)岀工作。2.3列數(shù)據(jù)庫在數(shù)據(jù)挖掘領(lǐng)域的應(yīng)用優(yōu)勢數(shù)據(jù)挖掘應(yīng)用有著數(shù)據(jù) 量大、主要針對少數(shù)列進(jìn)行復(fù)雜 查詢操作 的特點。在列存儲模式下，對于列的DM L ( Data Manipulation L anguage,數(shù)據(jù)操縱語言 命令)操作，僅僅是對 列所對應(yīng)的數(shù)據(jù)庫頁鏈進(jìn)行數(shù)據(jù)掃描，不會導(dǎo)致對全表的數(shù) 據(jù)訪問，可以有效降 低DM L操作的1/ O數(shù)量。

21、由于數(shù)據(jù)按 列存儲，為調(diào)整數(shù)據(jù)模型所做的新增列、刪除列操作不再會遇 到數(shù)據(jù)碎片問題。這是因為 在列存儲中，由于數(shù)據(jù)存儲以列 為單元，列刪除或者新增操作是將列所對應(yīng)的數(shù)據(jù)庫頁鏈從 表的頁鏈集 合中去除或 者新增，不涉及其他列對應(yīng) 的數(shù)據(jù)庫 頁鏈。此外，列數(shù)據(jù)庫中數(shù)據(jù)按列壓縮的特點也同樣能夠減 少挖掘時的I/O量2。3列數(shù)據(jù)庫的關(guān)鍵技術(shù)3.1壓縮隨著信息化的不斷發(fā)展，在數(shù)據(jù)倉庫與商業(yè)智能領(lǐng)域中， 數(shù)據(jù)量已經(jīng)越來越大，企業(yè)不可能不間斷地增加存儲成本，所 以數(shù)據(jù)壓縮已經(jīng)是目前IT領(lǐng)域一個一定要面對的問題。列 數(shù)據(jù)庫的存儲特點，決定了其在壓縮方面的優(yōu) 勢。在SIGMODO6會議 上,Daniel J.

22、Abadi3通過在 開源的 列數(shù)據(jù)庫C Store上進(jìn)行實驗比較和理論 分析指岀，主要的 壓縮方法有以下幾類：1) 行程編碼算法(Run length Encoding);2) 詞典編碼算法(Dict ionary Encoding);3) 位向量算法(Bit Vector Encoding)。3. 1.1 行程編碼算法(Run length Encoding)行程編碼算法(見圖1)是比較適合列數(shù)據(jù)庫的壓縮算法 之一,即用一個三元組記錄數(shù)據(jù)值、數(shù)據(jù)岀現(xiàn)的起始位置和持續(xù)長度(即行程),以代替具有相同值的若干連續(xù)原始數(shù)據(jù),使三元組的存儲長度少于原始數(shù)據(jù)的長度。三元組描述為(X, Y,Z):X:數(shù)據(jù)

23、的值，丫：起始位置，Z:長度。討單洪型嚴(yán)&類型QI12QL15容Qi14Qi2532Q234以宦一為別訂單類型嚴(yán)產(chǎn)圧類型(QI 15)(L W2a迫5 7 1)gr,>5nz24圖1行程編碼算法3. 1.2 詞典編碼算法(Dictio nary Encoding)詞典編碼就 是生成一個 原始值 替代值 的對照詞典。 為了起到壓縮的作用，替代值的長度小于原始值的長度。存 儲的時候，只存儲替代值而不是原始值，從而壓縮了存儲空 間。算法描述如下：T1:原始表(其中，T1有n行)DIC:詞典表(關(guān)于表T 1的第k列的詞典)T2:壓縮存儲表N:原始值M :替代壓縮值For( 1# i #

24、n)Begi n掃描T 1中第k列的第i個值得到原始值 N ;查找DIC中N對應(yīng)的壓縮值 M ;將壓縮值M作為T2中第k列的第i個值存儲;En d.如圖2所示的例子 中,簡單的兩位數(shù)字代替了原始的字 符串，縮短了所需的存儲空間長度。Q】»0心0102303訂單類電QI(M)QI00QI1QI11/00QI00Q2Q201圖2 詞典編碼算法3.1.3位向量編碼算法(Bit V ector Encoding)位向量編碼是為每一個不 同的取值生成一個位向量，根 據(jù)位向量(串)中不同的位置取值0或1來對應(yīng)并確定不同的 原始值。算法描述如下：T 1:原始表中的某一列(其中，T 1有n行)V:T

25、1的取值空間(無重復(fù)元素)M :原始值m: V的模數(shù)(V中的值的個數(shù))BVi( 1# i # m) : V中不同取值對應(yīng)的位向量For( 1# i # n)Begin掃描T 1中的第i個值M ;將M加入取值空間 V;End;計算V的模m;For( 1# i # m)初始化位向量 BV i;/ /m個位向量分別對應(yīng) m個不同的取值For( 1# i # n)Begi n掃描T 1中的第i個值M ; 確定M對應(yīng)的位向量 BV x;將位向量BVx的第i位值置為1;For( 1# j # m)if(j< > x) th en將位向量 BVj的第i位值置為0; En d.圖3中產(chǎn)品ID列的原

26、始數(shù)據(jù)經(jīng) 過位向量算法壓縮后, 形成如圖2所示的位向量。Q2位向覆00101flfl0101圖3位向量算法3.1.43種壓縮方法比較Daniel J. Abadi在文獻(xiàn)5中介紹的3種壓縮方法都是輕 量級壓縮算法。輕量級壓縮最大的優(yōu)點是能夠在不解壓的情 況下直接對壓縮狀態(tài)的數(shù)據(jù)進(jìn)行操作19。就目前的列數(shù)據(jù) 庫而言,行程編碼是一種最容易實現(xiàn)的壓縮方法,但是有一定的局限性。表1是3種壓縮方法的優(yōu)缺點比較。表1壓縮方法比較算法名稱行程編碼算法詞典編碼算法位向量算法數(shù)據(jù)列的a)適用于重復(fù)數(shù)據(jù)較多共同特征b)不適用于重復(fù)數(shù)據(jù)較少適用數(shù)據(jù)列 的不同特征重復(fù)數(shù)據(jù)的排序 比較規(guī)則取值空間較小取值空間較小不適用的

27、數(shù)a)取間空間較大據(jù)列不同特排序不規(guī)則b)數(shù)據(jù)類型長度比詞取值空間較大征典符號長度更小a)對于數(shù)據(jù)類型要求優(yōu)點對于適用的數(shù)據(jù) 特征,有比較好 的壓縮效果a) 對于數(shù)據(jù)類型要求 較低b) 對于數(shù)據(jù)排序要求 較低較低b)對于數(shù)據(jù)排序要求 較低0在有些情況，查詢效率要比詞典編碼高對列值的重復(fù)性 以及排序要求較 高需要創(chuàng)建一張詞典用位置代表數(shù)據(jù),如缺點表,增加維護(hù)代價，如取值空間較大,或重果數(shù)據(jù)重復(fù)性不高，復(fù)性較低，占用空間詞典表會過于巨大會比較大注：表中所謂適用即采用了某一壓縮算法可以起到減少存儲空間 的效果。3. 1.5壓縮優(yōu)勢的實例對于列數(shù)據(jù)庫主要應(yīng)用 的數(shù)據(jù) 倉庫領(lǐng)域,海量數(shù)據(jù)的有 效壓縮是一

28、個十分重要的優(yōu)勢。幾種開源和商業(yè)的列數(shù)據(jù)庫 系統(tǒng)都將良好的壓縮率作為自己突岀的優(yōu)勢。列數(shù)據(jù)庫的領(lǐng) 軍廠家SYBASE IQ就聲稱其壓 縮率可達(dá)到70%。表2是2005年 Winter Corporation做的10大數(shù)據(jù) 庫評 比。表中的數(shù)據(jù)倉庫大小是 建立兩年后數(shù)據(jù)倉庫的大小，而 原始數(shù)據(jù)大 小是指數(shù)據(jù)倉庫建立時的大小。N ielsen M edia Reseach是美國一家從事媒體 收視率 分析研究的公司，基于 SybaseIQ系統(tǒng)建立了數(shù)據(jù)倉庫,原始大小是17. 969TB。數(shù) 據(jù)倉庫建立兩年后，大小是17. 685TB。Yahoo點擊流分析數(shù) 據(jù)倉庫(基于Oracle系統(tǒng))建立的時候

29、數(shù)據(jù)量是17. 014 TB, 而建立兩年后,數(shù)據(jù)量大小為100. 386TB?；谛袛?shù)據(jù)庫 Oracle的Yahoo點擊流分析數(shù)據(jù)倉庫從約17TB擴(kuò)張到了約 100T B,大約擴(kuò)張了 6倍。而基于列數(shù)據(jù)庫Sybase IQ的 Nielsen Media Research數(shù)據(jù)倉庫卻隨著數(shù)據(jù)的積累被壓縮 得比原來還小。所以，從這個例子可以看出列數(shù)據(jù)庫Sybase IQ的壓縮比是非常高的。表2 對比表公司、數(shù)據(jù)倉庫大小(TB)原始數(shù)據(jù)大小(TB)數(shù)據(jù)數(shù)據(jù)操作體系數(shù)據(jù)庫系統(tǒng)存儲組織行數(shù)庫系統(tǒng)結(jié)構(gòu)廠商廠商廠商Y ahoo100. 38617. 0143853Oracleun ixCen tralize

30、d/ SMPOracleFujitsuSieme nsEM CN ielsenMed iaResear ch17. 68517. 9695024SybaseIQun ixCen tralized/ SMPSybaseFujitsuSieme nsEM C3. 1.6 總結(jié)在國內(nèi)，已經(jīng)有同行對 壓縮算法的性能分析做了很多工 作18,但列數(shù)據(jù)庫領(lǐng)域的壓縮算法研究 仍是我們未來工作的 重點之一。壓縮技術(shù)不僅可 以節(jié)約存儲空間,而且是提高查 詢效率的關(guān)鍵因素。但是上述列數(shù)據(jù)庫壓縮方法都有其局限 性,所以研發(fā)一個適用范圍更加廣泛、壓縮以及解壓的時間更 加快速的壓縮方法，必然是列數(shù)據(jù)庫領(lǐng)域?qū)W術(shù)研究的一個熱

31、 點。3. 2 延時物化為了說明延時物化，先介紹元組物化的概念。元組物 化, 即將常用元組或可能會用到的邏輯元組從實際物理存儲的狀 態(tài)生成為實體化的元組，也稱為物化，存儲在內(nèi)存中。在隨后 查詢時，直接讀取已經(jīng)物化的元組，以提高查詢的效率。而元 組物化有兩種 方案,分別是提前物化：在提交查詢之前物化元 組;延時物化：盡量推 遲物化 元組的時間,在查詢中間的某個 時刻物化元組。對于列數(shù)據(jù)庫來說，提前物化需要解壓所有已經(jīng)壓縮的 數(shù)據(jù)，其時間和空間的開銷是很大的。同時，提前物化會涉及 到很多不必 要的列，有悖列數(shù)據(jù)庫按列存儲、按需取用的初 衷。因此，在列數(shù)據(jù)庫領(lǐng)域，提岀了延時物化的思想。3. 2. 1

32、延時物化形式化描述假設(shè)有如下查詢：select value1, value 2, ? , value n , AGG 1, AGG 2, ? , AGG qfrom table 1, table 2, ? , tableMwherecondition 1 OP1 conditon 2 OP2, ? , OPt condition pLIST 1 , LIST2, ? , LIST lValue i(1# i # N):查詢直接要得到的值A(chǔ)GG i( 1# i# Q):對于查詢的值進(jìn)行聚集計算的結(jié)果table i( 1# i # M):查詢所涉及到的表 con dition i (1 # i #

33、 P):查詢的選擇條件 OPi( 1 # i # T):邏輯運算(與或非) LIST i( 1# i# L):對結(jié)果進(jìn)行排序處理指令算法描述如下：For( 1# i # P )Begi n對于conditioni,生成標(biāo)定符合條件的位向量hi；End;初始化目標(biāo)位向量H;H : = h 1;For( 1< i # P)H = H OP i- 1 hi；初始化目標(biāo)物化結(jié)果空間為0;/0有(N+ Q)個存儲空間For( 1# i # ( N+ Q)Begi nif( i# N ) then Oi = (Valuei 對應(yīng)的列)AND HelseOi= (AGG i- n 對應(yīng)的列)AND H

34、 ;End;初始化最終查詢結(jié)果空間為S;/S有(N + Q)個存儲空間For( 1= < i< = (N + Q)Begi nif( i< = N) then Si= Oielse S i = AGG i - n ( Ol );End;輸出結(jié)果時按照LI ST1, L IST2, ? , 口 STl的要求依次排 序。3. 2. 2延時物化測試實例以下面的查詢?yōu)槔篠elect custID, SUM ( price) From table whereI c I©今942和1*hims Academic Journal Kluctronic Puhlnhin I iO

35、Mse. Allg.hftp叮扎WR- ! 5打prodID = 4 andstorelD= 1gr oup by prodID如圖4所示,如果采用提前物化，列數(shù)據(jù)庫在執(zhí)行查詢 時，會首先將列中數(shù)據(jù)解壓，之后構(gòu)建（物化）元組。這樣的操 作有3個缺點：一是需要解壓所有數(shù)據(jù)；二是需要物化所有元 組;三是增加內(nèi)存負(fù)擔(dān)。prodIDElCHClDcusIlDpri-cc斗斗3134314243ao423甸圖4提前物化如果采用延時物化，列數(shù)據(jù)庫則按過程執(zhí)行查詢。如圖5 所示，根據(jù)判定條件 prodID = 4, storeID= 1,將 prodID, storelD兩列分別用位向量進(jìn)行選擇標(biāo)定。圖5

36、延時物化第一步之后將兩個列對應(yīng)的向 量進(jìn)行邏輯與運算，得到一個列 向量，如圖6所示。缶向也sidrelD 竝旬駅1+0fl111011圖6 延時物化第二步通過上面得到 的位向量,與相關(guān)兩列進(jìn)行邏輯與運算 在此刻將查詢得到的元組進(jìn)行物化，如圖7所示。圖7 延時物化第三步最后通過物化的元組,得到所要查詢的結(jié)果custID,SUM（price）,如圖 8 所示。ICDE2007會議上,Daniel J. A badi7在對延時物化和提 前物化進(jìn)行測試后得出了令人信服的定量化結(jié)論:在低選擇 性、中選擇性和高選擇性 3類具有代表性的查詢中，延時物化 的表現(xiàn)始終要好于提前物化，如圖9所示。在對比測試中，即

37、使在沒有壓縮的情況下，延時物化的表 現(xiàn)仍然要比提前物化的好，如圖10所示。圖9 對比圖圖10 對比圖3.2. 3 總結(jié)延時物化最主要的優(yōu)點在于其高效的壓縮傳輸數(shù)據(jù)開 銷:在執(zhí)行計劃中用位圖（位向量）來標(biāo)識行的位置，直到最后 必須取屬性值 時再實際取 相應(yīng)列的 值，盡可能地避免了不必 要的實際數(shù)據(jù) 傳輸開銷。延 時物化是一個比較實用的技術(shù), 非常適合在列數(shù)據(jù)庫中使用。單純的列數(shù)據(jù)庫是一列一列地 把數(shù)據(jù)存儲在 磁盤上，如果離開列數(shù)據(jù)庫，延時物化許多性能 上的潛力得不 到實現(xiàn)7。Daniel J. Abadi在文獻(xiàn)7中,利用 開源列數(shù)據(jù)庫平臺 C Sto re,詳細(xì)介紹了兩種物化方式 的實驗 過程。

38、另外，MonetDB/ X100這個比較有影響力的開源列數(shù) 據(jù)庫也運用了延時物化技術(shù)。3.3成組迭代要處理一系列記錄，行數(shù)據(jù)庫要對每個 記錄依次進(jìn)行迭 代，對于每一個記錄通過單個記錄的操作接口，從這些記錄中選取需要的屬性或者執(zhí)行函數(shù)的調(diào)用。這是一個成本很高的 操作。所以IBM的專家S. Padmanabhan提出，可以成組地調(diào) 用函數(shù)，這樣就可以節(jié)約很多資源。對于現(xiàn)代CPU而言,CPU在緩存中找到有用的數(shù)據(jù)被 稱為命中；當(dāng)緩存中沒 有CPU所需的數(shù)據(jù)時（未命中），CPU 才訪問內(nèi)存。所 以,CPU訪問內(nèi)存的頻率越低（也稱未命中 頻率）,查詢的效率也就越高。列式存儲具有高度的可壓縮 性。假設(shè)對一

39、列使用 行程編碼壓縮，就像本文3. 1節(jié)中提到 的一樣（值、起始位置、長度）,占10個字節(jié)。利用64字節(jié)的 高速緩存行，可以將6個壓縮的列值載入一個高速緩存行。 這樣,每次訪問內(nèi)存，讀取的壓縮列值 是6個,而這些壓縮的 列值對應(yīng)的實際數(shù)據(jù)就遠(yuǎn)遠(yuǎn)不止6個。此外，如果列被設(shè)定為固定寬度，這些值可以直接對應(yīng)為 一個數(shù)組。把數(shù)據(jù)當(dāng) 作一個數(shù)組來操作,可以使單個記錄處 理代價最小化。所以，列數(shù)據(jù)庫的存儲方式可以大大提高 CPU吞吐量。隨著CPU性能的不斷提高，運用成組迭代的 列數(shù)據(jù)庫在未來的表現(xiàn)將更加優(yōu)秀6。成組迭代的思想是針對行 數(shù)據(jù)庫提岀的，所以成組迭代 同樣也適用行 數(shù)據(jù)庫。在這 里也可以感覺到，

40、列數(shù)據(jù)庫作為 關(guān)系型數(shù)據(jù)庫，在許多方面是不 得不借鑒 行數(shù)據(jù)庫已 經(jīng)成熟 的技術(shù)。3. 4不可見連接這是Daniel J.Abadi3提出的一種專門針對列數(shù)據(jù)庫進(jìn) 行查詢效率優(yōu)化的技術(shù)。該方法將查詢所涉及的各個表的屬 性對于查詢條件的符合情況采用位向量的方式來標(biāo)定，之后 對這些位向量進(jìn)行邏輯與或運算，得到最終可用于標(biāo)定結(jié)果 的位向量。整個過程 沒有屬性或列之間直接的值連接操作, 這些直接的操作被位向量直接的邏輯與或運算替代，因此被 稱為 不可見連接。不可見連接的目的是 盡量避免原始數(shù)據(jù) 傳輸、處理和緩存的開 銷,而充分利用按列存儲的便利，采用 位向量的方式來標(biāo)定和連接符合條件的中間結(jié)果。該方法

41、適 用于星狀結(jié)構(gòu)的數(shù)據(jù)庫。3. 4. 1不可見連接形式化描述假設(shè)有如下查詢：select valu ei, valu e2, ?, value n , AGG 1 , AGG 2, ? , AGG qfrom tablei , tab©, ? , table mwh erecondition 1 OP 1 conditon 2 OP2 ? OPt condition pL IST1 , LIST 2,? , LIST lValu e(1# i# N):查詢直接要得到的值A(chǔ)GGi( 1 # i # Q):對于查詢的值進(jìn)行聚集計算的結(jié)果table i(1# i # M):查詢所涉及到的表

42、condition i( 1# i # P):查詢的選擇條件0Pi(1# i# T):邏輯運算(與或非)L ISTi (1# i# L):對結(jié)果進(jìn)行排序處理指令算法描述如下：count= 0; / / count用于記錄選擇性查詢條件的個數(shù)For( 1 # i # P )Beginif( condition i是選擇性條件而非連接條件)th enBegin 對于condition i,生成標(biāo)定符合條件的位向量hi；cou nt= count+ 1;end;End;初始化目標(biāo)位向量H;h : = m;For(1< i # P)if( condition i是選擇性條件而非連接條件)th e

43、n H = H 0P i- 1 hi ;初始化中間物化結(jié)果空間0;/0有(P count)個存儲空間將被物化中間結(jié)果填充For( 1 # i # P)Beginif( condition i是連接條件而非選擇性條件)th en 0i = (condition i對應(yīng)的事實表的列 )AND HEnd;初始化最終連接結(jié)果空間為R/ R有(P coun t)個存儲空間將被最終連接結(jié)果空間填充For( 1 # i # P)Beginif( 0i存儲的是中間物化結(jié)果而非初始化值)th enBegincondition i對應(yīng)的維表與0i在對應(yīng)列作連接；Ri=選取連接結(jié) 果中與 Value i(1# i#

44、 N )或者AGG i(1#i # Q)關(guān)聯(lián)的列；End;End;初始化最終查詢結(jié)果空間為S /S有(N + Q)個存儲空間For( 1 # i # (N+ Q)Beginif( i # N) then Si= Rielse S = AGGi - n ( R i);End;輸出結(jié)果時按照LI ST1, L IST2, ? , 口 STl的要求依次排 序。3. 4. 2 不可見連接測試實例以下面的查詢?yōu)槔簊elect c_nation, s_nation, d_year, sum( lo. revenu e) as revenu e from customer AS c, lineorder

45、AS lo, supplier AS s, dwdate AS d where lo_cu stkey= c_custk ey and lo_suppk ey= s_suppkey and lo_orderdate= d_datekey and c_region = %ASIA ?and s_region = %ASIA ?and d_year & 1992 and d_year # 1997grou p by c_nation, s_nation, d_year order by d_year asc, revenu e desc;首先我們按照這個順序來執(zhí)行w here子句，line

46、order, customer( reg ion = Asia), supplier( region = Asia), date( y ear betw een 1992 and 1997)。從表3中,根據(jù)判定條件region= Asia,得到custkey為1 和3的記錄符合條件。表3 客戶表cust keyregi onn ati on1A SIACHINA2EUROPEFRA NCE3A SIAINDIA在表4中,根據(jù)判定 條件region= Asia,得到suppkey為1的記錄符合條件。表4供應(yīng)商表suppkeyregi onn ati on1A SIARUSSIA2EUROPESP

47、AIN在表5中，根 據(jù)判定 條件(d _y ear& 1992 and d_y ear#1997),3條記錄都符合條件。表5日期表dateidyear010119971997010129971997010139971997之后在lineorder表(fact table)(見表6)中根據(jù)上述 判定 條件進(jìn)行符合 條件的連接。表6 事實表orderkeycustkeysuppkeyo rderdat erevenue131010119974325623201011997333333210102199712121411010219972323352201021997454566120103

48、1997432517320103199734235如圖11所示,根據(jù)對表3-表5的選擇判定,將表6中 custkey, suppkey, orderdate這3個用于 連接的列 分別用 位向 量進(jìn)行選擇標(biāo)定，之后將這3個列對應(yīng)的向 量進(jìn)行邏 輯與運 算,得到一個用于傳遞實際選擇條件和連接結(jié)果的列向量，如圖12所示。OIQtJW?0IQI1W701.0217QIQ21 叨0L021W70103170IQ31M7nri£en:luL£!>.<i dA；:duk-'.小圖11不可見連接第一步通過不可見連接，就可以得到所要查詢的數(shù)據(jù)revenue(43256+

49、23233), c_nation 為(china, india) , s_nation 為(Russia, Russia), d_year 為(1997,1997),如圖 13 所示。j1NDIIARUSSCASPAINRUSSIA(fiupplirr I'nliJniwiw1997DI99i1】但】9刑(Dntc Tabk)4. 1 TPCH官方數(shù)據(jù)庫測試4. 1. 1 TPC測試簡介T PC（ Transaction Processing Performance Council,事 務(wù) 處理性能委員 劊是由數(shù)10家會員公司創(chuàng)建的非盈利組織， 總部設(shè)在美國。該組織對全世界開放，但迄今

50、為止絕大多數(shù) 會員都是美、日、西歐的大公司。TPC的成員主要是計算機(jī) 軟硬件廠家，而非計算機(jī)用戶。TPC的功能是制定商務(wù)應(yīng)用 基準(zhǔn)程序（Benchmark）的標(biāo)準(zhǔn)規(guī)范、性能和價格度量,并管理 測試結(jié)果的發(fā)布。4. 1.2 TPCH測試簡介T PC H（商業(yè)智能計算 測試）是TPC的重要測試標(biāo)準(zhǔn)之 一,主要用來模擬真實 商業(yè)的應(yīng)用環(huán)境。與科學(xué)計算測試不 同，商務(wù)智能計算測試是對現(xiàn)實中商用計算需求的全面模擬,包括模擬真實商業(yè)交易數(shù)據(jù)庫的動態(tài)查詢，作為決策支持與 數(shù)據(jù)庫應(yīng)用系統(tǒng)的參考。這種商業(yè)測試可以全方位評測系統(tǒng)的整體商業(yè)計算綜合 能力，對廠商的要求更高，同時具有普遍的商業(yè)實用意義，目 前在銀行信

51、貸分析和信用卡分析、電信運營分析、稅收分析、 煙草行業(yè)決策分析中都有廣泛的應(yīng)用。4. 1.3 TPCH測試分析圖14是根據(jù)TPC官方網(wǎng)站上的TPC H測試數(shù)據(jù)分析 完成的柱狀圖4。QphH為縱坐標(biāo)，它的含義是每小時完成 的查詢數(shù)，這個值越高，說明查詢執(zhí)行的性能越高。圖14亦 是TPCH官方測試100G數(shù)據(jù)級的前10名對比柱狀圖。 EXAM.-» IWAnd 9n»Ti SQ1. Simh Sufcrnd l SQ1. imx SStiS ZsTOM g.timvr百 SQLSava3KS3 Kmdi SOL3014；圖13不可見連接第三步3. 4. 3 小結(jié)不可見連接是列數(shù)

52、據(jù)庫專家Daniel J. Abadi在2008年 提岀的技術(shù)。該技術(shù)還非常 年輕，還沒有 運用到真正的列數(shù) 據(jù)庫系統(tǒng)上，所以需要通過實踐來驗證它存在的價值。數(shù)據(jù) 庫連接無疑是數(shù)據(jù)庫技術(shù)中非常重要的組成部分,所以針對 列數(shù)據(jù)庫連接方面的研究將成為列數(shù)據(jù)庫領(lǐng)域工作者未來工 作的重點之一。3.5 總結(jié)綜上所述,支持列數(shù)據(jù)庫的4大關(guān)鍵技術(shù)分別是壓 縮、延 時物化、成組迭代和不可見連接?，F(xiàn)如今，已經(jīng)有很多列數(shù)據(jù) 庫成功地實施并運用了這些技術(shù)，將來圍繞著這4個方面,會有許多新技術(shù)不斷岀現(xiàn)，以促進(jìn)列數(shù)據(jù)庫技術(shù)的發(fā)展。4列數(shù)據(jù)庫性能測試列數(shù)據(jù)庫的發(fā)展勢頭非 常迅猛，大有在數(shù)據(jù)倉庫領(lǐng)域取 代傳統(tǒng)行數(shù)據(jù)庫的趨勢

53、。其兩大主要技術(shù)優(yōu)勢 ？?？有效的壓 縮和高效的 查詢性能，使其成為支撐大規(guī)模數(shù)據(jù)倉 庫和提供 高性能數(shù)據(jù)分析的良好平臺。作為衡量兩大技術(shù)優(yōu)勢之 一?高效查詢的性能測試 標(biāo)準(zhǔn),TPCH官方測試目前被廣 泛認(rèn)可，其測試結(jié)果無論是在 產(chǎn)品選型還是實驗研 究方面都 極具參考價值。圖14 TPCH對比圖從圖14中可以看出，在這一數(shù)據(jù)級中,表現(xiàn)最好的兩個 數(shù)據(jù)庫是 EXASQL EXA Solution2. 0 和 ParAccelAnalytic Da tabase,它們都是列數(shù)據(jù)庫。上述結(jié)果說明，列數(shù)據(jù)庫在100G 這個數(shù)據(jù)級里 表現(xiàn)出色（注：圖14中,相同的數(shù)據(jù)庫若采用的 操作系統(tǒng)不同，其測試結(jié)果

54、也就不一樣，詳細(xì)的操作系統(tǒng)及硬 件配置參考文獻(xiàn)4）。4. 2 總結(jié)在TPCH官方測試中，列數(shù)據(jù)庫已經(jīng)在 查詢性能上展示 了突岀的表現(xiàn)，這進(jìn)一步印證了列數(shù)據(jù)庫是支撐數(shù)據(jù)倉庫、數(shù)據(jù)分析以及商務(wù)智能的優(yōu)良平臺。列數(shù)據(jù)庫的基于列存儲的 方式和在此基礎(chǔ)上的幾大關(guān)鍵技術(shù)決定了其適用領(lǐng)域和應(yīng)用 的優(yōu)勢。結(jié)束語 在經(jīng)過一系列調(diào) 研與學(xué)習(xí)之后，我們實驗室小 組開發(fā)了 一個列數(shù)據(jù)庫H UABA SE,它雖然只是個內(nèi)核，但 是已經(jīng)在內(nèi)部 測試中表現(xiàn) 岀了良好 的性能，其效率已 經(jīng)大大 超過了進(jìn)行對 比的幾個行數(shù)據(jù)庫。本文介紹了列數(shù)據(jù)庫概念、幾個商業(yè)列 數(shù)據(jù)庫和開源列 數(shù)據(jù)庫以及列 數(shù)據(jù)庫的優(yōu) 勢，著重介紹了列數(shù)據(jù)庫

55、的 幾大關(guān) 鍵技術(shù)特點；引用了 TPCH官方測試結(jié)果，最后進(jìn)行了總結(jié)。（下轉(zhuǎn)第17頁）Q 今94MI* fliitts Academic Journal kJucti-anicI iOMse. All孕屮 三.hft護(hù)Vwvrh 初tYdQ 今94MI* fliitts Academic Journal kJucti-anicI iOMse. All孕屮 三.hft護(hù)Vwvrh 初tYdDynamic Grid Environment C ( Proceedings of DEXA Work shop. 2005: 356 36029 Cai M , Frank M, Chen J,et al. M AAN: A Multi Attrib ute Ad dressable Netw ork for Grid Inform ation Services C ( Procee din gs of 4th International Works hop on Grid Compu ti