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"
5 <!ENTITY in "<small style='font-size:small'>∈</small>">
6 <!ENTITY notin "<small style='font-size:small'>∉</small>">
11 <html xmlns="http://www.w3.org/1999/xhtml" >
13 <title>Optimisation de requêtes</title>
15 <meta http-equiv="Content-Type"
16 content="text/html; charset=utf-8" />
17 <meta name="copyright"
18 content="Copyright © 2013 Kim Nguyễn" />
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>
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" />
31 <!-- Customize some templates and initialize -->
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;
38 //Ensures that we load SWS at the very end, after MathJax has
41 $(window).load(SWS.Presentation.init);
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 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>
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;">
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>(π,
64 σ, ⨝, … )</em></span></li>
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>
76 <li>Évaluation du plan choisi</li>
77 <li>(Éventuellement mise à jour des statistiques)</li>
79 <p>On va voir comment optimiser l'évaluation d'une requête</p>
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);
89 <li><em>Sailors</em>: 50 octets/enr., 80 enr/page, 500
91 <li><em>Reserves</em>: 40 octets/enr., 100 enr/page, 1000
93 <li><em>Boats</em>: non utilisé dans la suite</li>
96 <div class="sws-slide">
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.
103 <li>Pour une requête donnée, quels plans doit-on considérer
105 <li>Comment peut on estimer le coût total d'un plan</li>
107 <p>Idéalement, on veut trouver le meilleur plan. En pratique, on
108 choisira le moins pire!</p>
110 <div class="sws-slide">
114 FROM Reserves R, Sailors S
115 WHERE R.sid = S.sid AND bid = 100 AND rating > 5
117 <p><img class="sws-pause" src="simple_plan.svg" width="50%"/></p>
119 <li class="sws-pause">Cout: 500+500*1000 E/S (pourquoi ?)</li>
120 <li> Plusieurs occasions manquées : pas d'utilisation d'index, on
121 aurait pu pousser la selection 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>
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 selection <tt>AND</tt>). On suppose qu'on a 100
131 bateaux, 10 notes et distributions uniformes. </p>
133 <li>Scan Reserves (1000 E/S) et écriture de 10 pages dans T1</li>
134 <li>Scan Sailors (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 sid, T2
138 uniquement sid et sname (cout <tt><</tt> 2000 E/S)</li>
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>
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
154 <li>Coût total: 1000 * 1.2 + 10.2 = 1210 E/S</li>
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>
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>
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>
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.
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
192 <p>Les catalogues sont mis à jours périodiquement mais pas à chaque
193 mise à jours, pour ne pas impacter les performances.</p>
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>
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>
207 <p>On fait la supposition que les expressions sont indépendantes.<br/>
208 Exemples de facteurs de réduction:
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 > valeur</tt> : <tt> (Max(I)-valeur)/(Max(I) - Min(I))</tt>
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>
226 <li> <tt>σ<sub>c<sub>1</sub>∧…∧c<sub>n</sub></sub>(R)
228 σ<sub>c<sub>1</sub></sub>(… (σ<sub>c<sub>n</sub></sub>(R)))</tt> [Cascade]
231 σ<sub>c<sub>1</sub></sub>(σ<sub>c<sub>2</sub></sub>(R))
233 σ<sub>c<sub>2</sub></sub>(σ<sub>c<sub>1</sub></sub>(R))
234 </tt> [Commutativité]
241 <li> <tt>π<sub>a<sub>1</sub>, …, a<sub>n</sub></sub>(
242 …(π<sub>z<sub>1</sub>, …, z<sub>m</sub></sub>(R))
244 π<sub>a<sub>1</sub>, …, a<sub>n</sub></sub>(R)</tt> [Cascade]
251 <li> <tt>R &join; (S &join; T) ≡ (R &join; S) &join; T</tt> [Associativité]
253 <li> <tt> (R &join; S) ≡ (S &join; R) </tt> [Commutativité]
259 <div class="sws-slide">
260 <h1>Autres équivalences</h1>
263 Une projection commute avec une selection qui utilise uniquement
264 les attributs de la projection</li>
265 <li>Une selection entre des attributs de deux arguments d'un
266 produit cartésien peut être converti en jointure:
267 <tt> σ<sub>φ</sub> (R × S) ≡ R &join;<sub>φ</sub> S</tt>
269 <li>Une selection sur des attributs de <tt>R</tt> commute avec la
270 jointure <tt>R&join;S</tt> (c'est à dire: <tt>σ(R&join;S) ≡ σ(R)&join;S </tt>)
272 <li>Règle similaire pour pousser les projections sous jointure</li>
275 <h1>Énumération de plans</h1>
276 <div class="sws-slide">
277 <h1>Modèle de calcul</h1>
279 Les SGBD modernes utilisent un modèle de
280 calcul <em><i>pull</i></em>. L'opérateur le plus « haut » (racine)
281 dans l'arbre de requête « tire » (<i>pull</i>) le résultat de ses
282 sous-arbres (similaire à l'appel de <i>next</i> sur les iterateurs
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
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 selections, projections et aggrégats
294 (<tt>max</tt>, <tt>count</tt>, <tt>average</tt>, …)</p>
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>
299 <li>Les opérateurs restants sont calculé <em>à la volée</em> (en
300 pipelinant les opérations)
304 <div class="sws-slide">
305 <h1>Estimation du coût pour les plans mono-relation</h1>
307 <li> Si on a un index I pour une selection 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 selection <tt>σ<sub>1</sub></tt>, …, <tt>σ<sub>n</sub></tt> :<br/>
312 <tt><s>(NPages(I) + NPages(R))* RF(σ<sub>1</sub>) * … * RF(σ<sub>n</sub>) </s></tt>
314 <li> Si on a un index I non-groupant pour plusieurs
315 selection <tt>σ<sub>1</sub></tt>, …, <tt>σ<sub>n</sub></tt> :<br/>
316 <tt><s>(NPages(I) + <u>NEnr</u>(R))* RF(σ<sub>1</sub>) * … * RF(σ<sub>n</sub>) </s></tt>
318 <li>Scan séquentiel à <tt>R</tt>: <tt><s>NPages(R)</s></tt></li>
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> π<sub>sid</sub>(σ<sub>rating = 8</sub>(S))</code>
326 <li>Avec un index sur <tt>rating</tt>:
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>
336 <li>Scan : on récupère toutes les pages et on filtre: <tt>500</tt> E/S</li>
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>
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 selections 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>.
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> »
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 sur d'avoir la solution optimale!</p>
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>
368 <li>1<sup>ère</sup> passe: on trouve la meilleure manière de calculer
369 chaque relation individuellement
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
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)
378 <p>Comment sélectionner les « meilleurs » 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
383 <div class="sws-slide">
384 <h1>Énumération des plans gauches en profondeur 2/2</h1>
385 <p>Exemple: si on a la possibilité de faire une jointure itérative de
386 cout 1000, une jointure par hash de coût 500 et une jointure
387 sort-merge de coût 1500, on garde les version hash
388 et <s>sort-merge</s> (car il est possible que le fait d'avoir les
389 résultats déjà trié rendent le coût moindre à l'étape suivante)
391 <p>On garde les <tt>ORDER BY</tt>, <tt>GROUP BY</tt>, aggrégats, …
392 pour la fin, en profitant si possible des ordres des résultats faits
393 par les jointures précédentes</p>
394 <p>On évite tant que possible de faire des produits cartésiens (en
395 poussant les selections par exemple)</p>
397 <div class="sws-slide">
398 <h1>Requêtes imbriquées</h1>
400 SELECT … FROM … WHERE
401 … e AND EXISTS (SELECT … WHERE … FROM …)
403 <p>On optimise d'abord la requête la plus « interne »</p>
404 <p>On optimise ensuite la requête englobante en utilisant prenant en
405 compte le coût de la requête interne pour chaque « évaluation » du