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.

Practice

1. What is the main advantage of using bitmap indexes in a database?

easy

A. They improve write performance for frequent updates

B. They reduce the size of the database tables

C. They automatically backup the database

D. They speed up queries on columns with few unique values

Solution

1. Step 1: Understand the purpose of bitmap indexes

   Bitmap indexes are designed to speed up searches on columns that have a small number of distinct values, like gender or status.

2. Step 2: Compare options with this purpose

   Only They speed up queries on columns with few unique values correctly states that bitmap indexes speed up queries on such columns. Other options describe unrelated features.

3. Final Answer:

   They speed up queries on columns with few unique values -> Option D

4. Quick Check:

   Bitmap indexes = speed up queries on low-cardinality columns [OK]

Hint: Bitmap indexes help when column values repeat often [OK]

Common Mistakes:

• Thinking bitmap indexes improve write speed
• Confusing bitmap indexes with data compression
• Assuming bitmap indexes backup data automatically

2. Which of the following is the correct way to describe a bitmap index?

easy

A. An index that stores row pointers in a tree structure

B. An index that stores full copies of data rows

C. An index that uses bits to represent the presence of values

D. An index that hashes values for quick lookup

Solution

1. Step 1: Recall bitmap index structure

   Bitmap indexes use bits (0 or 1) to indicate whether a row contains a specific value in a column.

2. Step 2: Match description to options

   An index that uses bits to represent the presence of values correctly describes this bit-based representation. Other options describe different index types.

3. Final Answer:

   An index that uses bits to represent the presence of values -> Option C

4. Quick Check:

   Bitmap index = bit representation of data presence [OK]

Hint: Bitmap means bits show if value exists in row [OK]

Common Mistakes:

• Confusing bitmap indexes with B-tree indexes
• Thinking bitmap indexes store full data rows
• Assuming bitmap indexes use hashing

3. Consider a column Gender with values 'M' or 'F' in a table of 1000 rows. How does a bitmap index represent this data?

medium

A. Two bitmaps, one for 'M' and one for 'F', each with 1000 bits

B. One bitmap with 2000 bits combining both values

C. A bitmap with 1000 bits storing the actual characters 'M' or 'F'

D. A bitmap that stores row numbers where values appear

Solution

1. Step 1: Understand bitmap index for low-cardinality columns

   For each distinct value, a bitmap index creates a bitmap with one bit per row indicating presence (1) or absence (0).

2. Step 2: Apply to 'Gender' column

   Since 'Gender' has two values ('M' and 'F'), there will be two bitmaps, each 1000 bits long, one for 'M' and one for 'F'.

3. Final Answer:

   Two bitmaps, one for 'M' and one for 'F', each with 1000 bits -> Option A

4. Quick Check:

   Bitmap per distinct value = two bitmaps of 1000 bits [OK]

Hint: One bitmap per distinct value, bits equal to rows [OK]

Common Mistakes:

• Thinking bitmap stores actual characters
• Assuming one combined bitmap for all values
• Confusing bitmap with row number storage

4. A bitmap index is used on a column that is frequently updated. What is the likely problem?

medium

A. Bitmap indexes improve update speed but slow down queries

B. Bitmap indexes slow down updates and cause locking issues

C. Bitmap indexes automatically adjust to frequent updates without issues

D. Bitmap indexes convert updates into batch inserts

Solution

1. Step 1: Recall bitmap index behavior on updates

   Bitmap indexes are not ideal for columns with frequent updates because changing bits can cause locking and slow performance.

2. Step 2: Evaluate options

   Bitmap indexes slow down updates and cause locking issues correctly states that bitmap indexes slow down updates and cause locking. Other options are incorrect or misleading.

3. Final Answer:

   Bitmap indexes slow down updates and cause locking issues -> Option B

4. Quick Check:

   Frequent updates + bitmap index = slow and locking [OK]

Hint: Bitmap indexes bad for frequent updates [OK]

Common Mistakes:

• Assuming bitmap indexes speed up updates
• Thinking bitmap indexes handle updates automatically
• Believing bitmap indexes convert updates to inserts

5. In a data warehouse, a bitmap index is created on a Region column with 5 distinct values. Which scenario best explains why bitmap indexes are preferred here?

hard

A. The column has few unique values and queries often filter by region

B. The column is updated every minute with new region codes

C. The column stores large text descriptions of regions

D. The column has millions of unique region codes

Solution

1. Step 1: Identify characteristics suitable for bitmap indexes

   Bitmap indexes work best on columns with few unique values and mostly read-only data, like in data warehouses.

2. Step 2: Analyze each option

   The column has few unique values and queries often filter by region fits perfectly: few unique values and frequent filtering. Options B, C, and D describe unsuitable scenarios.

3. Final Answer:

   The column has few unique values and queries often filter by region -> Option A

4. Quick Check:

   Few unique values + read-heavy queries = bitmap index ideal [OK]

Hint: Bitmap indexes suit low-cardinality, read-heavy columns [OK]

Common Mistakes:

• Using bitmap indexes on frequently updated columns
• Applying bitmap indexes to high-cardinality columns
• Confusing bitmap indexes with full-text indexes