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