Un plan d'exécution de requête est un arbre
dont les noeuds sont des opérateurs de l'algèbre relationnelle
annotés avec un algorithme particulier.
Pour une requête donnée, quels plans doit-on considérer
?
Comment peut on estimer le coût total d'un plan
Idéalement, on veut trouver le meilleur plan. En pratique, on
choisira le moins pire!
Exemple
SELECT S.sname
FROM Reserves R, Sailors S
WHERE R.sid = S.sid AND bid = 100 AND rating > 5
Cout: 500+500*1000 E/S (pourquoi ?)
Plusieurs occasions manquées : pas d'utilisation d'index, on
aurait pu pousser la selection sous la jointure, …
Notre but est de trouver des plans d'exécution plus efficaces
qui calculent le même résultat
Plan alternatif 1 (sans index)
On pousse la sélection sous la jointure (car
selection AND). On suppose qu'on a 100
bateaux, 10 notes et distributions uniformes.
Scan Reserves (1000 E/S) et écriture de 10 pages dans T1
Scan Sailors (500 E/S) et écriture de 250 pages dans T2
Tri T1 (3*10 E/S), Tri T2 (8*250 E/S), fusion (10+250 E/S)
Total: 4050 E/S
Si on pousse la projection, T1 ne contient que sid, T2
uniquement sid et sname (cout < 2000 E/S)
Plan alternatif 2 (avec index)
On suppose un hash-index groupant sur bid
Accès au premier enregistrement bid=100 1.2 E/S
Accès aux suivants: 9 E/S
sid est une clé pour Sailors. On a un hash-index dessus
(forcément non-groupant)
Pour chacun des 10 * 100 enr. tels que bid=100 on
cherche l'enregistrement de Sailors avec le même sid (1.2
E/S/enr)
Coût total: 1000 * 1.2 + 10.2 = 1210 E/S
Algorithme général de choix de plan
Cas mono-relation (une seule table dans le FROM):
On énumère tous les plans (en tenant compte des
équivalences de l'algèbre relationnelle)
On calcule le coût de chaque plan
On choisit le plan de moindre coût
Cas multi-relations (plusieurs tables dans le FROM):
Trop de plan pour les énumérer tous, on choisit des arbres
ayant une certaine forme
On calcule le coût de chaque plan
On choisit le plan de moindre coût
On sait (cours 4) estimer le coût d'un opérateur en fonction de
la taille de l'entrée. On va enchaîner les opérateurs donc il faut
estimer la taille du résultat pour calculer
le coût de l'opérateur suivant!
Estimation de coût
Statistiques et catalogues
On a besoin d'informations numériques sur les relations et les
indexes. Un catalogue contient en général:
Le nombre d'enregistrements (NEnr) et le
nombre de pages (NPages) de la relation.
Le nombre de clés distinctes (NClés) pour les
indexes ainsi que leur taille en pages
La hauteur ainsi que les clés min/max dans l'index, pour les
arbres
Les catalogues sont mis à jours périodiquement mais pas à chaque
mise à jours, pour ne pas impacter les performances.
Estimation du nombre de résultats et facteur de réduction
On considère une requête de la forme:
SELECT attributs FROM tables WHERE e1 AND … AND en
La taille maximale TMax du résultat est le produit des tailles des
tables se trouvant dans le FROM
Le facteur de réduction de chaque expression e
caractérise l'impact de ce terme sur la taille du résultat
La taille finale du résultat est approximée par: TMax *
RF1 * … * RFn
On fait la supposition que les expressions sont indépendantes.
Exemples de facteurs de réduction:
att = valeur : 1 /
NClés si att este une clé pour un index I
att1 = att2 : 1/Max(NClé(I1),
NClé(I2)) (avec atti une clé
de Ii)
att > valeur : (Max(I)-valeur)/(Max(I) - Min(I))
Équivalences de l'algèbre relationnelle
Permet de réordonner les jointures et de « pousser » les sélections
et les projections sous les jointures
R &join; (S &join; T) ≡ (R &join; S) &join; T [Associativité]
(R &join; S) ≡ (S &join; R) [Commutativité]
Autres équivalences
Une projection commute avec une selection qui utilise uniquement
les attributs de la projection
Une selection entre des attributs de deux arguments d'un
produit cartésien peut être converti en jointure:
σφ (R × S) ≡ R &join;φ S
Une selection sur des attributs de R commute avec la
jointure R&join;S (c'est à dire: σ(R&join;S) ≡ σ(R)&join;S )
Règle similaire pour pousser les projections sous jointure
Énumération de plans
Modèle de calcul
Les SGBD modernes utilisent un modèle de
calcul pull. L'opérateur le plus « haut » (racine)
dans l'arbre de requête « tire » (pull) le résultat de ses
sous-arbres (similaire à l'appel de next sur les iterateurs
de la bibliothèque standard Java). Cela permet
de pipeliner les opérateurs. Certains opérateurs «
bloquent » le pipeline (en particulier les tris et
aggrégats).
Cas mono-relation
Dans le cas mono-relation (i.e. sans jointure), la requête est
composée forcément de selections, projections et aggrégats
(max, count, average, …)
Pour chaque sous-terme, on considère tous les accès possibles
(scan, utilisation de l'index, …) et on prend le moins coûteux
Les opérateurs restants sont calculé à la volée (en
pipelinant les opérations)
Estimation du coût pour les plans mono-relation
Si on a un index I pour une selection sur clé primaire :
Hauteur(I) + 1 pour un arbre B+, 1.2
pour un hash-index
Si on a un index I groupant pour plusieurs
selection σ1, …, σn : (NPages(I) + NPages(R))* RF(σ1) * … * RF(σn)
Si on a un index I non-groupant pour plusieurs
selection σ1, …, σn : (NPages(I) + NEnr(R))* RF(σ1) * … * RF(σn)
Scan séquentiel à R: NPages(R)
Exemple de calcul de coût
SELECT S.sid FROM Sailors S WHERE S.rating = 8; πsid(σrating = 8(S))
Avec un index sur rating:
Groupant: 1/NClés(I) * (NPages(I) +
NPages(R)). Avec des valeurs numériques: 1/10 *
(50+500) = 55 E/S
Non-groupant: 1/NClés(I) * (NPages(I) +
NEnr(R)). Avec des valeurs numériques: 1/10 *
(50+40000) = 4005 E/S
Scan : on récupère toutes les pages et on filtre: 500 E/S
Note: Une fois que l'on a sélectionné un enregistrement,
la projection est « gratuite » (en terme d'E/S) car le résultat n'a
pas à être sauvé dans une table temporaire
Requêtes multi-relations
Les choix vont être guidé par les jointures
Si on considère uniquement n jointures (pas de projections ni
de selections dans le plan de requête). Le nombre de plans possible
est le nombre d'arbre binaires ayant n noeuds internes
(exponentiel en n, exactement: nombre de Catalan
d'indice n). Beaucoup trop pour les énumérer tous.
On se restreint aux arbres gauches en profondeur qui
permettent d'énumérer tous les plans complètement
« pipelinable »
Ce ne sont que des heuristiques pour réduire l'espace de
recherche, on n'est pas sur d'avoir la solution optimale!
Énumération des plans gauches en profondeur 1/2
Toujours exponentiel (mais moins)
Tous les arbres différent maintenant dans l'ordre dans lequel on
fait les jointures, la méthode d'accès pour chaque relation et les
algorithmes de jointure utilisés
On applique l'heuristique suivante:
1ère passe: on trouve la meilleure manière de calculer
chaque relation individuellement
2ème passe: on trouve la meilleure manière de joindre
deux à deux les résultats de la passe 1
nème passe: on trouve la meilleure manière de joindre
deux à deux les résultats de la passe (n-1)
Comment sélectionner les « meilleurs » jointures
? On garde pour chaque ordre de
résultat intermédiaire celle de moindre coût
Énumération des plans gauches en profondeur 2/2
Exemple: si on a la possibilité de faire une jointure itérative de
cout 1000, une jointure par hash de coût 500 et une jointure
sort-merge de coût 1500, on garde les version hash
et sort-merge (car il est possible que le fait d'avoir les
résultats déjà trié rendent le coût moindre à l'étape suivante)
On garde les ORDER BY, GROUP BY, aggrégats, …
pour la fin, en profitant si possible des ordres des résultats faits
par les jointures précédentes
On évite tant que possible de faire des produits cartésiens (en
poussant les selections par exemple)
Requêtes imbriquées
SELECT … FROM … WHERE
… e AND EXISTS (SELECT … WHERE … FROM …)
On optimise d'abord la requête la plus « interne »
On optimise ensuite la requête englobante en utilisant prenant en
compte le coût de la requête interne pour chaque « évaluation » du
WHERE