??

? ? ? ? 這是一篇讀書筆記，因?qū)?bitmap 技術(shù)感興趣，參考論文和官網(wǎng)資料學(xué)習(xí)和整理。

? ? ? ?本文討論用于在數(shù)據(jù)倉庫應(yīng)用程序中進(jìn)行高效查詢處理的各種位圖索引技術(shù)。我們回顧了現(xiàn)有的文獻(xiàn)并將該技術(shù)分為三類，即位圖編碼、壓縮和分箱。我們引入了一種高效的位圖壓縮算法，并在來自實(shí)際應(yīng)用的大型數(shù)據(jù)集上檢查壓縮位圖索引的空間和時(shí)間復(fù)雜度。根據(jù)傳統(tǒng)觀點(diǎn)，位圖索引僅對低基數(shù)屬性有效。然而，我們展示了壓縮位圖索引對于高基數(shù)屬性也是有效的。時(shí)序結(jié)果表明，位圖索引明顯優(yōu)于投影索引，投影索引通常被認(rèn)為是多維查詢最有效的訪問方法。最后，我們回顧了目前常用的商業(yè)數(shù)據(jù)庫系統(tǒng)支持的位圖索引技術(shù)，并討論了未來研究和開發(fā)的開放問題。

介紹

? ? ? ?查詢大型數(shù)據(jù)集以定位某些選定的記錄是數(shù)據(jù)倉庫應(yīng)用程序中的常見任務(wù)。由于數(shù)據(jù)復(fù)雜性，高效地實(shí)現(xiàn)查詢通常很困難。一個(gè)典型的搜索場景是統(tǒng)計(jì)生產(chǎn)者P在時(shí)間間隔T內(nèi)賣出的汽車數(shù)量。這種過程通常使用B-tree索引來加速。傳統(tǒng)的關(guān)系型數(shù)據(jù)庫大多數(shù)都支持B-tree索引。然而，隨著數(shù)據(jù)屬性數(shù)量的增加，可能的索引組合的數(shù)量也隨著增加。多場景下高效查詢變得艱難。這體現(xiàn)在復(fù)雜業(yè)務(wù)中，對于多個(gè)屬性值，是否為空、等值篩選、范圍篩選、排序等一些列的條件組合。在文獻(xiàn)中，這種困境通常被稱為 curse of dimensionality。

? ? ? ? 本文討論一種索引技術(shù)，有望打破數(shù)據(jù)倉庫應(yīng)用程序的維度詛咒，即位圖索引技術(shù)。位圖索引的一個(gè)非常顯著的特點(diǎn)是它對查詢的主要解決方案是位圖。打破維度詛咒的一種方法是為數(shù)據(jù)集的每個(gè)屬性建立一個(gè)位圖索引。為了解決涉及多個(gè)屬性條件的查詢，首先使用相應(yīng)的位圖索引解析每個(gè)屬性的條件，并將每個(gè)條件的解決方案作為位圖獲得。然后我們通過組合這些位圖來獲得整個(gè)查詢的答案。由于計(jì)算機(jī)硬件很好地支持對位圖的操作，因此位圖可以輕松有效地組合?？傮w而言，我們希望總查詢響應(yīng)時(shí)間與查詢中涉及的屬性數(shù)量呈線性關(guān)系，而不是與數(shù)據(jù)集的維度（屬性）數(shù)量呈指數(shù)關(guān)系，從而打破維度詛咒。

背景

? ? ? ? 幾乎每個(gè)數(shù)據(jù)庫產(chǎn)品都有B-tree，這種類型的基于樹的索引方法具有幾乎相同的搜索和更新索引的操作復(fù)雜性，這對于OLTP場景十分有效。然而對于OLAP場景來說，查詢操作執(zhí)行頻率比更新操作頻率高得多，這種情況下B-tree已不再是最優(yōu)解決方案。本文將證明，位圖索引在 OLAP 操作的搜索和更新之間具有最佳平衡。

? ? ? ? 通常，在 OLAP 場景下，每個(gè)查詢都涉及許多屬性，不同查詢通常涉及不同的屬性或者不同屬性的組合。使用傳統(tǒng)的多維索引方法，幾乎每個(gè)屬性組合都需要一個(gè)單獨(dú)的索引。這種方案索引的數(shù)量隨著數(shù)據(jù)集中屬性的數(shù)量呈指數(shù)增長。在文獻(xiàn)中，這有時(shí)被稱為維度災(zāi)難。對于具有中等維度的數(shù)據(jù)集，解決此問題的常用方法是使用一種多維索引方法，例如 R-Trees 或 kd-trees。這些方法有兩個(gè)顯著的缺點(diǎn)。首先，它們僅對維數(shù)適中的數(shù)據(jù)集有效，例如，< 15。其次，它們僅對涉及所有索引屬性的查詢有效。但是，在許多應(yīng)用程序中，查詢中只使用了一些屬性。在這些情況下，傳統(tǒng)的索引方法通常效率不高。對于范圍查詢，大多數(shù)已知的索引方法的性能不如投影索引，這可以看作是組織基礎(chǔ)的一種方式。另一方面，位圖索引在這些查詢上具有出色的性能特征。如理論分析和時(shí)序測量所示，壓縮位圖索引對于一維范圍查詢是非常高效的。由于可以有效地組合對一維范圍查詢的答案以應(yīng)對任意多維范圍查詢，因此壓縮位圖索引對于任何范圍查詢都是有效的。在計(jì)算復(fù)雜度方面，一種類型的壓縮位圖索引被證明在理論上對于一維范圍查詢是最優(yōu)的。理論上證明最優(yōu)的原因是查詢響應(yīng)時(shí)間是命中數(shù)的線性函數(shù)，即結(jié)果集的大小。有許多索引方法，包括 B*-tree 和 B+-tree，理論上對于一維范圍查詢是最優(yōu)的，但它們中的大多數(shù)不能用于有效地回答任意多維范圍查詢.

