列存儲(chǔ)系統(tǒng)的若干關(guān)鍵技術(shù)研究.pdf

1、當(dāng)今，許多企事業(yè)單位的高管人員，迫切需要高性能的分析型數(shù)據(jù)庫(kù)管理系統(tǒng)，用于分析大數(shù)據(jù)，輔助決策。列存儲(chǔ)技術(shù)在處理大數(shù)據(jù)方面，顯著優(yōu)于行存儲(chǔ)技術(shù)，所以吸引了許多學(xué)者的研究。列存儲(chǔ)技術(shù)的研究取得了一些成果，但是關(guān)于列存儲(chǔ)系統(tǒng)的存儲(chǔ)優(yōu)化、查詢優(yōu)化和查詢執(zhí)行等關(guān)鍵技術(shù)還有待進(jìn)一步研究。
　　 在列存儲(chǔ)系統(tǒng)中，按列存儲(chǔ)數(shù)據(jù)，使得在查詢處理時(shí)能夠只讀取查詢所需要的列，避免讀入無(wú)關(guān)的列。按列存儲(chǔ)的數(shù)據(jù)具有很好的可壓縮性，在查詢處理過(guò)程中可以直

2、接對(duì)壓縮數(shù)據(jù)進(jìn)行處理。這兩點(diǎn)使得列存儲(chǔ)系統(tǒng)在查詢處理過(guò)程中的數(shù)據(jù)I/0效率比行存儲(chǔ)高得多，有利于提高查詢處理的速度。另一方面，對(duì)按列存儲(chǔ)的數(shù)據(jù)進(jìn)行查詢處理時(shí)，需要將分散存儲(chǔ)在不同位置的多列數(shù)據(jù)進(jìn)行元組重構(gòu)。元組重構(gòu)形成了列存儲(chǔ)系統(tǒng)中的一個(gè)重要性能瓶頸。
　　 本文以國(guó)家工信部核高基重大專項(xiàng)課題“數(shù)據(jù)倉(cāng)庫(kù)專用DBMS原型系統(tǒng)研制”(2010ZX01042-001-003-04)和國(guó)家自然科學(xué)基金項(xiàng)目“數(shù)據(jù)倉(cāng)庫(kù)中行列混合存儲(chǔ)引擎的優(yōu)

3、化模型”(61070031)為依托，以提高列存儲(chǔ)系統(tǒng)的查詢性能為目標(biāo)，對(duì)影響列存儲(chǔ)系統(tǒng)性能的一些關(guān)鍵技術(shù)進(jìn)行了深入研究。本文主要做了以下幾個(gè)方面的工作:
　　 (1)研究列存儲(chǔ)系統(tǒng)中數(shù)據(jù)存儲(chǔ)布局對(duì)元組重構(gòu)性能的影響后，提出了一個(gè)以列存儲(chǔ)為基礎(chǔ)，結(jié)合組合多列的存儲(chǔ)模型。該模型對(duì)歷史查詢使用數(shù)據(jù)的方式進(jìn)行分析，分析一個(gè)邏輯表中的哪些列經(jīng)常一起被查詢輸出，將這些列進(jìn)行物化，供后續(xù)查詢使用。對(duì)需要物化的多列，首先形成邏輯上的一個(gè)投影并進(jìn)

4、行水平劃分，然后對(duì)劃分的每一塊，在塊內(nèi)按列組織并壓縮后存儲(chǔ)。這樣能充分利用列存儲(chǔ)的優(yōu)勢(shì)，同時(shí)也能減少元組重構(gòu)的開銷，為后續(xù)查詢提供了最優(yōu)存儲(chǔ)。
　　 (2)傳統(tǒng)B+樹索引是稀疏的，對(duì)其搜索的路徑較長(zhǎng)，對(duì)其進(jìn)行插入和搜索的效率較低，不適合分析型應(yīng)用。對(duì)此，本文提出了一種精簡(jiǎn)的、適合于列存儲(chǔ)的B+樹結(jié)構(gòu)—RB+樹。RB+樹幾乎是一棵滿的平衡二叉樹，一頁(yè)能容納更多的索引項(xiàng)，因而能用較矮的RB+樹存儲(chǔ)大量的索引項(xiàng)。按這種結(jié)構(gòu)樹組織數(shù)據(jù)，

