數(shù)據(jù)倉(cāng)庫(kù)中基于位圖索引查詢優(yōu)化的研究.pdf

1、索引是數(shù)據(jù)倉(cāng)庫(kù)查詢優(yōu)化的重要技術(shù)，主要包括樹(shù)形索引和位圖索引。其中位圖索引因?yàn)槠浣Y(jié)構(gòu)簡(jiǎn)單，并且硬件支持二進(jìn)制位運(yùn)算效率很高，被廣泛應(yīng)用在數(shù)據(jù)倉(cāng)庫(kù)中。在屬性的基數(shù)（該屬性可能的取值數(shù)）低的情況下，位圖索引已經(jīng)被證明是十分高效的。但在基數(shù)比較高的情況下，位圖索引需要占用大量的存儲(chǔ)空間。位圖索引往往被認(rèn)為只有在屬性基數(shù)較低情況下才適合使用。
　　 為了克服這個(gè)難題，現(xiàn)今研究者們已經(jīng)提出了很多方法，包括編碼，壓縮，bin。其中bin位圖

2、索引可以有效的降低高基數(shù)時(shí)位圖占用的空間。這種索引不像簡(jiǎn)單位圖索引那樣建立在每一個(gè)不同的屬性值上，而是建立在一個(gè)個(gè)的屬性范圍上。但它同時(shí)也帶來(lái)了另一個(gè)難題，就是候選檢查。候選檢查往往占用大部分的查詢時(shí)間。
　　 采用傳統(tǒng)多維查詢算法，對(duì)各屬性進(jìn)行查詢的順序不同，可能對(duì)總候選檢查數(shù)目產(chǎn)生重大影響。本文給出兩個(gè)定理，證明了影響排序的兩個(gè)因素。并據(jù)此提出一種基于權(quán)值排序算法，通過(guò)在執(zhí)行查詢前對(duì)各屬性查詢進(jìn)行排序，使總的候選檢查的數(shù)目盡

3、可能少。理論分析和實(shí)驗(yàn)表明，此排序算法可以明顯減少總候選檢查數(shù)目，優(yōu)化了傳統(tǒng)多維查詢算法。
　　 但是排序的傳統(tǒng)多維查詢算法并不能減少查詢的第一維所需的候選檢查數(shù)目，實(shí)驗(yàn)表明第一維所需的候選檢查數(shù)目往往占總候選檢查數(shù)目的大部。通過(guò)預(yù)掃描（推遲候選檢查）可以有效解決這個(gè)問(wèn)題，但是進(jìn)行預(yù)掃描需要額外的花費(fèi)，即要掃描更多的索引，這個(gè)代價(jià)是不能忽視的?？紤]到預(yù)掃描一定維數(shù)后，繼續(xù)預(yù)掃描將不會(huì)明顯的減少總的候選檢查數(shù)目，本文在排序的基礎(chǔ)上