Ottime ottimizzazioni SQL che non dipendono dal modello di costo. Parte 1

Cinque semplici ottimizzazioni che possono essere implementate basandosi solo sui metadati (ovvero i vincoli) e sulla query stessa Ti offriamo un adattamento dell'articolo di Lukas Eder, pensato per coloro che hanno una conoscenza generale di database e SQL, nonché qualche esperienza pratica con DBMS . L'ottimizzazione dei costi è in realtà un modo standard per ottimizzare le query SQL nei database moderni. Questo è il motivo per cui è così difficile scrivere manualmente un algoritmo complesso in 3GL (linguaggi di programmazione di terza generazione) le cui prestazioni supererebbero il piano di esecuzione calcolato dinamicamente generato da un moderno ottimizzatore. Oggi non parleremo dell'ottimizzazione dei costi, cioè dell'ottimizzazione basata sul modello di costo del database. Vedremo ottimizzazioni molto più semplici. Quelli che possono essere implementati basandosi solo sui metadati (ovvero sulle restrizioni) e sulla richiesta stessa. Di solito la loro implementazione per un database non è un binomio di Newton, poiché, in questo caso, qualsiasi ottimizzazione porterà a un piano di esecuzione migliore, indipendentemente dalla presenza di indici, volumi di dati e asimmetria della distribuzione dei dati. "Non un binomio di Newton" non significa quanto sia facile implementare l'ottimizzazione, ma se dovrebbe essere fatta. Queste ottimizzazioni eliminano il lavoro extra non necessario [per il database] ( al contrario del lavoro richiesto e non necessario, di cui ho già scritto ).

A cosa servono queste ottimizzazioni?

La maggior parte di essi sono utilizzati per:

• correzioni di bug nelle query;
• consentendo il riutilizzo delle viste senza che il database esegua effettivamente la logica della vista.

Nel primo caso, si potrebbe dire: “E allora, vai avanti e correggi questa stupida query SQL”. Ma chi non ha mai sbagliato mi scagli prima una pietra. Il secondo caso è particolarmente interessante: ci dà la possibilità di creare librerie complesse di viste e funzioni di tabella che possono essere riutilizzate su più livelli.

Database utilizzati

In questo articolo confronteremo 10 ottimizzazioni SQL nei cinque DBMS più utilizzati ( secondo le classifiche dei database ):

• Oracolo 12.2;
• MySQL 8.0.2;
• SQLServer2014;
• PostgreSQL 9.6;
• DB2LUW10.5.

Un'altra valutazione quasi gli fa eco. Come al solito, in questo articolo interrogherò il database Sakila . Ecco un elenco di questi dieci tipi di ottimizzazioni:

1. chiusura transitiva;
2. predicati impossibili e chiamate di tabelle non necessarie;
3. eliminando JOIN;
4. eliminazione dei predicati “privi di significato”;
5. proiezioni nelle sottoquery EXISTS;
6. fusione di predicati;
7. insiemi dimostrabilmente vuoti;
8. vincoli VERIFICA;
9. connessioni riflessive non necessarie;
10. Predicati pushdown

Oggi parleremo delle pp. 1-3, nella seconda parte - 4 e 5 e nella parte 3 - 6-10.

1. Chiusura transitiva

Cominciamo con qualcosa di più semplice: la chiusura transitiva . Questo è un concetto banale che si applica a molte operazioni matematiche, come l'operatore di uguaglianza. In questo caso può essere formulato come segue: se A = B e B = C, allora A = C.

Non è difficile, vero? Ma questo ha alcune implicazioni interessanti per gli ottimizzatori SQL. Diamo un'occhiata a un esempio. Estraiamo tutti i film con ACTOR_ID = 1:

SELECT first_name, last_name, film_id
FROM actor a
JOIN film_actor fa ON a.actor_id = fa.actor_id
WHERE a.actor_id = 1;

Il risultato è il seguente:

FIRST_NAME      LAST_NAME  FILM_ID
PENELOPE        GUINESS    1
PENELOPE        GUINESS    23
PENELOPE        GUINESS    25
PENELOPE        GUINESS    106
PENELOPE        GUINESS    140
PENELOPE        GUINESS    166
...

Diamo ora un'occhiata al piano per l'esecuzione di questa query nel caso del DBMS Oracle:

