位圖索引在數(shù)據(jù)倉庫低基數(shù)值列中的研究.pdf

1、在數(shù)據(jù)倉庫和商業(yè)智能(BI)解決方案中加快查詢處理是一個(gè)急需解決的問題。使用匯總表或索引等機(jī)制可以有效提高查詢速度，其中預(yù)定義查詢的匯總表已具有較好的性能，但需要預(yù)先花費(fèi)額外的執(zhí)行時(shí)間，而索引是一個(gè)更加高性能的且無需額外硬件的解決方案，但其中面臨的挑戰(zhàn)是如何找到一個(gè)合適各種數(shù)據(jù)集且都保持較高性能的索引類型。
　　低基數(shù)數(shù)據(jù)在數(shù)據(jù)倉庫中應(yīng)用廣泛，基數(shù)是一個(gè)數(shù)據(jù)集的列中值的個(gè)數(shù)。一般有大量重復(fù)值的列稱作為低基數(shù)列，例如性別列，一般只有

2、兩個(gè)值:男性和女性，當(dāng)然可以用其它的2個(gè)不同的符號來表示。
　　B樹是存儲排序數(shù)據(jù)并允許以O(shè)(logn)的運(yùn)行時(shí)間進(jìn)行查找的樹形數(shù)據(jù)結(jié)構(gòu)，但B樹索引應(yīng)用于低基數(shù)值列時(shí)是一個(gè)非常低效的索引方法，在進(jìn)行即席查詢且數(shù)據(jù)量大時(shí)需要非常多I/O操作。因此一些關(guān)系型數(shù)據(jù)庫管理系統(tǒng)采用新的索引技術(shù)，如位圖索引，用以加快查詢處理。
　　位圖索引有一個(gè)用于快速數(shù)據(jù)檢索的特定結(jié)構(gòu)，主要是利用二進(jìn)制數(shù)（0或1）的字符串，以指示一個(gè)表中被索引的列是

3、否為一個(gè)特定的值，也就是說，如果在一個(gè)索引列中一個(gè)特定的值存在，位圖索引設(shè)置為‘1'，否則為‘0'。與其它的索引技術(shù)相比，位圖索引能大幅減少空間的使用，對于復(fù)雜邏輯的選擇操作，可通過執(zhí)行位的運(yùn)算“AND”，“OR”，“NOT”等來快速地完成。位圖索引的應(yīng)用非常廣泛，主要用于數(shù)據(jù)倉庫系統(tǒng)和大型科學(xué)數(shù)據(jù)庫。通過執(zhí)行跨列位圖間的快速邏輯運(yùn)算，位圖索引提供了一個(gè)更快的查詢解決，而且能被被當(dāng)代硬件廣泛支持。
　　很多商業(yè)的數(shù)據(jù)庫系統(tǒng)都采用位

4、圖索引，如Oracle，從1995年開始就提供了位圖索引，其它主要系統(tǒng)如DB2和Microsoft SQL Server沒有采用。Microsoft SQL Server可能通過哈希連接生成位圖，但不是通用的索引。DB2已經(jīng)采用編碼矢量索引，但是這基本上是一個(gè)編碼投影索引，而不是一個(gè)位圖索引。
　　本論文的目的是通過實(shí)驗(yàn)的方式來證明在數(shù)據(jù)倉庫中位圖索引比B樹索引更有效，尤其是對于低基數(shù)值列。在Oracle環(huán)境中，B樹索引一般為默認(rèn)

5、的索引方式。我們通過3個(gè)典型的實(shí)驗(yàn)來測試在兩個(gè)索引方式下復(fù)雜查詢的執(zhí)行時(shí)間，在每一個(gè)實(shí)驗(yàn)中我們分別測試3個(gè)條件、2個(gè)條件與1個(gè)條件的查詢，并且測試4個(gè)不同的數(shù)據(jù)集，分別有100萬條、80萬條、60萬條、30萬條記錄。
　　我們首先在Oracle環(huán)境下設(shè)計(jì)并實(shí)現(xiàn)圖形用戶界面，采用Oracle Developer6i工具套件，這個(gè)套件由許多用于開發(fā)和編程項(xiàng)目的軟件組成，這些軟件以可視化的方式來處理數(shù)據(jù)倉庫并操縱數(shù)據(jù)庫。這意味著，使用可

6、視化編程組件，如按鈕、列表、標(biāo)簽、文本框、鼠標(biāo)移動等等，無需復(fù)雜編程即可編寫查詢并以圖形界面的方式呈現(xiàn)結(jié)果。我們使用Oracle10g的數(shù)據(jù)庫來創(chuàng)建表和索引。
　　我們設(shè)計(jì)與實(shí)現(xiàn)的界面有2個(gè)主要部分即搜索使用位圖索引、搜索使用B樹索引，這2個(gè)部分具有相同的查詢語句與數(shù)據(jù)集。我們在查詢項(xiàng)目中的選擇的參數(shù)選項(xiàng)有地區(qū)、學(xué)院、性別和年齡。當(dāng)要執(zhí)行查詢時(shí)，我們首先確定搜索選項(xiàng)，即相當(dāng)于在SQL語中復(fù)雜的“Where子句”條件，每個(gè)選項(xiàng)所代表

