Join algorithms (nested loop, sort-merge, hash join) in DBMS Theory - Practice Problems & Coding Challenges

Challenge - 5 Problems

🧠 Conceptual

intermediate

Understanding Nested Loop Join

Which statement best describes how a nested loop join works in database systems?

A It sorts both tables first and then merges them by scanning sequentially.

B It creates a hash table for the smaller table and probes it with rows from the larger table.

C It scans each row of the first table and for each row scans all rows of the second table to find matches.

D It uses indexes on both tables to directly find matching rows without scanning.

💡 Hint

Think about how many times the inner table is scanned for each row of the outer table.

A nested loop join works by taking each row from the first table and scanning all rows of the second table to find matching rows. This can be slow if tables are large.

📋 Factual

intermediate

Sort-Merge Join Characteristics

Which of the following is true about the sort-merge join algorithm?

A It only works if both tables have indexes on the join key.

B It requires both input tables to be sorted on the join key before merging.

C It compares every row of the first table with every row of the second table without sorting.

D It builds a hash table on the larger table and probes it with the smaller table.

💡 Hint

Consider what the 'merge' part of sort-merge join implies about the input data.

Sort-merge join requires both tables to be sorted on the join key so that they can be merged efficiently by scanning through both tables once.

🔍 Analysis

advanced

Choosing the Best Join Algorithm

Given two tables: one small and one very large, which join algorithm is generally the most efficient?

A Nested loop join, because it uses indexes to avoid scanning.

B Nested loop join, because it scans all rows of both tables repeatedly.

C Sort-merge join, because sorting is always faster than hashing.

D Hash join, because it builds a hash table on the smaller table and probes with the larger one.

💡 Hint

Think about which algorithm uses the smaller table to build a quick lookup structure.

Hash join is efficient when one table is small because it builds a hash table on the smaller table, allowing fast lookups when scanning the larger table.

❓ Comparison

advanced

Performance Differences Between Join Algorithms

Which of the following correctly compares the performance characteristics of nested loop join, sort-merge join, and hash join?

A Sort-merge join requires sorted inputs and is efficient for large datasets; hash join is efficient if enough memory is available; nested loop join is slow for large tables.

B Nested loop join is fastest for large unsorted tables; sort-merge join is slowest overall.

C Hash join always outperforms sort-merge join regardless of data size or memory.

D Nested loop join uses hashing internally; sort-merge join uses nested loops internally.

💡 Hint

Consider the requirements and typical use cases of each join algorithm.

Sort-merge join is efficient for large sorted datasets; hash join is fast if memory allows building a hash table; nested loop join is generally slow for large tables due to repeated scanning.

❓ Reasoning

expert

Memory Constraints Impact on Join Algorithm Choice

When memory is limited and cannot hold the entire smaller table for hashing, which join algorithm is most suitable?

A Sort-merge join, because it can handle large tables by sorting and merging in parts.

B None of the join algorithms can work without enough memory.

C Hash join, because it can always build a hash table regardless of memory size.

D Nested loop join, because it does not require sorting or hashing.

💡 Hint

Think about which algorithm can work efficiently even when data does not fit fully in memory.

Sort-merge join can handle large tables by sorting them in chunks and merging, making it suitable when memory is limited and hash join is not feasible.