Bitmap indexes in DBMS Theory - Step-by-Step Execution

Concept Flow - Bitmap indexes

Start Query

↓

Identify Column for Bitmap Index

↓

Create Bitmap for Each Distinct Value

↓

Store Bitmaps Efficiently

↓

Use Bitmap Index to Filter Rows

↓

Combine Bitmaps with AND/OR for Complex Queries

↓

Return Filtered Rows

↓

End Query

The flow shows how a bitmap index is created for a column, then used to quickly filter rows by combining bitmaps for query conditions.

Execution Sample

DBMS Theory

Column: Color
Values: Red, Blue, Green
Bitmap Index:
Red: 1 0 0 1 0
Blue: 0 1 0 0 1
Green: 0 0 1 0 0

This bitmap index represents which rows have each color value using bits.

Analysis Table

Step	Action	Bitmap Created	Bitmap State	Resulting Rows
1	Scan column values	None	None	All rows considered
2	Create bitmap for 'Red'	Red: 1 0 0 1 0	Red bitmap set	Rows 1 and 4 marked
3	Create bitmap for 'Blue'	Blue: 0 1 0 0 1	Blue bitmap set	Rows 2 and 5 marked
4	Create bitmap for 'Green'	Green: 0 0 1 0 0	Green bitmap set	Row 3 marked
5	Query: Color = Red OR Blue	Red OR Blue	1 1 0 1 1	Rows 1,2,4,5 selected
6	Query: Color = Red AND Row 4	Red AND Row 4	0 0 0 1 0	Only Row 4 selected
7	End	Final bitmaps used	Final bitmaps combined	Filtered rows returned

💡 All bitmaps created and combined to filter rows as per query conditions.

State Tracker

Variable	Start	After Step 2	After Step 3	After Step 4	After Step 5	After Step 6	Final
Red Bitmap	None	1 0 0 1 0	1 0 0 1 0	1 0 0 1 0	1 1 0 1 1	0 0 0 1 0	0 0 0 1 0
Blue Bitmap	None	None	0 1 0 0 1	0 1 0 0 1	0 1 0 0 1	0 1 0 0 1	0 1 0 0 1
Green Bitmap	None	None	None	0 0 1 0 0	0 0 1 0 0	0 0 1 0 0	0 0 1 0 0
Combined Bitmap	None	None	None	None	1 1 0 1 1	0 0 0 1 0	0 0 0 1 0

Key Insights - 3 Insights

Why do bitmap indexes use bits instead of storing actual values?

Bitmap indexes use bits to represent presence or absence of a value in rows, making filtering very fast and storage efficient, as shown in steps 2-4 where each color is represented by a bitmap.

How does combining bitmaps with AND/OR help in queries?

Combining bitmaps with AND/OR lets the database quickly find rows matching multiple conditions without scanning all rows, as seen in step 5 where Red OR Blue bitmaps combine to select multiple rows.

Can bitmap indexes be used for columns with many distinct values?

Bitmap indexes work best for columns with few distinct values because each distinct value needs a bitmap; too many distinct values create many bitmaps and reduce efficiency.

Visual Quiz - 3 Questions

Look at the execution table at step 5. What rows are selected when querying Color = Red OR Blue?

A Rows 1, 2, 4, 5

B Rows 1, 3, 4

C Rows 2, 3, 5

D Rows 3 and 4 only

💡 Hint

Check the 'Resulting Rows' column at step 5 in the execution table.

According to the variable tracker, what is the Red Bitmap after step 6?

A 0 1 0 0 1

B 1 0 0 1 0

C 0 0 0 1 0

D 0 0 1 0 0

💡 Hint

Look at the 'Red Bitmap' row under 'After Step 6' in the variable tracker.

If the column had 100 distinct values instead of 3, what would likely happen to the bitmap index?

A It would be more efficient because more bitmaps mean faster queries.

B It would be less efficient due to many bitmaps increasing storage and processing.

C It would not change anything.

D It would automatically convert to a B-tree index.

💡 Hint

Refer to the key moment about bitmap indexes and distinct values.

Concept Snapshot

Bitmap indexes use bits to represent presence of values in rows.
Each distinct value has a bitmap showing which rows contain it.
Queries combine bitmaps with AND/OR to filter rows quickly.
Best for columns with few distinct values.
Efficient for complex queries on low-cardinality data.

Full Transcript

Bitmap indexes work by creating a bit array for each distinct value in a column. Each bit represents whether a row has that value. When a query runs, the database combines these bitmaps using logical operations like AND and OR to quickly find matching rows. This method is very fast and space-efficient for columns with few distinct values. The execution steps show creating bitmaps for colors Red, Blue, and Green, then combining them to answer queries. Beginners often wonder why bits are used and how combining bitmaps helps; the key is fast filtering without scanning all rows. Bitmap indexes are less effective for columns with many distinct values because that creates many bitmaps, increasing storage and slowing queries.