Fun MySQL fact of the day: everything is a nested-loop join

Yesterday, we discussed that all queries in MySQL are joins, including single-table queries, but today, we'll start to focus on multi-table joins.

When joining multiple tables, MySQL may use one of several joining algorithms. For example, MySQL can join two tables with a Nested-Loop Join (NLJ). Or a variant of a Nested-Loop Join. Or another variant of a Nested-Loop Join. We'll talk about the latter two later this week, but today, we'll talk about the Nested-Loop Join. To start, what is a Nested Loop Join? Simply,

for each outer_row in table1 matching the query
    if outer_row matches where clause
        for each inner_row in table2 matching outer_row
            if inner_row matches where clause
                ... more nesting as necessary ...
                send to network
            end if
        end for
    end if
end for

Going back to yesterday, I think this will help us start to appreciate why "all queries are joins": it makes the code easier to write. For example, the code doesn't change for joins with one, two, three, or n tables. Of course, in the MySQL source code, this isn't implemented as a bunch of for loops. Instead, it's implemented with function pointers in the actual JOIN, creating a recursive call chain. For example, given a simple join query: sub_select calls evaluate_join_record, which, for any matching rows, calls sub_select, which calls evaluate_join_record, which for any matching rows calls...