+<?xml version="1.0" encoding="utf-8" ?>
+<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Strict//EN"
+ "http://www.w3.org/TR/xhtml1/DTD/xhtml1-strict.dtd"
+[
+ <!ENTITY in "<small style='font-size:small'>∈</small>">
+ <!ENTITY notin "<small style='font-size:small'>∉</small>">
+ <!ENTITY mapsto "↦">
+ <!ENTITY join "⨝">
+]
+ >
+<html xmlns="http://www.w3.org/1999/xhtml" >
+ <head>
+ <title>Optimisation de requêtes</title>
+
+ <meta http-equiv="Content-Type"
+ content="text/html; charset=utf-8" />
+ <meta name="copyright"
+ content="Copyright © 2013 Kim Nguyễn" />
+
+ <!-- Load jQuery -->
+ <script src="../jquery-2.0.3.min.js" type="text/javascript" ></script>
+ <script src="../libs/raphael-min.js" type="text/javascript" ></script>
+ <!-- Load the library -->
+ <script src="../simpleWebSlides.js" type="text/javascript" ></script>
+
+ <link rel="stylesheet" href="../simpleWebSlides.css" type="text/css" media="all" />
+ <!-- Load a custom Theme, the class-element marks this style-sheet
+ a "theme" that can be swtiched dynamicaly -->
+ <link class="sws-theme" rel="stylesheet" title="U-Psud style" href="../themes/uPsud.css" type="text/css" />
+
+ <!-- Customize some templates and initialize -->
+
+ <script type="text/javascript">
+ SWS.Config['sws-slide-change'] = SWS.Effects.slideChangeFadeOutIn;
+ SWS.Config['sws-object-deactivate'] = SWS.Effects.objectDeactivateFadeOut;
+ SWS.Config['sws-object-activate'] = SWS.Effects.objectActivateFadeIn;
+
+ //Ensures that we load SWS at the very end, after MathJax has
+ //been initialized
+
+ $(window).load(SWS.Presentation.init);
+ </script>
+ </head>
+ <body>
+ <a href="bd03.xhtml" class="sws-previous"/>
+ <div class="sws-slide sws-cover sws-option-nofooter">
+ <h1>Bases de données</h1>
+ <h3>Polytech Paris-Sud</h3>
+ <h3>Apprentis 4<sup>ème</sup> année</h3>
+ <h1>Cours 5 : Optimisation des requêtes</h1>
+ <a href="mailto:kn@lri.fr">kn@lri.fr</a><br/>
+ <a href="http://www.lri.fr/~kn/">http://www.lri.fr/~kn</a>
+ </div>
+
+ <h1>Motivation et introduction</h1>
+ <div class="sws-slide">
+ <h1>Principe d'évaluation d'une requête</h1>
+ <div style="padding-left:15pt;">
+ <ol>
+ <li><i>Parsing</i> de la requête</li>
+ <li>Traduction en arbre
+ d'opérateurs de l'algèbre
+ relationnelle <span class="sws-onframe-1-3"><em>(π,
+ σ, ⨝, … )</em></span></li>
+ <li>Optimisation :
+ <ol>
+ <li>Génération de <em>plans
+ d'évaluation</em> <span class="sws-onframe-2-3">(en
+ réordonnant les <em> opérations élémentaires</em>)</span></li>
+ <li>Estimation du <em>coût</em> de chacun des
+ plans <span class="sws-onframe-3-3">(en fonction du <em>coût
+ des opérations élémentaires</em>)</span></li>
+ <li>Choix du plan le plus <em>efficace</em></li>
+ </ol>
+ </li>
+ <li>Évaluation du plan choisi</li>
+ <li>(Éventuellement mise à jour des statistiques)</li>
+ </ol>
+ <p>On va voir comment optimiser l'évaluation d'une requête</p>
+ </div>
+ </div>
+ <div class="sws-slide">
+ <h1>Exemple pour la suite du cours</h1>
+<code> Sailors(<u>mid: integer</u>, sname: string, rating: integer, age: real);
+ Reserves(<u>sid: integer, bid: integer, day: date</u>, rname: string);
+ Boats(<u>bid: integer</u>, bname: string, capacity: integer);
+</code>
+<ul>
+ <li><em>Sailors</em>: 50 octets/enr., 80 enr/page, 500
+ 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>
+</ul>
+ </div>
+ <div class="sws-slide">
+ <h1>Généralités</h1>
+ <p>Un <em>plan d'exécution</em> de requête est un <em>arbre</em>
+ dont les noeuds sont des opérateurs de l'algèbre relationnelle
+ annotés avec un algorithme particulier.
+ </p>
+ <ul>
+ <li>Pour une requête donnée, quels plans doit-on considérer
+ ?</li>
+ <li>Comment peut on estimer le coût total d'un plan</li>
+ </ul>
+ <p>Idéalement, on veut trouver le meilleur plan. En pratique, on
+ choisira le moins pire!</p>
+ </div>
+ <div class="sws-slide">
+ <h1>Exemple</h1>
+<code>
+ SELECT S.sname
+ FROM Reserves R, Sailors S
+ WHERE R.sid = S.sid AND bid = 100 AND rating > 5
+</code>
+<p><img class="sws-pause" src="simple_plan.svg" width="50%"/></p>
+<ul>
+ <li class="sws-pause">Cout: 500+500*1000 E/S (pourquoi ?)</li>
+ <li> Plusieurs occasions manquées : pas d'utilisation d'index, on
+ aurait pu pousser la selection sous la jointure, …</li>
+ <li> Notre but est de trouver des plans d'exécution plus efficaces
+ qui calculent le même résultat</li>
+</ul>
+ </div>
+ <div class="sws-slide">
+ <h1>Plan alternatif 1 (sans index)</h1>
+<p><img class="sws-pause" src="simple_plan1.svg" width="50%"/></p>
+<p class="sws-pause">On pousse la sélection sous la jointure (car
+ selection <tt>AND</tt>). On suppose qu'on a 100
+ bateaux, 10 notes et distributions uniformes. </p>
+<ul>
+ <li>Scan Reserves (1000 E/S) et écriture de 10 pages dans T1</li>
+ <li>Scan Sailors (500 E/S) et écriture de 250 pages dans T2</li>
+ <li>Tri T1 (3*10 E/S), Tri T2 (8*250 E/S), fusion (10+250 E/S)</li>
+ <li>Total: <em>4050 E/S</em></li>
+ <li>Si on pousse la projection, T1 ne contient que sid, T2
+ uniquement sid et sname (cout <tt><</tt> 2000 E/S)</li>
+</ul>
+ </div>
+ <div class="sws-slide">
+ <h1>Plan alternatif 2 (avec index)</h1>
+<p><img class="sws-pause" src="simple_plan2.svg" width="50%"/></p>
+<p class="sws-pause">On suppose un hash-index groupant sur <tt>bid</tt>
+</p>
+<ul>
+ <li>Accès au premier enregistrement <tt>bid=100</tt> 1.2 E/S</li>
+ <li>Accès aux suivants: 9 E/S</li>
+ <li><tt>sid</tt> est une clé pour Sailors. On a un hash-index dessus
+ (forcément non-groupant)</li>
+ <li>Pour chacun des 10 * 100 enr. tels que <tt>bid=100</tt> on
+ cherche l'enregistrement de Sailors avec le même <tt>sid</tt> (1.2
+ E/S/enr)</li>
+ <li>Coût total: 1000 * 1.2 + 10.2 = 1210 E/S</li>
+</ul>
+ </div>
+<div class="sws-slide">
+<h1>Algorithme général de choix de plan</h1>
+<ul><li>Cas mono-relation (une seule table dans le <tt>FROM</tt>):
+ <ol><li>On énumère tous les plans (en tenant compte des
+ équivalences de l'algèbre relationnelle)</li>
+ <li>On calcule le coût de chaque plan</li>
+ <li>On choisit le plan de moindre coût</li>
+ </ol>
+ </li>
+<li>Cas multi-relations (plusieurs tables dans le <tt>FROM</tt>):
+ <ol><li>Trop de plan pour les énumérer tous, on choisit des arbres
+ ayant une certaine forme </li>
+ <li>On calcule le coût de chaque plan</li>
+ <li>On choisit le plan de moindre coût</li>
+ </ol>
+</li>
+ <li>On sait (cours 4) estimer le coût d'un opérateur en fonction de
+ la taille de l'entrée. On va enchaîner les opérateurs donc il faut
+ estimer <em>la taille du résultat</em> pour calculer
+ le <em>coût</em> de l'opérateur suivant!</li>
+</ul>
+</div>
+<h1>Estimation de coût</h1>
+<div class="sws-slide">
+<h1>Statistiques et catalogues</h1>
+<p>On a besoin d'informations numériques sur les relations et les
+ indexes. Un <em>catalogue</em> contient en général:</p>
+<ul><li>Le nombre d'enregistrements (<tt><s>NEnr</s></tt>) et le
+ nombre de pages (<tt><s>NPages</s></tt>) de la relation.
+ </li>
+ <li>Le nombre de clés distinctes (<tt><s>NClés</s></tt>) pour les
+ indexes ainsi que leur taille en pages</li>
+ <li>La hauteur ainsi que les clés min/max dans l'index, pour les
+ arbres</li>
+</ul>
+<p>Les catalogues sont mis à jours périodiquement mais pas à chaque
+ mise à jours, pour ne pas impacter les performances.</p>
+</div>
+<div class="sws-slide">
+<h1>Estimation du nombre de résultats et facteur de réduction</h1>
+<p>On considère une requête de la forme:</p>
+<code> SELECT <i>attributs</i> FROM <i>tables</i> WHERE <em>e<sub>1</sub></em> AND … AND <em>e<sub>n</sub></em>
+</code>
+<ul><li>La taille maximale <tt>TMax</tt> du résultat est le produit des tailles des
+ tables se trouvant dans le <tt>FROM</tt></li>
+<li>Le facteur de réduction de chaque expression <tt><em>e</em></tt>
+ caractérise l'impact de ce terme sur la taille du résultat</li>
+<li>La taille finale du résultat est approximée par: <tt>TMax *
+ RF<sub>1</sub> * … * RF<sub>n</sub></tt></li>
+</ul>
+<p>On fait la supposition que les expressions sont indépendantes.<br/>
+Exemples de facteurs de réduction:
+</p>
+<ul><li> <tt>att = valeur</tt> : <tt>1 /
+ NClés</tt> si <tt>att</tt> este une clé pour un index I</li>
+<li><tt>att<sub>1</sub> = att<sub>2</sub></tt> : <tt> 1/Max(NClé(I1),
+ NClé(I2))</tt> (avec <tt>att<sub>i</sub></tt> une clé
+ de <tt>Ii</tt>) </li>
+<li><tt>att > valeur</tt> : <tt> (Max(I)-valeur)/(Max(I) - Min(I))</tt>
+</li>
+</ul>
+ </div>
+<div class="sws-slide">
+ <h1>Équivalences de l'algèbre relationnelle</h1>
+ <p>Permet de réordonner les jointures et de « pousser » les sélections
+ et les projections sous les jointures</p>
+ <ul>
+ <li>Sélections :
+ <ul>
+ <li> <tt>σ<sub>c<sub>1</sub>∧…∧c<sub>n</sub></sub>(R)
+ ≡
+ σ<sub>c<sub>1</sub></sub>(… (σ<sub>c<sub>n</sub></sub>(R)))</tt> [Cascade]
+ </li>
+ <li> <tt>
+ σ<sub>c<sub>1</sub></sub>(σ<sub>c<sub>2</sub></sub>(R))
+ ≡
+ σ<sub>c<sub>2</sub></sub>(σ<sub>c<sub>1</sub></sub>(R))
+ </tt> [Commutativité]
+ </li>
+
+ </ul>
+ </li>
+ <li>Projections :
+ <ul>
+ <li> <tt>π<sub>a<sub>1</sub>, …, a<sub>n</sub></sub>(
+ …(π<sub>z<sub>1</sub>, …, z<sub>m</sub></sub>(R))
+ ≡
+ π<sub>a<sub>1</sub>, …, a<sub>n</sub></sub>(R)</tt> [Cascade]
+ </li>
+
+ </ul>
+ </li>
+ <li>Jointures :
+ <ul>
+ <li> <tt>R &join; (S &join; T) ≡ (R &join; S) &join; T</tt> [Associativité]
+ </li>
+ <li> <tt> (R &join; S) ≡ (S &join; R) </tt> [Commutativité]
+ </li>
+ </ul>
+ </li>
+ </ul>
+</div>
+<div class="sws-slide">
+ <h1>Autres équivalences</h1>
+ <ul>
+ <li>
+Une projection commute avec une selection qui utilise uniquement
+ les attributs de la projection</li>
+ <li>Une selection entre des attributs de deux arguments d'un
+ produit cartésien peut être converti en jointure:
+ <tt> σ<sub>φ</sub> (R × S) ≡ R &join;<sub>φ</sub> S</tt>
+ </li>
+ <li>Une selection sur des attributs de <tt>R</tt> commute avec la
+ jointure <tt>R&join;S</tt> (c'est à dire: <tt>σ(R&join;S) ≡ σ(R)&join;S </tt>)
+ </li>
+ <li>Règle similaire pour pousser les projections sous jointure</li>
+ </ul>
+</div>
+<h1>Énumération de plans</h1>
+<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
+ 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 «
+ <em>bloquent</em> » le <i>pipeline</i> (en particulier les tris et
+ aggrégats).
+</p>
+
+</div>
+<div class="sws-slide">
+<h1>Cas mono-relation</h1>
+<p>Dans le cas mono-relation (i.e. sans jointure), la requête est
+ composée forcément de selections, projections et aggrégats
+ (<tt>max</tt>, <tt>count</tt>, <tt>average</tt>, …)</p>
+<ol>
+ <li>Pour chaque sous-terme, on considère tous les accès possibles
+ (scan, utilisation de l'index, …) et on prend le moins coûteux</li>
+
+<li>Les opérateurs restants sont calculé <em>à la volée</em> (en
+ pipelinant les opérations)
+</li>
+</ol>
+</div>
+<div class="sws-slide">
+<h1>Estimation du coût pour les plans mono-relation</h1>
+<ul>
+<li> Si on a un index I pour une selection sur clé primaire :
+ <tt><s>Hauteur(I) + 1</s></tt> pour un arbre B+, <tt><s>1.2</s></tt>
+ pour un hash-index</li>
+<li> Si on a un index I groupant pour plusieurs
+ selection <tt>σ<sub>1</sub></tt>, …, <tt>σ<sub>n</sub></tt> :<br/>
+ <tt><s>(NPages(I) + NPages(R))* RF(σ<sub>1</sub>) * … * RF(σ<sub>n</sub>) </s></tt>
+</li>
+<li> Si on a un index I non-groupant pour plusieurs
+ selection <tt>σ<sub>1</sub></tt>, …, <tt>σ<sub>n</sub></tt> :<br/>
+ <tt><s>(NPages(I) + <u>NEnr</u>(R))* RF(σ<sub>1</sub>) * … * RF(σ<sub>n</sub>) </s></tt>
+</li>
+<li>Scan séquentiel à <tt>R</tt>: <tt><s>NPages(R)</s></tt></li>
+</ul>
+</div>
+<div class="sws-slide">
+<h1>Exemple de calcul de coût</h1>
+<code> SELECT S.sid FROM Sailors S WHERE S.rating = 8; </code>
+<code> π<sub>sid</sub>(σ<sub>rating = 8</sub>(R))</code>
+<ul>
+ <li>Avec un index sur <tt>rating</tt>:
+ <ul>
+ <li>Groupant: <tt>1/NClés(I) * (NPages(I) +
+ NPages(R))</tt>. Avec des valeurs numériques: <tt> 1/10 *
+ (50+500) = 55 E/S</tt></li>
+ <li>Non-groupant: <tt>1/NClés(I) * (NPages(I) +
+ NEnr(R))</tt>. Avec des valeurs numériques: <tt> 1/10 *
+ (50+40000) = 4005 E/S</tt></li>
+ </ul>
+ </li>
+ <li>Scan : on récupère toutes les pages et on filtre: <tt>500</tt> E/S</li>
+</ul>
+<p><em>Note</em>: Une fois que l'on a sélectionné un enregistrement,
+ la projection est « gratuite » (en terme d'E/S) car le résultat n'a
+ pas à être sauvé dans une table temporaire</p>
+</div>
+<div class="sws-slide">
+ <h1>Requêtes multi-relations</h1>
+<ul><li>Les choix vont être guidé par les <em>jointures</em></li>
+ <li>Si on considère uniquement <tt>n</tt> jointures (pas de projections ni
+ de selections dans le plan de requête). Le nombre de plans possible
+ est le nombre d'arbre binaires ayant <tt>n</tt> noeuds internes
+ (exponentiel en <tt>n</tt>, exactement: nombre de Catalan
+ d'indice <tt>n</tt>). <s>Beaucoup trop pour les énumérer tous</s>.
+ </li>
+<li>On se restreint aux <em>arbres gauches en profondeur</em> qui
+ permettent d'énumérer tous les plans complètement
+ « <i>pipelinable</i> »
+ </li>
+</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>
+</div>
+<div class="sws-slide">
+<h1>Énumération des plans gauches en profondeur 1/2</h1>
+<p>Toujours exponentiel (mais moins)</p>
+<p>Tous les arbres différent maintenant dans l'ordre dans lequel on
+ fait les jointures, la méthode d'accès pour chaque relation et les
+ algorithmes de jointure utilisés</p>
+<p>On applique l'heuristique suivante:</p>
+<ol>
+<li>1<sup>ère</sup> passe: on trouve la meilleure manière de calculer
+ chaque relation individuellement
+</li>
+<li>2<sup>ème</sup> passe: on trouve la meilleure manière de joindre
+ deux à deux les résultats de la passe 1
+</li>
+<li>n<sup>ème</sup> passe: on trouve la meilleure manière de joindre
+ 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
+</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>
+<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>
+</div>
+<div class="sws-slide">
+<h1>Requêtes imbriquées</h1>
+<code>
+ SELECT … FROM … WHERE
+ … e AND EXISTS (SELECT … WHERE … FROM …)
+</code>
+<p>On optimise d'abord la requête la plus « interne »</p>
+<p>On optimise ensuite la requête englobante en utilisant prenant en
+ compte le coût de la requête interne pour chaque « évaluation » du
+ <tt>WHERE</tt>
+</p>
+</div>
+</body>
+</html>