bd/bd04.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 des opérateurs</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="bd03.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 4 : Optimisation des opérateurs</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><br/>
  53       <a>version mise à jour le 09/04/2015</a>
  54     </div>
  55
  56     <h1>Motivation</h1>
  57     <div class="sws-slide">
  58       <h1>Principe d'évaluation d'une requête</h1>
  59       <div style="padding-left:15pt;">
  60       <ol>
  61         <li><i>Parsing</i> de la requête</li>
  62         <li>Traduction en arbre
  63         d'opérateurs de l'algèbre
  64         relationnelle <span class="sws-onframe-1-3"><em>(&pi;,
  65         &sigma;, ⨝, … )</em></span></li>
  66         <li>Optimisation :
  67           <ol>
  68             <li>Génération de <em>plans
  69             d'évaluation</em> <span class="sws-onframe-2-3">(en
  70             réordonnant les <em> opérations élémentaires</em>)</span></li>
  71             <li>Estimation du <em>coût</em> de chacun des
  72             plans <span class="sws-onframe-3-3">(en fonction du <em>coût
  73             des opérations élémentaires</em>)</span></li>
  74             <li>Choix du plan le plus <em>efficace</em></li>
  75           </ol>
  76         </li>
  77         <li>Évaluation du plan choisi</li>
  78         <li>(Éventuellement mise à jour des statistiques)</li>
  79       </ol>
  80       <p>Avant de s'intéresser à l'évaluation complète d'une requête,
  81         on étudie l'évaluation des opérateurs et leur coût
  82         respectifs</p>
  83       </div>
  84     </div>
  85     <h1>Algorithmes de jointure</h1>
  86     <div class="sws-slide">
  87       <h1>Jointure naturelle sur une colonne</h1>
  88       <p>Considérons :</p><code>          SELECT *
  89           FROM people,role
  90           WHERE people.pid = role.pid;
  91 </code>
  92       <p>Opération <em>fondamentale</em> utilisée
  93       par <em>toutes</em> les applications BD.<br/>
  94         L'AR nous dit que <tt>R &join; S = &sigma;<sub>=</sub>(R x
  95       T)</tt>, mais c'est <s>très inefficace</s>, on veut optimiser ce cas!
  96       </p>
  97       <p>On suppose dans la suite M pages dans R,
  98         P<sub>R</sub> enregistrements/page, N pages dans S,
  99         P<sub>S</sub> enregistrements/page.
 100       </p>
 101       <p>On pose pour les exemples: M=1000, N=500, P<sub>R</sub>=120, P<sub>S</sub>=100</p>
 102       <p>L'attribut commun est <tt>a</tt>.</p>
 103       <p>Le coût est toujours le nombre d'E/S (en ignorant l'écriture
 104       du résultat)</p>
 105     </div>
 106     <div class="sws-slide">
 107       <h1>Jointure itérative simple</h1>
 108       <p>On effectue une double boucle imbriquée:</p>
 109 <code>
 110       for each record <em>r &in; R</em> do
 111          for each record <em>s &in; S</em> do
 112           if <em>r.a = s.a</em> then res += <em>r &join; s</em> #jointure élémentaire de
 113          done                            #2 enregistrements
 114       done
 115 </code>
 116    <p>Pour chaque <s>enregistrement</s> de la relation externe (R) on
 117    scanne entièrement la relation interne (S)</p>
 118    <p>Coût: <em>M + P<sub>R</sub> * M * N</em><br/>
 119       Exemple: 1000 + 120*1000*500 = 60 001 000 E/S!</p>
 120     </div>
 121     <div class="sws-slide">
 122       <h1>Jointure itérative page à page</h1>
 123       <p>On effectue une double boucle imbriquée:</p>
 124 <code>
 125       for each page <em>P &in; R</em> do
 126          for each page <em>Q &in; S</em> do
 127           res += <em>P &join; Q</em>  #jointure entre 2 pages
 128          done           # peut être faite de manière simple
 129       done
 130 </code>
 131    <p>Pour chaque <em>page</em> de la relation externe (R) on
 132    scanne entièrement la relation interne (S)</p>
 133    <p>Coût: <em>M + M * N</em><br/>
 134       Exemple: 1000 + 1000*500 = 501 000 E/S!<br/>
 135       Optimisation: mettre la relation la plus petite à
 136       l'extérieur:<br/>
 137       500 + 500*1000 = 500 500
 138 </p>
 139     </div>
 140     <div class="sws-slide">
 141       <h1>Jointure itérative avec index</h1>
 142       <p>On effectue une double boucle imbriquée:</p>
 143 <code>
 144       for each record <em>r &in; R</em> do
 145          for each record <em>s &in; S where r.a = s.a</em> do
 146          #l'index doit permettre un accès rapide à la colonne a
 147            res += <em>r &join; s</em>
 148          done
 149       done
 150 </code>
 151    <p>On exploite l'existence d'un index sur l'une des relation pour
 152    en faire la relation interne.</p>
 153    <p>Coût: <em>M + P<sub>R</sub> * M * (coût d'accès index + coût
 154       index &mapsto; données)</em><br/>
 155      Plusieurs variantes: B+-tree/Hash-index, groupant/non-groupant,…
 156    </p>
 157     </div>
 158     <div class="sws-slide">
 159       <h1>Jointure par bloc (avec pages bufferisées)</h1>
 160       <p>On exploite le <i>buffer</i> (de taille B+2 pages, B = 10) de la
 161       manière suivante:</p>
 162       <ul>
 163         <li> 1 page du <i>buffer</i> pour l'écriture du résultat</li>
 164         <li> 1 page du <i>buffer</i> pour la relation interne (S)</li>
 165         <li> B pages du <i>buffer</i> pour la relation externe</li>
 166       </ul>
 167 <code>
 168       for each block <em>b of size B &in; R</em> do
 169          for each page <em>Q &in; S </em> do
 170            res += <em>b &join; Q</em> #en utilisant la méthode simple
 171          done
 172       done
 173 </code>
 174    <p>Coût: <em>M + N * ⌈M/B⌉</em><br/>
 175      Exemple: 1000 + 500 * 1000/10 = 51 000<br/>
 176      Variante: blocs sur R et S
 177    </p>
 178
 179     </div>
 180     <div class="sws-slide">
 181       <h1>Jointure par tri-fusion 1/2</h1>
 182       <p>Idée: « l'intersection » de deux listes est aisée si les deux
 183       listes sont triées</p>
 184 <code>      <em>sort R on a as Rs</em>
 185       <em>sort S on a as Ss</em>
 186       r := Rs.next();  #On suppose R et S non vides
 187       s := Ss.next();  #Sinon jointure vide directement
 188       while Rs and Ss are not empty do
 189          while r.a != s.a do  <s>#avance jusqu'à trouver la même valeur</s>
 190            while <em>r.a &lt; s.a</em> do
 191             if Rs.hasNext() then r:= Rs.next() else finished
 192            done
 193            while <em>s.a &lt; r.a</em> do
 194             if Ss.hasNext() then s:= Ss.next() else finished
 195            done
 196          done
 197          val := r.a <s>#on prend la liste des enregistrements
 198                     #ayant la même valeur d'attribut de jointure</s>
 199          P, Q := empty pages
 200          while r.a = val do P += r; r:= Rs.next() done
 201          while s.a = val do Q += s; s:= Ss.next() done
 202          res += <em>P &join; Q</em>
 203       done
 204 </code>
 205     </div>
 206     <div class="sws-slide">
 207       <h1>Jointure par tri &amp; fusion 2/2</h1>
 208       <p>Coût: M·log<sub>2</sub> M + N·log<sub>2</sub> N + M + N<br/>
 209         Exemple: 1000* (1+log<sub>2</sub> 1000) + 500 *
 210         (1+log<sub>2</sub> 500) = 15492
 211       </p>
 212       <p>Le tri n'est pas toujours nécessaire:</p>
 213       <ul>
 214         <li>si on a un index de type B+-tree sur l'attribut de
 215         jointure (pour l'une des relations)</li>
 216         <li>si R ou S (ou les deux) sont déjà le résultat de tris
 217         (<tt>ORDER BY</tt>)</li>
 218       </ul>
 219     </div>
 220     <div class="sws-slide">
 221       <h1>Jointure par hachage</h1>
 222       <p>On choisit une fonction de hachage <tt>h</tt> et on
 223       partitionne R selon <tt>h(r.a)</tt> pour obtenir K partitions</p>
 224       <p>On
 225         partitionne S selon <tt>h(s.a)</tt> pour obtenir K
 226         partitions</p>
 227       <p style="text-align:center"><img style="width:60%"
 228       src="hash_join.svg"/></p>
 229       <p>K choisi en fonction de la taille du <i>buffer</i><br/>
 230       Coût: 2(M+N) + M+N (pourquoi ?)</p>
 231     </div>
 232     <div class="sws-slide">
 233       <h1>Jointures généralisées</h1>
 234       <ul>
 235         <li>Égalité sur plusieurs attributs (<tt>R.a = S.a AND R.b =
 236             S.b</tt>) :
 237           <ul>
 238             <li>Jointure itérative par index: on peut créer un index
 239               pour S sur (a,b) ou utiliser des indexes existants sur l'un
 240               ou l'autre</li>
 241             <li>On peut aussi utiliser jointure par tri-fusion et
 242               hachage en utilisant (a,b) comme clé de tri/hachage</li>
 243           </ul>
 244         </li>
 245         <li>conditions d'inégalité:
 246           <ul>
 247             <li> Pour les jointures par index, il faut un arbre
 248               B+ <em>groupant</em> (sinon sur-coût pour aller chercher les
 249               données)
 250             </li>
 251             <li>Jointure par tri-fusion et hachage impossible</li>
 252             <li>Jointure itérative par bloc est la meilleure option en général</li>
 253           </ul>
 254         </li>
 255       </ul>
 256     </div>
 257     <h1>Autres opérateurs</h1>
 258     <div class="sws-slide">
 259       <h1>Sélectivité</h1>
 260       <p><em>Taux de sélectivité</em> d'une condition &phi; (ou d'une
 261       requête) pour une relation donnée:</p>
 262       <p style="text-align:center"> <span style="border-bottom-style: solid;
 263       border-width: 1pt ; border-color:black;"><tt># d'enregistrement
 264       sélectionnés</tt></span><br/>
 265         <tt>#d'enregistrements</tt></p>
 266       <p>Le choix de certains algorithmes dépend de la
 267       sélectivité </p>
 268       <p>On ne connaît la « vraie » valeur de la
 269       sélectivité <em>qu'après</em> avoir évalué la requête</p>
 270       <p>On utilise des statistiques sur les relations pour tenter une
 271       <em>approximation</em> du taux de sélectivité</p>
 272     </div>
 273     <div class="sws-slide">
 274       <h1>Statistiques sur les relations </h1>
 275       <p>Le SGBD conserve, entre autres, les statistiques
 276       suivantes pour chaque relations R:</p>
 277       <ul><li>Nombre d'enregistrements (<tt>N</tt>), taille d'un
 278       enregistrement, nombre d'attributs/page (<tt>P</tt>)</li>
 279         <li>Nombre de pages de la relation (les pages ne sont pas
 280         toutes remplies de manière optimale)</li>
 281         <li><tt>V(a)</tt> : nombre de valeurs distinctes pour l'attribut <tt>a</tt>
 282         (dans la relation R)</li>
 283         <li>Estimation de sélectivité pour l'attribut <tt>a</tt>: <tt>V(a)/N</tt></li>
 284         <li>Profondeur pour les arbres B+</li>
 285         <li>Nombre de page pour les feuilles d'un arbre B+</li>
 286         <li>Nombre de valeurs distinctes pour la clé de recherche d'un index</li>
 287       </ul>
 288     </div>
 289     <div class="sws-slide">
 290       <h1>Sélection</h1>
 291       <p>Sélection simple, égalité avec une constante : Scan ou
 292       Index (si groupant)</p>
 293       <p>Sélection simple avec index non groupant : Index + <em>tri des
 294       adresses de pages</em>, parcours ordonné. Très efficace si
 295       l'ensemble des adresses à trier tiens en mémoire</p>
 296       <p>Sélection généralisés, deux approches:</p>
 297       <ol>
 298         <li>On choisit une sous-condition (qui concerne le moins de
 299         pages = la plus sélective) et on applique les autres
 300         sous-conditions au résultat intermédiaire</li>
 301         <li>Si on a deux sous-conditions « <tt>AND</tt> » avec 2 indexes (types 2 ou 3)
 302         séparés, calcul des ensembles de <tt>rid</tt> et intersection
 303         des résultats. On applique ensuite les autres critères.
 304         </li>
 305       </ol>
 306     </div>
 307     <div class="sws-slide">
 308       <h1>Résultat trié/élimination des doublons</h1>
 309       <p>Plusieurs techniques :</p>
 310       <ul>
 311         <li>Utilisation d'un index (type B+-tree) si groupant ou si
 312         coût d'accès au données « raisonnable » (résultat dans l'index
 313         ou peu de résultats + accès aux données) </li>
 314         <li>Utilisation d'un tri explicite après calcul des résultats
 315           (+ élimination des doublons durant la phase de tri)
 316         </li>
 317       </ul>
 318     </div>
 319     <div class="sws-slide">
 320       <h1>Projection</h1>
 321       <p>On parle ici de la projection, <em>&pi;</em> de l'algèbre
 322       relationnelle, donc avec élimination des doublons : </p>
 323 <code>              SELECT <em>DISTINCT</em> a,b FROM t </code>
 324
 325       <ul>
 326         <li>Si index sur <tt>(a,b)</tt> disponible, utilisation
 327         directe de l'index</li>
 328         <li>Sinon tri et projection durant la phase de tri</li>
 329         <li>Double partitionnement par hachage</li>
 330       </ul>
 331     </div>
 332     <div class="sws-slide">
 333       <h1>Double partitionnement</h1>
 334       <p>Repose sur l'utilisation de <em>deux</em> fonctions de hachage
 335       <tt>h</tt> et <tt>g</tt> <s>distinctes</s></p>
 336       <ol>
 337         <li>On partitionne R en K partitions en
 338         utilisant <tt>h</tt></li>
 339         <li>En suite pour chaque partition entre 1 et K, on crée une
 340         table de hachage en mémoire (avec <tt>g</tt> comme fonction)
 341           pour pour éliminer les doublons de la partition</li>
 342       </ol>
 343       <p style="text-align:center;"><img src="hash_partition.svg"/></p>
 344       <p>Permet d'effectuer « <tt>DISTINCT</tt>» sans tri! </p>
 345     </div>
 346     <div class="sws-slide">
 347       <h1>Opérations ensemblistes</h1>
 348       <ul>
 349         <li>Intersection et produit cartésien: cas dégénérés de
 350         jointure (comment?)</li>
 351         <li><tt>UNION DISTINCT</tt> et <tt>EXCEPT</tt> sont
 352         similaires. 2 approches:
 353           <ol> <li>Par tri. On tri les deux relations sur tous les
 354           attributs et on fusionne en éliminant les doublons. Résultat
 355           trié</li>
 356             <li>Par hachage. Technique du double partitionnement. On
 357             partitionne R et S avec <tt>h</tt>. Pour chaque partition
 358             de S et R, on ajoute les éléments dans une table H, en
 359             éliminant les doublons</li>
 360             </ol>
 361         </li>
 362       </ul>
 363     </div>
 364     <div class="sws-slide">
 365       <h1>Opérations d'agrégat</h1>
 366       <ul>
 367         <li>Sans <tt>GROUP BY</tt>:
 368           <ul><li>En général, il faut faire un scan de la
 369           relation</li>
 370             <li>Si les attributs agrégés sont dans un index, on peut
 371             faire un scan d'index uniquement (en espérant que l'index
 372               est plus petit)</li></ul>
 373         </li>
 374         <li>Avec <tt>GROUP BY</tt>: identique au cas sans <tt>GROUP
 375         BY</tt> mais tri préalable pour déterminer les groupes, et
 376         scan « groupe par groupe » pour calculer la fonction
 377         d'agrégat</li>
 378       </ul>
 379
 380     </div>
 381     <div class="sws-slide">
 382       <h1>Conclusion</h1>
 383       <p>L'algèbre relationnelle <em>est simple</em> (quelques opérateurs pour
 384       exprimer l'ensemble des requêtes)</p>
 385       <p>Chaque opérateur peut être réalisé de <em>plusieurs manières</em>
 386       différentes, avec <em>différents compromis</em></p>
 387       <p>Tout cela est encore complexifié quand on considère les
 388         <em>compositions d'opérateurs</em> (prochain cours)</p>
 389       <p>Tout est encore plus complexifié si on considère que le SGBD
 390         gère plusieurs requêtes en parallèle (hors programme)</p>
 391       <p>En pratique, <em>une part importante</em> du moteur de
 392       requête des SGBD est l'implantation <em>d'heuristiques</em> pour
 393       faire les meilleurs choix (ou plutôt, les moins pires).</p>
 394     </div>
 395   </body>
 396 </html>