</script>
</head>
<body>
- <a href="bd03.xhtml" class="sws-previous"/>
+ <a href="bd04.xhtml" class="sws-previous"/>
<div class="sws-slide sws-cover sws-option-nofooter">
<h1>Bases de données</h1>
<h3>Polytech Paris-Sud</h3>
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>
+ <li><em>Boats</em>: 20 octets/enr., 200 enr/page, 200 pages</li>
</ul>
</div>
<div class="sws-slide">
annotés avec un algorithme particulier.
</p>
<ul>
- <li>Pour une requête donnée, quels plans doit-on considérer
+ <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>
</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 class="sws-pause">Coût: 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>
+ aurait pu pousser la sélection 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>
<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
+ sélection <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>Scan <tt>Reserves</tt> (1000 E/S) et écriture de 10 pages dans T1</li>
+ <li>Scan <tt>Sailors</tt> (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>
+ <li>Si on pousse la projection, T1 ne contient que <tt>sid</tt>, T2
+ uniquement <tt>sid</tt> et <tt>sname</tt> (cout <tt><</tt> 2000 E/S)</li>
</ul>
</div>
<div class="sws-slide">
<h1>Autres équivalences</h1>
<ul>
<li>
-Une projection commute avec une selection qui utilise uniquement
+Une projection commute avec une sélection qui utilise uniquement
les attributs de la projection</li>
- <li>Une selection entre des attributs de deux arguments d'un
+ <li>Une sélection 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
+ <li>Une sélection 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>
<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
+ 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 itérateurs
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).
+ agré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
+ composée forcément de sélections, projections et agré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
<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 :
+<li> Si on a un index I pour une sélection 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/>
+ sélection <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/>
+ sélection <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>
<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
+ de sélections 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>.
</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>
+ recherche, on n'est pas sûr d'avoir la solution optimale!</p>
</div>
<div class="sws-slide">
<h1>Énumération des plans gauches en profondeur 1/2</h1>
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
+<p>Comment sélectionner les « meilleures » 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>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>Cela 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 B 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) = 30 000</tt> E/S (pages) ou 19 200 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édent qu'on vient de créer en mémoire):
+ <tt>1 000 × (30 000 + 1000) = 31 000 000 E/S.</tt>
+</p>
+<p>Coût total: <tt>31 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édents, 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 <i>pipline</i> à 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 <i>pipline</i> à 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>.
</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>
+<p>Coût total : 555 200 E/S</p>
+</div>
+<div class="sws-slide">
+<h1>Exemple (conclusion)</h1>
+
+<ul>
+ <li>Utiliser l'index n'est pas toujours payant, surtout s'il est
+ non-groupant, car on ajoute un facteur qui est le nombre de
+ résultats, pas le nombre de pages</li>
+ <li>On a fait certaines approximations « à la louche » (taille des
+ enregistrements résultants d'une jointure, nombre des
+ enregistrements résultants)</li>
+ <li>On n'a pas considéré le fait que pousser les projections plus
+ bas pour ne garder que les colonnes strictement nécessaires pouvait
+ faire baisser la taille des tables intermédiaires
+ </li>
+</ul>
+
+
+
</div>
<div class="sws-slide">
<h1>Requêtes imbriquées</h1>
projects / hacks / simpleWebSlides.git / blobdiff