What is Database Indexing by Bitmap Indexing approach?

Introduction

Bitmap indexing is a type of database indexing that uses bitmap vectors to represent the values of attributes in a table. In this approach, each attribute value is mapped to a bit in a bitmap vector. If the value is present in a record, the corresponding bit is set to 1 otherwise, the bit is set to 0.

Under the Hood Structure

Under the hood, a bitmap index is typically implemented as a set of bitmap vectors, one for each attribute that is indexed. Each bit in a bitmap vector represents a value of the indexed attribute, and each record in the table is represented by a set of bits that correspond to the values of the indexed attributes in the record.

Bitmap indexing is particularly useful for columns with a small number of distinct values, as the bitmap vectors can be compressed to save space. It is also very efficient for queries that involve multiple columns, as the bitwise operations can be performed quickly using modern CPUs. However, it can be less efficient for columns with a large number of distinct values, as the bitmap vectors can become very large and slow down query performance.

Example

To retrieve records from the bitmap index, a query is expressed as a set of conditions on the indexed attributes. For example, a query might ask for all records where the Department attribute is "Sales" and the Salary attribute is greater than $50,000. To answer this query, the bitmap vectors for the Department and Salary attributes are combined using bitwise operations to produce a bitmap vector that represents the set of records that satisfy the query conditions. The set of records is then retrieved by scanning the table and selecting the records that have a corresponding bit set in the bitmap vector.

Suppose we have a table of employees with the following attributes:

EmployeeID
FirstName
LastName
Department
Salary

We want to create a bitmap index on the Department and Salary attributes. We start by creating a bitmap vector for each attribute:

Department:
----------
Sales:    00000000
Marketing: 00000000

Salary:
------
0-49999:  00000000
50000-99999:  00000000

Each bit in the bitmap vectors represents a possible value of the attribute. In this case, the Department attribute has two possible values, "Sales" and "Marketing", and the Salary attribute is divided into two ranges, $0-$49,999 and $50,000-$99,999.

When a record is inserted into the table, the bitmap vectors are updated to reflect the presence of the record. For example, if we insert a record with EmployeeID 123456, FirstName "John", LastName "Smith", Department "Sales", and Salary $50,000, the bitmap vectors would be updated as follows:

Department:
----------
Sales:    10000000
Marketing: 00000000

Salary:
------
0-49999:  00000000
50000-99999:  10000000

To retrieve records from the bitmap index, a query is expressed as a set of conditions on the indexed attributes. For example, if we want to retrieve all records where the Department attribute is "Sales" and the Salary attribute is greater than $50,000, we perform the following steps:

1. Look up the bitmap vectors for the Department and Salary attributes.

2. Perform a bitwise AND operation on the two bitmap vectors to produce a new bitmap vector that represents the set of records that satisfy both conditions:

Department:
----------
Sales:    10000000
Marketing: 00000000

Salary:
------
0-49999:  00000000
50000-99999:  10000000

Result:
-------
Sales & 50000-99999:  10000000

1. Scan the table and select the records that have a corresponding bit set in the result bitmap vector:

EmployeeID    FirstName   LastName   Department  Salary
----------------------------------------------------------------
123456        John        Smith      Sales       $50,000