Datafly.pro

Un petit rappel sur l'optimiseur

Pour rappel, le traitement d’une requête dans le moteur relationnel passe par différentes phase avant l’exécution :

• l’analyse de syntaxe (le « parser »),
• l’algébrisation (l’ « algebrizer ») qui produit un arbre de requête standardisé : l’arbre de requête décrit les tâches à exécuter par la requête. Chaque nœud représente une opération, de jointure, de regroupement… Deux requêtes qui font la même chose tout en étant écrites différemment auront un arbre algébrisé identique !
• l’optimisation (l’ « optimizer ») qui va élaborer le plan d’exécution

C’est ce dernier composant (l’optimiseur) qui va décider des méthodes d’accès aux données (parcours de table ou recherche avec un des index ?) et du choix des différents algorithmes utilisés pour l’exécution, comme par exemple les jointures (loop, merge, hash join ?). 
Ces choix sont très sensibles : on comprend aisément qu’un mauvais choix (une mauvaise optimisation) peut vite devenir catastrophique dès que le volume de données à traiter est conséquent !

Pour effectuer son travail, l’optimiseur s’appuie sur :

• l’arbre de requête « algébrisé » qui lui décrit les opérations à effectuer,
• les statistiques de distribution qui existent sur chaque index et sont générées aussi en fonction des besoins (par défaut) sur des colonnes non indexées,
• les contraintes CHECK et FOREIGN KEY,
• des heuristiques

Je n’irai pas vous décrire en détail le fonctionnement interne de l’optimiseur. Tout d’abord, c’est un secret bien gardé. Ensuite, il faut quelques solides connaissances mathématiques poussées qui me font défaut : j’ai souvenir d’une présentation chez Microsoft à Redmond par une des conceptrices de l’optimiseur, toute timide mais tête bien pleine, qui nous a rapidement laissés pour compte à coups de formules mathématiques.

Plan d'exécution estimé et estimation des cardinalités

Nous allons juste examiner certains comportements simples et en particulier l’estimation des cardinalités, et voir comment une mauvaise estimation au départ peut s’amplifier au fil des jointures… !
Commençons par une requête simple qui joint les produits aux fournisseurs et filtre sur un nom de fournisseur :

Voici le plan d'exécution réel (celui qui a été exécuté). L'affichage provient de SQLSentry Plan Explorer, un outil gratuit qu'il faut absolument que vous ayez !

Les 78 lignes de la table produit ont été parcourues et une recherche d'index dans la table fournisseur a été effectué, en filtrant sur le nom du fournisseur. 5 produits correspondent.

Voyons maintenant le plan d'exécution estimé (ce que SQL Server a estimé avant d'exécuter la requête) :

Nous constatons que SQL Server avait estimé le nombre de lignes correspondantes à 10 plutôt que 5. Une petite erreur du simple au double, qui en l’occurrence n’a aucun impact sur l’exécution d’une si petite requête.

Comment calcule l'optimiseur ?

Voyons maintenant de quoi a disposé l’optimiseur pour établir son plan de requête et la cause de cette erreur d'estimation.

Table produits

La table produits possède 78 lignes avec 30 fournisseurs différents. Cela donne donc en moyenne 2.6 produits par fournisseur. L’optimiseur est tenu au courant de ce fait grâce aux statistiques de la table produits sur la colonne IDFournisseur. C'est cette approximation, basée sur la densité de la colonne, qui sera utilisée.

La densité affichée pour cette colonne est de 0.03333334, faisons le calcul :
Nombre moyen lignes pour une valeur de IDfournisseur = nombres total de lignes de la table x densité de la colonne
soit : 78 * 0.03333334 = 2.6   (et donc 78/2.6 = 30 fournisseurs distincts)

Rappelons que la densité est une valeur moyenne : un calcul basé sur cette valeur sera donc approximatif et pourra s'écarter sensiblement de la vérité en fonction de la valeur recherchée et de la distribution des données...

Table fournisseurs

Passons à la table suivante. La table fournisseurs comprend 30 lignes. 4 lignes répondent à la condition « ContactNom = 'Carlos Diaz' ». SQL Server connait précisément ce nombre grâce aux statistiques : cette information est précise et suffisante, et il n’aura même pas besoin d’utiliser les informations de densité.

Et pour la jointure ?

Pour estimer le nombre de correspondances de la jointure, SQL Server va utiliser la formule suivante :
((Nb total lignes produits * densité produits) * Nb lignes estimées fournisseurs) – (densité produits * Nb lignes estimées fournisseurs)
Soit : ((78 * 0.03333334)*4)-(0.03333334*4) = 10.2666687 lignes estimées, CQFD !

Poussons un peu plus loin : quel est l'impact de l'erreur d'estimation ?

Ajoutons une jointure avec les lignes de commande :

Ici aussi nous allons retrouver notre erreur d'estimation, et en plus la jointure supplémentaire va en hériter.

Plan d'exécution réel :

Plan estimé :

SQL Server estime 27036 lignes retournées par la requête au lieu de 16917 : comment se fait ce calcul ?

La table LigneCommandes comprend 205406 lignes et la densité de la colonne de jointure IDProduit est de 0.01282051 comme nous l'indiquent les statistiques.

SQL Server va utiliser la formule suivante :

(Nb de lignes estimées Produits-Fournisseurs * (Nb total de lignes LignesCommandes * densité LignesCommandes))

Soit : (10.2666687 * (205406 * 0.01282051)) = 27036.3448 lignes estimées, CQFD !

Et si la jointure précédente avait été correctement estimée à 5 lignes ? Le résultat serait de (5 * (205406 * 0.01282051)) = 13167 lignes, ce qui n'est pas tout à fait exact non plus, mais nettement plus proche du résultat réel ! Dans notre cas cela ne prête pas à conséquences car le plan d'exécution reste le même et le volume est peu important, mais on peut très bien imaginer des cas ou cet écart d'estimation provoque le choix d'un plan d'exécution inefficace...

Moralité

Une mauvaise estimation se propage dans le plan d'exécution, de la droite vers la gauche. Au fil des jointures successives, cela peut devenir catastrophique. Il faut traiter la cause d'origine et non les effets !
Dans le pire des cas, pour des requêtes très complexes enchaînant les jointures avec des jeux de données volumineux et lorsqu'il est impossible d'améliorer les estimations, la solution ultime sera d'utiliser des résultats intermédiaires dans des tables temporaires !
Et n'oubliez pas que les statistiques doivent êtres à jour, mais ça c'est un autre débat...