</script>
</head>
<body>
- <a href="bd03.xhtml" class="sws-previous"/>
+ <a href="bd04.xhtml" class="sws-previous"/>
<div class="sws-slide sws-cover sws-option-nofooter">
<h1>Bases de données</h1>
<h3>Polytech Paris-Sud</h3>
pages</li>
<li><em>Reserves</em>: 40 octets/enr., 100 enr/page, 1000
pages</li>
- <li><em>Boats</em>: non utilisé dans la suite</li>
+ <li><em>Boats</em>: 20 octets/enr., 200 enr/page, 200 pages</li>
</ul>
</div>
<div class="sws-slide">
<h1>Modèle de calcul</h1>
<p>
Les SGBD modernes utilisent un modèle de
- calcul <em><i>pull</i></em>. L'opérateur le plus « haut » (racine)
- dans l'arbre de requête « tire » (<i>pull</i>) le résultat de ses
+ calcul <em><i>pull</i></em>. L'opérateur le plus « haut » (racine)
+ dans l'arbre de requête « tire » (<i>pull</i>) le résultat de ses
sous-arbres (similaire à l'appel de <i>next</i> sur les iterateurs
de la bibliothèque standard Java). Cela permet
de <em><i>pipeliner</i></em> les opérateurs. Certains opérateurs «
</ul>
<p><img src="left_deep.svg" style="width:80%;margin-left:10%;" /></p>
<p style="background:white">Ce ne sont que des <em>heuristiques</em> pour réduire l'espace de
- recherche, on n'est pas sur d'avoir la solution optimale!</p>
+ recherche, on n'est pas sûr d'avoir la solution optimale!</p>
</div>
<div class="sws-slide">
<h1>Énumération des plans gauches en profondeur 1/2</h1>
deux à deux les résultats de la passe (n-1)
</li>
</ol>
-<p>Comment sélectionner les « meilleurs » jointures
- ? <span class="sws-pause" style="background:white" >On garde pour chaque <em>ordre</em> de
- résultat intermédiaire celle de moindre coût
+<p>Comment sélectionner les « meilleures » jointures ?
+ <span class="sws-pause" style="background:white" >On garde pour chaque <em>ordre</em> de
+ résultat intermédiaire celle de moindre coût
</span></p>
</div>
<div class="sws-slide">
<h1>Énumération des plans gauches en profondeur 2/2</h1>
-<p>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 <s>sort-merge</s> (car il est possible que le fait d'avoir les
- résultats déjà trié rendent le coût moindre à l'étape suivante)
+<p>Points à prendre en compte pour le calcul du coût d'un plan</p>
+<ol>
+ <li><em>Éviter les plans qui génèrent des produits cartésiens</em>, sauf si
+ c'est indispensable</li>
+ <li>Les projections, sélections, et jointures itératives par index
+ peuvent êtres faites en <em><i>pipeline</i> (ou <i>streaming</i></em> sans
+ itération/matérialisation des résultats intermédiaires
+ </li>
+ <li>Celà peut valoir le coup d'utiliser un <i>merge-sort</i> join
+ (possiblement coûteux) si on demande les résultats dans un <em>certain
+ ordre</em> (<tt>ORDER BY</tt> compatible avec celui de la jointure). Cela évite de faire
+ une jointure suivie d'un tri.
+ </li>
+ <li>Pousser les sélections/projections <em>plus bas</em> 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 <em><i>sans
+ index</i></em>.
+ </li>
+</ol>
+</div>
+<div class="sws-slide">
+<h1>Exemple</h1>
+<p>Considérons la requête : </p>
+<code>
+ SELECT sname, bname FROM Boats B, Sailors S, Reserves R WHERE
+ B.bid = R.bid AND S.sid = R.sid AND S.rating > 8
+</code>
+<p>Deux jointures (<tt>B &join; R</tt> et <tt>R &join; S</tt>) 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 ?</p>
+<p class="sws-pause"><img src="example_plan.svg" style="width:80%;margin-left:10%;" /></p>
+</div>
+
+<div class="sws-slide">
+<h1>Exemple (Calculs préliminaires)</h1>
+
+<ul>
+<li>Taille d'une page : 4000 octets</li>
+<li>Taille de S : 500 pages, 40 000 enr.</li>
+<li>Taille de R : 1000 pages, 100 000 enr.</li>
+<li>Taille de B : 200 pages, 40 000 enr.</li>
+<li>Taux de sélectivité de <tt>rating > 8 : 20%</tt> </li>
+<li><tt>σ<sub>rating>8</sub>(S)</tt> : 8000 enr. ou 100 pages</li>
+</ul>
+
+</div>
+
+
+<div class="sws-slide">
+<h1>Exemple (Plan 1)</h1>
+<p>
+<span style='display:inline-block;
+ margin-right:1em;
+ vertical-align: top;
+ background-image: url("example_plan.svg");
+ background-repeat: no-repeat;
+ background-position: -5%;
+ border: 1px solid black;
+ width:5cm;
+ height:4cm;
+ float:left;'>
+ </span>
+
+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).
+</p>
+<p> Manière la plus efficace de calculer S : <em>appliquer la sélection
+ directement sur S, puis la jointure <tt>B &join;
+ (σ(S))</tt></em>. Pas d'utilisation d'index possible, jointure page
+ à page (car on génère tout le produit cartésien) : <tt>100 ×
+ (100 + 200) = 300 000</tt> E/S (pages) ou 192 000 000 enr.
+</p>
+<p>Puis jointure <em>itérative page à page</em> avec R (<em>pas d'index sur R</em>, pas d'index
+ sur le résultat précédant qu'on vient de créer en mémoire):
+ <tt>1 000 × (300 000 + 1000) = 301 000 000 E/S.</tt>
+</p>
+<p>Coût total: <tt>301 300 000 E/S</tt> (les projections sont faites
+ en pipline à la fin)</p>
+<p style="background:white">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 (<tt>SELECT * FROM A, B</tt>).
+</p>
+</div>
+
+<div class="sws-slide">
+<h1>Exemple (Plan 2 v1)</h1>
+<p>
+<span style='display:inline-block;
+ margin-right:1em;
+ vertical-align: top;
+ background-image: url("example_plan.svg");
+ background-repeat: no-repeat;
+ background-position: 53%;
+ border: 1px solid black;
+ width:5cm;
+ height:4cm;
+ float:left;'>
+ </span>
+
+On choisi de faire d'abord une jointure entre R et B, sur
+l'attribut <tt>bid</tt> puis jointure du résultat intermédiaire
+sur <tt>sid</tt>.</p>
+
+<p>On dispose <em>d'un index</em> sur <tt>B.bid</tt>. On effectue une
+ <em>jointure itérative par index</em> : <tt> 1000 + 100 000 × 3 :
+ 301 000 E/S</tt> (2 pour le hash-index et 1 pour la lecture des
+ données depuis l'index).
+</p>
+<p>La deuxième jointure peut être faite à la volée (jointure itérative
+ par index sur <tt>S.sid</tt>) 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).
+</p>
+<p>Coût total: <tt>601 000 E/S</tt> (les projections sont faites en pipline à la fin)</p>
+</div>
+
+<div class="sws-slide">
+<h1>Exemple (Plan 2 v2)</h1>
+<p>
+<span style='display:inline-block;
+ margin-right:1em;
+ vertical-align: top;
+ background-image: url("example_plan.svg");
+ background-repeat: no-repeat;
+ background-position: 53%;
+ border: 1px solid black;
+ width:5cm;
+ height:4cm;
+ float:left;'>
+ </span>
+
+On choisi de faire d'abord une jointure entre R et B, sur
+l'attribut <tt>bid</tt> puis jointure du résultat intermédiaire
+sur <tt>sid</tt>.</p>
+
+<p>On n'utilise <em>pas l'index</em> sur <tt>B.bid</tt>. On effectue une
+ <em>jointure itérative page à page</em> : <tt> 200 + 200 × 1000 :
+ 200 200 E/S</tt> . 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.
+</p>
+<p>On applique la sélection sur S par un scan linéaire: <tt>500
+ E/S</tt> et <tt>100 pages</tt> de résultats</p>
+<p> On fait une jointure page à page des deux résultats
+ précédents : <tt>100 + 100 × 1515 = 100 615 E/S</tt>.
+</p>
+<p>Coût total: <tt>102 630 E/S</tt> (les projections sont faites en pipline à la fin)</p>
+</div>
+
+
+
+<div class="sws-slide">
+<h1>Exemple (Plan 3)</h1>
+<p>
+<span style='display:inline-block;
+ margin-right:1em;
+ vertical-align: top;
+ background-image: url("example_plan.svg");
+ background-repeat: no-repeat;
+ background-position: 103%;
+ border: 1px solid black;
+ width:5cm;
+ height:4cm;
+ float:left;'>
+ </span>
+
+On choisi de faire d'abord une jointure entre R et S, sur
+l'attribut <tt>sid</tt> puis jointure du résultat intermédiaire
+sur <tt>bid</tt>.</p>
+<p>On applique la sélection sur S par un scan linéaire: <tt>500
+ E/S</tt> et <tt>100 pages</tt> de résultats</p>
+
+<p> On effectue une <em>jointure itérative page à page</em> : <tt> 100 + 100 × 1000 :
+ 100 100 E/S</tt> . On a 100 000 résultats (car tous les S.sid
+ sont présents dans la table R, <s>même après sélection</s> 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.
+</p>
+<p> On fait une jointure page à page des du résultat
+ précédent avec B : <tt>200 + 200 × 2272 = 454 600 E/S</tt>.
</p>
-<p>On garde les <tt>ORDER BY</tt>, <tt>GROUP BY</tt>, aggrégats, …
- pour la fin, en profitant si possible des ordres des résultats faits
- par les jointures précédentes</p>
-<p>On évite tant que possible de faire des produits cartésiens (en
- poussant les selections par exemple)</p>
+<p>Coût total : 555 200 E/S</p>
+</div>
+<div class="sws-slide">
+<h1>Exemple (conclusion)</h1>
+
+<ul>
+ <li>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</li>
+ <li>On a fait certaines approximations « à la louche » (taille des
+ enregistrements résultants d'une jointure, nombre des
+ enregistrements résultants)</li>
+ <li>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
+ </li>
+</ul>
+
+
+
</div>
<div class="sws-slide">
<h1>Requêtes imbriquées</h1>
projects / hacks / simpleWebSlides.git / commitdiff