Nested loop join

from the Artful MySQL Tips List


A nested loop join joins two tables p and q using this algorithm ...
for each row rp in table p 
  for each row rq in table q
    if rp and rq satisfy the join condition
      output the comjoined rows  
The algorithm ...

- needs rowcountp * blockcountq + blockcountp block transfers, and

- needs rowcountp + blockcountp seeks. - runs in O(|rowcountp||rowcountq|) I/Os.

It can be improved to a block nested loop by using read blocks:

for each blockp in p
  for each row in q
    for each row in blockq 
      if the rows the join condition
        output the conjoined rows
For more see https://mariadb.com/kb/en/mariadb/block-based-join-algorithms/

Last updated 16 Aug 2019


Return to the Artful MySQL Tips page