EXPLAIN EXTENDED

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

CREATE TABLE table1 (
        id INT NOT NULL PRIMARY KEY AUTO_INCREMENT,
	value VARCHAR(50) NOT NULL
) ENGINE=MyISAM DEFAULT CHARSET=utf8;

CREATE TABLE table2 (
        id INT NOT NULL PRIMARY KEY AUTO_INCREMENT,
	value VARCHAR(50) NOT NULL
) ENGINE=MyISAM DEFAULT CHARSET=utf8;

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(1000000);
COMMIT;

INSERT
INTO	table1 (id, value)
SELECT	id, CONCAT('Value One ', id)
FROM	filler;

INSERT
INTO	table2 (id, value)
SELECT	id, CONCAT('Value Two ', id)
FROM	filler
ORDER BY
	id
LIMIT	1000;
&#91;/sourcecode&#93;
</div>

There are <strong>1,000,000</strong> rows in <code>table1</code> and <strong>1,000</strong> rows in <code>table2</code>.

Now, let's see the execution plan for this query:


SELECT  COUNT(*)
FROM    table1 t1
WHERE   t1.id NOT IN
        (
        SELECT  id
        FROM    table2 t2
        )

select count(0) AS `COUNT(*)` from `20090418_in`.`table1` `t1` where (not(<in_optimizer>(`20090418_in`.`t1`.`id`,<exists>(<primary_index_lookup>(<cache>(`20090418_in`.`t1`.`id`) in table2 on PRIMARY)))))

We see that there is a DEPENDENT SUBQUERY in the plan, but we see no correlated subqueries. What is this DEPENDENT SUBQUERY and what does it depend on?

If we look into the notice returned by EXPLAIN EXTENDED, we can see that the subquery is optimized to a NOT EXISTS subquery using a correlated value:

SELECT  COUNT(*)
FROM    table1
WHERE   NOT EXISTS
        (
        SELECT  1
        FROM    table2
        WHERE   table2.id = table1.id
        )

For each record from table1, MySQL engine executes the following correlated subquery:

SELECT  1
FROM    table2
WHERE   table2.id = table1.id
LIMIT 1

and returns the record into the resultset only if this correlated subquery does not return any rows.

The latter subquery really depends on the values from the outer space, that's why EXPLAIN EXTENDED describes it as a dependent subquery.

So is it really correct that the NOT IN subquery is executed as many times as there are rows in table1?

Yes and no.

Yes, because some subquery is really executed 1,000,000 times.

No, because in fact it's another subquery. Instead of selecting whole 1,000 of rows from table2, on each step MySQL selects at most 1 record from table2 (using the index lookup), and doesn't even use the selected value: it just checks if it exists.

And now a bonus trick.

We select COUNT(*) of those records from table1 whose id's do not exist in table2. There are 1,000,000 rows in table1, and even with these optimizations, it takes a lot of time:

SELECT  COUNT(*)
FROM    table1 t1
WHERE   t1.id NOT IN
        (
        SELECT  id
        FROM    table2
        )

More than 4 seconds.

But there are only 1,000 rows in table2.

What if we COUNT(*) the values from table1 that do exist in table2?

It can be done in a simple join with table2 as a leading table, 1,000 index lookups instead of a 1,000,000. And then we just subtract this value from the total COUNT(*) of values in table1, which is stored in MyISAM's metadata and can be fetched instantly.

Let's try it:

SELECT  (
        SELECT  COUNT(*)
        FROM    table1 t1
        ) -
        (
        SELECT  COUNT(*)
        FROM    table2 t1, table1 t2
        WHERE   t2.id = t1.id
        ) AS count

Much faster, I should say.

To be continued.