比较 MySQL 中的 NOT IN, NOT EXISTS, LEFT JOIN / IS NULL

Tags: database mysql

当你被 Orace 的神话般的查询转换功能和优秀的基于成本的查询优化器宠坏了时,那么你可能会忘记在“旧时代”或针对那些相对简单的数据库的 SQL 查询调优是多么困难。下面是如何在 MySQL 中实现 ANTI-JOIN 的各种方法的详细介绍:

1. 下面哪种方法是查找存在于一张表中但不存在于另一张表中的数据

LEFT JOIN?

SELECT  l.*
FROM    t_left l
LEFT JOIN
        t_right r
ON      r.value = l.value
WHERE   r.value IS NULL

NOT IN?

SELECT  l.*
FROM    t_left l
WHERE   l.value NOT IN
        (
        SELECT  value
        FROM    t_right r
        )

或者 NOT EXISTS?

SELECT  l.*
FROM    t_left l
WHERE   NOT EXISTS
        (
        SELECT  NULL
        FROM    t_right r
        WHERE   r.value = l.value
        )

好了,现在是 MySQL 时间。

2. 创建测试表

跟往常一样,我们将创建测试表。

CREATE TABLE filler (
        id INT NOT NULL PRIMARY KEY AUTO_INCREMENT
) ENGINE=Memory;

CREATE TABLE t_left (
        id INT NOT NULL PRIMARY KEY,
        value INT NOT NULL,
        stuffing VARCHAR(200) NOT NULL
) ENGINE=InnoDB DEFAULT CHARSET=UTF8;

CREATE TABLE t_right (
        id INT NOT NULL PRIMARY KEY,
        value INT NOT NULL,
        stuffing VARCHAR(200) NOT NULL
) ENGINE=InnoDB DEFAULT CHARSET=UTF8;

CREATE INDEX ix_left_value ON t_left (value);

CREATE INDEX ix_right_value ON t_right (value);

DELIMITER $$

CREATE PROCEDURE prc_filler(cnt INT)
BEGIN
        DECLARE _cnt INT;
        SET _cnt = 1;
        WHILE _cnt <= cnt DO
                INSERT
                INTO    filler
                SELECT  _cnt;
                SET _cnt = _cnt + 1;
        END WHILE;
END
$$

DELIMITER ;

START TRANSACTION;
CALL prc_filler(100000);
COMMIT;

INSERT
INTO    t_left
SELECT  id, id % 10000,
        RPAD(CONCAT('Value ', id, ' '), 200, '*')
FROM    filler;

INSERT
INTO    t_right
SELECT  (l.id - 1) * 10 + f.id,
        l.value + 1,
        RPAD(CONCAT('Value ', (l.id - 1) * 10 + f.id, ' '), 200, '*')
FROM    (
        SELECT  id
        FROM    filler
        ORDER BY
                id
        LIMIT 10
        ) f
CROSS JOIN
        t_left l;
  1. 表 T_LEFT 包含 100,000 行数据,其中 10,000 行是唯一的。

  2. 表 T_RIGHT 包含 10,00,000 行数据,其中 10,000 行是唯一的。

  3. 其中 T_LEFT 表中的 10 条数据 T_RIGHT 表中没有

  4. 这两张表的 value 字段已经增加了索引

LEFT JOIN / IS NULL

SELECT  l.id, l.value
FROM    t_left l
LEFT JOIN
        t_right r
ON      r.value = l.value
WHERE   r.value IS NULL

执行计划:


idvalue
100000
200000
300000
400000
500000
800000
900000
1000000
10 rows fetched in 0.0003s (0.7344s)
idselect_typetabletypepossible_keyskeykey_lenrefrowsfilteredExtra
1SIMPLElindex
ix_left_value4
100045100.00Using index
1SIMPLErrefix_right_valueix_right_value420090918_anti.l.value33100.00Using where; Using index; Not exists
select `20090918_anti`.`l`.`id` AS `id`,`20090918_anti`.`l`.`value` AS `value` 
from `20090918_anti`.`t_left` `l` 
left join `20090918_anti`.`t_right` `r` 
on((`20090918_anti`.`r`.`value` = `20090918_anti`.`l`.`value`)) 
where isnull(`20090918_anti`.`r`.`value`)