? ? ? ?各種形式的位圖索引在關(guān)系數(shù)據(jù)庫系統(tǒng)或數(shù)據(jù)倉庫系統(tǒng)被開發(fā)之前就已經(jīng)使用了很長時(shí)間。早些時(shí)候，位圖索引被認(rèn)為是一種特殊形式的倒排文件。位轉(zhuǎn)置文件非常接近當(dāng)前使用的位圖索引。名稱位圖索引由 O'Neil 及其同事推廣。遵循 Model 204 描述中設(shè)置的示例，這是位圖索引的第一個(gè)商業(yè)實(shí)現(xiàn)，許多研究人員將位圖索引描述為 B 樹索引的變體。為了尊重它早期的化身為反轉(zhuǎn)文件，我們將位圖索引視為由鍵和位圖組成的數(shù)據(jù)結(jié)構(gòu)。此外，我們將 B-tree 視為在文件中布局鍵和位圖的一種方式。由于大多數(shù)位圖索引的商業(yè)實(shí)現(xiàn)是在產(chǎn)品已經(jīng)包含 B-tree 的實(shí)現(xiàn)之后出現(xiàn)的，因此這些產(chǎn)品利用現(xiàn)有的 B-tree 軟件是很自然的。對于新的開發(fā)和實(shí)驗(yàn)或研究代碼，不需要將位圖索引與 B 樹耦合。例如，在一個(gè)實(shí)現(xiàn)本章后面討論的許多位圖索引方法的研究程序中，鍵和位圖在二進(jìn)制文件中被組織為簡單的數(shù)組。發(fā)現(xiàn)這種安排比在 B 樹中實(shí)現(xiàn)位圖索引或作為 DBMS 之上的層更有效。

? ? ? ? 基本位圖索引使用索引屬性的每個(gè)不同值作為鍵，并生成一個(gè)位圖，其中包含與每個(gè)鍵的數(shù)據(jù)集中記錄數(shù)一樣多的位。讓屬性基數(shù)是數(shù)據(jù)集中存在的不同值的數(shù)量。對于“性別”、“每月銷售的汽車類型”或“空客和波音生產(chǎn)的飛機(jī)模型”等低基數(shù)屬性，基本位圖索引的大小相對較小。然而，對于諸如“超新星爆炸中的溫度值”之類的高基數(shù)屬性，索引大小可能太大而無法實(shí)際使用。在文獻(xiàn)中，減少位圖索引大小的基本策略有三種：（1）使用更復(fù)雜的位圖編碼方法來減少位圖的數(shù)量或提高查詢效率，（2）壓縮每個(gè)單獨(dú)的位圖，以及（3）使用分箱或其他映射策略以減少鍵的數(shù)量。在剩下的討論中，我們將這三種策略簡稱為編碼、壓縮和分箱。

位圖索引設(shè)計(jì)

基礎(chǔ)位圖索引

? ? ? ? 如上圖，其中每一行（每個(gè)特征）都是一個(gè)位圖，指示哪些動(dòng)物具有該特征。 雖然這是一個(gè)相當(dāng)簡單的概念，但相等編碼可以非常強(qiáng)大。 因?yàn)樗屛覀兛梢詫⒁磺卸急硎緸椴紶栮P(guān)系（即海牛有翅膀：是/否），我們可以對數(shù)據(jù)執(zhí)行各種按位運(yùn)算。

? ? ? ? 圖下方顯示了我們?nèi)绾瓮ㄟ^對 Invertebrate 和 Breathes Air 位圖執(zhí)行邏輯 AND 來找到所有呼吸空氣的無脊椎動(dòng)物。 根據(jù)我們的樣本數(shù)據(jù)，我們可以看到香蕉蛞蝓、花園蝸牛和輪蟲都具有這兩個(gè)特征。

? ? ? ? 這種基本位圖索引也稱為相等編碼位圖索引，因?yàn)槊總€(gè)位圖都只是屬性值是否等于鍵。此策略對于等值查詢最有效。

等值編碼

? ? ? ? 再來思考一個(gè)場景，添加一個(gè)名為Captivity的特征，表示當(dāng)前被圈養(yǎng)的樣本總數(shù)，并且我們想要執(zhí)行這些值的過濾查詢。

? ? ? ? 基于等值編碼，創(chuàng)建如下位圖：

? ? ? ? 這個(gè)方法是可以的，但是有限制。首先，高基數(shù)情況下并不是很有效，需要?jiǎng)?chuàng)建大量的位圖來代表所有可能的值。其次，如果你想通過范圍查詢過濾，需要對應(yīng)范圍內(nèi)每個(gè)可能的值都執(zhí)行or邏輯。例如，這里想知道captivity<100的動(dòng)物，需要 captivity=99 OR captivity=98 OR captivity=97 OR...

