条件查询 div 执行时间 oops 直接 bin 可能 查询
5.5 版本之前,MySQL 本身只支持一种表间关联方式,就是嵌套循环 (Nested Loop)。如果关联表的数据量很大,则 join 关联的执行时间会非常长。在 5.5 以后的版本中,MySQL 通过引入 BNL 算法来优化嵌套执行
【Nested Loop Join】
NLJ 算法: 将驱动表 / 外部表的结果集作为循环基础数据,然后循环从该结果集每次一条获取数据作为下一个表的过滤条件查询数据,然后合并结果。如果有多表 join,则将前面的表的结果集作为循环数据,取到每行再到联接的下一个表中循环匹配,获取结果集返回给客户端。
Nested-Loop 的伪算法如下:
- 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
- }
- }
- }
因为普通 Nested-Loop 一次只将一行传入内层循环, 所以外层循环 (的结果集) 有多少行, 内存循环便要执行多少次. 在内部表的连接上有索引的情况下,其扫描成本为 O(Rn), 若没有索引, 则扫描成本为 O(Rn*Sn)。如果内部表 S 有很多记录,则 Simpl eNested-Loops Join 会扫描内部表很多次,执行效率非常差。
【Block Nested-Loop Join】
BNL 算法: 将外层循环的行 / 结果集存入 join buffer, 内层循环的每一行与整个 buffer 中的记录做比较,从而减少内层循环的次数.
举例来说,外层循环的结果集是 100 行,使用 NLJ 算法需要扫描内部表 100 次,如果使用 BNL 算法,先把对 Outer Loop 表 (外部表) 每次读取的 10 行记录放到 join buffer, 然后在 InnerLoop 表 (内部表) 中直接匹配这 10 行数据,内存循环就可以一次与这 10 行进行比较, 这样只需要比较 10 次,对内部表的扫描减少了 9/10。所以 BNL 算法就能够显著减少内层循环表扫描的次数.
前面描述的 query, 如果使用 join buffer, 那么实际 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
- }
- }
- }
如果 t1, t2 参与 join 的列长度只和为 s, c 为二者组合数, 那么 t3 表被扫描的次数为
(S * C)/join_buffer_size + 1
扫描 t3 的次数随着 join_buffer_size 的增大而减少, 直到 join buffer 能够容纳所有的 t1, t2 组合, 再增大 join buffer size, query 的速度就不会再变快了
1. join_buffer_size 变量决定 buffer 大小。
2. 只有在 join 类型为 all, index, range 的时候才可以使用 join buffer。
3. 能够被 buffer 的每一个 join 都会分配一个 buffer, 也就是说一个 query 最终可能会使用多个 join buffer。
4. 第一个 nonconst table 不会分配 join buffer, 即便其扫描类型是 all 或者 index。
5. 在 join 之前就会分配 join buffer, 在 query 执行完毕即释放。
6. join buffer 中只会保存参与 join 的列, 并非整个数据行。
5.6 版本及以后,优化器管理参数 optimizer_switch 中中的 block_nested_loop 参数控制着 BNL 是否被用于优化器。默认条件下是开启,若果设置为 off,优化器在选择 join 方式的时候会选择 NLJ 算法。
MySQL Block Nested-Loop Join(BNL)
来源: http://www.bubuko.com/infodetail-2271727.html