Bitmap Indexes Explained For Developers

What Are Bitmap Indexes?

Think about how you’d find all the red cars in a parking lot. You could walk around and check each car’s color. That’s kind of like a full table scan in a database. Not ideal for big lots.

Now, imagine you have a list for every color. For ‘red’, you mark down the parking spot number of every red car. For ‘blue’, you do the same. If you want all red cars, you just grab the ‘red’ list. Much faster, right?

That’s the core idea behind bitmap indexes. Instead of storing data row by row, a bitmap index creates a separate bitmap (a sequence of bits, 0s and 1s) for each distinct value in a column. Each bit in the bitmap corresponds to a row. If the bit is 1, it means that row has the value; if it’s 0, it doesn’t.

How Do They Work?

Let’s say we have a simple cars table:

If we create a bitmap index on the color column, we’d get something like this (simplified, imagine many more rows):

• Color ‘red’ bitmap: 10101 (Row 1, 3, and 5 are red)
• Color ‘blue’ bitmap: 01000 (Row 2 is blue)
• Color ‘green’ bitmap: 00010 (Row 4 is green)

Now, what if we want to find all red cars from 2020? Databases can use bitwise operations on these bitmaps.

1. Get the ‘red’ bitmap: 10101
2. Get the ‘2020’ bitmap (if an index exists for year, otherwise a scan might happen): Let’s assume it’s 10010 (rows 1 and 4 are from 2020).

To find cars that are both red and from 2020, the database performs a bitwise AND operation:

1
  10101 (red)
2
& 10010 (year 2020)
3
-------
4
  10000

The resulting bitmap 10000 tells the database that only row 1 matches both criteria. It can then quickly fetch row 1’s data without scanning the whole table.

This bitwise magic is incredibly fast, especially for columns with low cardinality (few distinct values) and when queries involve multiple conditions. The operations are simple and can be executed very efficiently by the CPU.

When To Use Bitmap Indexes

Bitmap indexes shine in specific scenarios:

• Low Cardinality Columns: Columns like ‘gender’ (male/female), ‘status’ (active/inactive/pending), or ‘region’ (North/South/East/West) are perfect candidates. There aren’t too many unique values to create a separate bitmap for, so the bitmaps are relatively short and efficient.
• Data Warehousing & OLAP: These systems often deal with large datasets and aggregate queries. Bitmap indexes excel at answering complex queries with multiple AND, OR, and NOT conditions quickly. Think of reports that need to filter by product category, region, and sales channel simultaneously.
• Read-Heavy Workloads: Bitmap indexes are fantastic for SELECT queries. However, they can be slower for INSERT, UPDATE, and DELETE operations. When you modify a row, you might need to update multiple bitmaps, which can be costly. So, they’re best suited for tables where data changes infrequently.

When NOT To Use Them

• High Cardinality Columns: If a column has many unique values (like user IDs, email addresses, or timestamps), the number of bitmaps would explode, and each bitmap would be very sparse (mostly zeros). This negates the benefits and can even hurt performance.
• High Write Traffic: As mentioned, frequent updates or inserts will make bitmap indexes a bottleneck. Transactional (OLTP) databases that see a lot of data modification are usually better off with B-tree indexes.
• Single-Row Lookups: If your queries are primarily fetching single rows based on a unique key, a B-tree index is generally more appropriate and efficient.

Conclusion

Bitmap indexes are a powerful tool in a database optimizer’s arsenal, particularly for analytical workloads and columns with few distinct values. They leverage bitwise operations for lightning-fast filtering across multiple conditions. Understanding their strengths and weaknesses helps you make informed decisions about indexing strategies, ultimately leading to faster, more efficient queries. Don’t blindly apply them; choose them when the characteristics of your data and workload align with their design.