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

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

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

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