本文问题

1. 什么是外联接，什么是内联接？
2. MySQL中的JOIN语法与标准SQL语法有什么不同？
3. MySQL Join算法有几种？
4. NLJ算法的过程是怎样的？
5. BNL算法的过程是怎样的？

join语法

外联接和内联接

• 内联接：INNER JOIN是内联接
  内连接中，结果中只包括同时符合WHERE条件及ON条件的行
• 外联接：LEFT JOIN和RIGHT JOIN都是外联接
  外联接中，T2中的行可以不符合ON条件，如果T2中的没有符合ON条件的行，使用NULL代替T2中的列值

# 联接条件使用`ON`表示
# 外联接
SELECT * FROM T1 LEFT JOIN T2 ON T1.C1=T2.C2
# 内联接
SELECT * FROM T1 INNER JOIN T2 ON T1.C1=T2.C2

MySQL对JOIN语法的扩展

MySQL中，可以将多个表放在括号中，表示多表内联接：

SELECT * FROM t1 LEFT JOIN (t2, t3, t4)
                 ON (t2.a=t1.a AND t3.b=t1.b AND t4.c=t1.c)
# 等同与
SELECT * FROM t1 LEFT JOIN (t2 CROSS JOIN t3 CROSS JOIN t4)
                 ON (t2.a=t1.a AND t3.b=t1.b AND t4.c=t1.c)

在MySQL中，CROSS JOIN在语法上等同与INNER JOIN,他们可以互相替代。在标准SQL中，他们是不同的，INNER JOIN可以使用ON子句，CROSS JOIN不行。

Join算法

MySQL在表中执行join联结使用nested-loop算法或该算法的变体

• Nested-Loop Join(NLJ)
• Block Nested-Loop Join(BNL)

Nested-Loop Join算法

简单的nested-loop join(NLJ)算法是一次将第一个表中的一行读取到循环中，将每行放入到一个处理下一个join的表的嵌套循环中。如果仍有其他表加入，重复这个过程。
假设有一个在t1,t2,t3三个中的join操作，执行以下类型的join：

Table   Join Type
t1      range
t2      ref
t3      ALL

如果使用简单NLJ算法，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
    }
  }
}

由于NLJ算法从外循环到内循环处理行数据，通常会多次读取内循环中的表。

Block Nested-Loop Join算法

Block Nested-Loop(BNL)算法缓冲在外循环中读取的行，来减少读取内循环表的次数。例如，如果将10行数据读取到缓冲区中，然后将缓冲区传入到内循环，内循环中读取的行可以一次与缓冲区中的10行数据进行对比，这可以减少读取内循环中的表的次数。

MySQL join缓冲区具有以下特征：

• 当join类型为ALL或index，或者为range时，可以使用join缓冲区。缓冲区也可以应用于外联接。
• 即使类型为ALL或index，join buffer不会分配给非常量表。
• 只将join相关的列存储到join buffer，不会将整行都存储到join buffer中
• join_buffer_size决定了处理查询时每个join buffer的大小
• 为每个可以被缓冲的join分配缓冲区，所以一个查询在处理过程中可能会使用多个缓冲区
• 缓冲区在执行join前分配，在查询完成后释放

对于之前NLJ算法的示例，如果使用join buffer，过程如下：

# 就是每当join buffer满后，对内层的表进行一次扫描并返回结果，然后清空join buffer。
# 由于数据量不一定会总是填满join buffer。最后还要再检查一次join buffer，如果不为空的话，再对内层的表进行一次扫描

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
        }
      }  # for each row in t3 循环结束
      empty join buffer
    } #if buffer is full 循环结束
  } # for each row in t2 循环结束
} # for each row in t1 循环结束

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组合大小，C是组合数量。扫描t3表的次数是:
(S * C)/join_buffer_size + 1
增加join_buffer_size可以降低t3的扫描次数，直到join_buffer_size足够大，可以容纳所有的行组合，在这种情况下，增加缓冲区不能继续提升性能。

问题答案

1. 什么是外联接，什么是内联接？

• 内联接：INNER JOIN是内联接
  内连接中，结果中只包括同时符合WHERE条件及ON条件的行
• 外联接：LEFT JOIN和RIGHT JOIN都是外联接
  外联接中，T2中的行可以不符合ON条件，如果T2中的没有符合ON条件的行，使用NULL代替T2中的列值

2. MySQL中的JOIN语法与标准SQL语法有什么不同？

• MySQL可以将多个表放在括号中，表示多表内联接，如(T2,T3,T4)=(T2 CROSS JOIN T3 CROSS JOIN T3)。标准SQL不支持这么写
• MySQL中的CROSS JOIN等同与INNER JOIN。标准SQL中，INNER JOIN可以包含ON条件，CROSS JOIN只能使用WHERE条件

3. MySQL Join算法有几种？区别是什么？
   2种
   Nested-Loop Join算法，简称NLJ
Block Nested-Loop Join算法，简称BNL
BNL算法使用缓冲区缓存外层表的数据，以减少内层表的循环查询过程。
4. NLJ算法的过程是怎样的？
   读取第一个表中符合条件的行，将其放入到下层循环中，进入下一层循环处理（检查该行数据是否匹配其他条件），如果有其他要join的表，重复该过程。
5. BNL算法的过程是怎样的？
   将第一个表中符合条件的行中于join相关的列放入到join buffer中
   当join bufffer满后，将join buffer放入下层循环中，进入下一层循环处理（检查join buffer中的行数据是否匹配其他条件），如果有其他要join的表，重复该过程。在循环中，返回匹配的行。
   处理结束后清空join buffer，对第一个表继续进行循环
   循环结束后，检查join buffer是否为空，如果join buffer不为空，检查join buffer中的行数据是否匹配其他条件。