8.2.1.10 Nested-Loop Join Algorithms 嵌套循环 关联算法:

8.2.1.10 Nested-Loop Join Algorithms 嵌套循环 关联算法:


MySQL 执行关联在表之间使用一个嵌套循环算法或者变种


Nested-Loop Join Algorithm 嵌套循环算法:

一个简单的嵌套循环关联(NLJ)算法读取记录从第一个表在一个循环 一次一跳,

传递每条记录给一个嵌套循环来处理下一个表在关联里, 这个产生是被重复很多次,因为剩下的表被关联


假设一个关联在3个表t1,t2,t3 之间进行 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 嵌套循环算法:

一个Block 嵌套关联算法使用 记录buffer 读取在外部循环来减少内部循环表读取的次数。


比如,10条记录是读进到一个buffer,buffer 是被传递到下一个内部循环,


每条记录读到内部循环可以和所有10条记录比较。 降低内部表读取的次数

MySQL 使用 join buffering 在那些条件下:

1.join_buffer_size 系统变量决定了每个join buffer 的大小


buffer 的最小值是用于平面index scans,range index scans,


和关联,不使用indexes和因此执行全表扫描。

通常, 最好的方式得到快速关联是增加索引,增加join_buffer_size 的值可以得到快速的全关联当增加索引是不可能的时候

一个join buffer 是分配给每个full join 在2个表之间, 对于一个复杂的关联在多个表没有使用索引,多个join buffers是需要的

2. join buffering 可以用于当关联的类型是ALL或者index (换句话说,当没有可用的索引可以使用时,一个全表扫描被执行,

所有整个数据或者index rows 分别的).


使用buffer 对于外连接也是可用的


3.一个buffer 被分配对于每个连接可以被buffered,因此一个给定的查询可以产生使用多个join buffers.


4.一个join buffer 是不会被分配的对于第一个 nonconst table,即使它是ALL或者Index


5. 一个join buffer 是被有限分配来执行关联和释放在查询结束

6.只有关联感兴趣的列是被存储在join buffer，不是这个记录


join 先前描述用于NLJ 算法(没有buffering), 使用Buffering 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
    }
  }
}