MySQL的Nested Loop算法

原文地址:http://dev.mysql.com/doc/refman/5.0/en/nested-loop-joins.html
普通Nested-Loop算法:
有以下join:
Table   Join Type
t1      range
t2      ref
t3      ALL
实际join示意:
for each row in t1 matching range {
 for each row in t2 matching reference key {
   for each row in t3 {
     if row satisfies join conditions,
     send to client
   }
 }
}
因为普通Nested-Loop一次只将一行传入内存循环, 所以外层循环有多少行, 内存循环便要执行多少次.
Block Nested-Loop Join:
这种算法指的是使用join buffer的Nested Loop, 将外层循环的行读进buffer, 从而减少内层循环的次数. 例如, 如果读入了10行进入join buffer, 那么内存循环就可以一次与这10行进行比较, 这样就能够显著减少内层循环表扫描的次数.
MySQL使用Join Buffer有以下要点:
1. join_buffer_size变量决定buffer大小
2. 只有在join类型为all, index, range的时候才可以使用join buffer
3. 能够被buffer的每一个join都会分配一个buffer, 也就是说一个query最终可能会使用多个join buffer
4. 第一个nonconst table不会分配join buffer, 即便其扫描类型是all或者index
5. 在join之前就会分配join buffer, 在query执行完毕即释放
6. join buffer中只会保存参与join的列, 并非整个数据行

前面描述的query, 如果使用join buffer, 那么实际join示意如下:

for each row in t1 matching range {
 for each row in t2 matching reference key {
   store used columns from t1, t2 in join buffer
   if buffer is full {
     for each row in t3 {
       for each t1, t2 combination in join buffer {
         if row satisfies join conditions,
         send to client
       }
     }
     empty buffer
   }
 }
}

if buffer is not empty {
 for each row in t3 {
   for each t1, t2 combination in join buffer {
     if row satisfies join conditions,
     send to client
   }
 }
}

如果t1, t2参与join的列长度只和为s, c为二者组合数, 那么t3表被scan的次数为
(S * C)/join_buffer_size + 1
随着join_buffer_size的增大, t3将减少, 知道join buffer能够容纳所有的t1, t2组合, 到了这点以后, 再增大join buffer size, query的速度就不会再变快了.