From 1307c863879586a9e77904addf84616bd61ab168 Mon Sep 17 00:00:00 2001 From: =?utf8?q?Kim=20Nguy=E1=BB=85n?= Date: Thu, 9 Apr 2015 13:45:52 +0200 Subject: [PATCH] . --- bd/bd04.xhtml | 7 +- bd/bd05.xhtml | 56 +++---- bd/example_plan.svg | 371 +++++++++++++++++++++--------------------- bd/pdf/bd04.pdf | Bin 414842 -> 422224 bytes bd/pdf/bd04_print.pdf | Bin 400704 -> 408054 bytes bd/pdf/bd05.pdf | Bin 622808 -> 637300 bytes bd/pdf/bd05_print.pdf | Bin 603260 -> 617693 bytes 7 files changed, 214 insertions(+), 220 deletions(-) diff --git a/bd/bd04.xhtml b/bd/bd04.xhtml index c3a55b9..29656b9 100644 --- a/bd/bd04.xhtml +++ b/bd/bd04.xhtml @@ -49,7 +49,8 @@

Apprentis 4ème année

Cours 4 : Optimisation des opérateurs

kn@lri.fr
- http://www.lri.fr/~kn + http://www.lri.fr/~kn
+ version mise à jour le 09/04/2015

Motivation

@@ -93,8 +94,8 @@ L'AR nous dit que R &join; S = σ=(R x T), mais c'est très inefficace, on veut optimiser ce cas!

-

On suppose dans la suite M enregistrements dans R, - PR enregistrements/page, N enregistrement dans S, +

On suppose dans la suite M pages dans R, + PR enregistrements/page, N pages dans S, PS enregistrements/page.

On pose pour les exemples: M=1000, N=500, PR=120, PS=100

diff --git a/bd/bd05.xhtml b/bd/bd05.xhtml index 5c5c6f0..9ff0195 100644 --- a/bd/bd05.xhtml +++ b/bd/bd05.xhtml @@ -100,7 +100,7 @@ annotés avec un algorithme particulier.

@@ -116,9 +116,9 @@

@@ -127,15 +127,15 @@

Plan alternatif 1 (sans index)

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.

@@ -260,13 +260,13 @@ Exemples de facteurs de réduction:

Autres équivalences

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 + composée forcément de sélections, projections et agrégats (max, count, average, …)

  1. 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. @@ -390,7 +390,7 @@ Une projection commute avec une selection qui utilise uniquement peuvent êtres faites en pipeline (ou streaming sans itération/matérialisation des résultats intermédiaires
        • -
      • Celà peut valoir le coup d'utiliser un merge-sort join +
      • 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. @@ -452,7 +452,7 @@ uniformément réparties. Tous les sid et tous les bid sont présents float:left;'> -On choisi de faire d'abord une jointure entre R et S (i.e. un produit +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). @@ -461,13 +461,13 @@ attributs (bid,sid). 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. + (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édant qu'on vient de créer en mémoire): - 1 000 × (300 000 + 1000) = 301 000 000 E/S. + 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: 301 300 000 E/S (les projections sont faites +

        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 @@ -502,10 +502,10 @@ sur sid.

        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 + 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)

        +

        Coût total: 601 000 E/S (les projections sont faites en pipline à la fin)

    @@ -539,7 +539,7 @@ sur sid.

    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)

    +

    Coût total: 102 630 E/S (les projections sont faites en pipline à la fin)

    @@ -582,7 +582,7 @@ sur bid.