7、的組合列表是通過鼠標(biāo)左鍵點(diǎn)擊下拉列表選擇值進(jìn)行組合。在每次實(shí)驗(yàn)中，我們對位圖索引與B樹索引的查詢響應(yīng)時(shí)間進(jìn)行詳細(xì)記錄與比對，從而揭示在不同數(shù)據(jù)集與不同列值情形下兩個(gè)索引方法的性能差別。
　　實(shí)驗(yàn)主要包含以下三個(gè)方案:
　　方案一:搜索表使用三個(gè)條件，其中有兩個(gè)AND運(yùn)算操作。搜索上分別做4組記錄，30萬條、60萬條、80萬條與100萬條記錄。
　　方案二:搜索表使用兩個(gè)條件，即一個(gè)AND運(yùn)算操作，搜索上分別進(jìn)行4組記錄

8、，30萬條、60萬條、80萬條與100萬條記錄。
　　方案三:搜索表使用一個(gè)條件，搜索記錄4組，分別30萬條、60萬條、80萬條與100萬條記錄。
　　我們用許多不同的查詢參數(shù)來測試不同SQL查詢以獲得更多的結(jié)果進(jìn)行較為全面的分析。從三個(gè)實(shí)驗(yàn)方案進(jìn)行觀察發(fā)現(xiàn)，位圖索引在對于低基數(shù)值列如“Y”或“N”、“男”或“女”等比B樹索引速度優(yōu)勢明顯。但是位圖索引只是方便靜態(tài)表（無更新）的查詢，如果查詢的表不是只讀的，則B樹索引是一種相

9、對有效的選擇。位圖索引對于決策支持系統(tǒng)、數(shù)據(jù)倉庫、OLAP等數(shù)據(jù)相對靜態(tài)的情形非常有效，而B樹索引則對于OLTP環(huán)境更有效。已有相關(guān)研究將位圖索引和B樹索引的時(shí)間和空間復(fù)雜性計(jì)算規(guī)則進(jìn)行了分析，數(shù)學(xué)計(jì)算表明位圖索引的時(shí)間和空間復(fù)雜性比B樹索引低，尤其是對于低基數(shù)值列。
　　對于大型數(shù)據(jù)倉庫來說，位圖索引被認(rèn)為是在當(dāng)前和未來很有發(fā)展前途的索引，因此我們期待提出更有效的位圖索引方法。我們的目標(biāo)是通過采取新的方法來提高位圖索引的性能，這

10、個(gè)方法的主要思想是將基本的位圖索引算法和基于值域編碼算法進(jìn)行有效結(jié)合，考慮不同的基數(shù)值列類型。
　　在基于值域編碼算法（是基本的位圖索引算法的改進(jìn)）中，位圖矢量用于表示一定范圍內(nèi)的值，而不是一個(gè)單獨(dú)的值。查詢處理器讀取該位圖矢量中的對象，并刪除那些超出目標(biāo)范圍的對象。此方法的主要優(yōu)勢是提高了位圖索引性能的效率，通過減少位圖矢量所需的掃描時(shí)間，特別是當(dāng)我們處理一定范圍內(nèi)值的時(shí)候，通過將值域分割成更小的域用以顯著減少存儲開銷?；镜奈?/p>

11、圖索引的想法是使用一個(gè)字符串的比特0或1，以指示是否一個(gè)元組的屬性值為某一個(gè)特定值，其主要優(yōu)勢是邏輯運(yùn)算能很好的被硬件支持，操作的執(zhí)行都相當(dāng)快。而且，用于構(gòu)造位圖索引的成本及其根據(jù)位圖進(jìn)行查找的成本都非常低。然而，簡單的位圖索引只對具有低數(shù)量不同值的屬性才有效，因?yàn)?，如果索引的屬性的基?shù)值低，則需要一個(gè)較小的數(shù)字位圖，索引結(jié)構(gòu)的空間復(fù)雜度低，而對于高基數(shù)值屬性，則需要一個(gè)很大的數(shù)字位圖，索引結(jié)構(gòu)的空間復(fù)雜度高、時(shí)間性能也低，這成為基本位

12、置索引算法的明顯缺陷。
　　我們通過觀察發(fā)現(xiàn)，基于值域編碼算法由于可以將某一范圍數(shù)值歸類到某一個(gè)值，對于高基數(shù)值屬性，可以處理成相對規(guī)模較小的數(shù)字位圖，從而可以克服基本索引算法的缺陷。因此我們提出把基于值域編碼算法和基本位圖索引算法進(jìn)行有效結(jié)合，通過引進(jìn)相異值比率參數(shù)并對列進(jìn)行自動計(jì)算，在相異值比率較高即不同的值多稱之為高基數(shù)值屬性時(shí)采用基于值域編碼算法，當(dāng)相異值比率低即稱之為低基數(shù)值屬性時(shí)采用基本位置索引，如果相異值比率超過一定

13、值時(shí)，則采用B樹索引。
　　通過引入數(shù)學(xué)方程式并使用二項(xiàng)式概率分布規(guī)則，我們對提出的混合索引方法的時(shí)間復(fù)雜性進(jìn)行了分析，結(jié)果表明新方法的時(shí)間復(fù)雜性將低于單獨(dú)使用基本位圖算法，在最壞的情況下將和基于值域編碼算法的時(shí)間復(fù)雜度相同。
　　本論文包含五個(gè)章節(jié)，第一章敘述位圖索引的引言和相關(guān)工作。在第二章中，我們提出了B樹索引和位圖索引的概述和一些相關(guān)的索引技術(shù)及各個(gè)索引的優(yōu)勢和劣勢。在第三章中，我們闡述了oracle develop