--------------------------------------------------------------
| Id  | Operation                    | Name          | Rows  |
--------------------------------------------------------------
|   0 | SELECT STATEMENT             |               |       |
|   1 |  NESTED LOOPS                |               |    19 |
|   2 |   TABLE ACCESS BY INDEX ROWID| ACTOR         |     1 |
|*  3 |    INDEX UNIQUE SCAN         | PK_ACTOR      |     1 |
|*  4 |   INDEX RANGE SCAN           | PK_FILM_ACTOR |    19 |
--------------------------------------------------------------
Predicate Information (identified by operation id):
---------------------------------------------------
   3 - access("A"."ACTOR_ID"=1)
   4 - access("FA"."ACTOR_ID"=1)

Qui è particolarmente interessante la sezione sui predicati. Il predicato ACTOR_ID = 1, a causa della chiusura transitiva, si applica sia alla tabella ACTOR che alla tabella FILM_ACTOR. Se:

• A.ACTOR_ID = 1 (из предиката WHERE) и…
• A.ACTOR_ID = FA.ACTOR_ID (из предиката ON)
  То:
• FA.ACTOR_ID = 1

Per query più complesse, questo produce risultati molto interessanti. In particolare, l’accuratezza delle stime della cardinalità aumenta in modo significativo, poiché diventa possibile selezionare stime sulla base di uno specifico valore costante del predicato, e non, ad esempio, del numero medio di film per attori, come nella query seguente (restituendo il stesso risultato):

SELECT first_name, last_name, film_id
FROM actor a
JOIN film_actor fa ON a.actor_id = fa.actor_id
WHERE first_name = 'PENELOPE'
AND last_name = 'GUINESS'

Il suo piano:

----------------------------------------------------------------------------
| Id  | Operation                            | Name                | Rows  |
----------------------------------------------------------------------------
|   0 | SELECT STATEMENT                     |                     |       |
|   1 |  NESTED LOOPS                        |                     |     2 |
|*  2 |   TABLE ACCESS BY INDEX ROWID BATCHED| ACTOR               |     1 |
|*  3 |    INDEX RANGE SCAN                  | IDX_ACTOR_LAST_NAME |     3 |
|*  4 |   INDEX RANGE SCAN                   | PK_FILM_ACTOR       |    27 |
----------------------------------------------------------------------------
Predicate Information (identified by operation id):
---------------------------------------------------
   2 - filter("A"."FIRST_NAME"='PENELOPE')
   3 - access("A"."LAST_NAME"='GUINESS')
   4 - access("A"."ACTOR_ID"="FA"."ACTOR_ID")

Come puoi vedere, il numero di righe nella tabella FILM_ACTOR è sovrastimato, mentre il NESTED LOOP è sottostimato. Ecco un paio di valori interessanti:

SELECT count(*) FROM film_actor WHERE actor_id = 1;
SELECT avg(c) FROM (
  SELECT count(*) c FROM film_actor GROUP BY actor_id
);

Risultato:

19
27.315

Da qui provengono le stime. Se il database sa che stiamo parlando di ACTOR_ID = 1, allora può raccogliere statistiche sul numero di film per questo particolare attore . In caso contrario (poiché il meccanismo standard di raccolta delle statistiche non correla FIRST_NAME/LAST_NAME con ACTOR_ID), otterremo il numero medio di film per tutti gli attori . Un errore semplice e poco importante in questo caso particolare, ma in una query complessa può propagarsi ulteriormente, accumularsi e portare ulteriormente nella query (più in alto nel piano) ad una scelta JOIN errata. Pertanto, ogni volta che puoi, progetta i tuoi join e i predicati semplici per sfruttare la chiusura transitiva. Quali altri database supportano questa funzionalità?

DB2

SÌ!

Explain Plan
-----------------------------------------------------------
ID | Operation              |                 Rows | Cost
 1 | RETURN                 |                      |   13
 2 |  NLJOIN                |              27 of 1 |   13
 3 |   FETCH ACTOR          |     1 of 1 (100.00%) |    6
 4 |    IXSCAN PK_ACTOR     |   1 of 200 (   .50%) |    0
 5 |   IXSCAN PK_FILM_ACTOR | 27 of 5462 (   .49%) |    6