分箱策略

? ? ? ?另一種方法不是將每個(gè)可能的值都表示為唯一的位圖，而是創(chuàng)建Captivity范圍桶。這種情況下如下圖：

? ? ? ? binning 的基本思想是為一個(gè) bin 而不是每個(gè)不同的屬性值構(gòu)建一個(gè)位圖。這種策略將位圖的數(shù)量與屬性基數(shù)分離，并允許構(gòu)建一個(gè)規(guī)定大小的位圖索引，無論屬性基數(shù)有多大。這種方法的一個(gè)明顯優(yōu)勢是它允許控制索引大小。但是，如果只使用索引，它也會(huì)在答案中引入一些不確定性。為了生成準(zhǔn)確的答案，可能需要檢查原始數(shù)據(jù)記錄（候選）以驗(yàn)證是否滿足用戶指定的條件。讀取基礎(chǔ)數(shù)據(jù)以驗(yàn)證查詢條件的過程稱為候選檢查。

? ? ? ? 有許多策略可以最大限度地減少候選檢查所需的時(shí)間。專家考慮了為給定的一組相等查詢和范圍查詢找到最佳分箱的問題。他們的方法基于動(dòng)態(tài)規(guī)劃。由于動(dòng)態(tài)規(guī)劃所需的時(shí)間隨問題大小呈二次方增長，因此這些方法僅對具有相對較小屬性基數(shù)的屬性或具有相對較小的已知查詢集有效。也有人考慮了優(yōu)化評估多維范圍查詢的順序問題，關(guān)鍵思想是在位圖上使用更多操作來減少檢查的候選數(shù)量。這樣通常會(huì)減少總查詢響應(yīng)時(shí)間。這種方法的進(jìn)一步改進(jìn)是考慮影響候選檢查所需的實(shí)際時(shí)間的屬性分布和其他因素。

? ? ? ? 為了在候選檢查期間最小化磁盤頁面訪問次數(shù)，有必要對屬性值進(jìn)行聚類。一種常用的聚類（數(shù)據(jù)布局）技術(shù)稱為垂直分區(qū)或稱為投影索引。一般來說，垂直數(shù)據(jù)布局對于搜索更有效，而水平組織（在 DBMS 中常用）對于更新更有效。為了讓候選者檢查更有效率，我們推薦垂直數(shù)據(jù)組織。

范圍編碼

? ? ? ? 等值編碼和分箱策略都能解決問題，但是對于高基數(shù)且不接受丟失信息的情況，我們需要用另一種表示非布爾值的方法。即不需要編寫非常大和繁瑣的OR操作的情況下對值范圍執(zhí)行查詢。這就是范圍編碼位圖。

? ? ? ? 與相等編碼類似，需要設(shè)置特定值的位，此外，還要為每個(gè)大于實(shí)際值的值設(shè)置一個(gè)位。例如，圈養(yǎng)的考拉熊有14只，在位圖14，15，16等設(shè)置該位。位圖不代表具有特定數(shù)量，二十代表數(shù)量達(dá)到并包括該數(shù)量。

? ? ? ? 這種編碼方法可以執(zhí)行之前所做的那些范圍查詢，而不需要OR對許多不同的位圖操作，從一個(gè)或兩個(gè)位圖中就可以得到我們想要的。例如，想知道哪些動(dòng)物的圈養(yǎng)標(biāo)本少于 15 個(gè)，我們只需拉出 14 位圖就完成了。如果我們想知道哪些動(dòng)物有超過 15 個(gè)被圈養(yǎng)的標(biāo)本，拉取表示最大計(jì)數(shù)的位圖（在我們的例子中是 956 位圖），然后減去 15 位圖。

? ? ? ? 這些操作比我們以前的方法更簡單，也更有效。我們已經(jīng)解決了將OR數(shù)十個(gè)位圖組合在一起以找到我們的范圍的問題，并且不會(huì)像在分桶方法中那樣丟失任何信息。但是我們?nèi)匀挥袔讉€(gè)問題使這種方法不太理想。首先，我們?nèi)匀槐仨毐Ａ粢粋€(gè)位圖來表示每個(gè)特定的值計(jì)數(shù)。最重要的是，我們增加了復(fù)雜性和開銷，不僅要為我們感興趣的值設(shè)置一些值，而且還要為每個(gè)大于該值的值設(shè)置一些值。這很可能會(huì)在寫入繁重的用例中引入性能問題。

位切片

等值編碼

? ? ? ? 理想情況下，我們想要的是具有范圍編碼位圖的功能和相等編碼的效率。接下來，我們將討論位切片索引，看看它如何幫助我們實(shí)現(xiàn)我們想要的。

????????當(dāng)基數(shù)變得非常高時(shí)，我們需要維護(hù)得位圖數(shù)量會(huì)變得令人望而卻步。位切片索引讓我們以更有效地方式來表示這些相同的值。

????????將值分解為三個(gè)以10為底得組件，第一列表示值003，即圈養(yǎng)海牛得數(shù)量。組件0的值是003中得3，組件1和組件2的值是003中的0，在對應(yīng)值中設(shè)置位。base-10索引中的每個(gè)組件需要10個(gè)位圖來表示所有可能的值，因此需要表示范圍從0~956的值時(shí)，只需要3x10=30個(gè)位圖。這樣做大大減少了位圖的數(shù)量。我們基本上找到了一種方法來提高平等編碼策略的效率。

