Bitmap indexes in DBMS Theory - Full Explanation

Introduction

Searching large databases quickly can be slow when many records must be checked. Bitmap indexes solve this by using simple yes/no maps to speed up queries, especially when data has few unique values.

Explanation

Structure of Bitmap Indexes

A bitmap index uses a series of bits (0s and 1s) to represent whether each record has a specific value. Each distinct value in a column has its own bitmap, where a 1 means the record has that value and 0 means it does not.

Bitmap indexes represent data presence with bits, making lookups very fast and space-efficient for low-cardinality columns.

Use Cases for Bitmap Indexes

Bitmap indexes work best for columns with few unique values, like gender or status flags. They are less effective for columns with many unique values, such as names or IDs, because the bitmaps become large and less efficient.

Bitmap indexes are ideal for columns with low distinct values to speed up filtering and counting.

Query Performance with Bitmap Indexes

When a query filters on multiple conditions, bitmap indexes can combine bitmaps using simple bitwise operations like AND, OR, and NOT. This lets the database quickly find matching records without scanning all data.

Bitwise operations on bitmaps enable very fast multi-condition queries.

Storage Efficiency

Because bitmaps use only one bit per record per value, they use less space than traditional indexes for low-cardinality data. Compression techniques can further reduce storage needs by compacting long runs of 0s or 1s.

Bitmap indexes save storage space and improve speed by using compact bit representations.

Real World Analogy

Imagine a classroom where each student has a checklist for different activities like reading, sports, or music. For each activity, a sheet shows which students participate by marking a check or leaving it blank. To find students who do both reading and sports, you look at both sheets and find students checked on both.

Structure of Bitmap Indexes → Each activity sheet showing checkmarks for students participating

Use Cases for Bitmap Indexes → Activities with few participants, like a small sports team, making the sheets easy to manage

Query Performance with Bitmap Indexes → Looking at multiple sheets and finding students checked on all, using simple comparisons

Storage Efficiency → Using simple checkmarks instead of writing full names repeatedly, saving space

Diagram

Diagram

┌───────────────┐
│ Column Values │
├───────────────┤
│ Value A       │
│ 1010010       │
├───────────────┤
│ Value B       │
│ 0101101       │
└───────────────┘

Bitmaps show which records have each value.
Queries combine these bitmaps with AND/OR operations.

This diagram shows bitmap index bitmaps for two values and how they represent record presence.

Key Facts

Bitmap Index → An index using bits to represent presence or absence of values in records.

Low Cardinality → A column with few unique values, ideal for bitmap indexing.

Bitwise Operations → Logical operations like AND, OR, and NOT used to combine bitmaps.

Compression → Techniques to reduce bitmap size by compacting repeated bits.

Code Example

DBMS Theory

import sqlite3

# Create in-memory database
conn = sqlite3.connect(':memory:')
cur = conn.cursor()

# Create a table with a low-cardinality column
cur.execute('CREATE TABLE employees (id INTEGER, gender TEXT)')

# Insert sample data
cur.executemany('INSERT INTO employees VALUES (?, ?)', [
    (1, 'M'), (2, 'F'), (3, 'M'), (4, 'F'), (5, 'M')
])

# Simulate bitmap index creation for gender
# Bitmap for 'M': 1 if gender is 'M', else 0
cur.execute("SELECT id, CASE WHEN gender = 'M' THEN 1 ELSE 0 END AS bitmap_M FROM employees ORDER BY id")
bitmap_M = cur.fetchall()

# Bitmap for 'F': 1 if gender is 'F', else 0
cur.execute("SELECT id, CASE WHEN gender = 'F' THEN 1 ELSE 0 END AS bitmap_F FROM employees ORDER BY id")
bitmap_F = cur.fetchall()

print('Bitmap for M:', bitmap_M)
print('Bitmap for F:', bitmap_F)

Common Confusions

Bitmap indexes are good for all types of columns.

Bitmap indexes are good for all types of columns. Bitmap indexes work best only for columns with few unique values; for many unique values, traditional indexes are better.

Bitmaps store actual data values.

Bitmaps store actual data values. Bitmaps only store presence (1) or absence (0) of values per record, not the values themselves.

Summary

Bitmap indexes use bits to quickly show which records have certain values, making searches faster.

They work best for columns with few unique values, like gender or status.

Combining bitmaps with simple bitwise operations speeds up complex queries efficiently.