7.2、NLJ和BNL
2020-07-28 本文已影响0人
此间有道
MySQL使用嵌套循环算法或其变种来实现表之间的关联。
假设有三张表如下；
Table Join Type
t1 range
t2 ref
t3 ALL
一、NLJ（Nested-Loop Join Algorithm）
NLJ可以理解为关联多表时，执行循环遍历和嵌套操作来筛选结果集。
假如t1,t2,t3的行数分别为x,y,z，那么扫描行数n=xyz。
// 官网伪代码
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
}
}
}
二、BNL（Block Nested-Loop Join Algorithm）
BNL可以理解为在NLJ的基础上的变种，通过引入join buffer来缓存一批外层的行，减少遍历的次数。
假如t1,t2,t3的行数分别为x,y,z，joinbuffer一次可容纳j条记录，那么扫描行数n=xyz/j。
// 官方伪代码
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 join 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
}
}
}
BNL