查询使用了 0.73 秒,如果我们查看执行计划中的 Extra 部分,我们可以看到一些有意思的内容:

Using where; Using index; Not exists

这是什么意思?MySQL 文档是这么介绍的:

Not exists

MySQL 能够对 LEFT JOIN 查询进行优化,当找到第一个匹配 LEFT JOIN 条件的行时,它将不会使用这个条件组合检查这个表中剩余行。下面是这类是符合这类优化条件查询的例子:

  SELECT  *
    FROM    t1
    LEFT JOIN
            t2
    ON      t1.id = t2.id
    WHERE   t2.id IS NULL;

假设 t2.id 被定义为 NOT NULL,在这种情况下,MySQL 会扫描 t1 表中的每一行并使用 t1.id 在 t2 表中查找相匹配的数据,如果 MySQL 在 t2 中找到了匹配的行,那么 MySQL 就知道 t2.id 是不可能为 NULL的,并且不会继续在 t2 表中检索具有相同 id 的记录行了。换句话说就是,对于 t1 表中的每一行,MySQL 仅会在 t2 表中查找一次,无论 t2 表中到底有多少行数据是匹配的。

这就是上面的情况。

MySQL 以及其他数据库系统(除了 SQL Server),都可以优化 LEFT JOIN / IS NULL 在发现匹配行时快速返回 FALSE,不过仅有 MySQL 在文档中描述了这个行为。

对于 t2.id 必须定义为 NOT NULL 的假设有些牵强,因为全等于的 JOIN 条件已经暗示所检索到的值一定是 NOT NULL 的。

由于 MySQL 没有 HASH JOIN 和 MERGE JOIN 算法,因此可以实现 ANT JOIN 的方法也只有使用 NESTED LOOPS ANTI JOIN,我们可以从查询计划中明确看出来(虽然 MySQL 不这么称呼它)。但这个特性实际上就是完成了 ANTI JOIN 功能:它依据左表中的值查找右表中的每个不相同的值(去重)。

NOT IN

SELECT  l.id, l.value
FROM    t_left l
WHERE   value NOT IN
        (
        SELECT  value
        FROM    t_right
        )

查询计划:

idvalue
100000
200000
300000
400000
500000
600000
700000
800000
900000
1000000
10 rows fetched in 0.0003s (0.7187s)
idselect_typetabletypepossible_keyskeykey_lenrefrowsfilteredExtra
1PRIMARYlindex
ix_left_value4
100045100.00Using where; Using index
2DEPENDENT SUBQUERYt_rightindex_subqueryix_right_valueix_right_value4func33100.00Using index
select `20090918_anti`.`l`.`id` AS `id`,`20090918_anti`.`l`.`value` AS `value` 
from `20090918_anti`.`t_left` `l` 
where (not(<in_optimizer>(`20090918_anti`.`l`.`value`,<exists>(<index_lookup>(<cache>(`20090918_anti`.`l`.`value`) in t_right 
on ix_right_value)))))

这种查询的速度和 LEFT JOIN / NOT NULL 一样快,不过他们的查询计划缺不太一样。

首先,它使用 DEPENDENT SUBQUERY 而不是第二张表(在 LEFT JOIN /IS NULL 中使用的)。通常来说,的确是要使用 DEPENDENT SUBQUERY,因为我们在这里没有使用连接而是从一个单表中 SELECT 数据同时使用 WHERE 子句。

其次,执行计划的描述部分提到:

<exists>(<index_lookup>(<cache>(`20090918_anti`.`l`.`value`) in t_right on ix_right_value))

