<li> Notre but est de trouver des plans d'exécution plus efficaces
qui calculent le même résultat</li>
</ul>
<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
<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
- <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>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>
produit cartésien peut être converti en jointure:
<tt> σ<sub>φ</sub> (R × S) ≡ R &join;<sub>φ</sub> S</tt>
</li>
produit cartésien peut être converti en jointure:
<tt> σ<sub>φ</sub> (R × S) ≡ R &join;<sub>φ</sub> S</tt>
</li>
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>
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>
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
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
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
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
</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
</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
(<tt>max</tt>, <tt>count</tt>, <tt>average</tt>, …)</p>
<ol>
<li>Pour chaque sous-terme, on considère tous les accès possibles
(<tt>max</tt>, <tt>count</tt>, <tt>average</tt>, …)</p>
<ol>
<li>Pour chaque sous-terme, on considère tous les accès possibles
<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
<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
<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
<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
<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>
<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
<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
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>.
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>.
peuvent êtres faites en <em><i>pipeline</i> (ou <i>streaming</i></em> sans
itération/matérialisation des résultats intermédiaires
</li>
peuvent êtres faites en <em><i>pipeline</i> (ou <i>streaming</i></em> sans
itération/matérialisation des résultats intermédiaires
</li>
(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.
(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.
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).
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).
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 ×
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 ×
- sur le résultat précédant qu'on vient de créer en mémoire):
- <tt>1 000 × (300 000 + 1000) = 301 000 000 E/S.</tt>
+ 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>
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
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
<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
<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
<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> On fait une jointure page à page des deux résultats
précédents : <tt>100 + 100 × 1515 = 100 615 E/S</tt>.
</p>
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
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