列存儲系統(tǒng)的若干關鍵技術研究.pdf

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

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

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

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

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

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

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

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