Menu
PostgreSQL 9.4
I just encountered the node called Bitmap Index Scan and the concept of so-called underlying bitmap data structure mentioned in this post. As far as I know, PostgreSQL doesn't support creating bitmap indexes.
Question: So any time we need to use bitmap data-structure in order to perform Bitmap Index Scan, we need to build it first or PostgreSQL creates it during construction of a btree index and rebuilds it any time the table has changed?
942
Unlike B-tree indexes where an index entry points to a specific table row, a bitmap index stores a bitmap for each index key. Bitmap indexes are ideal for low-cardinality data filtering where the number of distinct values in a column is relatively small.
In a bitmap index, a bitmap for each key value is used instead of a list of rowids. Each bit in the bitmap corresponds to a possible rowid, and if the bit is set, it means that the row with the corresponding rowid contains the key value.
An index provides pointers to the rows in a table that contain a given key value. A regular index stores a list of rowids for each key corresponding to the rows with that key value. In a bitmap index, a bitmap for each key value replaces a list of rowids.
A bitmap index is a special kind of database index that uses bitmaps. Bitmap indexes have traditionally been considered to work well for low-cardinality columns, which have a modest number of distinct values, either absolutely, or relative to the number of records that contain the data.
The bitmap of pages is created dynamically for each query. It is not cached or re-used, and is discarded at the end of the bitmap index scan.
It doesn't make sense to create the page bitmap in advance because its contents depend on the query predicates.
Say you're searching for x=1 and y=2. You have b-tree indexes on x and y. PostgreSQL doesn't combine x and y into a bitmap then search the bitmap. It scans index x for the page address of all pages with x=1 and makes a bitmap where the pages that might contain x=1 are true. Then it scans y looking for the page addresses where y might equal 2, making a bitmap from that. Then it ANDs them to find pages where both x=1 and y=2 might be true. Finally, it scans the table its self, reading only the pages that might contain candidate values, reading each page and keeping only the rows where x=1 and y=2.
Now, if you're looking for something like a cached, pre-built bitmap index, there is such a thing in PostgreSQL 9.5: BRIN indexes. These are intended for very large tables, and provide a way to find ranges of the table that can be skipped over because they're known not to contain a desired value.
184
The bitmap of data pages is created from index or more indexes on demand (per query). It is used when index returns more than less rows, or when two or more indexes are used on same relation. The content of bitmap controls what pages should be processed and what pages should be skipped.
The basic requirement of this scan method is existing index on table.
33
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