这是什么呢?

这当然是我们的老朋友 ANTI JOIN 了。Mysql 会为 EXISTS 子查询进行优化:它查询时会使用 ix_right_value 索引,因此返回结果的速度非常快(或者查不到结果)。

NOT IN 在处理 NULL 时与 LEFT JOIN / IS NULL 是不同的。由于 t_left.value 和 t_right.value 都定义为 NOT NULL,因此这个子句不可能返回 NULL 值,并且 MySQL 已经考虑到了这点。

本质上来说,这个查询的执行计划于 LEFT JOIN / IS NULL 是想痛的,尽管这个计划执行了不同的代码分支,并且他们的解释结果看上去不一样。这两个算法实际上是一样的,并且会用相同的时间来完成查询。

NOT EXISTS

SELECT  l.id, l.value
FROM    t_left l
WHERE   NOT EXISTS
        (
        SELECT  value
        FROM    t_right r
        WHERE   r.value = l.value
        )

执行计划:

idvalue
100000
200000
300000
400000
500000
600000
700000
800000
900000
1000000
10 rows fetched in 0.0003s (0.9218s)
idselect_typetabletypepossible_keyskeykey_lenrefrowsfilteredExtra
1PRIMARYlindex
ix_left_value4
100045100.00Using where; Using index
2DEPENDENT SUBQUERYrrefix_right_valueix_right_value420090918_anti.l.value33100.00Using index
Field or reference '20090918_anti.l.value' of SELECT #2 was resolved in SELECT #1
select `20090918_anti`.`l`.`id` AS `id`,`20090918_anti`.`l`.`value` AS `value` 
from `20090918_anti`.`t_left` `l` 
where (not
    (exists(
        select `20090918_anti`.`r`.`value` AS `value` 
        from `20090918_anti`.`t_right` `r` 
        where (`20090918_anti`.`r`.`value` = `20090918_anti`.`l`.`value`))))

当然,上面查询的结果也是一样的。

同样,执行计划也不相同。MySQL 是唯一一种为三种不同方法生成不同执行计划的数据库系统。

执行计划没有太大的差别:MySQL 知道查询所需要使用的索引和如何处理 EXISTS,它会将二者结合使用。

MySQL 会优化 EXISTS 子句,因此查询返回结果的速度会非常快。所以,上面的查询实际上与前两个查询一样都是 ANTI JOIN 查询。不过这个查询比上两个查询稍微差一些,它使用了 0.92 秒。

这不是太大的性能损失,不过,它还是多用了 27% 的查询时间。

很难完全找到查询比较慢的原因,由于查询时间的增加是线性的,并且似乎不依赖于数据的分布,这两个表等中的值的数目,只要这两个字段都建立了索引。由于这三种方法本质上都完成相同的功能,因此 EXISTS 可能在执行时进行了额外检查,因此消耗了更多的时间。

总结

MySQL 可以在使用上面三种执行 NESTED LOOPS ANTI JOIN 查询时对他们进行优化。

它会取得 t_left 表中的每一个值,并在通过 t_right.value 的索引在 t_right 表中查找相同的值。当通过索引找到或未找到对饮值是,相应的断言会立即返回 TRUE 或 FALSE,相应的,可以立即决定是否返回 t_left 中对应行的数据而无需检查其他行。

然而,这三种查询生成了三种不同的执行计划并且执行三种不同的代码段,EXISTS 所执行的代码段要比使用 NOT EXISTS 的 index_subquery 和 LEFT JOIN 要慢 30%。

这就是为什么在 MySQL 中使用 LEFT JOIN / IS NULL 或 NOT IN 检索两个表的差异数据(一个表中存在另一个表中不存在)要比 NOT EXISTS 快的原因。

本文链接:http://www.4byte.cn/learning/37790/bi-jiao-mysql-zhong-de-not-in-not-exists-left-join-is-null.html