La strategia Semi-join Materialization

La Semi-join Materialization è un tipo particolare di materializzazione delle subquery utilizzata per le subquery di tipo semi-join. In realtà comprende due strategie:

• Materializzazione/ricerca
• Materializzazione/scansione

L'idea

Si consideri una query che trova i Paesi in Europa che contengono grandi città:

select * from Country 
where Country.code IN (select City.Country 
                       from City 
                       where City.Population > 7*1000*1000)
      and Country.continent='Europe'

La subquery non è correlata, quindi può essere eseguita indipendentemente dalla query esterna. L'idea della materializzazione delle semi-join consiste appunto nel materializzarle, popolare una tabella temporanea con i possibili valori del campo City.country e infine eseguire una join con gli Stati europei:

La join può essere eseguita in due direzioni:

1. Dalla tabella materializzata agli Stati in Europa
2. Dagli Stati in Europa alla tabella materializzata

Il primo modo implica l'esecuzione di una scansione completa della tabella materializzata, perciò viene chiamato "Materialization-scan".

Se si esegue una join da Countries alla tabella materializzata, il modo meno costoso per trovare una corrispondenza nella tabella materializzata è eseguire una ricerca sulla chiave primaria (ne ha una: è stata usata per eliminare i duplicati). Per questo motivo. questa strategia si chiama "Materialization-lookup".

Semi-join materialization in azione

Materialization-Scan

Se si cercano le città con una popolazione maggiore di 7 milioni, l'ottimizzatore usa la strategia Materialization-Scan, ed ecco il risultato di EXPLAIN:

MariaDB [world]> explain select * from Country where Country.code IN (select City.Country from City where  City.Population > 7*1000*1000);
+----+--------------+-------------+--------+--------------------+------------+---------+--------------------+------+-----------------------+
| id | select_type  | table       | type   | possible_keys      | key        | key_len | ref                | rows | Extra                 |
+----+--------------+-------------+--------+--------------------+------------+---------+--------------------+------+-----------------------+
|  1 | PRIMARY      | <subquery2> | ALL    | distinct_key       | NULL       | NULL    | NULL               |   15 |                       |
|  1 | PRIMARY      | Country     | eq_ref | PRIMARY            | PRIMARY    | 3       | world.City.Country |    1 |                       |
|  2 | MATERIALIZED | City        | range  | Population,Country | Population | 4       | NULL               |   15 | Using index condition |
+----+--------------+-------------+--------+--------------------+------------+---------+--------------------+------+-----------------------+
3 rows in set (0.01 sec)

Da qui si vede che:

• Ci sono ancora due SELECTs (sono le colonne con id=1 e id=2)
• La seconda select (con id=2) ha select_type=MATERIALIZED. Ciò significa che viene eseguita e il suo risultato viene inserito in una tabella temporanea con un indice unico su tutte le colonne. Lo scopo di questo indice è impedire la presenza di record doppi.
• La prima select ha ricevuto il nome di tabella <subquery2>. Essa è la tabella che si ottiene dalla materializzazione della select con id=2.

L'ottimizzatore sceglie di effettuare una scansione completa della tabella materializzata, perciò in questo esempio si usa la strategia Materialization-Scan.

Per quanto riguarda il costo dell'esecuzione, verranno lette 15 righe dalla tabella City, scritte 15 righe nella tabella materializzata, che poi verranno lette (l'ottimizzatore presume che non ci siano duplicati) e infine 15 accessi eq_ref alla tabella Country. In totale, sono 45 letture e 15 inserimenti.

Per comparare i due metodi, se si lancia EXPLAIN in MySQL, si ottiene quanto segue:

MySQL [world]> explain select * from Country where Country.code IN (select City.Country from City where  City.Population > 7*1000*1000);
+----+--------------------+---------+-------+--------------------+------------+---------+------+------+------------------------------------+
| id | select_type        | table   | type  | possible_keys      | key        | key_len | ref  | rows | Extra                              |
+----+--------------------+---------+-------+--------------------+------------+---------+------+------+------------------------------------+
|  1 | PRIMARY            | Country | ALL   | NULL               | NULL       | NULL    | NULL |  239 | Using where                        |
|  2 | DEPENDENT SUBQUERY | City    | range | Population,Country | Population | 4       | NULL |   15 | Using index condition; Using where |
+----+--------------------+---------+-------+--------------------+------------+---------+------+------+------------------------------------+

Con questo piano, si effettuano (239 + 239*15) = 3824 letture nelle tabelle.

Materialization-Lookup

Si supponga di modificare leggermente la query e cercare gli Stati che hanno città con una popolazione superiore a un milione (invece di sette):

MariaDB [world]> explain select * from Country where Country.code IN (select City.Country from City where  City.Population > 1*1000*1000) ;
+----+--------------+-------------+--------+--------------------+--------------+---------+------+------+-----------------------+
| id | select_type  | table       | type   | possible_keys      | key          | key_len | ref  | rows | Extra                 |
+----+--------------+-------------+--------+--------------------+--------------+---------+------+------+-----------------------+
|  1 | PRIMARY      | Country     | ALL    | PRIMARY            | NULL         | NULL    | NULL |  239 |                       |
|  1 | PRIMARY      | <subquery2> | eq_ref | distinct_key       | distinct_key | 3       | func |    1 |                       |
|  2 | MATERIALIZED | City        | range  | Population,Country | Population   | 4       | NULL |  238 | Using index condition |
+----+--------------+-------------+--------+--------------------+--------------+---------+------+------+-----------------------+
3 rows in set (0.00 sec)

