726 技術社區[雲棲]

Greenplum 最佳實踐 - 什麼時候選擇bitmap索引

標簽

PostgreSQL , Greenplum , bitmap index

背景

PostgreSQL 目前支持8種索引接口，包括B-Tree, hash, gin, gist, sp-gist, brin, rum, bloom。

Greenplum 目前支持B-Tree, GiST, bitmap三種索引接口。

用戶可以根據不同的數據類型，不同的請求類型，使用不同的索引接口建立相應的索引。例如對於數組，全文檢索類型，可以使用GIN索引，對於地理位置數據，範圍數據類型，圖像特征值數據，幾何類數據等，可以選擇GiST索引。

PG的八種索引的介紹，可以參考bruce寫的index internal、源碼以及如下文檔

https://leopard.in.ua/2015/04/13/postgresql-indexes

bitmap index 原理

如圖所示，bitmap索引將每個被索引的VALUE作為KEY，使用每個BIT表示一行，當這行中包含這個VALUE時，設置為1，否則設置為0。

如何從bitmap 索引檢索數據，並查找到對應HEAP表的記錄呢？

必須要有一個mapping 轉換功能（函數），才能將BIT位翻譯為行號。例如第一個BIT代表第一行，。。。以此類推。（當然了，mapping函數沒有這麼簡單，還有很多優化技巧）

bitmap 的優化技術舉例，比如

1. 壓縮

例如連續的0或1可以被壓縮，具體可以參考WIKI裏麵關於BITMAP的壓縮算法，算法也是比較多的。

2. 分段或分段壓縮

例如，每個數據塊作為一個分段，每個分段內，記錄這個數據塊中的VALU對應的BIT信息。

3. 排序

排序是為了更好的進行壓縮，例如堆表按被索引的列進行排序後，每個VALUE對應的行號就都是連續的了，壓縮比很高。

另外用戶也可以參考一下roaring bitmap這個位圖庫，應用非常廣泛，效果也很不錯。

https://github.com/zeromax007/gpdb-roaringbitmap

https://github.com/RoaringBitmap/CRoaring

bitmap index 適合什麼場景

從bitmap index的結構我們了解到，被索引的列上麵，每一個value都分別對應一個BIT串，BIT串的長度是記錄數，每個BIT代表一行，1表示該行存在這個值，0表示該行不存在這個值。

因此bitmap index索引的列，不能有太多的VALUE，最好是100到10萬個VALUE，也就是說，這樣的表的BITMAP索引有100到10萬條BIT串。

當我們對這個表的這個字段進行類似這樣的查詢時，效率就非常高。

select * from table where col = a and col = b and col2=xxx;        
-- a,b的bit串進行BITAND的操作，然後再和col2=xxx的BIT進行BITAND操作，返回BIT位為1的，使用bitmap function返回行號，取記錄。      
      
select count(*) from table where col = a and col = b and col2=xxx;        
-- a,b的bit串進行BITAND的操作，然後再和col2=xxx的BIT進行BITAND操作，返回BIT位為1的，使用bitmap function返回行號，取記錄，算count(*)。

1. 適合有少量不重複值的列。

2. 適合多個條件的查詢，條件越多，bit and,or 的操作過濾掉的數據就越多，返回結果集越少。

bitmap index 不適合什麼場景

由於每個VALUE都要記錄每行的BIT位，所以如果有1億條記錄，那麼每個VALUE的BIT串長度就是1億。如果有100萬個不同的VALUE，那麼BITMAP INDEX就有100萬個長度為1億的bit串。

1. 不適合有太多不重複值的表字段。

3. 同樣，也不適合有太少不重複值的列，例如男女。這樣的列，除非可以和其他列組合賽選出很少量的結果集，否則返回的結果集是非常龐大的，也是不適合的。

3. 不適合頻繁的更新，因為更新可能帶來行遷移，以及VALUE的變化。如果是行遷移，需要更新整個bitmap串。如果是VALUE變化，則需要修改整個與變化相關的VALUE的BIT串。

greenplum bitmap index手冊

About Bitmap Indexes

Greenplum Database provides the Bitmap index type.
Bitmap indexes are best suited to data warehousing applications and decision support systems with large amounts of data, many ad hoc queries, and few data modification (DML) transactions.

An index provides pointers to the rows in a table that contain a given key value.
A regular index stores a list of tuple IDs for each key corresponding to the rows with that key value.
Bitmap indexes store a bitmap for each key value. Regular indexes can be several times larger than the data in the table,
but bitmap indexes provide the same functionality as a regular index and use a fraction of the size of the indexed data.

Each bit in the bitmap corresponds to a possible tuple ID. If the bit is set, the row with the corresponding tuple ID contains the key value.
A mapping function converts the bit position to a tuple ID. Bitmaps are compressed for storage.
If the number of distinct key values is small, bitmap indexes are much smaller, compress better,
and save considerable space compared with a regular index.
The size of a bitmap index is proportional to the number of rows in the table times the number of distinct values in the indexed column.

Bitmap indexes are most effective for queries that contain multiple conditions in the WHERE clause.
Rows that satisfy some, but not all, conditions are filtered out before the table is accessed.
This improves response time, often dramatically.

When to Use Bitmap Indexes

Bitmap indexes are best suited to data warehousing applications where users query the data rather than update it.
Bitmap indexes perform best for columns that have between 100 and 100,000 distinct values and when the indexed column is often queried in conjunction with other indexed columns.
Columns with fewer than 100 distinct values, such as a gender column with two distinct values (male and female),
usually do not benefit much from any type of index.
On a column with more than 100,000 distinct values, the performance and space efficiency of a bitmap index decline.

Bitmap indexes can improve query performance for ad hoc queries.
AND and OR conditions in the WHERE clause of a query can be resolved quickly by performing the corresponding Boolean operations directly on the bitmaps before converting the resulting bitmap to tuple ids.
If the resulting number of rows is small, the query can be answered quickly without resorting to a full table scan.

When Not to Use Bitmap Indexes

Do not use bitmap indexes for unique columns or columns with high cardinality data,
such as customer names or phone numbers.
The performance gains and disk space advantages of bitmap indexes start to diminish on columns with 100,000 or more unique values,
regardless of the number of rows in the table.

Bitmap indexes are not suitable for OLTP applications with large numbers of concurrent transactions modifying the data.

Use bitmap indexes sparingly. Test and compare query performance with and without an index.
Add an index only if query performance improves with indexed columns.

greenplum中如何創建bitmap index

CREATE INDEX title_bmp_idx ON films USING bitmap (title);

bitmap 在PG數據庫中的應用

在PostgreSQL中雖然沒有bitmap索引，但是多個條件的查詢，支持自動生成BIT，並通過BitmapAnd, BitmapOr操作，計算並合並結果。

PostgreSQL is not provide persistent bitmap index.

But it can be used in database to combine multiple indexes.

PostgreSQL scans each needed index and prepares a bitmap in memory giving the
locations of table rows that are reported as matching that index’s conditions.

The bitmaps are then ANDed and ORed together as needed by the query.

Finally, the actual table rows are visited and returned.