Ottimizzazione da EXISTS a IN

MySQL (perfino MySQL 5.6) prevede una sola possibile strategia per eseguire le subquery EXISTS. La strategia è sostanzialmente un'esecuzione diretta, "naive", senza riscritture.

MariaDB 5.3 ha introdotto una ricca gamma di ottimizzazioni per le subquery IN. Ora, è interessante trasformare una clausola EXISTS in una IN, per poter applicare queste ottimizzazioni.

Una EXISTS viene convertita in una IN in due casi:

1. Subquery EXISTS correlate in modo triviale
2. Semi-join EXISTS

Ma analizziamole nei dettagli.

Subquery EXISTS correlate in modo triviale

Spesso la subquery EXISTS è correlata, ma la correlazione è triviale. La subquery è del tipo:

EXISTS (SELECT ...  FROM ... WHERE outer_col= inner_col AND inner_where)

Dove "outer_col" è l'unica menzione alla subquery che si trova nei campi esterni. In questo caso, la subquery può essere riscritta come una IN non correlata:

outer_col IN (SELECT ... FROM ... WHERE inner_where)

(E' necessaria una cura particolare per i valori NULL, si eda sotto). MariaDB, per le subquery IN non correlate, può scegliere tra due strategie di esecuzione, in base al loro costo:

• da IN- a EXISTS (essenzialmente, riconvertirla in una EXISTS)
• Materialization

In pratica, convertire una EXISTS correlata in modo triviale in una IN dà all'ottimizzatore la possibilità di utilizzare la Strategia di materializzazione.

Attualmente la conversione EXISTS->IN è possibile solo per le subquery che si trovano al livello più alto della clausola WHERE, o che si trovano in una operazione NOT che sia direttamente al livello più alto della clausola WHERE.

Semi-join EXISTS subqueries

If EXISTS subquery is an AND-part of the WHERE clause:

SELECT ... FROM outer_tables WHERE EXISTS (SELECT ...) AND ...

then it satisfies the main property of semi-join subqueries:

with semi-join subquery, we're only interested in records of outer_tables that have matches in the subquery

Semi-join optimizer offers a rich set of execution strategies for both correlated and uncorrelated subqueries. The set includes FirstMatch strategy which is an equivalent of how EXISTS suqueries are executed, so we do not lose any opportunities when converting an EXISTS subquery into a semi-join.

In theory, it makes sense to convert all kinds of EXISTS subqueries: convert both correlated and uncorrelated ones, convert irrespectively of whether the subquery has inner=outer equality.

In practice, the subquery will be converted only if it has inner=outer equality. Both correlated and uncorrelated subqueries are converted.

Handling of NULL values

TODO: rephrase this:

• IN has complicated NULL-semantics. NOT EXISTS doesn't.
• EXISTS-to-IN adds IS NOT NULL before the subquery predicate, when required

Control

The optimization is controlled by exists_to_in flag in @@optimizer_switch. Currently, the optimization is OFF by default.

Limitations

EXISTS-to-IN doesn't handle

• subqueries that have GROUP BY, aggregate functions, or HAVING clause
• subqueries are UNIONs
• a number of degenerate edge cases