Bitmap indexes in DBMS Theory - Practice Problems & Coding Challenges

Challenge - 5 Problems

🧠 Conceptual

intermediate

Understanding Bitmap Index Structure

What best describes the structure of a bitmap index in a database?

A A bitmap index is a hash table mapping each distinct value to a list of row pointers.

B A bitmap index uses a bitmap (array of bits) for each distinct value in a column, where each bit represents a row indicating presence or absence of that value.

C A bitmap index stores sorted lists of row IDs for each distinct value without using bits.

D A bitmap index stores the actual data values in a compressed tree structure for faster retrieval.

💡 Hint

Think about how bits can represent presence or absence efficiently.

A bitmap index creates a bitmap for each distinct value in a column. Each bit in the bitmap corresponds to a row in the table. If the bit is 1, the row contains that value; if 0, it does not. This allows very fast logical operations for queries.

📋 Factual

intermediate

Best Use Case for Bitmap Indexes

In which scenario is a bitmap index most effective?

A When the column has low cardinality, such as gender or boolean flags.

B When the column has a high number of distinct values, like unique IDs.

C When the table is frequently updated with many insertions and deletions.

D When the column contains large text strings requiring full-text search.

💡 Hint

Consider how many distinct values the column has and how that affects bitmap size.

Bitmap indexes work best on columns with low cardinality (few distinct values) because the bitmaps remain small and efficient. High cardinality columns would create large bitmaps, reducing efficiency.

🔍 Analysis

advanced

Query Performance with Bitmap Indexes

Consider a query filtering rows where two low-cardinality columns meet certain conditions combined with AND. How does a bitmap index improve performance?

A It duplicates the data in memory to avoid disk access.

B It sorts the rows physically on disk to speed up sequential reads.

C It creates a temporary hash table for the query to speed up lookups.

D It allows combining bitmaps with bitwise AND operations to quickly find matching rows without scanning the table.

💡 Hint

Think about how bitmaps can be combined logically.

Bitmap indexes allow fast bitwise operations like AND, OR, and NOT on bitmaps representing different conditions. This lets the database quickly find rows matching multiple conditions without scanning all rows.

❓ Comparison

advanced

Bitmap Index vs B-Tree Index

Which statement correctly compares bitmap indexes and B-tree indexes?

A Bitmap indexes require more storage space than B-tree indexes for the same data.

B Bitmap indexes are better for columns with many distinct values, while B-tree indexes are better for low-cardinality columns.

C B-tree indexes support fast range queries, while bitmap indexes are less efficient for range scans.

D B-tree indexes cannot be used for equality searches, unlike bitmap indexes.

💡 Hint

Consider how each index type handles range queries and distinct values.

B-tree indexes are efficient for range queries and high-cardinality columns. Bitmap indexes excel at equality queries on low-cardinality columns but are less efficient for range scans because bitmaps represent discrete values.

❓ Reasoning

expert

Impact of Frequent Updates on Bitmap Indexes

Why are bitmap indexes generally not recommended for tables with frequent insert, update, or delete operations?

A Because updating bitmaps requires locking and can cause contention, leading to slower write performance.

B Because bitmap indexes do not support any form of concurrency control.

C Because bitmap indexes automatically rebuild the entire index on every update.

D Because bitmap indexes store data redundantly, causing excessive disk usage on updates.

💡 Hint

Think about how bitmaps are stored and updated when data changes.

Bitmap indexes use bit arrays that need to be updated when rows change. This often requires locking parts of the index, which can cause contention and slow down write operations. Hence, they are best for mostly read-only or infrequently updated tables.

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