• 首页
  • vue
  • TypeScript
  • JavaScript
  • scss
  • css3
  • html5
  • php
  • MySQL
  • redis
  • jQuery
  • 嵌套循环联接算法

    MySQL使用嵌套循环算法或其上的变体在表之间执行联接。

    • 嵌套循环加入算法
    • 块嵌套循环连接算法
    嵌套循环加入算法

    一个简单的嵌套循环联接(NLJ)算法一次从一个循环中的第一个表中读取行,然后将每一行传递给一个嵌套循环,该循环处理联接中的下一个表。重复此过程的次数与要连接的表的次数相同。

    假定将使用以下联接类型执行三个表t1t2和之间的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算法一次将行从外循环传递到内循环,所以它通常读取多次在内循环中处理的表。

    块嵌套循环连接算法

    块嵌套循环(BNL)嵌套算法使用对在外部循环中读取的行进行缓冲,以减少必须读取内部循环中的表的次数。例如,如果将10行读入缓冲区并将缓冲区传递到下一个内部循环,则可以将内部循环中读取的每一行与缓冲区中的所有10行进行比较。这将内部表必须读取的次数减少了一个数量级。

    在MySQL 8.0.18之前,当无法使用索引时,该算法适用于等联接。在MySQL 8.0.18及更高版本中,在这种情况下采用了哈希联接优化。请参见“哈希联接优化”。

    MySQL连接缓冲具有以下特征:

    • 当连接的类型为ALL或时index(换句话说,当无法使用任何可能的键并分别对数据或索引行进行完整扫描时),可以使用连接缓冲range。缓冲的使用也适用于外部联接,如“阻止嵌套循环和批处理键访问联接”所述。
    • 连接缓冲区永远不会分配给第一个非恒定表,即使它的类型是ALLindex
    • 联接中只有感兴趣的列存储在其联接缓冲区中,而不是整个行。
    • join_buffer_size系统变量来确定每个的大小联接缓冲液用于处理查询。
    • 为每个可以缓冲的连接分配一个缓冲区,因此可以使用多个连接缓冲区来处理给定查询。
    • 在执行连接之前分配连接缓冲区,并在查询完成后释放连接缓冲区。

    对于先前针对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 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
    }
    }
    }
    

    如果S是每个所存储的大小t1t2在组合联接缓冲液和C在缓冲器中的组合的数量,次表的数量t3被扫描的是:

    (S * C)/join_buffer_size 	+ 1
    

    t3扫描降低为价值join_buffer_size时增加,最高可达点join_buffer_size是大到足以容纳所有上一行组合。那时,通过增大它无法获得任何速度。