Mysql Exists vs IN - sous-requête corrélée vs sous-requête?

Question

Je suis curieux de savoir comment l'exécution de EXISTS() est censé être plus rapide que IN().

j'étais answering a question quand Bill Karwin a soulevé un bon point. Lorsque vous utilisez EXISTS(), il utilise une sous-requête corrélée (sous-requête dépendante) et IN() n'utilise qu'une sous-requête.

EXPLIQUEZ montre que EXISTS et NOT EXISTS utilisent à la fois une sous-requête dépendante et IN/NOT IN les deux utilisent juste un sous-requête .. donc je suis curieux de voir comment une sous-requête corrélative est plus rapide qu'un sous-requête ??

Je l'ai utilisé préexiste et il n'exécute plus rapidement que dans ce qui est la raison pour laquelle je suis confus.

Voici un SQLFIDDLE avec le explique

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     | 
+-------+-------------------+-----------+-------+---------------+-----------+--------+----------+--------+------------------------------+ 

Quelques questions

Dans ce qui précède explique, comment n'EXISTE ont using where et using index dans les extras mais NOT EXISTS n'a pas using where dans les extras?

Comment une sous-requête corrélée plus vite qu'un sous-requête?

Answer 1

C'est une réponse SGBDR agnostique, mais peut aider quand même. À mon sens, la sous-requête corrélée (alias, dépendante) est peut-être le coupable le plus souvent faussement accusé de mauvaise performance. Le problème (comme il est le plus souvent décrit) est qu'il traite la requête interne pour chaque ligne de la requête externe. Par conséquent, si la requête externe renvoie 1 000 lignes et que la requête interne renvoie 10 000, votre requête doit parcourir 10 000 000 lignes (× interne) pour produire un résultat. Comparé aux 11 000 lignes (externe + interne) d'une requête non corrélée sur les mêmes ensembles de résultats, ce n'est pas bon.

Cependant, ceci est juste le pire des cas. Dans de nombreux cas, le SGBD pourra exploiter les index pour réduire considérablement le nombre de lignes. Même si seule la requête interne peut utiliser un index, les 10 000 lignes deviennent ~ 13, ce qui réduit le total à 13 000.

L'opérateur exists peut arrêter le traitement des lignes après le premier, réduisant ainsi le coût de la requête, en particulier lorsque la plupart des lignes externes correspondent à au moins une ligne interne.

Dans certains cas rares, j'ai vu SQL Server 2008R2 optimiser les sous-requêtes corrélées à une jointure de fusion (qui traverse les deux ensembles une seule fois - meilleur scénario possible) où un index approprié peut être trouvé dans les requêtes internes et externes.

Le vrai coupable de la mauvaise performance n'est pas nécessairement , les sous-requêtes corrélées mais scans imbriqués.

Answer 2

Cela dépend de la version MySQL - il y a un bogue dans l'optimiseur de requêtes MySQL dans les versions jusqu'à 6.0.

avec des sous-requêtes « IN » ne sont pas correctement optimisés (mais exécutés encore et encore comme ceux à charge). Ce bogue n'affecte pas les requêtes ou les jointures exists.

Le problème est que, pour une déclaration qui utilise un sous-requête, l'optimiseur Récrit comme sous-requête corrélée. Considérez l'instruction suivante qui utilise une sous-requête non corrélée:

SELECT ... FROM t1 O WH t1.a IN (SELECT b FROM t2);

L'optimiseur réécrit l'instruction à une sous-requête corrélée:

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

Si les requêtes internes et externes retournent M rangées et N, respectivement, le temps d'exécution devient de l'ordre de O (M × N), au lieu de O (M + N) en tant que il serait pour un décorrélées sous-requête.

réf.

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

Answer 3

Comme vous le savez déjà, une sous-requête n'utilise pas les valeurs de la requête externe, elle n'est donc exécutée qu'une seule fois. La sous-requête corrélée est synchronisée, elle est donc exécutée pour chaque ligne traitée dans la requête externe.

L'avantage d'utiliser EXISTS est que, s'il est considéré comme satisfait, l'exécution de la sous-requête s'arrête après le retour d'au moins une ligne. Donc, il peut être plus rapide qu'une simple sous-requête. Mais ce n'est pas une règle générale! Tout dépend de la requête que vous exécutez, de l'optimiseur de requête et de la version du moteur d'exécution SQL.

EXISTS est recommandé d'être utilisé lorsque vous avez, par exemple, une instruction conditionnelle if, car elle est certainement plus rapide que count.

Vous ne pouvez pas vraiment comparer les deux sous-requêtes en utilisant un simple benchmark de 4 ou 3 requêtes.

J'espère que c'est utile!