范圍編碼

????????將位切片索引與范圍編碼結(jié)合，情況如下：

????????觀察上圖，每個(gè)組件中9對應(yīng)的位始終為1，因此，不需要存儲(chǔ)最高值。對于base-10、范圍編碼、位切片索引，只需要9個(gè)位圖來表示一個(gè)組件。除此之外，還需要存儲(chǔ)一個(gè)名為“not null” 的位圖，指示是否為該列設(shè)置了值。

????????所以對于3分量值，需要（3*9+1）=28個(gè)位圖來表示0~999范圍內(nèi)的任何值?，F(xiàn)在我們有一種非常有效的方式來存儲(chǔ)值，受益于范圍編碼，因此我們可以執(zhí)行過濾范圍的查詢。

二進(jìn)制-范圍編碼

????????如果我們不是將我們的Captivity值表示為以10 為底的分量，而是使用以2 為底的分量，那么我們最終會(huì)得到一組范圍編碼的位切片索引，如下所示：

????????第一列位表示以 2 為底的值000000011，即圈養(yǎng)海牛的數(shù)量（以 10 為底的 3）。由于組件 0 和組件 1 000000011都是1，我們在組件 0 第 1 行和組件 1 第 1 行中設(shè)置一個(gè)位。由于的其余組件000000011都是0，我們在第 0 行中為組件 2 到 9 設(shè)置一個(gè)位，并且因?yàn)檫@些是范圍編碼的，在每個(gè)大于 0 的值中設(shè)置一個(gè)位。對于以 2 為底的組件，這意味著我們還在第 1 行中為組件 2 到 9 設(shè)置了位。

????????就像我們之前看到的基于 10 表示的位圖 9 一樣，位圖 1 始終是 1，因此我們不需要存儲(chǔ)它。這給我們留下了這個(gè)：

????????通過這種編碼，我們可以僅用 10 個(gè)位圖來表示樣本值的范圍！另外，請注意，base-2、范圍編碼、位切片索引是整數(shù)值的二進(jìn)制表示的倒數(shù)。這告訴我們的是，我們可以僅使用 (n + 1) 個(gè)位圖（其中附加位圖是“非空”位圖）來表示具有基數(shù) n 的任何值范圍。這意味著我們可以對大整數(shù)值執(zhí)行范圍查詢，而無需存儲(chǔ)不合理數(shù)量的位圖。

多分量編碼

????????二進(jìn)制編碼的優(yōu)點(diǎn)是它需要的位圖比間隔編碼少得多。但是，要做范圍查詢，使用區(qū)間編碼的人只需訪問兩個(gè)位圖，而使用二進(jìn)制編碼的人通常必須訪問所有位圖。

????????許多學(xué)者提出了在空間和時(shí)間要求之間找到平衡的策略。 提出的一種稱為多分量編碼的方法可以被認(rèn)為是二進(jìn)制編碼的一種推廣。在二進(jìn)制編碼中，每個(gè)位圖代表屬性值的一個(gè)二進(jìn)制位；多分量編碼以類似地方式切分值，其中每個(gè)分量可能具有不同的大小。考慮一個(gè)整數(shù)屬性，其值范圍為 0 到 c-1。設(shè) b1 和 b2 是兩個(gè)分量 c1 和 c2 的大小，其中 b1b2>=c。任何值 v 都可以表示為 v = c1b2+c2，其中 c1 = v / b2 和 c2 = v % b2，其中“/”表示整數(shù)除法，“%”表示取模運(yùn)算?？梢允褂靡环N簡單的位圖編碼方法分別對 c1 和 c2 的值進(jìn)行編碼。接下來，我們舉一個(gè)更具體的例子來說明多分量編碼。

????????上圖說明了基數(shù) c=1000 的屬性的 2 分量編碼位圖索引。這兩個(gè)組件的基本尺寸為 b1=25 和 b2=40。假設(shè)屬性值在 [0; 999]。一個(gè)屬性值 v 被分解為兩個(gè)分量，c1 = v / 40 和 c2 = v % 40。分量 c1 可以被視為 0 到 24 范圍內(nèi)的整數(shù)屬性；組件 c2 可以被視為 0 到 39 范圍內(nèi)的整數(shù)屬性。可以構(gòu)建兩個(gè)位圖索引，每個(gè)組件一個(gè)，例如，具有相等編碼的 c1 和具有范圍編碼的 c2。如果兩個(gè)分量都使用范圍編碼，則分量 1 使用 24 個(gè)位圖，分量 2 使用 39 個(gè)位圖。在這種情況下，2 分量編碼使用 63 個(gè)位圖，比二進(jìn)制編碼使用的 10 個(gè)位圖多。要使用 2 分量索引做相同的查詢“v < 105”，該查詢被有效地轉(zhuǎn)換為“c1<2 OR (c1=2 AND c2<25)”。評估這個(gè)表達(dá)式需要三個(gè)位圖，分別代表“c1<=1”、“c1<=2”和“c2<=24”。相反，使用二進(jìn)制編碼的位圖索引來評估相同的查詢，需要所有 10 個(gè)位圖。

