X-Git-Url: http://git.nguyen.vg/gitweb/?a=blobdiff_plain;ds=inline;f=bd%2Fbd05.xhtml;h=9ff0195a28674826d63f418f2a9af6b6977426b8;hb=HEAD;hp=7b0692e0ea72a96a747f9e5e2cbf1f1bb47d8fc9;hpb=171bd61f3e4cf06638c6a90fdc053efbec9623ff;p=hacks%2FsimpleWebSlides.git diff --git a/bd/bd05.xhtml b/bd/bd05.xhtml index 7b0692e..9ff0195 100644 --- a/bd/bd05.xhtml +++ b/bd/bd05.xhtml @@ -42,7 +42,7 @@
- +On pousse la sélection sous la jointure (car - selection AND). On suppose qu'on a 100 + sélection AND). On suppose qu'on a 100 bateaux, 10 notes et distributions uniformes.
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 + 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 itérateurs 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). + agrégats).
Dans le cas mono-relation (i.e. sans jointure), la requête est - composée forcément de selections, projections et aggrégats + composée forcément de sélections, projections et agrégats (max, count, average, â¦)
Ce ne sont que des heuristiques pour réduire l'espace de - recherche, on n'est pas sur d'avoir la solution optimale!
+ recherche, on n'est pas sûr d'avoir la solution optimale!Comment sélectionner les « meilleurs » jointures
- ? On garde pour chaque ordre de
- résultat intermédiaire celle de moindre coût
+ Comment sélectionner les « meilleures » jointures ?
+ On garde pour chaque ordre de
+ résultat intermédiaire celle de moindre coût
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)
+
Points à prendre en compte pour le calcul du coût d'un plan
+Considérons la requête :
+
+ SELECT sname, bname FROM Boats B, Sailors S, Reserves R WHERE
+ B.bid = R.bid AND S.sid = R.sid AND S.rating > 8
+
+Deux jointures (B &join; R et R &join; S) et une +sélection sur S. On suppose un hash-index sur S.sid et un +hash-index sur B.bid, les valeurs de notes vont de 1 à 10, +uniformément réparties. Tous les sid et tous les bid sont présents + dans R. + Les hash-index sont non-groupants et de coût + d'accès 2. + Quels sont les plans possibles ?
+ ++ + + +On choisi de faire d'abord une jointure entre B et S (i.e. un produit +cartésien car il n'y a pas de condition de jointure entre ces deux +tables). Puis la jointure de la table résultante avec B sur les +attributs (bid,sid). +
+Manière la plus efficace de calculer S : appliquer la sélection + directement sur S, puis la jointure B &join; + (σ(S)). Pas d'utilisation d'index possible, jointure page + à page (car on génère tout le produit cartésien) : 100 à + (100 + 200) = 30 000 E/S (pages) ou 19 200 000 enr. +
+Puis jointure itérative page à page avec R (pas d'index sur R, pas d'index + sur le résultat précédent qu'on vient de créer en mémoire): + 1 000 à (30 000 + 1000) = 31 000 000 E/S. +
+Coût total: 31 300 000 E/S (les projections sont faites + en pipline à la fin)
+Plan complètement inefficace. On ignorera les plans contenant un + produit cartésien, sauf si c'est le seul moyen de calculer la + requête (SELECT * FROM A, B). +
++ + + +On choisi de faire d'abord une jointure entre R et B, sur +l'attribut bid puis jointure du résultat intermédiaire +sur sid.
+ +On dispose d'un index sur B.bid. On effectue une + jointure itérative par index : 1000 + 100 000 à 3 : + 301 000 E/S (2 pour le hash-index et 1 pour la lecture des + données depuis l'index). +
+La deuxième jointure peut être faite à la volée (jointure itérative + par index sur S.sid) et la condition de sélection testée à + la volée. Coût total 100 000 à 3 (pour chacun des enregistrement + précédents, on paye un accès d'index + un accès à la ligne + correspondante dans S). +
+Coût total: 601 000 E/S (les projections sont faites en pipline à la fin)
++ + + +On choisi de faire d'abord une jointure entre R et B, sur +l'attribut bid puis jointure du résultat intermédiaire +sur sid.
+ +On n'utilise pas l'index sur B.bid. On effectue une + jointure itérative page à page : 200 + 200 à 1000 : + 200 200 E/S . On a 100 000 résultats (car tous les B.bid + sont présents dans la table R). Un enregistrement du + résultat fait environ 40+20 = 60 octets donc 66 enregistrements par + pages de 4000 octets donc 1515 pages de résultats. +
+On applique la sélection sur S par un scan linéaire: 500 + E/S et 100 pages de résultats
+On fait une jointure page à page des deux résultats + précédents : 100 + 100 à 1515 = 100 615 E/S. +
+Coût total: 102 630 E/S (les projections sont faites en pipline à la fin)
++ + + +On choisi de faire d'abord une jointure entre R et S, sur +l'attribut sid puis jointure du résultat intermédiaire +sur bid.
+On applique la sélection sur S par un scan linéaire: 500 + E/S et 100 pages de résultats
+ + On effectue une jointure itérative page à page : 100 + 100 à 1000 :
+ 100 100 E/S . On a 100 000 résultats (car tous les S.sid
+ sont présents dans la table R, même après sélection car
+ distribution uniforme). Un enregistrement du
+ résultat fait environ 40+50 = 90 octets donc 44 enregistrements par
+ pages de 4000 octets donc 2272 pages de résultats.
+
On fait une jointure page à page des du résultat + précédent avec B : 200 + 200 à 2272 = 454 600 E/S.
-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)
+Coût total : 555 200 E/S
+