bd/bd05.xhtml

   1 <?xml version="1.0" encoding="utf-8" ?>
   2 <!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Strict//EN"
   3           "http://www.w3.org/TR/xhtml1/DTD/xhtml1-strict.dtd"
   4 [
   5           <!ENTITY in  "<small style='font-size:small'>∈</small>">
   6           <!ENTITY notin  "<small style='font-size:small'>∉</small>">
   7           <!ENTITY mapsto  "↦">
   8           <!ENTITY join    "⨝">
   9 ]
  10           >
  11 <html xmlns="http://www.w3.org/1999/xhtml" >
  12   <head>
  13     <title>Optimisation de requêtes</title>
  14
  15     <meta http-equiv="Content-Type"
  16           content="text/html; charset=utf-8" />
  17     <meta name="copyright"
  18           content="Copyright &#169; 2013 Kim Nguyễn" />
  19
  20     <!-- Load jQuery -->
  21     <script src="../jquery-2.0.3.min.js" type="text/javascript" ></script>
  22     <script src="../libs/raphael-min.js" type="text/javascript" ></script>
  23     <!-- Load the library -->
  24     <script src="../simpleWebSlides.js" type="text/javascript" ></script>
  25
  26     <link rel="stylesheet" href="../simpleWebSlides.css" type="text/css"  media="all" />
  27     <!-- Load a custom Theme, the class-element marks this style-sheet
  28          a "theme" that can be swtiched dynamicaly -->
  29     <link class="sws-theme" rel="stylesheet"  title="U-Psud style"  href="../themes/uPsud.css" type="text/css" />
  30
  31     <!-- Customize some templates and initialize -->
  32
  33     <script type="text/javascript">
  34       SWS.Config['sws-slide-change'] = SWS.Effects.slideChangeFadeOutIn;
  35       SWS.Config['sws-object-deactivate'] =  SWS.Effects.objectDeactivateFadeOut;
  36       SWS.Config['sws-object-activate'] = SWS.Effects.objectActivateFadeIn;
  37
  38       //Ensures that we load SWS at the very end, after MathJax has
  39       //been initialized
  40
  41       $(window).load(SWS.Presentation.init);
  42     </script>
  43   </head>
  44   <body>
  45     <a href="bd04.xhtml" class="sws-previous"/>
  46     <div class="sws-slide sws-cover sws-option-nofooter">
  47       <h1>Bases de données</h1>
  48       <h3>Polytech Paris-Sud</h3>
  49       <h3>Apprentis 4<sup>ème</sup> année</h3>
  50       <h1>Cours 5 : Optimisation des requêtes</h1>
  51       <a href="mailto:kn@lri.fr">kn@lri.fr</a><br/>
  52       <a href="http://www.lri.fr/~kn/">http://www.lri.fr/~kn</a>
  53     </div>
  54
  55     <h1>Motivation et introduction</h1>
  56     <div class="sws-slide">
  57       <h1>Principe d'évaluation d'une requête</h1>
  58       <div style="padding-left:15pt;">
  59       <ol>
  60         <li><i>Parsing</i> de la requête</li>
  61         <li>Traduction en arbre
  62         d'opérateurs de l'algèbre
  63         relationnelle <span class="sws-onframe-1-3"><em>(&pi;,
  64         &sigma;, ⨝, … )</em></span></li>
  65         <li>Optimisation :
  66           <ol>
  67             <li>Génération de <em>plans
  68             d'évaluation</em> <span class="sws-onframe-2-3">(en
  69             réordonnant les <em> opérations élémentaires</em>)</span></li>
  70             <li>Estimation du <em>coût</em> de chacun des
  71             plans <span class="sws-onframe-3-3">(en fonction du <em>coût
  72             des opérations élémentaires</em>)</span></li>
  73             <li>Choix du plan le plus <em>efficace</em></li>
  74           </ol>
  75         </li>
  76         <li>Évaluation du plan choisi</li>
  77         <li>(Éventuellement mise à jour des statistiques)</li>
  78       </ol>
  79       <p>On va voir comment optimiser l'évaluation d'une requête</p>
  80       </div>
  81     </div>
  82     <div class="sws-slide">
  83       <h1>Exemple pour la suite du cours</h1>
  84 <code>  Sailors(<u>sid: integer</u>, sname: string, rating: integer, age: real);
  85   Reserves(<u>sid: integer, bid: integer, day: date</u>, rname: string);
  86   Boats(<u>bid: integer</u>, bname: string, capacity: integer);
  87 </code>
  88 <ul>
  89   <li><em>Sailors</em>: 50 octets/enr., 80 enr/page, 500
  90   pages</li>
  91   <li><em>Reserves</em>: 40 octets/enr., 100 enr/page, 1000
  92   pages</li>
  93   <li><em>Boats</em>: 20 octets/enr., 200 enr/page, 200 pages</li>
  94 </ul>
  95     </div>
  96     <div class="sws-slide">
  97       <h1>Généralités</h1>
  98       <p>Un <em>plan d'exécution</em> de requête est un <em>arbre</em>
  99       dont les noeuds sont des opérateurs de l'algèbre relationnelle
 100       annotés avec un algorithme particulier.
 101       </p>
 102       <ul>
 103         <li>Pour une requête donnée, quels plans doit on considérer
 104         ?</li>
 105         <li>Comment peut on estimer le coût total d'un plan</li>
 106       </ul>
 107       <p>Idéalement, on veut trouver le meilleur plan. En pratique, on
 108       choisira le moins pire!</p>
 109     </div>
 110     <div class="sws-slide">
 111       <h1>Exemple</h1>
 112 <code>
 113   SELECT S.sname
 114   FROM Reserves R, Sailors S
 115   WHERE R.sid = S.sid AND bid = 100 AND rating > 5
 116 </code>
 117 <p><img class="sws-pause" src="simple_plan.svg" width="50%"/></p>
 118 <ul>
 119   <li class="sws-pause">Coût: 500+500*1000 E/S (pourquoi ?)</li>
 120   <li> Plusieurs occasions manquées : pas d'utilisation d'index, on
 121   aurait pu pousser la sélection sous la jointure, …</li>
 122   <li> Notre but est de trouver des plans d'exécution plus efficaces
 123   qui calculent le même résultat</li>
 124 </ul>
 125     </div>
 126     <div class="sws-slide">
 127       <h1>Plan alternatif 1 (sans index)</h1>
 128 <p><img class="sws-pause" src="simple_plan1.svg" width="50%"/></p>
 129 <p class="sws-pause">On pousse la sélection sous la jointure (car
 130   sélection <tt>AND</tt>). On suppose qu'on a 100
 131   bateaux, 10 notes et distributions uniformes. </p>
 132 <ul>
 133   <li>Scan <tt>Reserves</tt> (1000 E/S) et écriture de 10 pages dans T1</li>
 134   <li>Scan <tt>Sailors</tt> (500 E/S) et écriture de 250 pages dans T2</li>
 135   <li>Tri T1 (3*10 E/S), Tri T2 (8*250 E/S), fusion (10+250 E/S)</li>
 136   <li>Total: <em>4050 E/S</em></li>
 137   <li>Si on pousse la projection, T1 ne contient que <tt>sid</tt>, T2
 138     uniquement <tt>sid</tt> et <tt>sname</tt> (cout <tt>&lt;</tt> 2000 E/S)</li>
 139 </ul>
 140     </div>
 141     <div class="sws-slide">
 142       <h1>Plan alternatif 2 (avec index)</h1>
 143 <p><img class="sws-pause" src="simple_plan2.svg" width="50%"/></p>
 144 <p class="sws-pause">On suppose un hash-index groupant sur <tt>bid</tt>
 145 </p>
 146 <ul>
 147   <li>Accès au premier enregistrement <tt>bid=100</tt> 1.2 E/S</li>
 148   <li>Accès aux suivants: 9 E/S</li>
 149   <li><tt>sid</tt> est une clé pour Sailors. On a un hash-index dessus
 150   (forcément non-groupant)</li>
 151   <li>Pour chacun des 10 * 100 enr. tels que <tt>bid=100</tt> on
 152   cherche l'enregistrement de Sailors avec le même <tt>sid</tt> (1.2
 153   E/S/enr)</li>
 154   <li>Coût total: 1000 * 1.2 + 10.2 = 1210 E/S</li>
 155 </ul>
 156     </div>
 157 <div class="sws-slide">
 158 <h1>Algorithme général de choix de plan</h1>
 159 <ul><li>Cas mono-relation (une seule table dans le <tt>FROM</tt>):
 160     <ol><li>On énumère tous les plans (en tenant compte des
 161     équivalences de l'algèbre relationnelle)</li>
 162       <li>On calcule le coût de chaque plan</li>
 163       <li>On choisit le plan de moindre coût</li>
 164     </ol>
 165   </li>
 166 <li>Cas multi-relations (plusieurs tables dans le <tt>FROM</tt>):
 167     <ol><li>Trop de plan pour les énumérer tous, on choisit des arbres
 168     ayant une certaine forme </li>
 169       <li>On calcule le coût de chaque plan</li>
 170       <li>On choisit le plan de moindre coût</li>
 171     </ol>
 172 </li>
 173   <li>On sait (cours 4) estimer le coût d'un opérateur en fonction de
 174   la taille de l'entrée. On va enchaîner les opérateurs donc il faut
 175   estimer <em>la taille du résultat</em> pour calculer
 176   le <em>coût</em> de l'opérateur suivant!</li>
 177 </ul>
 178 </div>
 179 <h1>Estimation de coût</h1>
 180 <div class="sws-slide">
 181 <h1>Statistiques et catalogues</h1>
 182 <p>On a besoin d'informations numériques sur les relations et les
 183   indexes. Un <em>catalogue</em> contient en général:</p>
 184 <ul><li>Le nombre d'enregistrements (<tt><s>NEnr</s></tt>) et le
 185     nombre de pages (<tt><s>NPages</s></tt>) de la relation.
 186     </li>
 187   <li>Le nombre de clés distinctes (<tt><s>NClés</s></tt>) pour les
 188   indexes ainsi que leur taille en pages</li>
 189   <li>La hauteur ainsi que les clés min/max dans l'index, pour les
 190   arbres</li>
 191 </ul>
 192 <p>Les catalogues sont mis  à jours périodiquement mais pas à chaque
 193   mise à jours, pour ne pas impacter les performances.</p>
 194 </div>
 195 <div class="sws-slide">
 196 <h1>Estimation du nombre de résultats et facteur de réduction</h1>
 197 <p>On considère une requête de la forme:</p>
 198 <code>  SELECT <i>attributs</i> FROM <i>tables</i> WHERE <em>e<sub>1</sub></em> AND … AND <em>e<sub>n</sub></em>
 199 </code>
 200 <ul><li>La taille maximale <tt>TMax</tt> du résultat est le produit des tailles des
 201     tables se trouvant dans le <tt>FROM</tt></li>
 202 <li>Le facteur de réduction de chaque expression <tt><em>e</em></tt>
 203  caractérise l'impact de ce terme sur la taille du résultat</li>
 204 <li>La taille finale du résultat est approximée par: <tt>TMax *
 205     RF<sub>1</sub> * … * RF<sub>n</sub></tt></li>
 206 </ul>
 207 <p>On fait la supposition que les expressions sont indépendantes.<br/>
 208 Exemples de facteurs de réduction:
 209 </p>
 210 <ul><li> <tt>att = valeur</tt> :  <tt>1 /
 211       NClés</tt> si <tt>att</tt> este une clé pour un index I</li>
 212 <li><tt>att<sub>1</sub> = att<sub>2</sub></tt> : <tt> 1/Max(NClé(I1),
 213     NClé(I2))</tt> (avec <tt>att<sub>i</sub></tt> une clé
 214     de <tt>Ii</tt>) </li>
 215 <li><tt>att &gt; valeur</tt> : <tt> (Max(I)-valeur)/(Max(I) - Min(I))</tt>
 216 </li>
 217 </ul>
 218  </div>
 219 <div class="sws-slide">
 220   <h1>Équivalences de l'algèbre relationnelle</h1>
 221   <p>Permet de réordonner les jointures et de « pousser » les sélections
 222   et les projections sous les jointures</p>
 223   <ul>
 224     <li>Sélections :
 225       <ul>
 226         <li> <tt>&sigma;<sub>c<sub>1</sub>&#8743;…&#8743;c<sub>n</sub></sub>(R)
 227         ≡
 228         &sigma;<sub>c<sub>1</sub></sub>(… (&sigma;<sub>c<sub>n</sub></sub>(R)))</tt>  [Cascade]
 229           </li>
 230         <li> <tt>
 231             &sigma;<sub>c<sub>1</sub></sub>(&sigma;<sub>c<sub>2</sub></sub>(R))
 232         ≡
 233             &sigma;<sub>c<sub>2</sub></sub>(&sigma;<sub>c<sub>1</sub></sub>(R))
 234           </tt> [Commutativité]
 235           </li>
 236
 237       </ul>
 238     </li>
 239     <li>Projections :
 240       <ul>
 241         <li> <tt>&pi;<sub>a<sub>1</sub>, …, a<sub>n</sub></sub>(
 242             …(&pi;<sub>z<sub>1</sub>, …, z<sub>m</sub></sub>(R))
 243         ≡
 244              &pi;<sub>a<sub>1</sub>, …, a<sub>n</sub></sub>(R)</tt> [Cascade]
 245           </li>
 246
 247       </ul>
 248     </li>
 249     <li>Jointures :
 250       <ul>
 251         <li> <tt>R &join; (S &join; T) ≡ (R &join; S) &join; T</tt> [Associativité]
 252         </li>
 253         <li> <tt> (R &join; S) ≡ (S &join; R) </tt> [Commutativité]
 254         </li>
 255       </ul>
 256     </li>
 257   </ul>
 258 </div>
 259 <div class="sws-slide">
 260   <h1>Autres équivalences</h1>
 261   <ul>
 262     <li>
 263 Une projection commute avec une sélection qui utilise uniquement
 264   les attributs de la projection</li>
 265     <li>Une sélection entre des attributs de deux arguments d'un
 266     produit cartésien peut être converti en jointure:
 267       <tt> &sigma;<sub>&phi;</sub> (R &times; S) ≡ R &join;<sub>&phi;</sub> S</tt>
 268       </li>
 269     <li>Une sélection sur des attributs de <tt>R</tt> commute avec la
 270     jointure <tt>R&join;S</tt> (c'est à dire:  <tt>&sigma;(R&join;S) ≡  &sigma;(R)&join;S </tt>)
 271       </li>
 272     <li>Règle similaire pour pousser les projections sous jointure</li>
 273   </ul>
 274 </div>
 275 <h1>Énumération de plans</h1>
 276 <div class="sws-slide">
 277 <h1>Modèle de calcul</h1>
 278 <p>
 279   Les SGBD modernes utilisent un modèle de
 280   calcul <em><i>pull</i></em>. L'opérateur le plus «&nbsp;haut&nbsp;» (racine)
 281   dans l'arbre de requête «&nbsp;tire&nbsp;» (<i>pull</i>) le résultat de ses
 282   sous-arbres (similaire à l'appel de <i>next</i> sur les itérateurs
 283   de la bibliothèque standard Java). Cela permet
 284   de <em><i>pipeliner</i></em> les opérateurs. Certains opérateurs «
 285   <em>bloquent</em> » le <i>pipeline</i> (en particulier les tris et
 286   agrégats).
 287 </p>
 288
 289 </div>
 290 <div class="sws-slide">
 291 <h1>Cas mono-relation</h1>
 292 <p>Dans le cas mono-relation (i.e. sans jointure), la requête est
 293   composée forcément de sélections, projections et agrégats
 294   (<tt>max</tt>, <tt>count</tt>, <tt>average</tt>, …)</p>
 295 <ol>
 296   <li>Pour chaque sous-terme, on considère tous les accès possibles
 297   (scan, utilisation de l'index, …) et on prend le moins coûteux</li>
 298
 299 <li>Les opérateurs restants sont calculé <em>à la volée</em> (en
 300   pipelinant les opérations)
 301 </li>
 302 </ol>
 303 </div>
 304 <div class="sws-slide">
 305 <h1>Estimation du coût pour les plans mono-relation</h1>
 306 <ul>
 307 <li> Si on a un index I pour une sélection sur clé primaire :
 308   <tt><s>Hauteur(I) + 1</s></tt> pour un arbre B+, <tt><s>1.2</s></tt>
 309   pour un hash-index</li>
 310 <li> Si on a un index I groupant pour plusieurs
 311   sélection <tt>&sigma;<sub>1</sub></tt>, …, <tt>&sigma;<sub>n</sub></tt> :<br/>
 312   <tt><s>(NPages(I) + NPages(R))* RF(&sigma;<sub>1</sub>) * … * RF(&sigma;<sub>n</sub>) </s></tt>
 313 </li>
 314 <li> Si on a un index I non-groupant pour plusieurs
 315   sélection <tt>&sigma;<sub>1</sub></tt>, …, <tt>&sigma;<sub>n</sub></tt> :<br/>
 316   <tt><s>(NPages(I) + <u>NEnr</u>(R))* RF(&sigma;<sub>1</sub>) * … * RF(&sigma;<sub>n</sub>) </s></tt>
 317 </li>
 318 <li>Scan séquentiel à <tt>R</tt>: <tt><s>NPages(R)</s></tt></li>
 319 </ul>
 320 </div>
 321 <div class="sws-slide">
 322 <h1>Exemple de calcul de coût</h1>
 323 <code>   SELECT S.sid FROM Sailors S WHERE S.rating = 8; </code>
 324 <code>       &pi;<sub>sid</sub>(&sigma;<sub>rating = 8</sub>(S))</code>
 325 <ul>
 326   <li>Avec un index sur <tt>rating</tt>:
 327     <ul>
 328       <li>Groupant: <tt>1/NClés(I) * (NPages(I) +
 329       NPages(R))</tt>. Avec des valeurs numériques: <tt> 1/10 *
 330       (50+500) = 55 E/S</tt></li>
 331       <li>Non-groupant: <tt>1/NClés(I) * (NPages(I) +
 332       NEnr(R))</tt>. Avec des valeurs numériques: <tt> 1/10 *
 333       (50+40000) = 4005 E/S</tt></li>
 334     </ul>
 335   </li>
 336   <li>Scan : on récupère toutes les pages et on filtre: <tt>500</tt> E/S</li>
 337 </ul>
 338 <p><em>Note</em>: Une fois que l'on a sélectionné un enregistrement,
 339   la projection est « gratuite » (en terme d'E/S) car le résultat n'a
 340   pas à être sauvé dans une table temporaire</p>
 341 </div>
 342 <div class="sws-slide">
 343   <h1>Requêtes multi-relations</h1>
 344 <ul><li>Les choix vont être guidé par les <em>jointures</em></li>
 345   <li>Si on considère uniquement <tt>n</tt> jointures (pas de projections ni
 346   de sélections dans le plan de requête). Le nombre de plans possible
 347   est le nombre d'arbre binaires ayant <tt>n</tt> noeuds internes
 348   (exponentiel en <tt>n</tt>, exactement: nombre de Catalan
 349   d'indice <tt>n</tt>). <s>Beaucoup trop pour les énumérer tous</s>.
 350   </li>
 351 <li>On se restreint aux <em>arbres gauches en profondeur</em> qui
 352   permettent d'énumérer tous les plans complètement
 353   « <i>pipelinable</i> »
 354   </li>
 355 </ul>
 356 <p><img src="left_deep.svg" style="width:80%;margin-left:10%;" /></p>
 357 <p style="background:white">Ce ne sont que des <em>heuristiques</em> pour réduire l'espace de
 358   recherche, on n'est pas sûr d'avoir la solution optimale!</p>
 359 </div>
 360 <div class="sws-slide">
 361 <h1>Énumération des plans gauches en profondeur 1/2</h1>
 362 <p>Toujours exponentiel (mais moins)</p>
 363 <p>Tous les arbres différent maintenant dans l'ordre dans lequel on
 364   fait les jointures, la méthode d'accès pour chaque relation et les
 365   algorithmes de jointure utilisés</p>
 366 <p>On applique l'heuristique suivante:</p>
 367 <ol>
 368 <li>1<sup>ère</sup> passe: on trouve la meilleure manière de calculer
 369   chaque relation individuellement
 370 </li>
 371 <li>2<sup>ème</sup> passe: on trouve la meilleure manière de joindre
 372   deux à deux les résultats de la passe 1
 373 </li>
 374 <li>n<sup>ème</sup> passe: on trouve la meilleure manière de joindre
 375   deux à deux les résultats de la passe (n-1)
 376 </li>
 377 </ol>
 378 <p>Comment sélectionner les « meilleures » jointures ?
 379   <span class="sws-pause" style="background:white" >On garde pour chaque <em>ordre</em> de
 380     résultat intermédiaire celle de moindre coût
 381 </span></p>
 382 </div>
 383 <div class="sws-slide">
 384 <h1>Énumération des plans gauches en profondeur 2/2</h1>
 385 <p>Points à prendre en compte pour le calcul du coût d'un plan</p>
 386 <ol>
 387   <li><em>Éviter les plans qui génèrent des produits cartésiens</em>, sauf si
 388   c'est indispensable</li>
 389   <li>Les projections, sélections, et jointures itératives par index
 390     peuvent êtres faites en <em><i>pipeline</i> (ou <i>streaming</i></em> sans
 391     itération/matérialisation des résultats intermédiaires
 392   </li>
 393   <li>Cela peut valoir le coup d'utiliser un <i>merge-sort</i> join
 394     (possiblement coûteux) si on demande les résultats dans un <em>certain
 395     ordre</em> (<tt>ORDER BY</tt> compatible avec celui de la jointure). Cela évite de faire
 396     une jointure suivie d'un tri.
 397   </li>
 398   <li>Pousser les sélections/projections <em>plus bas</em> dans le plan
 399   permet de faire diminuer la taille des résultats
 400   intermédiaires. Attention cependant, appliquer une sélection ou une
 401   projection à une table T munie d'un index crée une table T' plus
 402   petite mais <em><i>sans
 403   index</i></em>.
 404   </li>
 405 </ol>
 406 </div>
 407 <div class="sws-slide">
 408 <h1>Exemple</h1>
 409 <p>Considérons la requête : </p>
 410 <code>
 411   SELECT sname, bname FROM Boats B, Sailors S, Reserves R WHERE
 412   B.bid = R.bid AND S.sid = R.sid AND S.rating > 8
 413 </code>
 414 <p>Deux jointures (<tt>B &join; R</tt> et <tt>R &join; S</tt>) et une
 415 sélection sur S. On suppose un hash-index sur S.sid et un
 416 hash-index sur B.bid, les valeurs de notes vont de 1 à 10,
 417 uniformément réparties. Tous les sid et tous les bid sont présents
 418   dans R.
 419   Les hash-index sont non-groupants et de coût
 420   d'accès 2.
 421   Quels sont les plans possibles ?</p>
 422 <p class="sws-pause"><img src="example_plan.svg" style="width:80%;margin-left:10%;" /></p>
 423 </div>
 424
 425 <div class="sws-slide">
 426 <h1>Exemple (Calculs préliminaires)</h1>
 427
 428 <ul>
 429 <li>Taille d'une page : 4000 octets</li>
 430 <li>Taille de S : 500 pages, 40 000 enr.</li>
 431 <li>Taille de R : 1000 pages, 100 000 enr.</li>
 432 <li>Taille de B : 200 pages, 40 000 enr.</li>
 433 <li>Taux de sélectivité de <tt>rating &gt; 8 : 20%</tt> </li>
 434 <li><tt>&sigma;<sub>rating&gt;8</sub>(S)</tt> : 8000 enr. ou 100 pages</li>
 435 </ul>
 436
 437 </div>
 438
 439
 440 <div class="sws-slide">
 441 <h1>Exemple (Plan 1)</h1>
 442 <p>
 443 <span style='display:inline-block;
 444             margin-right:1em;
 445             vertical-align: top;
 446             background-image: url("example_plan.svg");
 447             background-repeat: no-repeat;
 448             background-position: -5%;
 449             border: 1px solid black;
 450             width:5cm;
 451             height:4cm;
 452             float:left;'>
 453  </span>
 454
 455 On choisi de faire d'abord une jointure entre B et S (i.e. un produit
 456 cartésien car il n'y a pas de condition de jointure entre ces deux
 457 tables). Puis la jointure de la table résultante avec B sur les
 458 attributs (bid,sid).
 459 </p>
 460 <p> Manière la plus efficace de calculer S : <em>appliquer la sélection
 461   directement sur S, puis la jointure <tt>B &join;
 462   (&sigma;(S))</tt></em>. Pas d'utilisation d'index possible, jointure page
 463   à page (car on génère tout le produit cartésien) : <tt>100 ×
 464   (100 + 200) = 30 000</tt> E/S (pages) ou 19 200 000 enr.
 465 </p>
 466 <p>Puis jointure <em>itérative page à page</em> avec R (<em>pas d'index sur R</em>, pas d'index
 467   sur le résultat précédent qu'on vient de créer en mémoire):
 468   <tt>1 000 × (30 000 + 1000) = 31 000 000 E/S.</tt>
 469 </p>
 470 <p>Coût total: <tt>31 300 000 E/S</tt> (les projections sont faites
 471   en pipline à la fin)</p>
 472 <p style="background:white">Plan complètement inefficace. On ignorera les plans contenant un
 473   produit cartésien, sauf si c'est le seul moyen de calculer la
 474   requête (<tt>SELECT * FROM A, B</tt>).
 475 </p>
 476 </div>
 477
 478 <div class="sws-slide">
 479 <h1>Exemple (Plan 2 v1)</h1>
 480 <p>
 481 <span style='display:inline-block;
 482             margin-right:1em;
 483             vertical-align: top;
 484             background-image: url("example_plan.svg");
 485             background-repeat: no-repeat;
 486             background-position: 53%;
 487             border: 1px solid black;
 488             width:5cm;
 489             height:4cm;
 490             float:left;'>
 491  </span>
 492
 493 On choisi de faire d'abord une jointure entre R et B, sur
 494 l'attribut <tt>bid</tt> puis jointure du résultat intermédiaire
 495 sur <tt>sid</tt>.</p>
 496
 497 <p>On dispose <em>d'un index</em> sur <tt>B.bid</tt>. On effectue une
 498   <em>jointure itérative par index</em> : <tt> 1000 + 100 000 × 3 :
 499   301 000 E/S</tt> (2 pour le hash-index et 1 pour la lecture des
 500   données depuis l'index).
 501 </p>
 502 <p>La deuxième jointure peut être faite à la volée (jointure itérative
 503   par index sur <tt>S.sid</tt>) et la condition de sélection testée à
 504   la volée. Coût total 100 000 × 3 (pour chacun des enregistrement
 505   précédents, on paye un accès d'index + un accès à la ligne
 506   correspondante dans S).
 507 </p>
 508 <p>Coût total: <tt>601 000 E/S</tt> (les projections sont faites en <i>pipline</i> à la fin)</p>
 509 </div>
 510
 511 <div class="sws-slide">
 512 <h1>Exemple (Plan 2 v2)</h1>
 513 <p>
 514 <span style='display:inline-block;
 515             margin-right:1em;
 516             vertical-align: top;
 517             background-image: url("example_plan.svg");
 518             background-repeat: no-repeat;
 519             background-position: 53%;
 520             border: 1px solid black;
 521             width:5cm;
 522             height:4cm;
 523             float:left;'>
 524  </span>
 525
 526 On choisi de faire d'abord une jointure entre R et B, sur
 527 l'attribut <tt>bid</tt> puis jointure du résultat intermédiaire
 528 sur <tt>sid</tt>.</p>
 529
 530 <p>On n'utilise <em>pas l'index</em> sur <tt>B.bid</tt>. On effectue une
 531   <em>jointure itérative page à page</em> : <tt> 200 + 200 × 1000 :
 532   200 200 E/S</tt> . On a 100 000 résultats (car tous les B.bid
 533   sont présents dans la table R). Un enregistrement du
 534   résultat fait environ 40+20 = 60 octets donc 66 enregistrements par
 535   pages de 4000 octets donc 1515 pages de résultats.
 536 </p>
 537 <p>On applique la sélection sur S par un scan linéaire: <tt>500
 538   E/S</tt> et <tt>100 pages</tt> de résultats</p>
 539 <p> On fait une jointure page à page des deux résultats
 540  précédents : <tt>100 + 100 × 1515 = 100 615 E/S</tt>.
 541 </p>
 542 <p>Coût total: <tt>102 630 E/S</tt> (les projections sont faites en <i>pipline</i> à la fin)</p>
 543 </div>
 544
 545
 546
 547 <div class="sws-slide">
 548 <h1>Exemple (Plan 3)</h1>
 549 <p>
 550 <span style='display:inline-block;
 551             margin-right:1em;
 552             vertical-align: top;
 553             background-image: url("example_plan.svg");
 554             background-repeat: no-repeat;
 555             background-position: 103%;
 556             border: 1px solid black;
 557             width:5cm;
 558             height:4cm;
 559             float:left;'>
 560  </span>
 561
 562 On choisi de faire d'abord une jointure entre R et S, sur
 563 l'attribut <tt>sid</tt> puis jointure du résultat intermédiaire
 564 sur <tt>bid</tt>.</p>
 565 <p>On applique la sélection sur S par un scan linéaire: <tt>500
 566   E/S</tt> et <tt>100 pages</tt> de résultats</p>
 567
 568 <p> On effectue une <em>jointure itérative page à page</em> : <tt> 100 + 100 × 1000 :
 569   100 100 E/S</tt> . On a 100 000 résultats (car tous les S.sid
 570   sont présents dans la table R, <s>même après sélection</s> car
 571   distribution uniforme). Un enregistrement du
 572   résultat fait environ 40+50 = 90 octets donc 44 enregistrements par
 573   pages de 4000 octets donc 2272 pages de résultats.
 574 </p>
 575 <p> On fait une jointure page à page des du résultat
 576  précédent avec B : <tt>200 + 200 × 2272 = 454 600 E/S</tt>.
 577 </p>
 578 <p>Coût total : 555 200 E/S</p>
 579 </div>
 580 <div class="sws-slide">
 581 <h1>Exemple (conclusion)</h1>
 582
 583 <ul>
 584   <li>Utiliser l'index n'est pas toujours payant, surtout s'il est
 585     non-groupant, car on ajoute un facteur qui est le nombre de
 586     résultats, pas le nombre de pages</li>
 587   <li>On a fait certaines approximations « à la louche » (taille des
 588     enregistrements résultants d'une jointure, nombre des
 589     enregistrements résultants)</li>
 590   <li>On n'a pas considéré le fait que pousser les projections plus
 591     bas pour ne garder que les colonnes strictement nécessaires pouvait
 592     faire baisser la taille des tables intermédiaires
 593   </li>
 594 </ul>
 595
 596
 597
 598 </div>
 599 <div class="sws-slide">
 600 <h1>Requêtes imbriquées</h1>
 601 <code>
 602     SELECT … FROM … WHERE
 603      … e AND EXISTS  (SELECT … WHERE … FROM …)
 604 </code>
 605 <p>On optimise d'abord la requête la plus « interne »</p>
 606 <p>On optimise ensuite la requête englobante en utilisant prenant en
 607   compte le coût de la requête interne pour chaque « évaluation » du
 608   <tt>WHERE</tt>
 609 </p>
 610 </div>
 611 </body>
 612 </html>