????????使用更多組件可以減少位圖的數(shù)量，從而減少總索引大小。 然而，使用更多的組件也會(huì)增加為了回答查詢而訪問的位圖數(shù)量，從而增加查詢響應(yīng)時(shí)間。 顯然，在索引大小和查詢響應(yīng)時(shí)間之間存在權(quán)衡。 在不考慮壓縮的情況下，Chan & Ioannidis (1999) 分析了這種時(shí)空權(quán)衡。 他們建議權(quán)衡曲線的拐點(diǎn)在 2 個(gè)分量處。 他們進(jìn)一步建議這兩個(gè)組件應(yīng)該具有幾乎相同的基本大小以減小索引大小。

壓縮

方法

????????壓縮是減小位圖索引大小的第三種策略。由于位圖索引的每個(gè)位圖可以與其他位圖分開使用，因此通常對每個(gè)單獨(dú)的位圖應(yīng)用壓縮。壓縮是一個(gè)經(jīng)過充分研究的主題，高效的壓縮軟件包廣泛可用。盡管這些通用壓縮方法在減小位圖大小方面是有效的，但壓縮位圖上的查詢處理操作通常比未壓縮位圖上的要慢。這促使許多研究人員提高壓縮位圖索引的效率。兩種最著名的壓縮方法是字節(jié)對齊位圖編碼 (BBC) 和字對齊混合 (WAH) 編碼。使用 BBC 壓縮的位圖比使用最佳通用壓縮方法壓縮的位圖稍大。然而，對 BBC 壓縮位圖的操作通常更快。顯然，有一個(gè)值得的時(shí)空權(quán)衡。 WAH 壓縮使這種時(shí)空權(quán)衡更進(jìn)了一步。更具體地說，WAH 壓縮位圖比 BBC 壓縮位圖大，但 WAH 壓縮位圖的操作比 BBC 壓縮位圖快得多。因此，WAH 壓縮位圖索引可以更快地回答查詢。

????????WAH 位圖壓縮基于游程長度編碼，其中連續(xù)的相同位用其位值（0 或 1）和計(jì)數(shù)（游程長度）表示。在 WAH 中，字有兩種情況, 原文字(literal word)和壓縮字(fill word)。兩種字通過32個(gè)bit中的第一個(gè)bit來區(qū)分, 第一個(gè)bit為0是原文字, 為1則是壓縮字。如果是壓縮字, 那么剩余31個(gè)bit中，第2bit表示壓縮的值是0還是1。剩余30個(gè)bit表示有多少字的重復(fù)的值, 稱為run number。比如第一個(gè)bit是1, 第2個(gè)bit是1, 剩下30個(gè)bit是數(shù)值5, 則表示有連續(xù)的5*31個(gè)1。WAH 的一個(gè)關(guān)鍵思想是定義fill word 和literal word，以便它們可以存儲(chǔ)以word（現(xiàn)代計(jì)算機(jī)硬件的最小操作單元）的形式存儲(chǔ)。

????????在理論分析中，使用 WAH 壓縮索引的一維范圍查詢的查詢響應(yīng)時(shí)間顯示出隨著命中數(shù)線性增長。 這種時(shí)間復(fù)雜度對于任何搜索算法都是最佳的。 各種眾所周知的索引方法，例如 B+-trees 和 B-trees，都具有相同的最佳縮放屬性。 但是，壓縮位圖索引具有獨(dú)特的優(yōu)勢，即它們可以輕松組合以回答多維即席范圍查詢，而 B+-tree 或 B-tree 的組合效率幾乎不高。

????????一般來說，查詢響應(yīng)時(shí)間可以分為I/O時(shí)間和CPU時(shí)間。由于 WAH 壓縮位圖的大小比 BBC 壓縮位圖大，我們預(yù)計(jì) WAH 需要更多 I/O 時(shí)間來讀取壓縮位圖。對于許多數(shù)據(jù)庫操作，CPU 時(shí)間與 I/O 時(shí)間相比可以忽略不計(jì)。事實(shí)證明，在使用壓縮位圖索引回答查詢時(shí)情況并非如此。在一項(xiàng)性能實(shí)驗(yàn)中，學(xué)者將 WAH 壓縮索引與 BBC 壓縮索引的兩種獨(dú)立實(shí)現(xiàn)進(jìn)行了比較，結(jié)果表明，使用 WAH 壓縮位圖索引的總查詢響應(yīng)時(shí)間比使用 BBC 壓縮位圖的要小，即使在一個(gè)相對較慢的磁盤系統(tǒng)上，從磁盤讀取文件只能維持 5 MB/s。在速度更快的磁盤系統(tǒng)上，WAH 壓縮位圖索引的性能優(yōu)勢更加明顯。使用 WAH 可能比使用 BBC 快 10 倍。

位圖索引拐點(diǎn)

????????除非使用二進(jìn)制編碼，否則壓縮位圖索引很重要。為了構(gòu)建有效的壓縮位圖索引，要考慮的三個(gè)主要因素是：編碼，分箱數(shù)，以及分箱策略。在下文中，我們提出了選擇這三個(gè)參數(shù)的經(jīng)驗(yàn)法則。