L'output di EXPLAIN è simile a quello ottenuto per la Materialization-scan, con qualche eccezione:

• L'accesso alla tabella <subquery2> avviene con il metodo eq_ref
• L'accesso utilizza un indice chiamato distinct_key

Ciò significa che l'ottimizzatore pianifica di effettuare ricerche sull'indice nella tabella materializzata. In altre parole, sceglie di usare la strategia Materialization-lookup.

In MySQL (o con optimizer_switch='semijoin=off,materialization=off'), EXPLAIN produce il seguente output:

MySQL [world]> explain select * from Country where Country.code IN (select City.Country from City where  City.Population > 1*1000*1000) ;
+----+--------------------+---------+----------------+--------------------+---------+---------+------+------+-------------+
| id | select_type        | table   | type           | possible_keys      | key     | key_len | ref  | rows | Extra       |
+----+--------------------+---------+----------------+--------------------+---------+---------+------+------+-------------+
|  1 | PRIMARY            | Country | ALL            | NULL               | NULL    | NULL    | NULL |  239 | Using where |
|  2 | DEPENDENT SUBQUERY | City    | index_subquery | Population,Country | Country | 3       | func |   18 | Using where |
+----+--------------------+---------+----------------+--------------------+---------+---------+------+------+-------------+

Come si vede, entrambi i piani eseguono una scansione completa della tabella Country. Come secondo passaggio, MariaDB riempe la tabella materializzata (238 righe lette dalla tabella City e scritte nella tabella temporanea) ed esegue una ricerca su indice univoco per ogni record nella tabella Country, quindi esegue 238 ricerche su indice univoco. In totale, il costo del secondo passaggio è di (239+238) = 477 letture e 238 inserimenti (questi ultimi su tabella temporanea).

Il piano di MySQL per il secondo passaggio consiste nel leggere 18 righe utilizzando un indice su City.Country per ogni record trovato nella tabella Country. Questa operazione ha un costo di (18*239) = 4302 letture. Se la subquery venisse invocata meno volte, questo piano risulterebbe molto migliore rispetto alla materializzazione. Anche MariaDB ha la possibilità di scegliere questo piano (si veda la strategia FirstMatch), ma in questo caso non l'ha fatto.

Subquery con raggruppamento

MariaDB è in grado di utilizzare la strategia di materializzazione delle Semi-join anche quando la subquery ha un raggruppamento (mentre le altre strategie per le semi-join non sono applicabili in questi casi).

Ciò permette un'esecuzione efficiente delle query che cercano l'elemento migliore, o l'ultimo elemento, in un dato gruppo.

Per esempio, ecco come cercare le città che hanno la popolazione più alta nel continente in cui si trovano:

explain 
select * from City 
where City.Population in (select max(City.Population) from City, Country 
                          where City.Country=Country.Code 
                          group by Continent)
+------+--------------+-------------+------+---------------+------------+---------+----------------------------------+------+-----------------+
| id   | select_type  | table       | type | possible_keys | key        | key_len | ref                              | rows | Extra           |
+------+--------------+-------------+------+---------------+------------+---------+----------------------------------+------+-----------------+
|    1 | PRIMARY      | <subquery2> | ALL  | distinct_key  | NULL       | NULL    | NULL                             |  239 |                 |
|    1 | PRIMARY      | City        | ref  | Population    | Population | 4       | <subquery2>.max(City.Population) |    1 |                 |
|    2 | MATERIALIZED | Country     | ALL  | PRIMARY       | NULL       | NULL    | NULL                             |  239 | Using temporary |
|    2 | MATERIALIZED | City        | ref  | Country       | Country    | 3       | world.Country.Code               |   18 |                 |
+------+--------------+-------------+------+---------------+------------+---------+----------------------------------+------+-----------------+
4 rows in set (0.00 sec)

Le città sono queste:

+------+-------------------+---------+------------+
| ID   | Name              | Country | Population |
+------+-------------------+---------+------------+
| 1024 | Mumbai (Bombay)   | IND     |   10500000 |
| 3580 | Moscow            | RUS     |    8389200 |
| 2454 | Macao             | MAC     |     437500 |
|  608 | Cairo             | EGY     |    6789479 |
| 2515 | Ciudad de México | MEX     |    8591309 |
|  206 | São Paulo        | BRA     |    9968485 |
|  130 | Sydney            | AUS     |    3276207 |
+------+-------------------+---------+------------+

Riassunto

Materializzazione delle semi-join

• Può essere usata per le subquery IN non correlate. La subquery può utilizzare il raggruppamento e/o le funzioni aggreganti.
• Appare in EXPLAIN come type=MATERIALIZED per la subquery, e una riga contenente table=<subqueryN> nella query madre.
• E' abilitata quando si hanno materialization=on e semijoin=on in @@optimizer_switch.
• Condivide il flag materialization=on|off con la materializzazione delle semi-join.