Mysql Exists vs IN -- correlated subquery vs subquery?

Question

I'm curious about how the execution of EXISTS() is supposed to be faster than IN().

I was answering a question when Bill Karwin brought up a good point. when you use EXISTS() it is using a correlated subquery (dependent subquery) and IN() is only using a subquery.

EXPLAIN shows that EXISTS and NOT EXISTS both use a dependent subquery and IN / NOT IN both use just a subquery.. so I'm curious how a correlated subquery is faster than a subquery??

I've used EXISTS before and it does execute faster than IN which is why I'm confused.

Here is a SQLFIDDLE with the explains

EXPLAIN SELECT COUNT(t1.table1_id) 
FROM table1 t1 
WHERE EXISTS
(   SELECT 1 
    FROM table2 t2
    WHERE t2.table1_id <=> t1.table1_id
);

+-------+-----------------------+-----------+-------+---------------+-----------+--------+--------------------------+--------+------------------------------+
| ID    |   SELECT_TYPE         |   TABLE   | TYPE  | POSSIBLE_KEYS |   KEY     |KEY_LEN |  REF                     |   ROWS |  EXTRA                       |
+-------+-----------------------+-----------+-------+---------------+-----------+--------+--------------------------+--------+------------------------------+
|  1    |   PRIMARY             |   t1      | index | (null)        |   PRIMARY |   4    | (null)                   |   4    |  Using where; Using index    |
|  2    |   DEPENDENT SUBQUERY  |   t2      | REF   | table1_id     |  table1_id|   4    | db_9_15987.t1.table1_id  |   1    |  Using where; Using index    |
+-------+-----------------------+-----------+-------+---------------+-----------+--------+--------------------------+--------+------------------------------+

---

EXPLAIN SELECT COUNT(t1.table1_id) 
FROM table1 t1 
WHERE NOT EXISTS
(   SELECT 1 
    FROM table2 t2
    WHERE t2.table1_id = t1.table1_id
);
+-------+-----------------------+-----------+-------+---------------+-----------+--------+--------------------------+--------+------------------------------+
| ID    |   SELECT_TYPE         |   TABLE   | TYPE  | POSSIBLE_KEYS |   KEY     |KEY_LEN |  REF                     |   ROWS |  EXTRA                       |
+-------+-----------------------+-----------+-------+---------------+-----------+--------+--------------------------+--------+------------------------------+
|  1    |   PRIMARY             |   t1      | index | (null)        |   PRIMARY |   4    | (null)                   |   4    |  Using where; Using index    |
|  2    |   DEPENDENT SUBQUERY  |   t2      | ref   | table1_id     |  table1_id|   4    | db_9_15987.t1.table1_id  |   1    |  Using index                 |
+-------+-----------------------+-----------+-------+---------------+-----------+--------+--------------------------+--------+------------------------------+

---

EXPLAIN SELECT COUNT(t1.table1_id) 
FROM table1 t1 
WHERE t1.table1_id NOT IN 
(   SELECT t2.table1_id 
    FROM table2 t2
);
+-------+-------------------+-----------+-------+---------------+-----------+--------+----------+--------+------------------------------+
| ID    |   SELECT_TYPE     |   TABLE   | TYPE  | POSSIBLE_KEYS |   KEY     |KEY_LEN |  REF     |   ROWS |  EXTRA                       |
+-------+-------------------+-----------+-------+---------------+-----------+--------+----------+--------+------------------------------+
|  1    |   PRIMARY         |   t1      | index | (null)        |   PRIMARY |   4    | (null)   |   4    |  Using where; Using index    |
|  2    |   SUBQUERY        |   t2      | index | (null)        |  table1_id|   4    | (null)   |   2    |  Using index                 |
+-------+-------------------+-----------+-------+---------------+-----------+--------+----------+--------+------------------------------+

FEW questions

In the explains above, how does EXISTS have using where and using index in extras but NOT EXISTS does not have using where in extras?

How is a correlated subquery faster than a subquery?

Answer 1

This is a RDBMS-agnostic answer, but may help nonetheless. In my understanding, the correlated (aka, dependent) subquery is perhaps the most often falsely accused culprit for bad performance.

The problem (as it is most often described) is that it processes the inner query for every row of the outer query. Therefore, if the outer query returns 1,000 rows, and the inner query returns 10,000, then your query has to slog through 10,000,000 rows (outer×inner) to produce a result. Compared to the 11,000 rows (outer+inner) from a non-correlated query over the same result sets, that ain't good.

However, this is just the worst case scenario. In many cases, the DBMS will be able to exploit indexes to drastically reduce the rowcount. Even if only the inner query can use an index, the 10,000 rows becomes ~13 seeks, which drops the total down to 13,000.

The exists operator can stop processing rows after the first, cutting down the query cost further, especially when most outer rows match at least one inner row.

In some rare cases, I have seen SQL Server 2008R2 optimise correlated subqueries to a merge join (which traverses both sets only once - best possible scenario) where a suitable index can be found in both inner and outer queries.

The real culprit for bad performance is not necessarily correlated subqueries, but nested scans.

Answer 2

This depends on the MySQL version - there is a bug in the MySQL query optimizer in versions up to 6.0.

Subqueries with "IN" were not optimized correctly (but executed again and again like dependant ones). This bug does not affect exists queries or joins.

The problem is that, for a statement that uses an IN subquery, the optimizer rewrites it as a correlated subquery. Consider the following statement that uses an uncorrelated subquery:

SELECT ... FROM t1 WHERE t1.a IN (SELECT b FROM t2);

The optimizer rewrites the statement to a correlated subquery:

SELECT ... FROM t1 WHERE EXISTS (SELECT 1 FROM t2 WHERE t2.b = t1.a);

If the inner and outer queries return M and N rows, respectively, the execution time becomes on the order of O(M×N), rather than O(M+N) as it would be for an uncorrelated subquery.

Refs.

• https://dev.mysql.com/doc/refman/5.6/en/subquery-restrictions.html
• http://plosquare.blogspot.de/2012/10/uncorrelated-subqueries-treated-as.html