8.2.1.10 Nested-Loop Join Algorithms 8.2.1.10嵌套循环连接算法

MySQL 执行廉洁在表之间使用一个嵌套循环算法

嵌套循环连接算法

一个简单的nested-loop join(NLJ)算法一次读取一行从循环的第一个表读取数据,把每一行传递给一个嵌套循环来处理下一个表。

这个过程是重复的很多次因为还有余下的被关联的表。

假设关联在3个表t1,t2和t3 使用下面的关联类型:

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

因为嵌套循环算法一次传递一行从外部循环到内部循环, 它典型的读取表处理内部循环很多次

块嵌套循环连接算法

一个Block Nested-Loop (BNL) 连接算法使用buffering of rows 从外部循环读取,

来减少内部表读取的次数。比如, 如果19行被读取buffer，buffer被传递给下一个内部循环,

从内部循环读取的每条记录可以和所有的10条记录匹配。降低了内部表的读取次数

ALL: 扫描全表
index: 扫描全部索引树
range: 扫描部分索引，索引范围扫描，对索引的扫描开始于某一点，返回匹配值域的行，常见于between、<、>等的查询
ref: 非唯一性索引扫描，返回匹配某个单独值的所有行。常见于使用非唯一索引即唯一索引的非唯一前缀进行的查找
eq_ref：唯一性索引扫描，对于每个索引键，表中只有一条记录与之匹配。常见于主键或唯一索引扫描
const, system: 当MySQL对查询某部分进行优化，并转换为一个常量时，使用这些类型访问。如将主键置于where列表中，MySQL就能将该查询转换为一个常量。system是const类型的特例，当查询的表只有一行的情况下，使用system。
NULL: MySQL在优化过程中分解语句，执行时甚至不用访问表或索引。

在这些情况下,MySQL 使用join buffering

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

Join buffering 可以用于当join是ALL或者index 类型(换句话说,没有keys 可以使用,必须是全扫描)，或者range.

在Mysql 5.6中, 使用buffering 是扩展了适用于外部表。

一个buffer 被分配给每个连接,因此一个给定的查询可能被处理使用多个join buffers.

一个join buffer 永远不会被分配对于第一个非const表，即使它的类型是ALL或者index .

一个join buffer 被分配在执行关联前,查询结束后释放。

唯一感兴趣的列来关联是存储在join buffer，不是所有的记录。

例如 join描述先前的用于NLJ 算法(没有buffering)， join如下使用join buffering：

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

如果S 是每个存储的t1,t2 组合的大小,组合是join buffer