Des optimisations SQL sympas qui ne dépendent pas du modèle de coût. Partie 1

Cinq optimisations simples qui peuvent être mises en œuvre uniquement sur la base des métadonnées (c'est-à-dire des contraintes) et de la requête elle-même. Nous vous proposons une adaptation de l'article de Lukas Eder, conçue pour ceux qui ont une compréhension générale des bases de données et de SQL, ainsi qu'une certaine expérience pratique du SGBD. . L'optimisation des coûts est en fait un moyen standard d'optimiser les requêtes SQL dans les bases de données modernes. C'est pourquoi il est si difficile d'écrire manuellement un algorithme complexe en 3GL (langages de programmation de troisième génération) dont les performances dépasseraient le plan d'exécution calculé dynamiquement généré par un optimiseur moderne. Aujourd'hui, nous ne discuterons pas de l'optimisation des coûts, c'est-à-dire de l'optimisation basée sur le modèle de coût de la base de données. Nous examinerons des optimisations beaucoup plus simples. Ceux qui peuvent être mis en œuvre uniquement sur la base des métadonnées (c'est-à-dire des restrictions) et de la demande elle-même. Habituellement, leur mise en œuvre pour une base de données n'est pas un binôme de Newton, puisque, dans ce cas, toute optimisation conduira à un meilleur plan d'exécution, indépendamment de la présence d'index, des volumes de données et de l'asymétrie de la distribution des données. "Pas un binôme de Newton" ne signifie pas à quel point il est facile de mettre en œuvre l'optimisation, mais plutôt si cela doit être fait. Ces optimisations éliminent le travail supplémentaire inutile [pour la base de données] ( par opposition au travail inutile et requis, dont j'ai déjà parlé ).

A quoi servent ces optimisations ?

La plupart d’entre eux sont utilisés pour :

• corrections de bugs dans les requêtes ;
• permettant aux vues d'être réutilisées sans que la base de données exécute réellement la logique de vue.

Dans le premier cas, on pourrait dire : « Et alors, allez-y et corrigez cette stupide requête SQL. » Mais que celui qui n'a jamais commis d'erreur me jette d'abord la pierre. Le deuxième cas est particulièrement intéressant : il nous donne la possibilité de créer des bibliothèques complexes de vues et de fonctions de table pouvant être réutilisées sur plusieurs couches.

Bases de données utilisées

Dans cet article, nous comparerons 10 optimisations SQL dans les cinq SGBD les plus utilisés ( selon le classement des bases de données ) :

• Oracle 12.2 ;
• MySQL 8.0.2 ;
• SQL Serveur 2014 ;
• PostgreSQL 9.6 ;
• DB2 LUW 10.5.

Une autre note en fait presque écho. Comme d'habitude, dans cet article, j'interrogerai la base de données Sakila . Voici une liste de ces dix types d’optimisations :

1. fermeture transitive;
2. prédicats impossibles et appels de table inutiles ;
3. éliminer JOIN ;
4. élimination des prédicats « dénués de sens » ;
5. projections dans les sous-requêtes EXISTS ;
6. fusion de prédicats ;
7. ensembles manifestement vides ;
8. contraintes CHECK;
9. connexions réflexives inutiles ;
10. Prédicats de refoulement

Aujourd'hui, nous discuterons des pp. 1-3, dans la deuxième partie - 4 et 5, et dans la partie 3 - 6-10.

1. Clôture transitive

Commençons par quelque chose de plus simple : la fermeture transitive . Il s'agit d'un concept trivial qui s'applique à de nombreuses opérations mathématiques, comme l'opérateur d'égalité. Elle peut être formulée dans ce cas comme suit : si A = B et B = C, alors A = C.

Pas difficile, non ? Mais cela a des implications intéressantes pour les optimiseurs SQL. Regardons un exemple. Extrayons tous les films avec 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;

Le résultat est le suivant :

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

Voyons maintenant le plan d'exécution de cette requête dans le cas du SGBD 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)

La section sur les prédicats est ici particulièrement intéressante. Le prédicat ACTOR_ID = 1, en raison de la fermeture transitive, s'applique à la fois à la table ACTOR et à la table FILM_ACTOR. Si:

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

Pour les requêtes plus complexes, cela produit de très bons résultats. En particulier, la précision des estimations de cardinalité augmente considérablement, puisqu'il devient possible de sélectionner des estimations basées sur une valeur constante spécifique du prédicat, et non, par exemple, sur le nombre moyen de films par acteurs, comme dans la requête suivante (renvoyant le même résultat) :

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'

Son projet :

----------------------------------------------------------------------------
| 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")

Comme vous pouvez le constater, le nombre de lignes de la table FILM_ACTOR est surestimé, tandis que la BOUCLE NESTED est sous-estimée. Voici quelques valeurs intéressantes :

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

Résultat:

19
27.315

C'est de là que viennent les estimations. Si la base de données sait que nous parlons de ACTOR_ID = 1, elle peut alors collecter des statistiques sur le nombre de films pour cet acteur particulier . Si ce n'est pas le cas (puisque le mécanisme standard de collecte de statistiques ne corrèle pas FIRST_NAME/LAST_NAME avec ACTOR_ID), nous obtiendrons le nombre moyen de films pour tous les acteurs . Une erreur simple et sans importance dans ce cas particulier, mais dans une requête complexe elle peut se propager plus loin, s'accumuler et conduire plus loin dans la requête (plus haut dans le plan) à un choix JOIN incorrect. Ainsi, chaque fois que vous le pouvez, concevez vos jointures et vos prédicats simples pour tirer parti de la fermeture transitive. Quelles autres bases de données prennent en charge cette fonctionnalité ?

DB2

Oui!

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)

À propos, si vous aimez les plans d'exécution sympas comme celui-ci, consultez le script de Markus Winand .

MySQL

Malheureusement, les plans d'exécution MySQL ne sont pas bien adaptés à ce type d'analyse. Le prédicat lui-même est absent des informations de sortie :

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

Mais le fait que const soit spécifié deux fois dans la colonne REF montre que les deux tables recherchent une valeur constante. Dans le même temps, le plan de requête avec FIRST_NAME/LAST_NAME ressemble à ceci :

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

Et comme vous pouvez le voir, le REF fait désormais référence à la colonne du prédicat JOIN. Le score de cardinalité est presque le même que dans Oracle. Alors oui, MySQL prend également en charge les fermetures transitives.

PostgreSQL

Oui!

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)

serveur SQL

Oui!

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

Résumé

Toutes nos bases de données prennent en charge la fermeture transitive. Cependant, attendez le numéro 6 dans la prochaine partie de l'article. Il existe des cas complexes de fermeture transitive que toutes les bases de données ne peuvent pas gérer.

2. Prédicats impossibles et appels de table inutiles

C’est une optimisation complètement stupide, mais pourquoi pas ? Si les utilisateurs écrivent des prédicats impossibles, pourquoi s’embêter à les exécuter ? Voici quelques exemples:

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

La première requête ne renverra évidemment jamais aucun résultat, mais la même affirmation est vraie pour la seconde. Après tout, bien que NULL IS NULL soit toujours TRUE, le résultat du calcul NULL = NULL est NULL, ce qui, selon la logique à trois valeurs , équivaut à FALSE. Cela est assez explicite, alors passons directement à la découverte des bases de données qui effectuent cette optimisation.

DB2

Oui!

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

Comme vous pouvez le constater, l'accès à la table ACTEUR est totalement exclu du forfait. Il contient uniquement l'opération GENROW, qui génère zéro ligne. Parfait.

MySQL

Oui!

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

Cette fois, MySQL a eu la gentillesse de nous informer de l'impossible clause WHERE. Merci! Cela rend l’analyse beaucoup plus facile, surtout par rapport à d’autres bases de données.

Oracle

Oui!

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

On voit que le plan mentionne toujours l'accès à la table ACTOR, et le nombre de lignes attendu est toujours de 200, mais il y a aussi une opération de filtrage (FILTER) avec Id=1, où il n'y aura jamais de TRUE. En raison de l'aversion d'Oracle pour le type de données booléen SQL standard , Oracle affiche NULL IS NOT NULL dans le plan, au lieu de simplement FALSE. Eh bien... Mais sérieusement, surveillez ce prédicat. J'ai eu l'occasion de déboguer des plans d'exécution avec des sous-arbres de 1 000 lignes et des valeurs de coût extrêmement élevées, pour découvrir après coup que le sous-arbre entier était "coupé" par le filtre NULL IS NOT NULL. Un peu décourageant, je vous dis.

PostgreSQL

Oui!

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

Déjà mieux. Pas d'appels de table ACTOR ennuyeux et un petit prédicat FALSE soigné.

Serveur SQL?

Oui!

|--Constant Scan

SQL Server appelle cela une « analyse constante », qui est une analyse où rien ne se passe – similaire à DB2. Toutes nos bases de données peuvent exclure des prédicats impossibles :

3. Éliminez les JOIN

Dans la section précédente, nous avons observé des accès inutiles aux tables dans les requêtes à table unique. Mais que se passe-t-il si le JOIN ne nécessite pas l'un des nombreux accès à la table ? J'ai déjà parlé de l'élimination de JOIN dans un article précédent de mon blog . Le moteur SQL est capable de déterminer, en fonction du type de requête et de la présence de clés primaires et étrangères, si un JOIN particulier est réellement nécessaire dans une requête donnée, ou si son élimination n'affectera pas la sémantique de la requête. Dans les trois exemples suivants, JOIN n'est pas nécessaire. Une jointure interne ...-to-one peut être éliminée en ayant une clé étrangère NOT NULL.

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

La base de données peut effectuer les opérations suivantes :

SELECT first_name, last_name
FROM customer c

Un INNER JOIN de type "...-to-one" peut être remplacé s'il existe une clé étrangère nullable. La requête ci-dessus fonctionne si la clé étrangère est soumise à une contrainte NOT NULL. Sinon, par exemple, comme dans cette demande :

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

alors JOIN peut toujours être éliminé, mais vous devrez ajouter le prédicat NOT NULL, comme ceci :

SELECT title
FROM film
WHERE original_language_id IS NOT NULL

Un OUTER JOIN de type "...-to-one" peut être supprimé s'il existe une clé unique. Au lieu de cela:

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

La base de données, encore une fois, peut effectuer les opérations suivantes :

SELECT first_name, last_name
FROM customer c

... même s'il n'y a pas de clé étrangère pour CUSTOMER.ADDRESS_ID. La connexion externe unique (DISTINCT OUTER JOIN) du type "...-to-many" peut être supprimée. Au lieu de cela:

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

La base de données peut effectuer les opérations suivantes :

SELECT DISTINCT first_name, last_name
FROM actor a

Tous ces exemples ont été étudiés en détail dans l'article précédent, je ne vais donc pas me répéter, mais résumerai simplement tout ce que diverses bases de données peuvent éliminer : Malheureusement, toutes les bases de données ne peuvent pas résoudre tous les types de connexions. DB2 et SQL Server sont ici les leaders incontestés ! À suivre