Predicate Information
 4 - START (Q2.ACTOR_ID = 1)
      STOP (Q2.ACTOR_ID = 1)
 5 - START (1 = Q1.ACTOR_ID)
      STOP (1 = Q1.ACTOR_ID)

A proposito, se ti piacciono i piani di esecuzione interessanti come questo, dai un'occhiata allo script di Markus Winand .

MySQL

Sfortunatamente, i piani di esecuzione MySQL non sono adatti per questo tipo di analisi. Il predicato stesso manca dalle informazioni di output:

ID  SELECT TYPE  TABLE  TYPE   REF    ROWS
------------------------------------------
1   SIMPLE       a      const  const  1
1   SIMPLE       fa     ref    const  19

Ma il fatto che const sia specificato due volte nella colonna REF indica che entrambe le tabelle stanno cercando un valore costante. Allo stesso tempo, il piano di query con FIRST_NAME/LAST_NAME si presenta così:

ID  SELECT TYPE  TABLE  TYPE   REF         ROWS
-----------------------------------------------
1   SIMPLE       a      ref    const       3
1   SIMPLE       fa     ref    a.actor_id  27

E come puoi vedere, REF ora fa riferimento alla colonna dal predicato JOIN. Il punteggio di cardinalità è quasi lo stesso di Oracle. Quindi sì, MySQL supporta anche le chiusure transitive.

PostgreSQL

SÌ!

QUERY PLAN
------------------------------------------------------------------------------------
Nested Loop  (cost=4.49..40.24 rows=27 width=15)
  ->  Seq Scan on actor a  (cost=0.00..4.50 rows=1 width=17)
        Filter: (actor_id = 1)
  ->  Bitmap Heap Scan on film_actor fa  (cost=4.49..35.47 rows=27 width=4)
        Recheck Cond: (actor_id = 1)
        ->  Bitmap Index Scan on film_actor_pkey  (cost=0.00..4.48 rows=27 width=0)
              Index Cond: (actor_id = 1)

server SQL

SÌ!

|--Nested Loops(Inner Join)
     |--Nested Loops(Inner Join)
     |    |--Index Seek (SEEK:([a].[actor_id]=(1)))
     |    |--RID Lookup
     |--Index Seek (SEEK:([fa].[actor_id]=(1)))

Riepilogo

Tutti i nostri database supportano la chiusura transitiva. Tuttavia, attendi il punto 6 nella parte successiva dell'articolo. Esistono casi complessi di chiusura transitiva che non tutti i database possono gestire.

2. Predicati impossibili e chiamate di tabella non necessarie

Questa è un'ottimizzazione completamente stupida, ma perché no? Se gli utenti scrivono predicati impossibili, allora perché preoccuparsi di eseguirli? Ecco alcuni esempi:

-- "Очевидный"
SELECT * FROM actor WHERE 1 = 0
-- "Хитрый"
SELECT * FROM actor WHERE NULL = NULL

La prima query ovviamente non restituirà mai alcun risultato, ma la stessa affermazione vale per la seconda. Dopotutto, sebbene NULL IS NULL sia sempre TRUE, il risultato del calcolo NULL = NULL è NULL, che, secondo la logica a tre valori , equivale a FALSE. Questo è abbastanza auto-esplicativo, quindi passiamo direttamente a scoprire quali database eseguono questa ottimizzazione.

DB2

SÌ!

Explain Plan
-----------------------------------
ID | Operation      |   Rows | Cost
 1 | RETURN         |        |    0
 2 |  TBSCAN GENROW | 0 of 0 |    0

Come puoi vedere, l'accesso al tavolo ACTOR è completamente escluso dal piano. Contiene solo l'operazione GENROW, che genera zero righe. Perfetto.

MySQL

SÌ!

ID  SELECT TYPE  TABLE   EXTRAS
-----------------------------------------
1   SIMPLE         Impossible WHERE

Questa volta MySQL è stato così gentile da informarci dell'impossibile clausola WHERE. Grazie! Ciò rende l'analisi molto più semplice, soprattutto rispetto ad altri database.

Oracolo

SÌ!

