Ottimizzazioni delle subquery non-semi-join

Alcuni tipi di subquery "IN" non possono essere trasformate in semi-join. Queste subquery possono essere sia correlate sia non correlate. MariaDB, per avere buone performance in tutti i casi, ha diverse strategie alternative per questi tipi di subquery. Qualora sia possibile applicare diverse strategie, l'ottimizzatore sceglie quella ottimale basandosi su una stima dei costi.

Le due strategie principali per le non-semi-join sono la materializzazione (detta anche materializzazione outside-in) e la trasformazione da-in-a-exists. La prima è applicabile solo per le subquery non correlate, mentre la seconda può essere usata sia per le correlate sia per le non correlate.

Applicabilità

Le subquery IN non possono essere trasformate in semi-join nei seguenti casi. Gli esempi sono utilizzano il database World della regression test suite di MariaDB.

Subquery in una disgiunzione (OR)

La subquery si trova direttamente o indirettamente in una operazione OR nella clausola WHERE della query esterna.

Schema:

SELECT ... FROM ... WHERE (espr1, ..., esprN) [NOT] IN (SELECT ... ) OR espr;

Esempio:

SELECT Name FROM Country
WHERE (Code IN (select Country from City where City.Population > 100000) OR
       Name LIKE 'L%') AND
      surfacearea > 1000000;

Predicato di negazione delle subquery (NOT IN)

Schema:

SELECT ... FROM ... WHERE ... (espr1, ..., esprN) NOT IN (SELECT ... ) ...;

Esempio:

SELECT Country.Name
FROM Country, CountryLanguage 
WHERE Code NOT IN (SELECT Country FROM CountryLanguage WHERE Language = 'English')
  AND CountryLanguage.Language = 'French'
  AND Code = Country;

Subquery nelle clausole SELECT o HAVING

La subquery si trova nelle clausole SELECT o HAVING della query esterna.

Query pattern:

SELECT campo1, ..., (SELECT ...)  WHERE ...;
SELECT ...  WHERE ... HAVING (SELECT ...);

Esempio:

select Name, City.id in (select capital from Country where capital is not null) as is_capital
from City
where City.population > 10000000;

Subquery con una UNION

La subquery stessa è una UNION, mentre il predicato IN può trovarsi in qualsiasi punto della query.

Schema:

... [NOT] IN (SELECT ... UNION SELECT ...)

Esempio:

SELECT * from City where (Name, 91) IN
(SELECT Name, round(Population/1000) FROM City WHERE Country = "IND" AND Population > 2500000
UNION
 SELECT Name, round(Population/1000) FROM City WHERE Country = "IND" AND Population < 100000);

La materializzazione per le subquery IN non correlate

Le basi della materializzazione

L'idea di base della materializzazione delle subquery è eseguire subquery e registrare il risultato in una tabella temporanea interna le cui colonne sono tutte indicizzate. Naturalmente, questo è possibile solo se la subquery non è correlata. Il predicato IN verifica se l'operando di sinistra è presente nel risultato. Pertanto non è necessario registrare le righe duplicate della subquery nella tabella temporanea. Registrare le righe in modo univoco ha due vantaggi: le dimensioni della tabella temporanea sono più ridotte e l'indice su tutte le colonne può essere univoco.

Se le dimensioni della tabella temporanea sono minori della variabile tmp_table_size system, la tabella è una HEAP in memoria, con l'indice di tipo hash. Nei rari casi in cui il risultato della subquery eccede questo limite, la tabella temporanea viene registrata su disco con ARIA o MyISAM, con l'indice di tipo B-tree (ARIA è il default).

La materializzazione avviene su richiesta durante la prima esecuzione del predicato IN. Una volta materializzata la subquery, il predicato IN viene elaborato in modo molto efficiente tramite ricerche sugli indice dell'espressione esterna nell'indice univoco della tabella temporanea materializzata. Se c'è una corrispondenza, IN è vero, altrimenti è falso.

Esecuzione efficiente sensibile ai NULL

I predicati IN possono restituire NULL se uno qualsiasi dei suoi argomenti è NULL. A seconda della sua posizione in una query, un valore NULL può essere equivalente a FALSE. Questo avviene quando, sostituendo NULL con FALSE, si otterrebbero esattamente gli stessi risultati. Quando IN restituisce NULL, non è distinguibile da FALSE se il predicato:

• non è negato,
• non è passato a una funzione come argomento,
• è in una clausola WHERE oppure ON.

In tutti questi casi, IN viene elaborato come descritto nel paragrafo precedente con una ricerca sugli indici nella subquery materializzata. In tutti i casi rimanenti, quando NULL non può essere distinto da FALSE, non è possibile utilizzare le ricerche sugli indici. Non si tratta di una limitazione del server, ma è una conseguenza della semantica di NULL nello standard ANSI SQL.

