联接查问
联接查问是一种常见的数据库操作,即在两张表(或更多表)中进行行匹配的操作。个别称之为程度操作,这是因为对几张表进行联接操作所产生的后果集能够蕴含这几张表中所有的列。
CROSS JOIN
CROSS JOIN 对两个表执行笛卡儿积,返回两个表中所有列的组合。若左表有 m 行数据,右表有 n 行数据,则 CROSS JOIN 将返回 m * n 行的表。
CROSS JOIN 的一个用途是疾速生成反复测试数据,因为通过它能够很快地结构 m *n* o 行的数据。
CROSS JOIN 的另一个用途是能够作为返回后果集的行号,例如:
SELECT emp_no, dept_no, @a:=@a+1 AS row_num FROM dept_emp, (SELECT @a:=0) t;
INNER JOIN
通过 INNER JOIN 用户能够依据一些过滤条件来匹配表之间的数据。在逻辑查问的前三个解决阶段中,INNER JOIN 利用前两个阶段,即首先产生笛卡儿积的虚构表,再依照 ON 过滤条件来进行数据的匹配操作。
INNER 关键字可省略。因为不会增加内部行,INNER JOIN 中 WHERE 的过滤条件能够写在 ON 子句中。在 MySQL 数据库中,如果 INNER JOIN 后不跟 ON 子句,这时 INNER JOIN 等于 CROSS JOIN。此外,如果 ON 子句中的列具备雷同的名称,能够应用 USING 子句来进行简化。
OUTER JOIN
通过 OUTER JOIN 用户能够依照一些过滤条件来匹配表之间的数据。与 INNER JOIN 不同的是,在通过 OUTER JOIN 增加的保留表中存在未找到的匹配数据。
NATURAL JOIN
ANSI SQL 还反对 NATURAL JOIN,即天然联接。NATURAL JOIN 等同于 INNTER JOIN 与 USING 的组合,它隐含的作用是将两个表中具备雷同名称的列进行匹配。
NONEQUI JOIN
NONEQUI JOIN 的联接条件蕴含“等于”运算符之外的运算符。例如,有一张部门经理表 dept_manager,要生成表中所有两个不同经理的组合。这里先假如以后表中仅蕴含员工号 A、B、C,执行 CROSS JOIN 后将生成上面九对:(A,A)、(A,B)、(A,C)、(B,A)、(B,B)、(B,C)、(C,A)、(C,B)、(C,C)。
显然,(A,A)、(B,B)和(C,C)蕴含雷同的员工号,不是无效的员工组合。而(A,B)、(B,A)又示意同样的组合。要解决这个问题,能够指定一个右边值小于左边值的联接条件,这样能够移除上述两种状况。该问题的解决方案为:
SELECT a.emp_no,b.emp_no FROM dept_manager a INNER JOIN dept_manager b ON a.emp_no < b.emp_no;
联接算法
联接算法是 MySQL 数据库用于解决联接的物理策略。旧版本的 MySQL 数据库仅反对 Nested-Loops Join 算法,自 8.0.18 版本开始反对 Hash Join 算法。
当联接的表上有索引时,Nested-Loops Join 是十分高效的算法。依据 B + 树的个性,其联接的工夫复杂度为 O(N),若没有索引,则可视为最坏的状况,工夫复杂度为 O(N2)。MySQL 数据库依据不同的应用场合,反对两种 Nested-Loops Join 算法,一种是 Simple Nested-LoopsJoin(NLJ)算法,另一种是 Block Nested-Loops Join(BNL)算法。
Simple Nested-Loops Join 算法(简略嵌套循环算法)
Simple Nested-Loops Join 从第一张表中每次读取一条记录,而后将记录与嵌套表中的记录进行比拟。
假如在两张表 R 和 S 上进行联接的列都不含有索引。这个算法的扫描次数为:Rn+Rn*Sn,扫描老本为 O(Rn*Sn)。Rn 和 Sn 别离代表 R 表和 S 表中别离含有的记录数。
对于联接的列含有索引的状况,内部表的每条记录不再须要扫描整张外部表,只须要扫描外部表上的索引即可失去联接的判断后果。 如果外部表联接列的索引高度为 SBH,那么上述算法的扫描次数为 Rn+SBH*Rn,扫描老本为 O(Rn)。而个别 B + 树的高度为 3~4 层,因而在有索引的状况下,Simple Nested-Loops Join 算法的执行速度是比拟快的。
优化器在个别状况下总是抉择将联接列含有索引的表作为外部表。如果两张表 R 和 S 在联接的列上都有索引,并且索引的高度雷同,那么优化器会抉择将记录数起码的表作为内部表,这是因为外部表的扫描次数总是索引的高度,与记录的数量无关。
Block Nested-Loops Join 算法(块嵌套循环算法)
Block Nested-Loops Join 算法是针对没有索引的联接状况设计的,其应用 Join Buffer(联接缓冲)来缩小外部循环读取表的次数。
例如,Block Nested-Loops Join 算法先把对 Outer Loop 表(内部表)每次读取的 10 行记录(精确地说是 10 行须要进行联接的列)放入 Join Buffer 中,而后在 Inner Loop 表(外部表)中间接匹配这 10 行数据。因而,对 Inner Loop 表的扫描缩小了 1 /10。
MySQL 数据库应用 Join Buffer 的准则如下:
- 零碎变量 join_buffer_size 决定了 Join Buffer 的大小。
- Join Buffer 可被用于联接是 ALL、index 和 range 的类型。
- 每次联接应用一个 Join Buffer,因而多表的联接能够应用多个 Join Buffer。
- Join Buffer 在联接产生之前进行调配,在 SQL 语句执行完后进行开释。
- Join Buffer 只存储须要进行查问操作的相干列数据,而不是整行的记录。
在 MySQL 5.5 以及之前的版本中,Join Buffer 只能在 INNER JOIN 中应用,在 OUTER JOIN 中则不能应用,即 Block Nested-Loops Join 算法不反对 OUTER JOIN。
Batched Key Access Join 算法(批量键值拜访联接算法)
MySQL 5.6(MariaDB 5.3)开始反对 BatchedKey Access Join 算法(简称 BKA),该算法的思维为联合索引和 group 这两种办法(SimpleNested-Loops Join 和 Block Nested-Loops Join 只能应用一种)来进步 search-for-match 的操作,以此放慢联接的执行效率。咱们能够把这种算法了解为 group-index-lookup(组索引查问)。
为什么应用 group-index-lookup 能进步 search-for-match 的操作呢?因为这样能够进步数据库整体资源的 Cache 命中率,从 CPU Cache、PageCache 到 Disk 的拜访,效率都变得更高。 如果内部表扫描的是主键,那么表中的记录拜访都是比拟有序的,然而如果联接的列是非主键索引,那么对于表中记录的拜访可能就是十分离散的。因而对于非主键索引的联接,Batched Key Access Join 算法将能极大进步 SQL 的执行效率。
为什么应用 group-index-lookup 能进步 search-for-match 的操作呢?因为这样能够进步数据库整体资源的 Cache 命中率,从 CPU Cache、PageCache 到 Disk 的拜访,效率都变得更高。 如果内部表扫描的是主键,那么表中的记录拜访都是比拟有序的,然而如果联接的列是非主键索引,那么对于表中记录的拜访可能就是十分离散的。因而对于非主键索引的联接,Batched Key Access Join 算法将能极大进步 SQL 的执行效率。
Batched Key Access Join 算法的工作步骤如下:
- 将内部表中相干的列放入 Join Buffer 中。
- 批量地将 Key(索引键值)发送到 Multi-Range Read(MRR)接口。
- Multi-Range Read(MRR)通过收到的 Key,依据其对应的 ROWID 进行排序,而后再进行数据的读取操作。
- 返回后果集给客户端。
举个例子,当初有这样一条 SQL 语句:
SELECT MAX(l_extendedprice) FROM orders, lineitem WHERE o_orderdate BETWEEN '1995-01-01' AND '1995-01-31' AND l_orderkey=o_orderkey;
在上述 SQL 语句中,lineitem 的主键为(l_orderkey,l_linenumber)的联结索引,l_orderkey、o_orderdate 和 o_orderkey 上都有索引。l_extendedprice 是表 lineitem 中的列,不在索引 l_orderkey 中。因而当通过 l_orderkey 索引来进行 search-for-match 操作之后,还须要依据 ROWID 来查找 l_extendedprice 的值,而这个查找是离散的,故应用 Batched Key Access Join 算法能进步 SQL 语句执行的效率。
在 MySQL 5.5 下,数据库外部表的 search-for-match 操作抉择了 PRIMARY 这个索引,也就是主键索引,而没有应用曾经存在于列 l_orderkey 上的 i_l_orderkey 索引。产生这个后果的起因还是优化器认为利用辅助索引失去联接判断后,还要再次读取主键上的列 l_ extendedprice,这是离散读取,因而要远远慢于间接的主键拜访,并且主键索引的最左列也是 l_orderkey。
在 MySQL 5.6 下,能够应用下列语句启用 BatchedKey Access Join 算法。
SET optimizer_switch='mrr=on,mrr_cost_based=off,batched_key_access=on';
因为 Batched Key Access Join 算法的实质是通过 Multi-Range Read 接口将非主键索引对于记录的拜访,转化为依据 ROWID 排序的较为有序的记录获取,所以要想通过 Batched Key Access Join 算法来进步性能,岂但须要确保联接的列参加 match 的操作,还要有对非主键列的 search 操作。如果联接不波及针对主键进一步获取数据,外部表只参加联接判断,那么就不会启用 Batched Key Access Join 算法,因为没有必要去调用 Multi-Range Read 接口。
Batched Key Access Join 算法从实质上来说还是 Simple Nested-Loops Join 算法,其产生的条件为外部表上有索引,并且该索引为非主键的,并且联接须要拜访外部表主键上的索引。这时 Batched Key Access Join 算法调用 Multi-RangeRead 接口,批量地进行索引键的匹配和主键索引上获取数据的操作,以此来进步联接的执行效率。
Classic Hash Join 算法(经典哈希联接算法)
Batched Key Access Join 算法尽管解决了一些问题,然而还存在一些问题。一方面,不是每个联接语句都是有索引的,对于没有索引的状况,MySQL 数据库目前只能应用 Block Nested-LoopsJoin 算法。这样尽管缩小了外部表的扫描次数,然而没有缩小执行 search-for-match 的次数。另一方面,即便有索引,然而当失去的数据占据表中大部分时,间接应用主键索引扫描更有效率,应用 Multi-Range Read 反而显得没有什么必要。
对于上述的两方面问题,能够通过另外一种联接算法来解决,即 Hash Join,是一种广泛应用于数据仓库和 OLAP 利用的经典联接算法。
Classic Hash Join 算法同样应用 Join Buffer,先将内部表中数据放入 Join Buffer 中,而后依据键值产生一张散列表,这是第一个阶段,称为 build 阶段。随后读取外部表中的一条记录,对其利用散列函数,将其和散列表中的数据进行比拟,这是第二个阶段,称为 probe 阶段。
如果将 Hash 查找利用于 Simple Nested-LoopsJoin 中,则执行打算的 Extra 列会显示 BNLH。如果将 Hash 查找利用于 Batched Key Access Join 中,则执行打算的 Extra 列会显示 BKAH。
假使 Join Buffer 可能齐全寄存下内部表的数据,那么 Classic Hash Join 算法只须要扫描一次外部表。反之,Classic Hash Join 须要扫描屡次外部表。为了使 Classic Hash Join 更有效率,应该更好地布局 Join Buffer 的大小。
注:Hash Join 只能利用于等值的联接操作中,因为已通过散列函数生成新的联接值,不能将 Hash Join 用于非等值的联接操作中。