Cet article est la traduction d’un article de Jonathan Lewis. L’article original en anglais se trouve ici.
J’ai cependant traduit l’exemple de requête dans une syntaxe Oracle, et l’idée d’index cluster de SQL Server correspond à celle d’IOT sous Oracle.

Jonathan Lewis décrit ici une démarche visuelle pour comprendre une requête SQL en faisant un schéma des tables impliquées.

C’est parfois intéressant de s’éloigner du clavier lorsqu’on se bat avec une requête peu performante et assez complexe, et de prendre un papier et un crayon à la place. En faisant un schéma qui montre les tables impliquées, les jointures, les volumes de données manipulées, et les indexes, vous pourrez comparer plus facilement l’efficacité des différents chemins d’exécution que la requête peut prendre pour passer d’une table à une autre.

Les gens pensent souvent que, parce que le SQL est un langage déclaratif, il ne faut pas coder la manière de récupérer les données, mais seulement de décrire le résultat que l’on cherche. C’est vrai: décrivez ce que vous attendez et vous aurez ce que vous demandez. Mais rien ne garantit que vous l’aurez avec la rapidité et le coût que vous souhaitiez. C’est une peu comme prendre un taxi dans une ville étrangère. Vous pouvez dire au chauffeur où est-ce que vous souhaitez aller et espérer qu’il prendra la meilleure route pour vous y amener, mais parfois le trajet est plus long et coûte plus cher que ce à quoi vous vous attendiez. A moins que vous ne donniez au conducteur quelques indications sur la route que vous souhaitez qu’il prenne.

Aussi bon que soit l’optimiseur, il est limité par certains cas pour lesquels ses algorithmes ne sont pas bien adaptés à vos besoins. Peut-être parce que les statistiques disponibles sont trompeuses, ou parce que l’optimiseur a fait des hypothèses sur vos données, et que celles-ci ne sont pas correctes. Lorsque c’est le cas, vous devez trouver un moyen de guider un peu l’optimiseur.

Cet article décrit une approche visuelle pour construire les requêtes SQL, surtout pour les requêtes complexes, et devrait vous permettre de trouver un plan d’execution approprié. En plus d’être une bonne méthode pour l’écriture d’une nouvelle requête, cette approche est particulièrement utile pour ‘débugger’ et écrire différemment des requêtes sur lesquelles l’optimiseur a un problème et a besoin d’être aidé. Ces idées sont simples, et indépendantes du SGBD, le code pour passer du plan d’exécution au SQL, lui, est vraisemblablement dépendant du SGBD.

Connaissez vos données

Avant de pouvoir optimiser une requête, vous devez d’abord connaître:

