Pour chaque sous-terme, on considère tous les accès possibles
@@ -304,15 +304,15 @@ Une projection commute avec une selection qui utilise uniquement
Estimation du coût pour les plans mono-relation
-- Si on a un index I pour une selection sur clé primaire :
+
- Si on a un index I pour une sélection 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 :
+ sélection σ1, â¦, σn :
(NPages(I) + NPages(R))* RF(σ1) * ⦠* RF(σn)
- Si on a un index I non-groupant pour plusieurs
- selection σ1, â¦, σn :
+ sélection σ1, â¦, σn :
(NPages(I) + NEnr(R))* RF(σ1) * ⦠* RF(σn)
- Scan séquentiel à R:
NPages(R)
@@ -343,7 +343,7 @@ Une projection commute avec une selection qui utilise uniquement
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
+ de sélections 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.
@@ -355,7 +355,7 @@ Une projection commute avec une selection qui utilise uniquement
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!
Ãnumération des plans gauches en profondeur 1/2
@@ -375,24 +375,226 @@ Une projection commute avec une selection qui utilise uniquement
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
+Comment sélectionner les « meilleures » 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)
+
Points à prendre en compte pour le calcul du coût d'un plan
+
+ - Ãviter les plans qui génèrent des produits cartésiens, sauf si
+ c'est indispensable
+ - Les projections, sélections, et jointures itératives par index
+ peuvent êtres faites en pipeline (ou streaming sans
+ itération/matérialisation des résultats intermédiaires
+
+ - Cela peut valoir le coup d'utiliser un merge-sort join
+ (possiblement coûteux) si on demande les résultats dans un certain
+ ordre (ORDER BY compatible avec celui de la jointure). Cela évite de faire
+ une jointure suivie d'un tri.
+
+ - Pousser les sélections/projections plus bas dans le plan
+ permet de faire diminuer la taille des résultats
+ intermédiaires. Attention cependant, appliquer une sélection ou une
+ projection à une table T munie d'un index crée une table T' plus
+ petite mais sans
+ index.
+
+
+
+
+
Exemple
+
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 ?
+
+
+
Exemple (Calculs préliminaires)
+
+
+- Taille d'une page : 4000 octets
+- Taille de S : 500 pages, 40 000 enr.
+- Taille de R : 1000 pages, 100 000 enr.
+- Taille de B : 200 pages, 40 000 enr.
+- Taux de sélectivité de rating > 8 : 20%
+- σrating>8(S) : 8000 enr. ou 100 pages
+
+
+
+
Exemple (Plan 1)
+
+
+
+
+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).
+
+
+
Exemple (Plan 2 v1)
+
+
+
+
+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)
+
+
Exemple (Plan 2 v2)
+
+
+
+
+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)
+
+
Exemple (Plan 3)
+
+
+
+
+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
+
+
Exemple (conclusion)
+
+
+ - Utiliser l'index n'est pas toujours payant, surtout s'il est
+ non-groupant, car on ajoute un facteur qui est le nombre de
+ résultats, pas le nombre de pages
+ - On a fait certaines approximations « à la louche » (taille des
+ enregistrements résultants d'une jointure, nombre des
+ enregistrements résultants)
+ - On n'a pas considéré le fait que pousser les projections plus
+ bas pour ne garder que les colonnes strictement nécessaires pouvait
+ faire baisser la taille des tables intermédiaires
+
+
+
+
+
Requêtes imbriquées
