From: Kim Nguyễn Date: Thu, 9 Apr 2015 11:45:52 +0000 (+0200) Subject: . X-Git-Url: http://git.nguyen.vg/gitweb/?p=hacks%2FsimpleWebSlides.git;a=commitdiff_plain;h=1307c863879586a9e77904addf84616bd61ab168 . --- 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.

    • 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 + 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 diff --git a/bd/example_plan.svg b/bd/example_plan.svg index 3c3812f..677ff8f 100644 --- a/bd/example_plan.svg +++ b/bd/example_plan.svg @@ -9,11 +9,11 @@ xmlns="http://www.w3.org/2000/svg" xmlns:sodipodi="http://sodipodi.sourceforge.net/DTD/sodipodi-0.dtd" xmlns:inkscape="http://www.inkscape.org/namespaces/inkscape" - width="568.40125" - height="122.59209" + width="572.80127" + height="126.99208" id="svg2" version="1.1" - inkscape:version="0.48.5 r10040" + inkscape:version="0.48.4 r9939" sodipodi:docname="example_plan.svg"> @@ -25,20 +25,21 @@ inkscape:pageopacity="0.0" inkscape:pageshadow="2" inkscape:zoom="1.3734375" - inkscape:cx="375.34095" - inkscape:cy="69.837239" + inkscape:cx="377.54095" + inkscape:cy="72.037241" inkscape:document-units="px" inkscape:current-layer="layer1" showgrid="true" - fit-margin-top="0.3" - fit-margin-left="0.3" - fit-margin-right="0.3" - fit-margin-bottom="0.3" - inkscape:window-width="1317" - inkscape:window-height="744" - inkscape:window-x="49" - inkscape:window-y="24" - inkscape:window-maximized="1"> + fit-margin-top="2" + fit-margin-left="2" + fit-margin-right="2" + fit-margin-bottom="2" + inkscape:window-width="1631" + inkscape:window-height="1026" + inkscape:window-x="1249" + inkscape:window-y="407" + inkscape:window-maximized="1" + units="pt"> + originx="121.30664px" + originy="-807.31591px" /> @@ -65,9 +66,9 @@ inkscape:label="Layer 1" inkscape:groupmode="layer" id="layer1" - transform="translate(119.10664,-120.25418)"> + transform="translate(121.30664,-118.05418)"> + id="g3116"> Plan 2 - - ⨝ - ⨝ + R - R + S - - - S + + + ⨝ - ⨝ + B - - - B + + + Plan 3 - - - Plan 3 + ⨝ + ⨝ - R - S - - - B + S + + + ⨝ + ⨝ - B - - - Plan 1 - + x="20" + id="tspan2997-6-33" + sodipodi:role="line">R + + + Plan 1 diff --git a/bd/pdf/bd04.pdf b/bd/pdf/bd04.pdf index 28eafaa..dd5d0d5 100644 Binary files a/bd/pdf/bd04.pdf and b/bd/pdf/bd04.pdf differ diff --git a/bd/pdf/bd04_print.pdf b/bd/pdf/bd04_print.pdf index 26cb610..3f26edb 100644 Binary files a/bd/pdf/bd04_print.pdf and b/bd/pdf/bd04_print.pdf differ diff --git a/bd/pdf/bd05.pdf b/bd/pdf/bd05.pdf index 767466d..5e80052 100644 Binary files a/bd/pdf/bd05.pdf and b/bd/pdf/bd05.pdf differ diff --git a/bd/pdf/bd05_print.pdf b/bd/pdf/bd05_print.pdf index 2e54095..0e96cad 100644 Binary files a/bd/pdf/bd05_print.pdf and b/bd/pdf/bd05_print.pdf differ