Nested-Loop Join Algorithms

MySQL使用嵌套循环算法来实现多表之间的联接。

Nested-Loop Join Algorithms

一个简单的嵌套循环联接（NLJ）算法，循环从第一个表中依次读取行，取到每行再到联接的下一个表中循环匹配。这个过程会重复多次直到剩余的表都被联接了。 假设表t1、t2、t3用下面的联接类型进行联接：

Table   Join Type
t1      range
t2      ref
t3      ALL

如果使用的是简单NLJ算法，那么联接的过程像这样：

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
    }
  }
}

因为NLJ算法是通过外循环的行去匹配内循环的行，所以内循环的表会被扫描多次。

Block Nested-Loop Join Algorithm

一个块嵌套循环联接（BNL）算法，将外循环的行缓存起来，读取缓存中的行，减少内循环的表被扫描的次数。例如，如果10行读入缓冲区并且缓冲区传递给下一个内循环，在内循环读到的每行可以和缓冲区的10行做比较。这样使内循环表被扫描的次数减少了一个数量级。 MySQL使用联接缓冲区时，会遵循下面这些原则：

• join_buffer_size系统变量的值决定了每个联接缓冲区的大小。
• 联接类型为ALL、index、range时（换句话说，联接的过程会扫描索引或数据时），MySQL会使用联接缓冲区。
• 缓冲区是分配给每一个能被缓冲的联接，所以一个查询可能会使用多个联接缓冲区。
• 联接缓冲区永远不会分配给第一个表，即使该表的查询类型为ALL或index。
• 联接缓冲区联接之前分配，查询完成之后释放。
• 使用到的列才会放到联接缓冲区中，并不是所有的列。

上面的例子使用的是NLJ算法（没有使用缓存），使用缓存的联接方式像下面这样：

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
    }
  }
}

对上面的过程解释如下： 1. 将t1、t2的联接结果放到缓冲区，直到缓冲区满为止； 2. 遍历t3，内部再循环缓冲区，并找到匹配的行，发送到客户端； 3. 清空缓冲区； 4. 重复上面步骤，直至缓冲区不满； 5. 处理缓冲区中剩余的数据，重复步骤2。

设S是每次存储t1、t2组合的大小，C是组合的数量，则t3被扫描的次数为：

(S * C)/join_buffer_size + 1

由此可见，随着join_buffer_size的增大，t3被扫描的次数会较少，如果join_buffer_size足够大，大到可以容纳所有t1和t2联接产生的数据，t3只会被扫描1次。

英文地址：http://dev.mysql.com/doc/refman/5.5/en/nested-loop-joins.html