Algorithms: Nested Loop Join

Nested Loop Joins are used to join two arrays of elements together based on a condition. It is commonly used in RDBMS's.

Documentation

wikipedia	https://en.wikipedia.org/wiki/Nested_loop_join
MySQL-5.7 docs	https://dev.mysql.com/doc/refman/5.7/en/nested-loop-joins.html

Basics

users = [
    {id: 1, firstname: 'darth',   lastname: 'vader'},
    {id: 2, firstname: 'luke',    lastname: 'skywalker'},
    {id: 3, firstname: 'obi-wan', lastname: 'kenobi'},
]

faction_users = [
    {id: 1, name: 'imperials', user_id: 1},
    {id: 2, name: 'rebels', user_id: 2},
    {id: 3, name: 'rebels', user_id: 3},
]

For every row in the outer loop,
Search every row in the inner loop,
When a condition matches, add all columns to a combined result set.

SELECT *
FROM users
INNER JOIN faction_users
ON faction_users.user_id = users.id

results = []
for user in users:
    for faction_user in faction_users:
        if faction_users.user_id != user.id:
            continue
        results.append(users.update(faction_users))

Variations

The above example is a NAIVE nested loop join.
There are other variations.

- naive nested loop join: all outer/inner rows must be searched (full table scan)
- indexed nested loop join: an index us used to reduce the number of rows to be searched in each table
- block nested loop join: loads chunks of rows from both tables into memory