Join algorithms (nested loop, sort-merge, hash join) in DBMS Theory - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is a Nested Loop Join in database systems?

A Nested Loop Join compares each row of one table with every row of another table to find matching pairs. It is simple but can be slow for large tables.

intermediate

How does a Sort-Merge Join work?

Sort-Merge Join first sorts both tables on the join key, then merges them by scanning through both sorted lists to find matching rows efficiently.

intermediate

What is the main idea behind a Hash Join?

Hash Join builds a hash table on the smaller table using the join key, then scans the larger table to find matches by looking up the hash table, making it fast for large data.

beginner

Which join algorithm is generally best for small tables?

Nested Loop Join is often best for small tables because it is simple and does not require sorting or hashing.

intermediate

Why is Sort-Merge Join efficient for already sorted data?

Because it can merge the two sorted tables in a single pass without extra sorting, reducing the time needed to find matching rows.

Which join algorithm compares every row of one table with every row of another?

A Index Join

B Sort-Merge Join

C Nested Loop Join

D Hash Join

Nested Loop Join works by checking each row of one table against all rows of the other.

What is the first step in a Sort-Merge Join?

A Sort both tables on the join key

B Build a hash table

C Scan the larger table

D Compare each row pair

Sort-Merge Join starts by sorting both tables on the join key to prepare for merging.

Hash Join is most efficient when:

A Both tables are very small

B One table is much smaller than the other

C Both tables are already sorted

D Tables have no indexes

Hash Join builds a hash table on the smaller table to quickly find matches in the larger table.

Which join algorithm requires sorting the tables?

A Sort-Merge Join

B Hash Join

C Nested Loop Join

D Cartesian Join

Sort-Merge Join requires sorting both tables before merging.

Which join algorithm is simplest but can be slow for large tables?

A Hash Join

B Sort-Merge Join

C Index Join

D Nested Loop Join

Nested Loop Join is simple but inefficient for large tables due to many comparisons.

Explain how a Hash Join works and why it is efficient for large tables.

Think about dividing work between small and large tables using a hash.

Compare Nested Loop Join and Sort-Merge Join in terms of when each is best used.

Consider table size and sorting when choosing the join.