Last updated: July 9, 2019
Topic: SocietyWork
Sample donated:

1    IntroductionA bitmap index is a special kind of database index that uses bitmaps, Oracle bitmap indexes are very different from standard b-tree indexes , Bitmap Indexes were first introduced by O’Neil and implemented in the Model 204 DBMS. This indexing technique is mostly used for typical data warehouse applications, which are mainly characterized by complex query types and read-mostly environments that are more or less static. In data warehouse environments insert, delete or update operations are not very common and, therefore, it is better to build an index which optimizes the query performance rather than the dynamic features.Bitmap indexes are used by DBMS to accelerate decision support queries. The main advantage of Bitmap indexes is that complex logical selection operations can be performed very quickly by applying low-cost Boolean operations such as OR, AND, and NOT, this will reduce search space before going to the primary source data.2    Characteristic of Bitmap indexing•    For columns with very few unique values (low cardinality)•    Columns that have low cardinality are good candidates •    Tables that have no or little insert/update are good candidates •    Stream of bits: each bit relates to a column value in a single row of table2.1    Advantage of Bitmap IndexesThe main advantage of the Bitmap indexes that are high compressed structure, which will make the read is really fast. in addition, the bitmap structure makes the system merge multiple indexes together for faster access to the underlying tables.Compressed indexes are like a bitmap indexes, its represent a trade-off between CPU and Disk usage. The compressed structure is faster to read-only from disk but unfortunately it takes additional CPU cycles to decompress for access an uncompressed structure.One belief concerning bitmap indexes is that they are only suitable for indexing low-cardinality data. This is not necessarily true, because by compressing the indexes in bitmap indexes, it can be used very successfully for indexing columns with many millions of different values.2.2    Disadvantage of Bitmap IndexesThe main disadvantage is the modification on bitmap indexing which is really dreadful, because it requires a huge deal work on behalf of the system which is worst than modification on B-tree index, on other hand the overhead on maintaining the bits is enormous.3    Bitmap index Design3.1    Basic Bitmap IndexBitmap indices are one of the most efficient indexing methods available for speeding up multi-dimensional range queries for reading only (projection), the queries are evaluated with bitwise logical operations that are well supported by computer hardware,” for an attribute with C distinct values, the basic bitmap index generates C bitmaps with N bits each, where N is the number of records in the data set. Each bit in a bitmap is set to “1” if the attribute in the record is of a specific value; otherwise the bit is set to “0””. Figure 1 below will demonstrate a simple bitmap index with 6 bitmaps. “Each bitmap represents a distinct attribute value. For instance, the attribute value 3 is highlighted to demonstrate the encoding. In this case, bitmap 3 is set to “1”, all other bits on the same horizontal position are set to “0””.3.2    EncodingThe basic bitmap index introduced above is also called equality encoded bitmap index since each bitmap indicates whether or not an attribute value equals to the key. This strategy is the most efficient for equality queries such as “temperature = 100.” Chan and Ioannidis (1998; 1999) developed two other encoding strategies that are called range encoding and interval encoding. These bitmap indices are optimized for one-sided and two-sided range queries, respectively. Anexample of a one-sided range query is “pressure < 56.7". A two-sided range query, for instance, is "35.8 < pressure < 56.7".A comparison of an equality-encoded and range-encoded bitmap index is given in Figure 2 (based on Chan & Ioannidis, 1999). Let us look at the encoding of value 2, which is highlighted in the figure. For equality encoding, the third bitmap is set to "1" (E2), whereas all other bits on the same horizontal line are set to "0". For the range-encoded bitmap index, all bits between bitmap R2 and R8 are set to "1", the remaining bits are set to "0". This encoding is very efficient for evaluating range queries. Consider, for instance, the query "A <= 4". In this case, at most one bitmap, namely bitmap R4, has to be accessed (scanned) for processing the query. All bits that are set to "1" in this bitmap fulfill the query constraint. On the other hand, for the equality-encoded bitmap index, the bitmaps E0 to E4 have to be ORed together (via the Boolean operator OR). This means that 5 bitmaps have to be accessed, as opposed to only 1 bitmap for the case of range encoding. In short, range encoding requires at most one bitmap scan for evaluating range queries, whereas equality encoding requires in the worst-case c/2 bitmap scans, where c corresponds to the number of bitmaps. Since one bitmap in range encoding contains only "1" s, this bitmap is usually not stored. Therefore, there are only c-1 bitmaps in a range-encoded index.3.3    Binning  The binning is the simplest form of bitmap indices works well for low-cardinality attributes, such as gender.The basic idea of binning is to construct a bitmap for a bin rather than for each distinct attribute value. This approach disassociates the number of bitmaps from the attribute cardinality and allows one to construct a bitmap index of a prescribed size, no matter how large the attribute cardinality is. A clear advantage of this approach is that it allows one to control the index size. However, it also introduces some uncertainty in the answers if one only uses the index.3.4    CompressionCompression is the third approach to reduce the size of bitmap indices. Since each bitmap of the bitmap index may be used separately from others, compression is typically applied on each individual bitmap. Compression is a well-researched topic and efficient compression software packages are widely available. Even though these general-purpose compression methods are effective in reducing the size of bitmaps.4    ConclusionSo, I can say that there is no basic index that is best suited for all applications. Each application has its own advantages or disadvantages. The Bitmap indexing works well in low cardinality but not for high cardinalities; we can use B-Tree for high cardinalities. Compressed Bitmap is a promising technique to overcome this problem. Nowadays, there are several fast algorithms for evaluating Boolean operators on compressed bitmaps. Another issue is that we need also some other efficient encoding techniques to lower the number of logical operations.