Si supponga che un predicato venga valutato come

NULL IN (select
not_null_col from t1)

, cioè che l'operatore di sinistra sia un valore NULL, e che non ci siano NULL nella the subquery. In questo caso il valore di IN non è né FALSE, né TRUE; piuttosto, è NULL. Se si eseguisse una ricerca su indice con il NULL nella chiave, quel valore non può essere trovato in not_null_col, e il predicato IN restituirebbe erroneamente FALSE.

In generale, una valore NULL su qualsiasi lato di IN agisce come "jolly" che corrisponde a qualsiasi valore, e se esiste una corrispondenza, il risultato di IN è NULL. Si consideri il seguente esempio:

Se l'argomento di sinistra di IN è la riga: (7, NULL, 9) , e il risultato della subquery a destra è la tabella:

(7, 8, 10)
(6, NULL, NULL)
(7, 11, 9)

Il predicato IN corrisponde alla riga (7, 11, 9) , e il risultato di IN è NULL. Le corrispondenze in cui i valori differenti su qualsiasi lato della IN corrispondono a un NULL sull'altro lato della IN, si chiamano partial match.

Per poter calcolare in modo efficiente il risultato di un predicato IN in presenza di valori NULL, MariaDB implementa due particolari algoritmi per il partial matching, descritti qui nel dettaglio.

• Partial match con il rowid-merge
  Questa tecnica viene usata quando il numero delle righe del risultato della subquery supera un certo limite. Vengono creati indici speciali su alcune delle colonne della tabella temporanea, e vengono uniti con la scansione individuale di ogni indice, effettuando un'operazione simile a set-intersection.

• Partial matching con la scansione della tabella
  Questo algoritmo di usa per tabelle molto piccole quando il carico di lavoro della tecnica rowid-merge non è giustificato. Allora il server fa semplicemente una scansione della subquery materializzara, e cerca i partial match. Poiché tale strategia non necessita di alcun buffer in memoria, viene usata anche quando non c'è memoria a sufficienza per gli indici dell'algoritmo rowid-merge.

Limitazioni

La stratezia della materializzazione delle subquery in teoria è universale; tuttavia, a causa di alcune limitazioni tecniche del server MariaDB, vi sono alcuni casi in cui non può essere usata.

• Campi BLOB
  O l'operando di sinistra del predicato IN è un campo di tipo BLOB, o la subquery estrae uno o più campi BLOB.

• Campi incompatibili
  TODO

In questi casi, il server rimedia utilizzando la trasformazione da-IN-a-EXISTS transformation.

Trasformazione da-IN-a-EXISTS

Questa ottimizzazione è l'unica strategia di esecuzione delle subquery che esisteva nelle versioni di MariaDB e MySQL antecedenti a MariaDB 5.3. Sono stati apportati vari cambiamenti e corretti numerosi bug nel codice di questa funzionalità, ma rimane essenzialmente uguale a prima.

Per il momento si rimanda il lettore alla documentazione di MySQL per approfondire questa ottimizzazione.

Performance

Esempio di velocizzazione tra MySQL 5.x e MariaDB 5.1/5.2

A seconda della query e dei dati, una delle tue strategie descritte qui potrebbe essere esponenzialmente più veloce o più lenta dell'altra.

Le versioni più vecchie di MariaDB e tutte le attuali versioni di MySQL (comprese MySQL 5.5 e MySQL 5.6 DMR, al luglio 2011) implementano solo la trasformazione da-IN-a-EXISTS. Come illustrato sotto, questa strategia è inferiore nella maggior parte dei casi alla materializzazione delle subquery.

Si consideri la query seguente sui dati del benchmark DBT3 scale 10. Si vogliono trovare i clienti che hanno il bilancio più alto nel loro stato:

SELECT * FROM part
WHERE p_partkey IN
      (SELECT l_partkey FROM lineitem
       WHERE l_shipdate between '1997-01-01' and '1997-02-01')
ORDER BY p_retailprice DESC LIMIT 10;

I tempi di esecuzione di questa query sono i seguenti:

• Tempo di esecuzione in MariaDB 5.2/MySQL 5.x (tutte le versioni di MySQL): > 1 h
  La query impiega più di un'ora (non abbiamo voluto aspettare oltre), perché fa un uso poco pratico delle subquery in casi simili. L'istruzione EXPLAIN, sotto, mostra che la subquery viene trasformata in una correlata, il che indica una trasformazione da-IN-a-EXISTS.
  

