Have you heard of Nested Loop Join? What is it and when is it used?

Nested Loop Join is one of the algorithms for joining tables in relational databases. It operates on the principle of nested loops: for each row in the first (outer) table, it iterates through all rows in the second (inner) table to find matches based on the join condition.

When to use:

• When one of the tables is very small, and iterating over it is not too costly.
• When there are no suitable indexes for more efficient join algorithms.
• When joining with conditions that are difficult to optimize with other methods.

The disadvantage is high computational complexity (O(n*m)), so for large tables, more efficient algorithms like Hash Join or Merge Join are usually used.

Example:

If you need to join an employees table with a departments table by department id, Nested Loop Join will iterate over each employee and for each, all departments to find a match.