1. Quel est le volume de données que vous devez manipuler (data volume
2. Où se trouvent les données: comment sont-elles distribuées (éparpillées ou regroupées – data scatter)

Lorsqu’il s’agit d’évaluer la charge de travail nécessaire pour retourner le résultat que l’on attend, et le temps que ça mettra, le volume et la distribution des données ont la même importance. Si vous avez besoin d’un gros volume de données, et qu’il est éparpillé sur une grande partie de la base de données, alors votre requête a peu de chance d’être rapide. Par contre, vous pouvez quand même récupérer un gros volume si vous pavez profité, par exemple, d’une table IOT (table organisée en index), qui fait en sorte que tout est regroupé dans un espace relativement petit.

Donc, les deux premières questions auxquelles vous devez répondre sont: « Quel est le volume de données ? » et « Où sont ces données ? »

A partir de là, la question suivante est: « Comment récupérer ces données ? Disons que vous voulez récupérer 50 enregistrements d’une table, répondant à une certaine condition de sélection. Celà semble très simple, mais quel est le moyen le plus efficace pour ne récupérer que ces 50 enregistrements ? Vous pouvez avoir le choix entre:

1. un index ‘très précis’
2. un index raisonnablement précis qui ramènera 100 enregistrements parmi lesquels vous devrez en éliminer 50.
3. un index ‘plutôt inutile’ qui ramènera 500 enregistrements parmi lesquels vous devez en éliminer 450.

Voici l’idée importante: si vous devez choisir entre le deuxième et le troisième index, peut-on dire, d’après ce que j’ai écrit jusqu’ici, lequel sera le plus efficace ? Non, on ne peut pas. Récupérer seulement 100 lignes pour en éliminer 50 semble à première vue plus efficace que d’en récupérer 500 pour en éliminer 450. Mais il faut se souvenir que le ‘clustering‘, la manière sont les données sont physiquement rassemblées ou dispersées, est un facteur primordial.

Supposons qu’on aie un index qui va identifier 10 lignes de chaque bloc, avec 10 blocs en tout, et que les 50 lignes dont vous avez besoin sont regroupées sur seulement 5 blocs parmi les 10. On est dans le cas 2: il faut éliminer 50 lignes parmi 100.

Et maintenant, un autre index qui va identifier 100 lignes de chaque bloc, avec 5 blocs en tout. On est là dans le cas 3: il faut éliminer 450 lignes parmi 500.

Alors vaut-il mieux lire 10 blocs et éliminer 50 lignes, ou visiter juste 5 blocs et éliminer 450 lignes ? Le meilleur choix sera probablement de lire le minimum de blocs.

Souvenez-vous que vous avez la meilleure compréhension de votre application et de vos données, meilleure que celle de l’optimiseur. Il peut arriver que l’optimiseur choisisse un mauvais plan d’exécution parce qu’il ne connaît pas les données aussi bien que vous, et ne sait pas comment l’application manipule les données.

Si un bon vieux dessin vaut mieux qu’un long discours…

… pourquoi ne pas dessiner votre requête ? Lorsque vous avez une requête SQL complexe, avec de nombreuses tables, alors vous avez vraiment besoin de collecter et présenter de nombreuses informations, et d’une manière facile à appréhender. C’est alors une bonne idée d’en faire un schéma, encore plus si vous essayez de reprendre du code SQL qui a été écrit par quelqu’un d’autre.

Ma approche est simple:

1. Parcourez la requête SQL et dessinez une boite pour chaque table, et une ligne entre ces boites pour chaque condition de jointure.
2. Si vous connaissez la cardinalité de la jointure (one-to-one, one-to-many, many-to-many), alors notez là (ici nous utilisons une une ‘patte de corbeau’ du côté ‘many‘ de la ligne).
3. Si vous voyez un prédicat de filtre sur la table, dessinez une flèche vers la boite, et écrivez le prédicat au-dessus
4. Si la ‘table’ est en réalité une sous-requête qui comprends plusieurs tables, tracez un rectangle en pointillé autour de ce groupe de tables

Prenons un exemple.

Imaginons que vous avez un schéma de base de données qui implémente un simple système de gestion de commandes: les clients (customers) font des commandes (orders), lesquelles peuvent avoir plusieurs lignes (order_lines), une ligne étant associée à un produit (product), et les produits viennent des fournisseurs (suppliers). De plus, certains produits peuvent être remplacés par d’autres produits (alternatives).

On vous demande un jour de faire un rapport sur:  » les commandes passées durant la dernière semaine par des clients qui sont situés à Londres, ces commandes concernant des produits venant de fournisseurs situés à Leeds, et seulement les produits qui auraient pu être fournis par des fournisseurs d’un autre endroit « 

Si l’on suppose qu’on ne veut comme détail pour chaque commande que les lignes correspondant aux produits spécifiés, cela pourrait donner la requête suivante:

Il est possible que la description textuelle ne soit pas directement compréhensible à partir du code SQL, mais avec une approche visuelle on arrive au diagramme suivant. Ne soyez pas surpris si vous devez vous y reprendre à deux ou trois reprises pour avoir un diagramme clair et net, notamment si vous faite du reverse engineering d’une requête qui a été écrite par quelqu’un d’autre. Mes premiers brouillons se retrouvent souvent avec toutes les tables entassées dans un coin de la page.

A partir de ce diagramme, on va rajouter quelques chiffres dont nous aurons besoin. Le niveau de détail dépendra de la connaissance qu’on a sur ces tables, et sur l’application de base. Ici, nous allons le faire sur la table orders pour montrer le principe et le type d’information dont nous avons besoin. Certains chiffres viennent des statistiques du dictionnaire, et d’autres viennent de requêtes que nous avons fait sur les données. Idéalement, nous en connaissons la majorité parce que nous sommes familiers avec l’application et la nature des données:

• Nombre d’enregistrements: 250000
• Nombre de Blocs: 8000
• Cardinalité initiale: 2400
• Cardinalité finale: 20
• Indexes ‘entrants‘ vers la table orders:
  (date_placed) très bon clustering factor avec environ 400 lignes par jour
  (id_customer) très mauvais clustering factor avec 10 à 150 lignes par client
• Indexes ‘sortants‘ de la table orders:
  order_lines (id_order, line_no) très bon clustering factor avec 1 à 15 lignes par commande
  customers (id) clé primaire

Normalement j’indique les indexes pertinents sur le diagramme avec des flèches entre les boites, et leur statistiques à côté. J’écris aussi dans les boites les statistiques des tables, parce que des longues listes de texte en dessous du diagramme ne sont pas très faciles à utiliser. Mais il faut souvent une grande feuille pour faire un schéma correct, et ici la place sur cette page web est limitée.

La ‘cardinalité initiale’ et la ‘cardinalité finale’ méritent quelques explications.

La ‘cardinalité initiale‘ est le nombre de lignes que je m’attends à avoir si la table est la première lue dans la requête. En d’autres mots, c’est le nombre de lignes qui vérifient les prédicats constants que j’ai sur cette table. Ici, la requête concerne ‘les commandes passées durant la dernière semaine’, et je sais par exemple, que nous avons en moyenne 2400 commandes par semaines. Si je n’ai pas cette information, je peux lancer une requête simple: select count(*) from orders group by week qui me donnera cette estimation.

La ‘cardinalité finale‘ est le nombre de lignes de cette table qui va se retrouver dans le résultat final. Elle peut être beaucoup plus difficile à estimer sans l’aide de quelqu’un qui connait bien le fonctionnel.
Dans notre cas, nos estimations montrent une grande différence entre les cardinalités finales et initiales. Cela signifie que, à une certaine étape, il y a peut-être beaucoup de travail à faire pour éliminer les lignes qui ne sont pas nécessaires, et ce filtrage est peut-être justement le travail que je cherche à réduire.

Après avoir collecté toutes les informations sur ce qu’il y a dans les tables, ce que l’on veut de ces tables, comment l’atteindre, et quel coût cela représente, nous n’avons plus qu’à prendre une table de départ dans le diagramme et poursuivre en répétant ces questions: Quelle table vais-je aller voir après? Et Comment y aller ?

Pour répondre à ces questions, chaque fois, il faudra considérer les questions sous-jacentes, dans l’ordre de priorité suivant:

1. Est-ce que je peux agréger le résultat en cours pour réduire le volume (de manière significative) avant d’aller à la table suivante ?
2. Est-ce qu’il y a une table où je peux aller et qui va éliminer des données (à un faible coût)
3. Est-ce qu’il y a une table qui va augmenter (faiblement) la taille des enregistrements sans augmenter le nombre de lignes
4. Quelle table augment le moins le nombre de ligne (et pour un coût faible)

Si vous vous appuyez sur ces questions pour diriger votre choix de la prochaine table à visiter, le volume intermédiaire et la charge resteront les plus faibles. Inévitablement, il y a des compromis à faire entre, par exemple, augmenter fortement la taille d’une ligne (option 3) et augmenter faiblement le nombre de lignes (option 4). Et pourtant, si vous prenez ces règles comme une indication plutôt qu’une règle rigide, et que vous réfléchissez quelques pas à l’avance, pour ne devriez pas vous tromper beaucoup.

Dans un datawarehouse (ou ‘DSS’ – support d’aide à la décision) vous verrez que vous pouvez prendre presque n’importe quelle table comme table de départ, et suivre plusieurs chemins avant de trouver le meilleur. Mais le principe général serait de prendre la table qui retourne un petit volume de données à un coût relativement faible.

En transactionnel (OLTP), il y aura vraisemblablement une ou deux table par où commencer qui sembleront évidentes, à condition que vous ayez une bonne connaissance du fonctionnel. Dans cet exemple, les points de départ évidents sont la table orders et la table customers. Après tout, le rapport concerne  » des commandes passées par quelques clients sur une courte durée « , donc on sent bien que c’est en partant des commandes et des clients que l’on aura le plus petit ensemble de données.
Toutefois, pour le besoin de la démonstration, nous allons voir comment cela se passe si l’on démarre par la table des fournisseurs suppliers.

A partir de la table suppliers (qui retourne seulement quelques lignes pour ‘LEEDS’), le seul choix pertinent est d’aller vers products par l’index sur la clef étrangère (on peut supposer qu’il a été créé). Bien sûr, techniquement parlant, on pourrait aller vers n’importe quelle table, si on ne cherchait pas à éviter le produit cartésien.

A partir de products, on peut aller vers order_lines ou vers la table alternatives. La table order_lines nous ferait augmenter massivement le nombre de lignes, et nous devrions aller chercher des enregistrements qui sont éparpillé sur toute la table, qui est très grosse, et nous devrions soit utiliser un index coûteux avec une jointure ‘nested loop‘, ou bien faire un full scan de la table avec une jointure ‘hash join‘.

Par contre, si nous allons vers la table alternatives, dans l’idée d’aller voir les tables products et suppliers de la sous requête, avant de revenir vers order_lines, alors nous verrons qu’il y a beaucoup de produits qui n’ont pas de fournisseur alternatif, et donc que le nombre de lignes va diminuer, ce qui en fait un meilleur choix. Et ce nombre va diminuer encore plus lorsque nous irons voir les fournisseurs qui ne sont pas à ‘LEEDS’.

Cependant, en fin de compte, nous devrons aller voir ce qu’il reste dans la table products et faire la jointure avec order_lines, et ma culture générale à propos de ce qu’on peut trouver dans une table de lignes de commandes me dit qu’on va ramener un large volume de données, souvent de manière pas très efficace. Un produit spécifique a des chances de se trouver dans de nombreuses lignes de commandes, éparpillées sur une bonne partie de la table order_lines. Ce n’est donc pas une bonne perspective.

Alors, les seules options possibles pour la table de départ sont orders ou customers, et après avoir traversé les deux, le chemin sera: order_lines, products, suppliers, (alternatives, products, suppliers).

Alors doit-on partir sur customers puis orders ou l’inverse ? C’est ici que l’indexation et le clustering vont être des paramètres très importants.

Dans l’état, et compte tenu de la liste des indexes de la table orders, si nous sélectionnons les clients de Londres, alors nous devrons utiliser l’index sur id_customer de la table orders pour récupérer toutes les commandes de ces clients, et ensuite éliminer toutes les commandes qui ne sont pas dans notre fenêtre d’une semaine. Si l’on retourne aux statistiques, nous avons 250 000 commandes et à peu près 2400 par semaine, ce qui veut dire que nos données couvrent un historique de deux ans (104 semaines). Donc si l’on prends un client et qu’on récupère toutes ses commandes, nous devrons éliminer environ 99% de ce qu’on a récupéré. Vu le volume de données et la manière dont elles sont distribuées sur l’axe du temps, ce serait un gros travail pour récupérer les données, et une bonne partie pour rien.

L’autre choix, alors, c’est de partir de la table orders, récupérer les 2400 commandes de la semaine, et passant par l’index sur date_placed, et faire la jointure sur customers avec son index de la clé primaire, pour éliminer tous ceux qui ne sont pas de Londres. Les commandes ont de grandes chances d’être bien ‘clusterisées’ sur l’axe du temps: celles passées à deux instants proches sont probablement stockées de manière proches aussi. De plus, comme les commandes récentes sont plus sujettes à des traitements fréquents, elles ont de grandes chances de se trouver en cache, et d’y rester. Cela veut dire que même si nous devons récupérer beaucoup de commandes pour commencer, nous pourrons probablement le faire de manière très efficace.

Au pire, nous aurons à lire 2400 lignes de customers et elles ont de grandes chances d’être éparpillées sur toute la table, donc il y a peut-être une menace sur les performances (I/O). Cependant, une table de référence comme la table client bénéficie souvent du cache (plus que les tables transactionnelles comme la table des commandes), et dans ce cas, nous pouvons nous préparer à ignorer cette menace sur les I/O.

Cela nous amène à faire notre deuxième schéma:

L’ordre dans lequel l’accès aux tables doit se faire

Une fois que nous avons décidé du meilleur chemin d’exécution de la requête, nous pouvons faire en sorte que ce soit celui-ci qui soit exécuté, par exemple avec un moyen expéditif: ordonner les tables dans la clause from et ajouter le hint /*+ ORDERED */

D’un autre côté, si la requête est suffisamment importante, et que nous sommes toujours en phase de conception, il y a peut-être des changement de structure à considérer.

Le texte original, dans le contexte de SQL Server, parle du choix des indexes, et notamment des indexes cluster, qui sont propres à SQL Server. Même si Oracle a quelque chose d’équivalent, les IOT (Indexed-Organized Table – table stockée comme un index), j’ai préféré ne pas traduire ce passage. J’espère mettre sur ce blog prochainement des articles plus précis sur les IOT et sur le clustering factor

Conclusion

Pour écrire une requête performante, vous devez connaître le volume de données que vous attendez, et d’où elles viennent. Pour décider du bon ordre de parcours des tables, vous devez aussi savoir quelles sont les options de récupération des données, et quel va être le coût si vous ramenez des données dont vous n’avez pas besoin.

Pour des requêtes complexes, le meilleur moyen est commencer par dessiner un schéma de toutes les tables impliquées, montrant les jointures entre les tables, indiquant le volume de données impliquées, et décrivant les indexes qui permettent d’aller d’une table à l’autre. Un tel diagramme va permettre de comprendre plus facilement l’efficacité des différents plans d’exécution.