????????最佳位圖編碼技術(shù)取決于評估的查詢類型。范圍編碼是范圍查詢的最佳位圖編碼技術(shù)，但是，范圍編碼可能并不總是適用于高基數(shù)屬性或大量分箱。正如我們將在下一節(jié)中展示的那樣，范圍編碼的位圖索引不像等式編碼的位圖索引那樣壓縮。

????????選擇 bin 數(shù)量的一般規(guī)則如下： bin 越多，候選檢查的工作量就越少。隨著 bin 數(shù)量的增加，每個(gè) bin 的候選者數(shù)量會(huì)減少。假設(shè)基礎(chǔ)數(shù)據(jù)服從均勻隨機(jī)分布。對于 8KB 的典型頁面大小，使用投影索引，一個(gè)頁面可以容納 2048 個(gè) 4 字節(jié)字。如果在候選檢查期間訪問了千分之一的word，則很可能會(huì)觸及包含屬性值的每一頁。因此，我們建議使用 1000 個(gè)或更多分箱。

????????對于相等編碼有一個(gè)額外的權(quán)衡，即使用更多的 bin 也可能會(huì)增加索引掃描的成本。對于范圍編碼，索引掃描的成本不受 bin 數(shù)量的顯著影響，因?yàn)樾枰L問不超過兩個(gè)位圖來評估范圍查詢。如果沒有壓縮，人們顯然會(huì)傾向于范圍編碼。然而，隨著壓縮，相對強(qiáng)度并不那么明顯。使用 WAH 壓縮等值編碼索引，索引掃描的成本與命中數(shù)成正比，與所涉及的位圖數(shù)量無關(guān)。因?yàn)榈戎稻幋a索引更容易壓縮，這使 WAH 壓縮的等值編碼索引成為首選。

????????分箱策略對候選檢查有影響。最簡單的一種分箱稱為等寬分箱，將索引屬性的域劃分為大小相等的箱。因此，每個(gè) bin 可能有不同數(shù)量的條目。另一方面，等深度分箱在分箱之間平均分配條目數(shù)。這種技術(shù)比等寬分箱更好，但構(gòu)建成本更高，因?yàn)橥ǔ１仨毾葤呙钄?shù)據(jù)以生成精確的直方圖，然后再開始分箱。

????????降低構(gòu)建一組等深 bin 的成本的一種方法是使用采樣直方圖而不是精確直方圖。另一種方法是首先構(gòu)建一個(gè)等寬分箱索引，其中包含比期望更多的分箱，然后將相鄰分箱組合形成近似等深分箱。但是，第二種方法可能由于異常值不會(huì)產(chǎn)生平衡良好的 bin。采樣直方圖的方法在檢測異常值方面通常更可靠，并且通常會(huì)產(chǎn)生平衡良好的 bin。

空間復(fù)雜性

????????分析壓縮位圖索引的大小，這里主要集中在 WAH 壓縮方法上，因?yàn)?BBC 壓縮在 (Johnson, 1999) 中得到了廣泛的研究。我們給出了最壞情況大小的上限，并為各種應(yīng)用數(shù)據(jù)集提供了壓縮位圖索引的實(shí)驗(yàn)研究。

索引大小：最壞情況的行為

????????在上一節(jié)中，我們將 WAH 運(yùn)行定義為原文字(literal word)和壓縮字(fill word)。為了使討論更具體，讓我們假設(shè)一個(gè)機(jī)器字是 32 位。在這種情況下，WAH 尾部正好包含來自輸入位圖的 31 位，而 WAH 填充包含 31 位的倍數(shù)，它們都是相同的（0 或 1）。因?yàn)橐阎粓D索引對低基數(shù)屬性有效，所以我們進(jìn)一步將討論僅限于高基數(shù)屬性，例如 c > 100。在等值編碼的位圖索引中，有 c 個(gè)鍵（屬性的不同值）因此 c 位圖。我們不知道每個(gè)位圖中有多少位被設(shè)置為 1。但是，我們知道為 1 的總位數(shù)正好是 N（數(shù)據(jù)集中的行數(shù)）。在最壞的情況下，位圖中有 (N+c) 個(gè) WAH 運(yùn)行，其中 N 是指尾字的最大數(shù)量（每個(gè)包含一個(gè)設(shè)置為 1 的位），c 是指在結(jié)尾處的最大運(yùn)行數(shù)每個(gè)不以尾字結(jié)尾的位圖。

????????每個(gè) WAH 運(yùn)行由兩個(gè)機(jī)器字編碼。因此，我們總共需要 2(N+c) 個(gè)詞來表示位圖。假設(shè)每個(gè)鍵由一個(gè)單詞和一個(gè)附加單詞編碼以將鍵與位圖相關(guān)聯(lián)，則總索引大小為 2N+4c 個(gè)單詞。在大多數(shù)情況下，屬性基數(shù) c 遠(yuǎn)小于 N。在這些情況下，WAH 壓縮的等值編碼位圖索引大小最多為 2N 個(gè)字。使用分箱，可以使用數(shù)千個(gè) bin，最大索引大小仍不超過 2N。由于觀察到許多 B 樹的商業(yè)實(shí)現(xiàn)使用 3N 到 4N 個(gè)字，因此壓縮位圖索引的最大大小相對適中。正如將針對實(shí)際應(yīng)用程序數(shù)據(jù)展示的那樣，WAH 壓縮索引通常遠(yuǎn)小于預(yù)測的最壞情況大小。