+--+------------------+--------+--------------+-------------------+----+------+---------------------------+
|id|select_type       |table   |type          |key                |ref |rows  |Extra                      |
+--+------------------+--------+--------------+-------------------+----+------+---------------------------+
| 1|PRIMARY           |part    |ALL           |NULL               |NULL|199755|Using where; Using filesort|
| 2|DEPENDENT SUBQUERY|lineitem|index_subquery|i_l_suppkey_partkey|func|    14|Using where                |
+--+------------------+--------+--------------+-------------------+----+------+---------------------------+

• Tempo di esecuzione in MariaDB 5.3: 43 secondi
  In MariaDB 5.3, la stessa query impiega meno di un minuto. La EXPLAIN mostra che la subquery resta non correlata, e questo significa che viene materializzata.
  

+--+------------+-----------+------+------------------+----+------+-------------------------------+
|id|select_type |table      |type  |key               |ref |rows  |Extra                          |
+--+------------+-----------+------+------------------+----+------+-------------------------------+
| 1|PRIMARY     |part       |ALL   |NULL              |NULL|199755|Using temporary; Using filesort|
| 1|PRIMARY     |<subquery2>|eq_ref|distinct_key      |func|     1|                               |
| 2|MATERIALIZED|lineitem   |range |l_shipdate_partkey|NULL|160060|Using where; Using index       |
+--+------------+-----------+------+------------------+----+------+-------------------------------+

La velocizzazione qui è praticamente infinita, perché MySQL e le più vecchie versioni di MariaDB non possono completare la query in un tempo ragionevole.

Per mostrare i benefici del partial match, è stata estesa la tabella customer del benchmark DBT3 con due colonne aggiuntive:

• c_pref_nationkey - lo stato da cui si preferisce acquistare,
• c_pref_brand - il brand preferito.

Entrambe hanno un prefisso con la percentuale di valori NULL presenti, quindi ad esempio c_pref_nationkey_05 ha un 5% di valori NULL.

Si consideri la query "Trova tutti i clienti che non hanno acquistato dallo stato preferito, o il brand preferito in un dato intervallo di tempo":

SELECT count(*)
FROM customer
WHERE (c_custkey, c_pref_nationkey_05, c_pref_brand_05) NOT IN
  (SELECT o_custkey, s_nationkey, p_brand
   FROM orders, supplier, part, lineitem
   WHERE l_orderkey = o_orderkey and
         l_suppkey = s_suppkey and
         l_partkey = p_partkey and
         p_retailprice < 1200 and
         l_shipdate >= '1996-04-01' and l_shipdate < '1996-04-05' and
         o_orderdate >= '1996-04-01' and o_orderdate < '1996-04-05');

• Tempo di esecuzione in MariaDB 5.2/MySQL 5.x (any MySQL): 40 secondi
• Tempo di esecuzione in MariaDB 5.3: 2 secondi

Questa query è stata velocizzata di 20 volte.

Linee guida sulle performance

TODO

Controllo dell'ottimizzatore

In alcuni casi potrebbe essere necessario forzare una scelta per l'ottimizzatore. Tipicamente questo avviene per scopi di benchmark o di test, o per imitare il comportamento di una versione più vecchia del server, o se l'ottimizzatore ha fatto una scelta infelice.

Tutte le strategie sopra possono essere controllare con i seguenti switch nella variabile di sistema optimizer_switch:

• materialization=on/off
  In casi molto particolari, anche se si forza la materializzazione, l'ottimizzazione potrebbe ricorrere comunque alla strategia da-IN-a-EXISTS perché la materializzazione non è applicabile. Nei casi in cui la materializzazione richiede il partial match (perché sono presenti i valori NULL), vi sono due switch che controllano le due strategie di partial match:
  
  • partial_match_rowid_merge=on/off
    Questo switch controlla la strategia Rowid-merge. In aggiunta, la variabile di sistema rowid_merge_buff_size determina la memoria massima disponibile per l'algoritmo Rowid-merge.
  • partial_match_table_scan=on/off
    Determina la strategia alternatica di partial match, che esegue la scansione completa di una tabella.

• in_to_exists=on/off
  Questo switch controlla la trasformazione da-IN-a-EXISTS.

• Variabili di sistema tmp_table_size e max_heap_table_size
  La variabile tmp_table_size determina il limite massimo per le tabelle temporanee interne di tipo MEMORY. Se una tabella temporanea interna supera questo limite, viene convertita automaticamente in una tabella su disco, di tipo Aria o MyISAM, con un indice B-tree. Si noti però che una tabella MEMORY non può essere più grande di max_heap_table_size.

I due principali switch - materialization e in_to_exists non possono essere off contemporaneamente. Se entrambi sono off, il server produce un errore.