Calcul du coût d'une requête
Soit deux relations t1(a:char(8),b:integer) et t2(b:integer) de respectivement 100 et 10 lignes.
Soit la requête SELECT * FROM t1 INNER JOIN t2 ON t1.b=t2.b WHERE t2.b=1.
Soit n1 le nombre de tuples tels que b=1 dans t1 ; n1 ∈[0..100]
Soit n2 le nombre de tuples tels que b=1 dans t2 ; n2 ∈[0..10]
Soit n3 le nombre de tuples tels que t1.b=t2.b ; : n3 ∈[0..1000]
Question
Il existe plusieurs façons de traduire cette requête en algèbre relationnel, proposer quelques exemples.
Solution
Exemple :
Restriction (JointureNaturelle t1,t2), t2.b=1)JointureNaturelle (Restriction (t2, b=1), t1)JointureNaturelle (Restriction (t1, b=1), t2)
Question
Calculer le nombre d'instructions de chaque exemple d'expression relationnelle :
en considérant que les restrictions sont effectuées par un parcours intégral dans des listes non triées (comme si c'était effectué avec des boucles de type FOR) ;
en considérant que chaque opération est effectuée séparément.
Effectuer les calculs pour trois valeurs de n1,n2 et n3 (une valeur minimum, une valeur maximum et une valeur intermédiaire). Donner un intervalle [min..max] indépendant de n1, n2 et n3.
Solution
Exemple : Restriction (JointureNaturelle t1,t2), t2.b=1)
JointureNaturelle : 100 x 10 = 1000 instructions ; renvoie n3 tuples
Restriction : n3 instructions
Nombre de tuples renvoyés :
Total : 1000 + n3
Min(n3=0) : 1000 ; Max (n3=1000) : 2000 ; Exemple (n3=500) : 1500
Intervalle : [1000..2000]
Exemple : JointureNaturelle (Restriction (t2, b=1), t1)
Restriction : 10 instructions ; renvoie n2 tuples
JointureNaturelle : n2 x 100
Nombre de tuples renvoyés :
Total : 10 + n2 x 100
Min(n2=0) : 10 ; Max (n2=10) : 1010 ; Exemple (n2=1) : 110 ; Exemple (n2=5) : 510
Intervalle : [10..1010]
Exemple : JointureNaturelle (Restriction (t1, b=1), t2)
Restriction : 100 instructions ; renvoie n1 tuples
JointureNaturelle : n1 x 10
Nombre de tuples renvoyés :
Total : 100 + n1 x 10
Min(n1=0) : 100 ; Max (n1=100) : 1100 ; Exemple (n1=1) : 110 ; Exemple (n1=5) : 150 ; Exemple (n1=50) : 500
Intervalle : [100..1100]
Question
Conclure en indiquant quelle opération nécessite le moins d'instructions.
Solution
Dans (presque) tous les cas les requêtes 2 et 3 sont plus efficaces que 1 (il vaut mieux faire la restriction avant la jointure), le choix entre 2 et 3 dépend de n1 et de n2.
Un cas où il est préférable de faire la jointure avant est par exemple lorsque n3=0 (donc il n'y a aucun tuples à joindre). Notons que le gain est marginal (gain de 10% dans le meilleur des cas).
On en conclut que pour faire le meilleur choix le moteur de requête doit :
décider dans quel ordre effectuer les opération relationnelle (ici jointure ou restriction)
disposer d'information a priori sur le volume des tables (ici 10 et 100 tuples)
disposer d'information a priori sur le résultat des requêtes (ici les valeurs de n1, n2 et n3)