????????對于 WAH 壓縮，在最壞的情況下，范圍編碼位圖索引中大約 90% 的位圖將不可壓縮（Wu 等人，2006 年）。除非可以容忍非常大的索引，或者事先知道壓縮會(huì)有效，否則我們通常建議對范圍編碼位圖索引使用不超過 100 個(gè) bin。這保證了位圖索引的大小在最壞的情況下是 B 樹的大小。

實(shí)際應(yīng)用

????????我們現(xiàn)在將通過實(shí)驗(yàn)分析各種應(yīng)用程序數(shù)據(jù)集的壓縮位圖索引的大小。

燃燒數(shù)據(jù)集

????????燃燒數(shù)據(jù)集來自于 TeraScale High-Fidelity Simulation of Turbulent Combustion withDetailed Chemistry（Tera Scale Combustion，2005 年）中對湍流氫-空氣混合物的自動(dòng)點(diǎn)火的模擬。 該數(shù)據(jù)集包含 2400 萬條記錄，每條記錄有 16 個(gè)屬性。 對于這個(gè)數(shù)據(jù)集，我們使用不同數(shù)量的等深 bin 構(gòu)建了等值編碼和范圍編碼的位圖索引。 下圖顯示了每個(gè)屬性的壓縮位圖索引的平均大小。 我們可以看到，具有 1000 個(gè) bin 的等值編碼位圖索引和具有 100 個(gè) bin 的范圍編碼位圖索引與基本數(shù)據(jù)的大小大致相同。 請注意，具有 100 個(gè) bin 的未壓縮位圖索引的大小約為基礎(chǔ)數(shù)據(jù)的 3 倍。 使用 1000 個(gè) bin，未壓縮位圖索引的大小大約是 30 倍。 這表明 WAH 壓縮算法在該數(shù)據(jù)集上運(yùn)行良好。

高能物理數(shù)據(jù)集

????????第二個(gè)數(shù)據(jù)集來自斯坦福直線加速器中心的高能物理實(shí)驗(yàn)。它由具有 10 個(gè)屬性的 760 萬條記錄組成。下圖顯示了壓縮位圖索引的大小。我們注意到具有 100 個(gè) bin 的范圍編碼位圖索引的大小大約是基礎(chǔ)數(shù)據(jù)的兩倍。具有 1000 個(gè) bin 的等式編碼位圖索引比基本數(shù)據(jù)小約 30%。

????????通常，這些高能物理實(shí)驗(yàn)的記錄彼此不相關(guān)。因此，游程編碼通常很難有效。這就是為什么范圍編碼的索引大小與之前的數(shù)據(jù)集相比相對較大的原因。然而，等值編碼對于這個(gè)物理數(shù)據(jù)集的壓縮非常好?？傮w而言，我們看到實(shí)際位圖索引大小遠(yuǎn)小于基礎(chǔ)數(shù)據(jù)大小，并且小于 B 樹的典型商業(yè)實(shí)現(xiàn)的大小（通常是基礎(chǔ)數(shù)據(jù)大小的三到四倍）。

時(shí)間復(fù)雜度

????????等式編碼被證明是最節(jié)省空間的方法。另一方面，范圍編碼是我們在實(shí)驗(yàn)中使用的單邊范圍查詢最省時(shí)的方法。

????????分析表明，使用 WAH 壓縮的基本位圖索引（沒有分箱的等值編碼）回答一維范圍查詢的最壞情況查詢響應(yīng)時(shí)間是命中數(shù)的線性函數(shù)。分析還表明，最壞情況下的行為是遵循均勻隨機(jī)分布的屬性。

????????接下來將提供更多時(shí)間測量來比較相等編碼和范圍編碼位圖索引的查詢響應(yīng)時(shí)間。所有索引都使用 WAH 壓縮進(jìn)行壓縮。由于這兩個(gè)數(shù)據(jù)集的結(jié)果相似，我們僅報(bào)告基于更大且更具挑戰(zhàn)性的燃燒數(shù)據(jù)集的測量結(jié)果。我們使用投影指數(shù)作為所有比較的基線。我們注意到這是一個(gè)很好的基線，因?yàn)橥队爸笖?shù)以優(yōu)于許多多維指數(shù)而聞名。

????????通常，我們看到位圖索引的查詢處理時(shí)間隨著查詢變得更具選擇性而減少。 另一方面，投影索引的查詢處理時(shí)間隨著選擇性的變化而保持不變。 對于所有查詢維度，具有 100 個(gè) bin 的范圍編碼位圖索引顯示出最佳性能特征，但有時(shí)會(huì)以更大的索引為代價(jià)。 如果存儲(chǔ)空間是一個(gè)限制因素，最好選擇具有 1000 個(gè) bin 的等式編碼位圖索引。 如下圖，等式編碼位圖索引的性能與范圍編碼位圖索引的性能沒有顯著差異。

總結(jié)

????????對不同的位圖編碼方法，我們做如下簡要總結(jié):

	總Bitmap個(gè)數(shù)	查詢獲取Bitmap 個(gè)數(shù)	是否精確	查詢復(fù)雜度
