{"id":474,"date":"2017-09-01T14:44:53","date_gmt":"2017-09-01T14:44:53","guid":{"rendered":"http:\/\/www.gnial.com.br\/gnialhelp\/?p=474"},"modified":"2019-11-26T10:40:12","modified_gmt":"2019-11-26T13:40:12","slug":"mysql-not-in-vs-not-exists-vs-left-join-is-null","status":"publish","type":"post","link":"http:\/\/www.gnial.com.br\/gnialhelp\/mysql-not-in-vs-not-exists-vs-left-join-is-null\/","title":{"rendered":"MySQL – NOT IN vs. NOT EXISTS vs. LEFT JOIN \/ IS NULL"},"content":{"rendered":"

NOT IN vs. NOT EXISTS vs. LEFT JOIN \/ IS NULL: MySQL<\/h2>\n
\n

Which method is best to select values present in one table but missing in another one?<\/p>\n

This:<\/p>\n

\n
<\/div>\n
\n
1.<\/code>SELECT<\/code>\u00a0\u00a0l.*<\/code><\/span><\/span><\/div>\n
2.<\/code>FROM<\/code>\u00a0\u00a0\u00a0\u00a0t_left l<\/code><\/span><\/span><\/div>\n
3.<\/code>LEFT<\/code>\u00a0JOIN<\/code><\/span><\/span><\/div>\n
4.<\/code>t_right r<\/code><\/span><\/span><\/div>\n
5.<\/code>ON<\/code>\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0r.value = l.value<\/code><\/span><\/span><\/div>\n
6.<\/code>WHERE<\/code>\u00a0\u00a0\u00a0r.value\u00a0<\/code>IS<\/code>\u00a0NULL<\/code><\/span><\/span><\/div>\n<\/div>\n<\/div>\n

, this:<\/p>\n

\n
<\/div>\n
\n
1.<\/code>SELECT<\/code>\u00a0\u00a0l.*<\/code><\/span><\/span><\/div>\n
2.<\/code>FROM<\/code>\u00a0\u00a0\u00a0\u00a0t_left l<\/code><\/span><\/span><\/div>\n
3.<\/code>WHERE<\/code>\u00a0\u00a0\u00a0l.value\u00a0<\/code>NOT<\/code>\u00a0IN<\/code><\/span><\/span><\/div>\n
4.<\/code>(<\/code><\/span><\/span><\/div>\n
5.<\/code>SELECT<\/code>\u00a0\u00a0value<\/code><\/span><\/span><\/div>\n
6.<\/code>FROM<\/code>\u00a0\u00a0\u00a0\u00a0t_right r<\/code><\/span><\/span><\/div>\n
7.<\/code>)<\/code><\/span><\/span><\/div>\n<\/div>\n<\/div>\n

or this:<\/p>\n

\n
<\/div>\n
\n
1.<\/code>SELECT<\/code>\u00a0\u00a0l.*<\/code><\/span><\/span><\/div>\n
2.<\/code>FROM<\/code>\u00a0\u00a0\u00a0\u00a0t_left l<\/code><\/span><\/span><\/div>\n
3.<\/code>WHERE<\/code>\u00a0\u00a0\u00a0NOT<\/code>\u00a0EXISTS<\/code><\/span><\/span><\/div>\n
4.<\/code>(<\/code><\/span><\/span><\/div>\n
5.<\/code>SELECT<\/code>\u00a0\u00a0NULL<\/code><\/span><\/span><\/div>\n
6.<\/code>FROM<\/code>\u00a0\u00a0\u00a0\u00a0t_right r<\/code><\/span><\/span><\/div>\n
7.<\/code>WHERE<\/code>\u00a0\u00a0\u00a0r.value = l.value<\/code><\/span><\/span><\/div>\n
8.<\/code>)<\/code><\/span><\/span><\/div>\n<\/div>\n<\/div>\n<\/blockquote>\n

Finally, it’s\u00a0MySQL<\/strong>\u00a0time.<\/p>\n

As always, we will create the sample tables:<\/p>\n

<\/span>
\nTable creation details<\/strong><\/a><\/p>\n

Table\u00a0t_left<\/code>\u00a0contains\u00a0100,000<\/strong>\u00a0rows with\u00a010,000<\/strong>\u00a0distinct values.<\/p>\n

Table\u00a0t_right<\/code>\u00a0contains\u00a01,000,000<\/strong>\u00a0rows with\u00a010,000<\/strong>\u00a0distinct values.<\/p>\n

There are\u00a010<\/strong>\u00a0rows in\u00a0t_left<\/code>\u00a0with values not present in\u00a0t_right<\/code>.<\/p>\n

In both tables the field\u00a0value<\/code>\u00a0is indexed.<\/p>\n

LEFT JOIN \/ IS NULL<\/h3>\n
\n
\n
view source<\/a>print<\/a>?<\/a><\/div>\n<\/div>\n
\n
1.<\/code>SELECT<\/code>\u00a0\u00a0l.id, l.value<\/code><\/span><\/span><\/div>\n
2.<\/code>FROM<\/code>\u00a0\u00a0\u00a0\u00a0t_left l<\/code><\/span><\/span><\/div>\n
3.<\/code>LEFT<\/code>\u00a0JOIN<\/code><\/span><\/span><\/div>\n
4.<\/code>t_right r<\/code><\/span><\/span><\/div>\n
5.<\/code>ON<\/code>\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0r.value = l.value<\/code><\/span><\/span><\/div>\n
6.<\/code>WHERE<\/code>\u00a0\u00a0\u00a0r.value\u00a0<\/code>IS<\/code>\u00a0NULL<\/code><\/span><\/span><\/div>\n<\/div>\n<\/div>\n

View query results and execution plan<\/strong><\/a><\/p>\n

The query returns correct results in\u00a00.73 seconds<\/strong>.<\/p>\n

If we look into the\u00a0Extra<\/strong>\u00a0part of the execution plan, we will see an interesting thing there:<\/p>\n

Using where; Using index; Not exists<\/code><\/p>\n

What does it mean?<\/p>\n

MySQL<\/strong>\u00a0documentation<\/a>\u00a0mentions this:<\/p>\n

Not exists<\/code><\/p>\n

MySQL<\/strong>\u00a0was able to do a\u00a0LEFT JOIN<\/code>\u00a0optimization on the query and does not examine more rows in this table for the previous row combination after it finds one row that matches the\u00a0LEFT JOIN<\/code>criteria. Here is an example of the type of query that can be optimized this way:<\/p>\n

\n
\n
view source<\/a>print<\/a>?<\/a><\/div>\n<\/div>\n
\n
1.<\/code>SELECT<\/code>\u00a0\u00a0*<\/code><\/span><\/span><\/div>\n
2.<\/code>FROM<\/code>\u00a0\u00a0\u00a0\u00a0t1<\/code><\/span><\/span><\/div>\n
3.<\/code>LEFT<\/code>\u00a0JOIN<\/code><\/span><\/span><\/div>\n
4.<\/code>t2<\/code><\/span><\/span><\/div>\n
5.<\/code>ON<\/code>\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0t1.id = t2.id<\/code><\/span><\/span><\/div>\n
6.<\/code>WHERE<\/code>\u00a0\u00a0\u00a0t2.id\u00a0<\/code>IS<\/code>\u00a0NULL<\/code>;<\/code><\/span><\/span><\/div>\n<\/div>\n<\/div>\n

Assume that\u00a0t2.id<\/code>\u00a0is defined as\u00a0NOT NULL<\/code>. In this case,\u00a0MySQL<\/strong>\u00a0scans\u00a0t1<\/code>\u00a0and looks up the rows in\u00a0t2<\/code>using the values of\u00a0t1.id<\/code>. If\u00a0MySQL<\/strong>\u00a0finds a matching row in\u00a0t2<\/code>, it knows that\u00a0t2.id<\/code>\u00a0can never be\u00a0NULL<\/code>, and does not scan through the rest of the rows in\u00a0t2<\/code>\u00a0that have the same id value. In other words, for each row in\u00a0t1<\/code>,\u00a0MySQL<\/strong>\u00a0needs to do only a single lookup in\u00a0t2<\/code>, regardless of how many rows actually match in\u00a0t2<\/code>.<\/p><\/blockquote>\n

This is exactly our case.<\/p>\n

MySQL<\/strong>, as well as all other systems except\u00a0SQL Server<\/strong>, is able to optimize\u00a0LEFT JOIN \/ IS NULL<\/code>\u00a0to return\u00a0FALSE<\/code>\u00a0as soon the matching value is found, and it is the only system that cared to document this behavior.<\/p>\n

The assumption that\u00a0t2.id<\/code>\u00a0should be defined as\u00a0NOT NULL<\/code>, however, is too strong, since a successfull\u00a0JOIN<\/code>\u00a0on equality condition implies that the value found is\u00a0NOT NULL<\/code>.<\/p>\n

Since\u00a0MySQL<\/strong>\u00a0is not capable of using\u00a0HASH<\/code>\u00a0and\u00a0MERGE<\/code>\u00a0join algorithms, the only\u00a0ANTI JOIN<\/code>\u00a0it is capable of is the\u00a0NESTED LOOPS ANTI JOIN<\/code>, which is exactly what we see in the query plan (despite the fact that\u00a0MySQL<\/strong>\u00a0doesn’t call it that). However, this behavior is what an\u00a0ANTI JOIN<\/code>\u00a0does: it checks the values from the left table against only one of each distinct values in the right table, skipping the duplicates.<\/p>\n

NOT IN<\/h3>\n
\n
\n
view source<\/a>print<\/a>?<\/a><\/div>\n<\/div>\n
\n
1.<\/code>SELECT<\/code>\u00a0\u00a0l.id, l.value<\/code><\/span><\/span><\/div>\n
2.<\/code>FROM<\/code>\u00a0\u00a0\u00a0\u00a0t_left l<\/code><\/span><\/span><\/div>\n
3.<\/code>WHERE<\/code>\u00a0\u00a0\u00a0value\u00a0<\/code>NOT<\/code>\u00a0IN<\/code><\/span><\/span><\/div>\n
4.<\/code>(<\/code><\/span><\/span><\/div>\n
5.<\/code>SELECT<\/code>\u00a0\u00a0value<\/code><\/span><\/span><\/div>\n
6.<\/code>FROM<\/code>\u00a0\u00a0\u00a0\u00a0t_right<\/code><\/span><\/span><\/div>\n
7.<\/code>)<\/code><\/span><\/span><\/div>\n<\/div>\n<\/div>\n

View query results and execution plan<\/strong><\/a><\/p>\n

This query is as fast as the\u00a0LEFT JOIN \/ NOT NULL<\/code>, however its plan looks quite different.<\/p>\n

First, it mentions a\u00a0DEPENDENT SUBQUERY<\/code>\u00a0instead of a second table (which was used in the\u00a0LEFT JOIN \/ IS NULL<\/code>). Nominally, is a dependent subquery indeed, since we don’t have a join here but rather a\u00a0SELECT<\/code>\u00a0from a single table with predicate in the\u00a0WHERE<\/code>\u00a0clause.<\/p>\n

Second, the description part of the plan mentions this:<\/p>\n

<exists>(<index_lookup>(<cache>(`20090918_anti`.`l`.`value`) in t_right on ix_right_value))<\/code><\/p>\n

What is that?<\/p>\n

This is of course our good old friend, the\u00a0ANTI JOIN<\/code>.\u00a0MySQL<\/strong>\u00a0applies\u00a0EXISTS<\/code>\u00a0optimization to the subquery: it uses the index scan over\u00a0ix_right_value<\/code>\u00a0and returns as soon as it finds (or not finds) a row.<\/p>\n

NOT IN<\/code>\u00a0is different in how it handles\u00a0NULL<\/code>\u00a0values. However, since both\u00a0t_left.value<\/code>\u00a0and\u00a0t_right.value<\/code>\u00a0are defined as\u00a0NOT NULL<\/code>, no\u00a0NULL<\/code>\u00a0value can ever be returned by this predicate, and\u00a0MySQL<\/strong>\u00a0takes this into account.<\/p>\n

Essentially, this is exactly the same plan that\u00a0LEFT JOIN \/ IS NULL<\/code>\u00a0uses, despite the fact these plans are executed by the different branches of code and they look different in the results of\u00a0EXPLAIN<\/code>. The algorithms are in fact the same in fact and the queries complete in same time.<\/p>\n

NOT EXISTS<\/h3>\n
\n
\n
view source<\/a>print<\/a>?<\/a><\/div>\n<\/div>\n
\n
1.<\/code>SELECT<\/code>\u00a0\u00a0l.id, l.value<\/code><\/span><\/span><\/div>\n
2.<\/code>FROM<\/code>\u00a0\u00a0\u00a0\u00a0t_left l<\/code><\/span><\/span><\/div>\n
3.<\/code>WHERE<\/code>\u00a0\u00a0\u00a0NOT<\/code>\u00a0EXISTS<\/code><\/span><\/span><\/div>\n
4.<\/code>(<\/code><\/span><\/span><\/div>\n
5.<\/code>SELECT<\/code>\u00a0\u00a0value<\/code><\/span><\/span><\/div>\n
6.<\/code>FROM<\/code>\u00a0\u00a0\u00a0\u00a0t_right r<\/code><\/span><\/span><\/div>\n
7.<\/code>WHERE<\/code>\u00a0\u00a0\u00a0r.value = l.value<\/code><\/span><\/span><\/div>\n
8.<\/code>)<\/code><\/span><\/span><\/div>\n<\/div>\n<\/div>\n

View query results and execution plan<\/strong><\/a><\/p>\n

This query of course produces the same results.<\/p>\n

Execution plan, again, is different.\u00a0MySQL<\/strong>\u00a0is the only system that produces three different plans for three different methods.<\/p>\n

The plan does not differ much:\u00a0MySQL<\/strong>\u00a0does know what an index lookup is and what\u00a0EXISTS<\/code>\u00a0is and it does combine them together.<\/p>\n

EXISTS<\/code>\u00a0in\u00a0MySQL<\/strong>\u00a0is optimized so that it returns as soon as the first value is found. So this query in fact is an\u00a0ANTI JOIN<\/code>\u00a0as well as first two queries are.<\/p>\n

This query, however, is a little bit less efficient than the previous two: it takes\u00a00.92 s<\/strong>.<\/p>\n

This is not much of a performance drop, however, the query takes\u00a027%<\/strong>\u00a0more time.<\/p>\n

It’s hard to tell exact reason for this, since this drop is linear and does not seem to depend on data distribution, number of values in both tables etc., as long as both fields are indexed. Since there are three pieces of code in\u00a0MySQL<\/strong>\u00a0that essentialy do one job, it is possible that the code responsible for\u00a0EXISTS<\/code>\u00a0makes some kind of an extra check which takes extra time.<\/p>\n

Summary<\/h3>\n

MySQL<\/strong>\u00a0can optimize all three methods to do a sort of\u00a0NESTED LOOPS ANTI JOIN<\/code>.<\/p>\n

It will take each value from\u00a0t_left<\/code>\u00a0and look it up in the index on\u00a0t_right.value<\/code>. In case of an index hit or an index miss, the corresponding predicate will immediately return\u00a0FALSE<\/code>\u00a0or\u00a0TRUE<\/code>, respectively, and the decision to return the row from\u00a0t_left<\/code>\u00a0or not will be made immediately without examining other rows in\u00a0t_right<\/code>.<\/p>\n

However, these three methods generate three different plans which are executed by three different pieces of code. The code that executes\u00a0EXISTS<\/code>\u00a0predicate is about\u00a030%<\/strong>\u00a0less efficient than those that execute\u00a0index_subquery<\/code>\u00a0and\u00a0LEFT JOIN<\/code>\u00a0optimized to use\u00a0Not exists<\/code>\u00a0method.<\/p>\n

That’s why the best way to search for missing values in\u00a0MySQL<\/strong>\u00a0is using a\u00a0LEFT JOIN \/ IS NULL<\/code>\u00a0or\u00a0NOT IN<\/code>rather than\u00a0NOT EXISTS<\/code>.<\/p>\n

fonte:<\/p>\n

NOT IN vs. NOT EXISTS vs. LEFT JOIN \/ IS NULL: MySQL<\/a><\/p><\/blockquote>\n