Nested-Loop Join Algorithms

MySQL使用嵌套循环算法来实现多表之间的联接。

Nested-Loop Join Algorithms

一个简单的嵌套循环联接(NLJ)算法,循环从第一个表中依次读取行,取到每行再到联接的下一个表中循环匹配。这个过程会重复多次直到剩余的表都被联接了。 假设表t1、t2、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 Nested-Loop Join Algorithm

一个块嵌套循环联接(BNL)算法,将外循环的行缓存起来,读取缓存中的行,减少内循环的表被扫描的次数。例如,如果10行读入缓冲区并且缓冲区传递给下一个内循环,在内循环读到的每行可以和缓冲区的10行做比较。这样使内循环表被扫描的次数减少了一个数量级。 MySQL使用联接缓冲区时,会遵循下面这些原则:

  • join_buffer_size系统变量的值决定了每个联接缓冲区的大小。
  • 联接类型为ALL、index、range时(换句话说,联接的过程会扫描索引或数据时),MySQL会使用联接缓冲区。
  • 缓冲区是分配给每一个能被缓冲的联接,所以一个查询可能会使用多个联接缓冲区。
  • 联接缓冲区永远不会分配给第一个表,即使该表的查询类型为ALL或index。
  • 联接缓冲区联接之前分配,查询完成之后释放。
  • 使用到的列才会放到联接缓冲区中,并不是所有的列。

上面的例子使用的是NLJ算法(没有使用缓存),使用缓存的联接方式像下面这样:

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

对上面的过程解释如下: 1. 将t1、t2的联接结果放到缓冲区,直到缓冲区满为止; 2. 遍历t3,内部再循环缓冲区,并找到匹配的行,发送到客户端; 3. 清空缓冲区; 4. 重复上面步骤,直至缓冲区不满; 5. 处理缓冲区中剩余的数据,重复步骤2。

设S是每次存储t1、t2组合的大小,C是组合的数量,则t3被扫描的次数为:

(S * C)/join_buffer_size + 1

由此可见,随着join_buffer_size的增大,t3被扫描的次数会较少,如果join_buffer_size足够大,大到可以容纳所有t1和t2联接产生的数据,t3只会被扫描1次。

英文地址:http://dev.mysql.com/doc/refman/5.5/en/nested-loop-joins.html

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏张善友的专栏

轻型的ORM类Dapper

Dapper是一个轻型的ORM类。代码就一个SqlMapper.cs文件,主要是IDbConnection的扩展方法,编译后就40K的一个很小的dll。官方站点...

21690
来自专栏张善友的专栏

ASP.NET SignalR HubPipelineModule

ASP.NET SignalR 1.0 实现的一个特性HubPipeline -实现任何消息incoming和outgoing的拦截。SignalR HubPi...

22670
来自专栏大内老A

Enterprise Library Policy Injection Application Block 之二: PIAB设计和实现原理

在前面一篇文章中,我对Enterprise Library中的PIAB (Policy Injection Application Block)作了简单的介绍。...

22460
来自专栏包子铺里聊IT

How to design and implement a blocking queue?

Question: Blocking queue related question often gets asked from Google, LinkedI...

347120
来自专栏我的小碗汤

爬虫遇到了点问题

golang爬珍爱网代码优化后,运行报了如下的错,找了半小时才找到原因,在此记录一下。

26840
来自专栏me的随笔

.NET中数据访问方式(一):LINQ

语言集成查询(Language-Integrated Query),简称LINQ,.NET中的LINQ体系如下图所示:

9530
来自专栏程序员的SOD蜜

.net访问PostgreSQL数据库发生“找不到函数名”的问题追踪

    PostgreSQL是一个使用广泛的免费开源的数据库,与MySQL比较,它更适合复杂的企业计算任务,而MySQL在互联网领域应用更为广泛,究其原因,可能...

37570
来自专栏数据分析

C# 调用PowerShell方法

PowerShell应为编写和运行都很方便,所以为了重复利用,经常写了一些小方法或者PS代码片段。使用的时候可能会很难找到自己想要的那个方法,如果要是有一个界面...

44340
来自专栏安恒网络空间安全讲武堂

逆向专题 | Writeup分享一

逆向WP分享一 0x01.re4 首先我们先点开运行试玩一下,大意就是让你输入正确的用户名和密码就能拿到flag,接下来进入正题。 ? 丢进IDA中,先shi...

24590
来自专栏跟着阿笨一起玩NET

.NET深入解析LINQ框架(六:LINQ执行表达式)

在看本篇文章之前我假设您已经具备我之前分析的一些原理知识,因为这章所要讲的内容是建立在之前的一系列知识点之上的,为了保证您的阅读顺利建议您先阅读本人的LINQ系...

7210

扫码关注云+社区

领取腾讯云代金券