MySQL-join算法

MySQL-join算法

起男 79 2025-01-10

MySQL-join算法

sql连接查询（join）可以同时获取多个表中的数据。通常实现连接查询算法有：嵌套循环连接、哈希连接和排序合并连接

MySQL支持其中的嵌套循环连接和哈希连接

嵌套循环连接

嵌套循环连接（nested loop join）是一种最基本的连接实现算法。它从驱动表中获取数据，然后为每一行数据遍历一次被驱动表

在具体的算法实现上又被分为了SNL、INL和BNL

SNL

SNL（simple nested loop join）这种算法实现简单就是一个双重的for循环，将驱动表中的每一行数据，拿到被驱动表中进行逐行匹配。匹配的次数就是两表行数的乘积

由于这种算法效率太低，MySQL在实现上并不会使用这种算法

INL

INL（index nested loop join）当被驱动表关联字段可以使用索引时使用这种算法。这种算法的匹配次数大大减少，匹配的次数减少到驱动表行数乘以被驱动表索引的树高

BNL

BNL（block nested loop join）当没有办法使用INL时，数据库也不会使用SNL算法，而是BNL。数据库会创建一个缓存空间，将一定数据量的驱动表数据缓存到此空间，然后批量的到被驱动表中进行匹配。匹配次数虽然没有INL那么少，但是优于SNL

哈希连接

哈希连接（hash join）是为驱动表中的数据创建一个哈希表，然后再用这个哈希表和被驱动表进行匹配。

注意：

  • 哈希连接是不支持范围连接条件的
  • 哈希连接是不会利用被驱动表的索引的
  • 哈希连接会在内存中创建哈希表。如果数据量太大，则会在磁盘创建临时表

MySQL在8.0.18版本中引入了哈希连接，使用此连接时需要满足：表之间的连接是等值连接，并且无法使用索引。并且连接查询中任何两个表之间不满足等值连接，整个查询中的所有join都无法使用哈希连接

排序合并连接

排序合并连接（sort merge join）先将驱动表和被驱动表进行排序，然后合并两个有序的集合（归并排序）

MySQL并不支持此算法

mysql