等值編碼	=N（屬性值個(gè)數(shù)）	<=N/2	是	高
分箱策略	與基數(shù)無關(guān)，可自由控制	取決于分箱個(gè)數(shù)	否	取決于分箱策略和候選檢查如何平衡
范圍編碼	=N（屬性值個(gè)數(shù)）	1	是	低
區(qū)間編碼	=N（屬性值個(gè)數(shù)）	2	是	低
位切片-等值編碼	10*log(10)N	10*log(10)N	是	高
位切片-范圍編碼	9*(log(10)N)+1	9*(log(10)N)+1	是	低
位切片-二進(jìn)制范圍編碼	log(2)N+1	log(2)N+1	是	低

商業(yè)產(chǎn)品的主要特性

????????由于生產(chǎn)和維護(hù)強(qiáng)大的商業(yè)軟件系統(tǒng)涉及大量工作，因此只有最有效和經(jīng)過驗(yàn)證的索引技術(shù)才能進(jìn)入商業(yè) DBMS。在本節(jié)中，我們將簡要回顧各種知名商業(yè)產(chǎn)品目前使用的關(guān)鍵位圖索引技術(shù)。這并不意味著是一個(gè)詳盡的調(diào)查。我們的主要興趣是了解缺少哪種位圖索引技術(shù)以及哪種技術(shù)可能會(huì)對商業(yè)產(chǎn)品產(chǎn)生影響。

????????第一個(gè)使用位圖索引名稱的商業(yè)產(chǎn)品是 Model 204。O'Neil 在 (O'Neil, 1987) 中發(fā)表了對索引方法的描述。Model 204 實(shí)現(xiàn)了基本的位圖索引。它沒有分箱或壓縮。目前，Model 204 由美國計(jì)算機(jī)公司銷售。從 7.3 版開始，ORACLE 在其旗艦產(chǎn)品中具有一個(gè)壓縮位圖索引版本。他們實(shí)施了一種專有的壓縮方法。根據(jù)觀察到的性能特征，它似乎使用相等編碼而不進(jìn)行分箱。

????????Sybase IQ 實(shí)現(xiàn)了位切片索引。Sybase IQ 支持未合并、二進(jìn)制編碼、未壓縮的位圖索引。此外，它還具有低基數(shù)屬性的基本位圖索引。 IBM DB2 實(shí)現(xiàn)了一種二進(jìn)制編碼位圖索引的變體，稱為編碼向量索引。 IBM Informix 產(chǎn)品還包含一些版本的位圖索引，用于涉及一個(gè)或多個(gè)表的查詢。這些索引是專門為加速連接操作而設(shè)計(jì)的，通常被稱為連接索引。 InterSystems Corp 的 Cache 從 5.0 版開始也支持位圖索引。

???????? 達(dá)夢數(shù)據(jù)庫的位圖索引采用了二進(jìn)制范圍編碼的方案，支持對低基數(shù)的列創(chuàng)建位圖索引, 其建立過程是，首先構(gòu)造二進(jìn)制等值編碼位圖索引，然后采用逐級位圖向量相加構(gòu)造二進(jìn)制范圍編碼位圖索引。在查詢階段采用了流水線方式讀取位圖塊，實(shí)現(xiàn)了IO異步化。另外在數(shù)據(jù)倉庫中，也支持針對兩個(gè)或者多個(gè)表連接的位圖索引，稱為位圖連接索引。

????????Postgresql在8.3 提供了 on disk bitmap索引，后續(xù)移除了，但是Postgres的延展數(shù)據(jù)庫Greenplum DB中被保留了下來。pg支持 in memory bitmap索引，在bitmap scan index 時(shí)，通過在內(nèi)存中建立基礎(chǔ)位圖的方式，將回表過程中對標(biāo)訪問隨機(jī)性IO的轉(zhuǎn)換為順行性行為，從而減少查詢過程中IO的消耗。

????????盡管我們沒有關(guān)于大多數(shù)這些商業(yè)產(chǎn)品的技術(shù)細(xì)節(jié)，但通常很清楚它們傾向于使用基本位圖索引或位切片索引。沒有使用分箱和多分量編碼等策略，部分原因是沒有穩(wěn)健的策略來選擇適合不同應(yīng)用的分箱數(shù)量或組件數(shù)量等參數(shù)。

未解決的問題

????????回顧了位圖索引技術(shù)領(lǐng)域的一些最新發(fā)展后，我們簡要概述了主要供應(yīng)商的商業(yè)位圖索引實(shí)現(xiàn)。

????????盡管位圖索引取得了成功，但仍有許多重要問題需要解決。例如，是否有用于相似性查詢的有效位圖索引？如何自動(dòng)選擇編碼、壓縮和分箱技術(shù)的最佳組合？如何使用位圖索引來回答更一般的連接查詢？

????????迄今為止，位圖索引的研究工作集中在有效地回答查詢上，但往往忽略了更新索引的問題。顯然，在添加新記錄時(shí)需要更新索引。這個(gè)問題的有效解決方案可能是在商業(yè)應(yīng)用中更廣泛地適應(yīng)位圖索引的關(guān)鍵。

參考鏈接

(PDF) Bitmap Indices for Data Warehouses (researchgate.net)

Using Bitmaps to Perform Range Queries - Pilosa

更多技術(shù)文章參見達(dá)夢社區(qū)：https://eco.dameng.com