From a06550bc77c1cbee8d1cd79147a10b4532683b8e Mon Sep 17 00:00:00 2001 From: =?utf8?q?Kim=20Nguy=E1=BB=85n?= Date: Wed, 8 Apr 2015 21:43:37 +0200 Subject: [PATCH] Cours BD 5. --- bd/bd05.xhtml | 238 ++++++++++++++++++++++++++++++++++++++++++++++---- 1 file changed, 220 insertions(+), 18 deletions(-) diff --git a/bd/bd05.xhtml b/bd/bd05.xhtml index 7b0692e..5c5c6f0 100644 --- a/bd/bd05.xhtml +++ b/bd/bd05.xhtml @@ -42,7 +42,7 @@ - +

Bases de données

Polytech Paris-Sud

@@ -90,7 +90,7 @@ pages
  • Reserves: 40 octets/enr., 100 enr/page, 1000 pages
    • -
  • Boats: non utilisé dans la suite
    • +
  • Boats: 20 octets/enr., 200 enr/page, 200 pages
    • @@ -277,8 +277,8 @@ Une projection commute avec une selection qui utilise uniquement

    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 + 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 « @@ -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

    +
      +
    1. Éviter les plans qui génèrent des produits cartésiens, sauf si + c'est indispensable
      2. +
    2. 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 +
      3. +
    3. Celà 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. +
      4. +
    4. 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. +
      5. +
    +
    +
    +

    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 R 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) = 300 000 E/S (pages) ou 192 000 000 enr. +

    +

    Puis jointure itérative page à page avec R (pas d'index sur R, pas d'index + sur le résultat précédant qu'on vient de créer en mémoire): + 1 000 × (300 000 + 1000) = 301 000 000 E/S. +

    +

    Coût total: 301 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édants, 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 et qu'il 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

    -- 2.17.1