---------------------------------------------------------------
| Id  | Operation          | Name  | Starts | E-Rows | A-Rows |
---------------------------------------------------------------
|   0 | SELECT STATEMENT   |       |      1 |        |      0 |
|*  1 |  FILTER            |       |      1 |        |      0 |
|   2 |   TABLE ACCESS FULL| ACTOR |      0 |    200 |      0 |
---------------------------------------------------------------
Predicate Information (identified by operation id):
---------------------------------------------------
   1 - filter(NULL IS NOT NULL)

Vediamo che il piano menziona ancora l'accesso alla tabella ACTOR e il numero di righe previsto è ancora 200, ma c'è anche un'operazione di filtraggio (FILTER) con Id=1, dove non ci sarà mai TRUE. A causa dell'avversione di Oracle per il tipo di dati SQL Boolean standard , Oracle visualizza NULL IS NOT NULL nel piano, anziché solo FALSE. Vabbè... Ma sul serio, attenzione a quel predicato. Ho avuto occasione di eseguire il debug di piani di esecuzione con sottoalberi da 1000 righe e valori di costo estremamente elevati, solo per scoprire dopo il fatto che l'intero sottoalbero veniva "tagliato" dal filtro NULL IS NOT NULL. Un po' scoraggiante, te lo dico.

PostgreSQL

SÌ!

QUERY PLAN
-------------------------------------------
Result  (cost=0.00..0.00 rows=0 width=228)
  One-Time Filter: false

Già meglio. Nessuna fastidiosa chiamata alla tabella ACTOR e un piccolo predicato FALSE.

Server SQL?

SÌ!

|--Constant Scan

SQL Server la chiama " scansione costante ", ovvero una scansione in cui non accade nulla, simile a DB2. Tutti i nostri database possono escludere predicati impossibili:

3. Elimina i JOIN

Nella sezione precedente abbiamo osservato accessi non necessari alle tabelle nelle query a tabella singola. Ma cosa succede se il JOIN non richiede uno dei numerosi accessi alla tabella? Ho già scritto sull'eliminazione di JOIN in un post precedente dal mio blog . Il motore SQL è in grado di determinare, in base al tipo di query e alla presenza di chiavi primarie ed esterne, se un particolare JOIN è effettivamente necessario in una determinata query, o se eliminarlo non influenzerà la semantica della query. In tutti i tre esempi successivi, JOIN non è necessario. Un inner ...-to-one join può essere eliminato utilizzando una chiave esterna NOT NULL. Invece:

SELECT first_name, last_name
FROM customer c
JOIN address a ON c.address_id = a.address_id

Il database può eseguire le seguenti operazioni:

SELECT first_name, last_name
FROM customer c

Una INNER JOIN di tipo "...-to-one" può essere sostituita se è presente una chiave esterna nullable. La query precedente funziona se la chiave esterna è soggetta a un vincolo NOT NULL. In caso contrario, ad esempio, come in questa richiesta:

SELECT title
FROM film f
JOIN language l ON f.original_language_id = l.language_id

allora JOIN può ancora essere eliminato, ma dovrai aggiungere il predicato NOT NULL, in questo modo:

SELECT title
FROM film
WHERE original_language_id IS NOT NULL

Un OUTER JOIN del tipo "...-to-one" può essere rimosso se è presente una chiave univoca. Invece di questo:

SELECT first_name, last_name
FROM customer c
LEFT JOIN address a ON c.address_id = a.address_id

Il database, ancora una volta, può fare quanto segue:

SELECT first_name, last_name
FROM customer c

... anche se non esiste una chiave esterna per CUSTOMER.ADDRESS_ID. La connessione esterna univoca (DISTINCT OUTER JOIN) del tipo "...-to-many" può essere rimossa. Invece di questo:

SELECT DISTINCT first_name, last_name
FROM actor a
LEFT JOIN film_actor fa ON a.actor_id = fa.actor_id

Il database può eseguire le seguenti operazioni:

SELECT DISTINCT first_name, last_name
FROM actor a

Tutti questi esempi sono stati studiati in dettaglio nell'articolo precedente, quindi non mi ripeterò, ma mi limiterò a riassumere tutto ciò che i vari database possono eliminare: Sfortunatamente, non tutti i database possono risolvere tutti i tipi di connessioni. DB2 e SQL Server sono i leader indiscussi qui! Continua