Nested loops in MySQL

Question

In this O'Reilly presentation, there is a paragraph introducing some key concepts for understanding MySQL's EXPLAIN:

What is a JOIN?

• Everything is a JOIN, because MySQL always uses nested-loops
• Even a single-table SELECT or a UNION or a subquery

Can anyone explain how this works for a single table SELECT?

Answer 1

Nested loops is one way of processing joins:

for each row of table A
  if this row matches where clauses
    for each row of joined table B
      if this row matches where clauses and join clauses
        accept row
      end
    end
  end
end

That can be optimized with indexes quite a bit, by doing "for each row found at key K in some index" instead of "each row of table A", and the same with table B.

The presentation is saying this is the only way MySQL processes joins. There are other methods than can be used, but MySQL doesn't implement them. This OraFAQ entry gives several that Oracle implements: http://www.orafaq.com/tuningguide/join%20methods.html Similarly: http://oracle-online-help.blogspot.com/2007/03/nested-loops-hash-join-and-sort-merge.html

"Everything is a join" is just an implementation detail, I believe. Not really that important.