5、搜索數(shù)據(jù)的路徑短，搜索效率高。關(guān)于RB+樹索引的創(chuàng)建和維護(hù)，分別對(duì)行號(hào)索引和列值索引提出了自底向上的高效創(chuàng)建方法和維護(hù)方法。
　　 (3)研究了數(shù)據(jù)庫(kù)中的數(shù)據(jù)壓縮技術(shù)，包括輕量級(jí)的壓縮方法、壓縮粒度的選擇和壓縮方法的選擇策略。特別對(duì)位圖壓縮技術(shù)進(jìn)行了深入的研究，提出了一種富擴(kuò)展劃分位圖索引和一種自適應(yīng)的劃分字對(duì)齊壓縮方法（APWAH）。富擴(kuò)展劃分位圖包含了一些統(tǒng)計(jì)信息，為直接使用劃分位圖進(jìn)行聚集操作提供了方便。APWAH能根據(jù)位

6、向量中0-1分布情況，自適應(yīng)地選擇最合適的0-填充段長(zhǎng)和1-填充段長(zhǎng)，提高了壓縮效率和查詢處理效率。同時(shí)研究了區(qū)級(jí)壓縮，區(qū)級(jí)壓縮同時(shí)具有壓縮率高和壓縮管理方便的優(yōu)點(diǎn)。本文提出根據(jù)數(shù)據(jù)的分布情況，自適應(yīng)地選擇區(qū)的大小。一個(gè)區(qū)由若干塊構(gòu)成，每區(qū)的塊數(shù)不一定相同。這樣可以根據(jù)相鄰數(shù)據(jù)塊之間的相似性，靈活地進(jìn)行區(qū)劃分，不受區(qū)大小的限制，保證區(qū)內(nèi)數(shù)據(jù)分布特征相似性強(qiáng)，區(qū)之間數(shù)據(jù)分布特征相似性弱，以便對(duì)每個(gè)區(qū)選擇更合適的壓縮方法。關(guān)于壓縮方法的選擇

7、，建立了一個(gè)數(shù)據(jù)分布特征模型，并根據(jù)提出的模型建立了選擇壓縮方法的決策方案。
　　 (4)研究緩沖區(qū)管理技術(shù)，提出了一種適應(yīng)于列存儲(chǔ)系統(tǒng)的三級(jí)緩沖區(qū)管理方案。在全局級(jí)，使用兩條鏈分別管理系統(tǒng)的自由緩沖區(qū)和所有查詢使用的緩沖區(qū)，對(duì)使用的緩沖區(qū)按綜合自適應(yīng)置換策略進(jìn)行置換。一個(gè)緩沖區(qū)是否可被置換，不僅考慮正在執(zhí)行的查詢，同時(shí)還考慮了一定量的后續(xù)查詢。在查詢級(jí)，每個(gè)執(zhí)行的查詢都用一條主鏈管理它使用的緩沖區(qū)，一個(gè)查詢處理中每出現(xiàn)一個(gè)并發(fā)

8、操作階段，都從主鏈中產(chǎn)生一條相應(yīng)的分支鏈來(lái)管理并發(fā)操作階段使用的緩沖區(qū)。在操作階段級(jí)，對(duì)每個(gè)操作階段設(shè)計(jì)了一種靈活且自適應(yīng)的緩沖區(qū)分配策略(MG-x-y-z)和與它的訪問(wèn)模式相適應(yīng)的置換策略。提出的三級(jí)緩沖區(qū)管理方案充分考慮了分析型工作負(fù)載的特點(diǎn)、數(shù)據(jù)訪問(wèn)模式特點(diǎn)和可用的緩沖區(qū)情況，也考慮了數(shù)據(jù)預(yù)取。
　　 (5)研究列存儲(chǔ)系統(tǒng)中的物化技術(shù)后，針對(duì)現(xiàn)有物化技術(shù)的不足，提出了基于帶值路徑的物化技術(shù)(PVM)。PVM在物理執(zhí)行樹中增