6. Opérateurs et algorithmes¶

Une des tâches essentielles d’un SGBD est d’exécuter les requêtes SQL soumises par une application afin de fournir le résultat avec le meilleur temps d’exécution possible. La combinaison d’un langage de haut niveau, et donc en principe facile d’utilisation, et d’un moteur d’exécution puissant, apte à traiter efficacement des requêtes extrêmement complexes, est l’un des principaux atouts des SGBD (relationnels).

Ce chapitre présente les composants de base d’un moteur d’évaluation de requêtes: le modèle d’exécution, les opérateurs algébriques, et les principaux algorithmes de jointure. Ce sont les briques à partir desquels un système construit dynamiquement le programme d’exécution d’une requête, également appelé plan d’exécution. Dans l’ensemble du chapitre, nous donnons une spécification détaillée d’un catalogue d’opérateurs qui permettent d’évaluer toutes les requêtes SQL conjonctives (c’est-à-dire sans négation).

La manière dont le plan d’exécution est construit à la volée quand une requête est soumise fait l’objet du chapitre suivant.

S4: Algorithmes de jointure¶

Supports complémentaires:

Passons maintenant aux algorithmes de jointure. Avec les opérateurs présentés dans cette section, nous complétons notre catalogue d’opérateurs et nous saurons exécuter toutes les requêtes SQL dites conjonctives, c’est-à-dire ne comprenant ni négation (not exists) ni union. Cela couvre beaucoup de requêtes et montre que l’implantation d’un moteur d’exécution de requêtes SQL n’est finalement pas si compliqué.

select a1, a2, .., an
from T1, T2, ..., Tm
where T1.x = T2.y and ...
order by ...

La jointure est une des opérations les plus courantes et les plus coûteuses, et savoir l’évaluer de manière efficace est une condition indispensable pour obtenir un système performant. On peut classer les algorithmes de jointure en deux catégories, suivant l’absence ou la présence d’index sur les attributs de jointure. En l’absence d’index, les trois algorithmes les plus répandus sont les suivants:

L’algorithme le plus simple est la jointure par boucles imbriquées. Il est malheureusement très coûteux dès que les tables à joindre sont un tant soit peu volumineuses.

L’algorithme de jointure par tri-fusion est basé, comme son nom l’indique, sur un tri préalable des deux tables. C’est le plus ancien et le plus répandu des concurrents de l’algorithme par boucles imbriquées, auquel il se compare avantageusement dès que la taille des tables dépasse celle de la mémoire disponible.

Enfin la jointure par hachage est une technique qui donne de très bons résultats quand une des tables au moins tient en mémoire.

Quand un index est disponible (ce qui est le cas le plus courant, notamment quand la jointure associe la clé primaire d’une table à la clé étrangère d’une autre), on utilise une variante de l’algorithme par boucles imbriquées avec traversée d’index, dite jointure par boucles indexée.

Note

si les deux tables sont indexées, on utilise parfois une variante du tri-fusion sur les index, mais cette technique pose quelques problèmes et nous ne l’évoquerons que brièvement.

On note dans ce qui suit $R$ et $S$ les relations à joindre et $T$ la relation résultat. Le nombre de blocs est noté respectivement par $B_R$ et $B_S$ . Le nombre d’enregistrements de chaque relation est respectivement $N_R$ et $N_S$.

Nous commençons par l’algorithme le plus efficace et le plus courant: celui utilisant un index.

Jointure avec un index¶

La jointure entre deux tables comporte le plus souvent une condition de jointure qui associe la clé primaire d’une table à la clé étrangère de l’autre. Voici quelques exemples pour s’en convaincre.

Les films et leur metteur en scène

select * from Film as f, Artiste as a
where f.id_realisateur = a.id

Les artistes et leurs rôles

select * from Artiste as a, Role as r
where a.id = r.id_acteur

Les employés et leur département

select * from emp e, dept d
where e.dnum = d.num

Cette forme de jointure est courante car elle est « naturelle »: elle consiste à reconstruire l’information dispersée entre plusieurs tables par le processus de normalisation du schéma. Le point important (pour les performances) est que la condition de jointure porte sur au moins un attribut indexé (la clé primaire) et éventuellement sur deux si la clé étrangère est, elle aussi, indexée.

Cette situation permet l’exécution d’un algorithme à la fois très simple et assez efficace (on suppose pour l’instant que seule la clé primaire est indexée):

on parcourt séquentiellement la table contenant la clé étrangère;

pour chaque nuplet, on utilise la valeur de la clé étrangère pour accéder à l’index sur la clé primaire de la second table: on récupère l’adresse adr d’un nuplet;

il reste à effectuer un accès direct, avec l’adresse adr, pour obtenir le second nuplet et constituer la paire.

Prenons comme exemple la première jointure SQL donnée ci-dessus. On va parcourir la table Film qui contient la clé étrangère id_réalisateur. Pour chaque nuplet film obtenu durant ce parcours, on prend la valeur de id_réalisateur et on recherche, avec l’index, l’adresse de l’artiste correspondant. Il reste à effectuer un accès direct à la table Artiste.

Nous avons un nouvel opérateur que nous appellerons IndexedJoin. Il consomme des données fournis par deux autres opérateurs que nous avons déjà définis: un parcours séquentiel FullScan, un parcours d’index IndexScan. Il est complété par un troisième, lui aussi déjà étudié: DirectAccess. La forme du programme qui effectue ce type de jointure est illustrée par la Fig. 6.9. Elle peut paraître un peu complexe, mais elle vaut la peine d’être étudiée soigneusement. Le motif est récurrent et doit pouvoir être repéré quand on étudie un plan d’exécution.

Fig. 6.9 Algorithme de jointure avec index¶

L’opérateur IndexedJoin lui-même fait peu de choses puisqu’il s’appuie essentiellement sur d’autres composants qui font déjà une bonne partie du travail. Implanter un moteur d’exécution, tâche qui peut sembler extrêmement complexe à priori, s’avère en fait relativement simple avec cette approche très générique et décomposant les opérations nécessaires en briques élémentaires.

Voici le pseudo-code de la fonction next() de l’opérateur de jointure. Il faudrait, dans une implantation réelle, ajouter quelques contrôles, mais l’essentiel est là, et reste relativement simple.

function nextIndexJoin
{
  # $tScan est l'opérateur de parcours séquentiel de la première table
  # On récupère un nuplet
  $nuplet = $tScan.next();

  # On crée un opérateur de parcours d'index
  iScan = new IndexScan ();
  # On exécute le parcours d'index avec la clé étrangère
  $iScan.open ($nuplet.foreignKey);
  # On récupère l'adresse
  addr = $iScan.next();

  # Et on renvoie la paire avec le nuplet et l'adresse
  return [$nuplet, $addr];
 }

Cet algorithme peut être considéré comme le meilleur possible pour une jointure.

Il s’appuie essentiellement sur un parcours d’index qui, en pratique, va s’effectuer en mémoire RAM car un arbre-B est compact, très sollicité, et résidera dans le cache la plupart du temps.

Il permet un pipelinage complet: quelle que soit la taille des données, une application communiquant avec ce plan d’exécution recevra tout de suite la première paire-résultat, et obtiendra les suivantes avec très peu de latence à chaque appel next().

En contrepartie, l’algorithme nécessite des accès directs (aléatoires) pour obtenir les nuplets de la seconde table. C’est loin d’être très efficace, pour des raisons déjà soulignées, et explique que la jointure reste une opération coûteuse.

Pour conclure sur cet algorithme, notez qu’il est présenté ici comme s’appuyant sur un parcours séquentiel, mais qu’il fonctionne tout aussi bien si la source de données (à gauche) est n’importe quel autre opérateur. Il est donc très facile à intégrer dans les plans d’exécution très complexes comprenant plusieurs jointures, sélection, projections, etc.

Jointure avec deux index¶

Peut-on faire mieux si les deux tables sont indexées? Lorsque $R$ et $S$ ont un index sur l’attribut de jointure, on peut tirer parti du fait que les feuilles de ceux-ci sont triées sur cet attribut. En fusionnant les feuilles des index $B_R$ et $B_S$ de la même manière que pendant la phase de fusion de l’algorithme de jointure par tri-fusion, on obtient une liste de couples d’adresses d’enregistrements de $R$ et $S$ à joindre. Cette première phase est très efficace, car les deux index sont très probablement en mémoire et l’algorithme de fusion est lui-même simple et performant.

La deuxième phase consiste à lire les enregistrements par deux accès directs, l’un sur $R$, l’autre sur $S$. C’est ici que les choses se compliquent, car la multiplication des accès aléatoires devient très pénalisante. Comme déjà discuté, si une partie significative d’une table est concernée, il est préférable d’efectuer un parcours séquentiel qu’une succession d’accès directs. Pour cette raison, beaucoup de SGBD (dont Oracle), en présence d’index sur l’attribut de jointure dans les deux relations, préfèrent quand même appliquer l’algorithme IndexedJoin. L’amélioration permise par cette situation reste le choix de la table à parcourir séquentiellement: pour des raisons évidentes on prend la plus petite.

Jointure par boucles imbriquées¶

Nous abordons maintenant le cas des jointures où aucun index n’est disponible. Disons tout de suite que les performances sont alors nettement moins bonnes, et devraient amener à considérer la création d’un index approprié pour des requêtes fréquemment utilisées.

L’algorithme direct et naïf, que nous appellerons NestedLoop, s’adapte à tous les prédicats de jointure. Il consiste à énumérer tous les enregistrements dans le produit cartésien de $R$ et $S$ (en d’autres termes, toutes les paires possibles) et garde ceux qui satisfont le prédicat de jointure. La fonction de base est la jointure de deux listes en mémoire, L1 et L2, et se décrit simplement comme suit:

 function JoinList
 {
   # $L1 est la liste dite "extérieure"
   # $L2 est la liste dite "intérieure"
   # $condition est la condition de jointure
   resultat = [];

   for nuplet1 in $L1
   do
    for nuplet2 in $L2
    do
      if (condition ($nuplet1, $nuplet2) = true) the
        $resultats[] = ($nuplet1, $nuplet2);
      fi
    done
  done
}

Le coût de cette fonction se mesure au nombre de fois où on effectue le test de la condition de jointure. Il est facile de voir que chaque nuplet de L1 est comparé à chaque nuplet de L2, d’où un coût de $|L1| \times |L2|$.

Maintenant, ce qui nous intéresse dans un contexte de base de données, c’est aussi (surtout) le nombre de lectures de blocs nécessaires. Dès lors que la jointure implique des accès disques, ces entrées/sorties (E/S) constituent le facteur prédominant. La méthode de base, illustrée par la Fig. 6.10, consiste à charger toutes les paires de blocs en mémoire, et à appliquer la fonction JoinList sur chaque paire.

Fig. 6.10 Boucle imbriquée sur les blocs¶

Le pseudo-code suivant montre la jointure par boucle imbriquée, constituant toutes les paires de blocs par un unique parcours séquentiel sur la première table, et des parcours séquentiels répétés sur la seconde.

 function NestedLoopJoin
 {
   # $R est la tablee dite "extérieure"
   # $S est la table dite "intérieure"
   # $condition est la condition de jointure
   resultat = [];

   for blocR in $R
   do
    for blocS in $S
    do
      JoinList ($blocR, $blocS)
    done
  done
}

Le principale mérite (le seul) de cet algorithme est de demander très peu de mémoire: deux blocs suffisent. En revanche, le nombre de lectures et très important:

il faut lire toute la table R,

il faut lire autant de fois la table S qu’il y a de blocs dans R.

Le nombre de lectures est donc $B_R + B_R \times B_S$. Cette petite formule montre au passage qu’il est préférable de prendre comme table extérieure la plus petite des deux.

Cela étant, on peut faire beaucoup mieux en utilisant plus de mémoire. Soit $R$ la table la plus petite. Si le nombre de blocs $M$ est au moins égal à $B_R + 1$, la table $R$ tient en mémoire centrale. On peut alors lire $S$ une seule fois, bloc par bloc, en effectuant à chaque fois la jointure entre le bloc et l’ensemble des blocs de $R$ chargés en RAM (Fig. 6.11).

Fig. 6.11 Boucle imbriquée avec chargement complet d’une table en RAM¶

Avec cette solution (très fréquemment applicable en ces temps où la mémoire RAM est devenue très grosse), le coût est de $B_R + B_S$: une seule lecture des deux tables suffit. D’un coût quadratique dans les tailles des relations, lorsqu’on n’a que 3 blocs, on est passé à un coût linéaire. Cet algorithme en devient très efficace et simple à implanter.

S’il s’agit d’une équi-jointure, une variante encore améliorée de cet algorithme consiste à hacher $R$ en mémoire à l’aide d’une fonction de hachage $h$ . Alors pour chaque enregistrement de $S$, on cherche par $h(s)$ les enregistrements de $R$ joignables. Le coût en E/S est inchangé, mais le coût CPU est linéaire dans le nombre d’enregistrement des tables $N_R + N_S$ (alors qu’avec la procédure JoinList c’est une fonction quadratique du nombre d’enregistrements).

Fig. 6.12 Boucle imbriquée avec chargement par fragments d’une table en RAM¶

Si $R$ ne tient pas en mémoire car $B_R > M -1$, il reste la version la plus générale de la jointure par boucles imbriquées (Fig. 6.12): on découpe $R$ en fragments de taille $M-1$ blocs et on utilise la variante ci-dessus pour chaque groupe. $R$ est lue une seule fois, groupe par groupe, $S$ est lue $\lceil \frac{B_R}{M-1} \rceil$ fois. On obtient un coût final de:

\[B_R + \lceil \frac{B_R}{M-1} \rceil \times B_S\]

Exemple

On prend l’exemple d’une jointure entre Film et Artiste en supposant, pour les besoins de la cause, qu’il n’y a pas d’index. La table Film occupe 1000 blocs, et la table Artiste 10 000 blocs. On suppose que la mémoire disponible a pour taille $M=251$ blocs.

En prenant la table Artiste comme table extérieure, on obtient le coût suivant:

\[10 000 + \lceil \frac{10000}{250} \rceil \times 1000 = 50 000\]

Et en prenant la table Film comme table extérieure:

\[1 000 + \lceil \frac{1000}{250} \rceil \times 1000 = 41 000\]

Conclusion: il faut prendre la table la plus petite comme table extérieure. Cela suppose bien entendu que l’optimiseur dispose des statistiques suffisantes.

En résumé, cette technique est simple, et relativement efficace quand une des deux relations peut être découpée en un nombre limité de groupes (autrement dit, quand sa taille par rapport à la mémoire disponible reste limitée). Elle tend vite cependant à être très coûteuse en E/S, et on lui préfère donc en général la jointure par tri-fusion, ou la jointure par hachage, présentées dans ce qui suit.

Jointure par tri-fusion¶

L’algorithme de jointure par tri-fusion que nous présentons ici s’applique à l’équijointure (jointure avec égalité). C’est un exemple de technique à deux phases: la première consiste à trier les deux tables sur l’attribut de jointure (si elles ne le sont pas déjà). Ce tri facilite l’identification des paires d’enregistrement partageant la même valeur pour l’attribut de jointure.

À l’issue du tri on dispose de deux fichiers temporaires stockés sur disque

Note

En fait on évite d’écrire le résultat de la dernière étape de fusion du tri, en prenant « à la volée » les enregistrements produits par l’opérateur de tri. Il s’agit d’un exemple de petites astuces qui peuvent avoir des conséquences importantes, mais dont nous omettons en général la description pour des raisons de clarté.

On utilise l’algorithme de tri externe vu précédemment pour cette première étape. La deuxième phase, dite de fusion, consiste à lire bloc par bloc chacun des deux fichiers temporaires et à parcourir séquentiellement en parallèle ces deux fichiers pour trouver les enregistrements à joindre. Comme les fichiers sont triés, sauf cas exceptionnel, chaque bloc n’est lu qu’une fois.

Prenons l’équijointure de $R$ et $S$ sur les attributs a et b.

select * from R, S where R.a = S.b

On va trier $R$ et $S$ et on parcourt ensuite les tables triées en parallèle. Regardons plus en détail la fusion. C’est une variante très proche de l’agorithme de fusion de liste. On commence avec les premiers enregistrements $r_1$ et $s_1$ de chaque table.

Si $r_1.a = s_1.b$ , on joint les deux enregistrements, on passe au enregistrements suivants, jusqu’à ce que $r_i.a \not= s_i.b$.

Si $r_1.a < s_1.b$, on avance sur la liste de $R$.

Si $r_1.a > s_1.b$, on avance sur la liste de $S$.

Donc on balaie une table tant que l’attribut de jointure a une valeur inférieure à la valeur courante de l’attribut de jointure dans l’autre table. Quand il y a égalité, on fait la jointure. Ceci peut impliquer la jointure entre plusieurs enregistrements de $R$ en séquence et plusieurs enregistrements de $S$ en séquence. Ensuite on recommence.

L’opérateur de jointure peut s’appuyer sur l’opérateur de tri, déjà étudié. Il suffit donc d’implanter la jointure de deux listes triées dans un opérateur Merge. Voici la fonction next() de cet opérateur, avec deux opérateurs de tris opérant respectivement sur la première et la seconde table (plus généralement, ces opérateurs de tri peuvent opérer sur n’importe quel sous-plan d’exécution).

 function nextMerge
 {
   # $triR est l'opérateur de tri sur la première table
   # $triS est l'opérateur de tri sur la seconde table
   # a et b désignent les attributs de jointure

   # Récupération de nuplets fournis par les opérateurs
   $nupletR = $triR.next();
   $nupletS = $triS.next();

   # Tant que les deux nuplets de joignent pas sur a et b, on avance
   # sur une des deux listes
  while ($nupletR.a != $nupletS.b) do
    if ($nupletR.a < $nupletS.b) then
      $nupletR = $triR.next();
     else
      $nupletS = $triR.next();
     fi
  done

  return [$nupletR, $nupletS];
}

Le plan d’exécution typique d’une jointure par tri-fusion avec cet opérateur est illustré par la Fig. 6.13.

Fig. 6.13 Plan d’exécution type pour la jointure par tri-fusion¶

La jointure $s$ par tri-fusion est illustrée dans la Fig. 6.14.

Fig. 6.14 Exemple de jointure par tri-fusion¶

Le coût de la jointure par tri-fusion est important, et impose une latence due à la phase de tri initiale. Une fois la phase de fusion débutée, le débit est en revanche très rapide. La performance dépend donc essentiellement du tri, et donc de la mémoire disponible. C’est l’algorithme privilégié par les SGBD pour la jointure sans index de très grosses tables (situation qu’il vaut mieux éviter quand c’est possible).

Jointure par hachage¶

Comme tous les algorithmes à base de hachage, cet algorithme ne peut s’appliquer qu’à une équi-jointure. Comme l’algorithme de tri-fusion, il comprend deux phases: une phase de partitionnement des deux relations en $k$ fragments chacune, avec la même fonction de hachage, et une phase de jointure proprement dite.

La première phase a pour but de réduire le coût de la jointure proprement dite de la deuxième phase. Au lieu de comparer tous les enregistrements de $R$ et $S$, on ne comparera les enregistrements de chaque fragment $F_R^i$ de $R$ qu’aux enregistrements du fragment $F_S^i$ associée de $S$. Notez bien qu’il s’agit du même exposant $i$: les fragements sont associés par paire, ce qui implique que l’on a la garantie qu’aucun nuplet de $F_R^i$ ne joint avec un nuplet de $F_S^j$, pour $i \not= j$.

Le partitionnement de $R$ se fait par hachage. On suppose toujours que a et b sont les attributs de jointure respectifs et on note $h$ la fonction de hachage qui s’applique à la valeur de a ou b et renvoie un entier compris entre 1 et $k$.

Un enregistrement $r$ de $R$ est donc placé dans le fragment $F_R^{h(r.a)}$; un enregistrement $s$ de $S$ est donc placé dans le fragment $F_S^{h(s.b)}$. On obtient exactement le même nombre de fragments pour $R$ et $S$, placés sur le disque si nécessaire, comme le montre la figure Première phase de la jointure par hachage: le partitionnement.

Fig. 6.15 Première phase de la jointure par hachage: le partitionnement¶

Important

Comment est choisi $k$, le nombre de fragments? Le critère que, pour la plus petite des deux tables, chaque fragment doit tenir dans la mémoire disponible. Si, par exemple, $R$ est la plus petite des deux tables et occupe 100 blocs, alors que 20 blocs de RAM sont disponibles, il faudra au moins $k=5$ fragments. Pourquoi? Lire la suite.

On peut alors passer à la seconde phase, dite de jointure. La remarque fondamentale ici est la suivante: si deux nuplets $r$ et $s$ doivent être joints, alors on a $h(r.a) = h(s.b)=u$ et on les trouvera, respectivement, dans $F_R^u$ et $F_S^u$. En d’autres termes, il suffit d’effectuer la jointure sur les paires de fragments correspondant à la même valeur de la fonction de hachage.

Note

Le paragraphe qui précède est vraiment le cœur de l’algorithme de hachage et justifie tout sont fonctionnement. Lisez-le et relisez-le jusqu’à être convaincus que vous le comprennez.

La deuxième phase consiste alors pour $i = 1, ..., k$, à lire le fragment $F_R^i$ de $R$ en mémoire et à effectuer la jointure avec le fragment $F_S^i$ de $S$. La technique de jointure à appliquer au fragment est exactement celle par boucle imbriquées, décrite ci-dessus, quand l’une des deux tables tient en RAM: . Le point important (et qui explique le choix du nombre de fragments) est qu’au moins l’un des deux fragments à joindre doit résider en mémoire; l’autre, lu séquentiellement, peut avoir une taille quelconque.

La Fig. 6.16 montre le calcul de la jointure pour deux fragments. Celui de la première table est entièrement en mémoire, celui de la seconde est lu séquentiellement et placé au fur et à mesure de la lecture dans le reste de la mémoire disponible, pour être joint avec le fragment résidant.

Fig. 6.16 Première phase de la jointure par hachage: la jointure¶

Le coût de la première phase de partitionnement de cet algorithme est $2 \times (B_R + B_S)$. Chaque relation est lue entièrement et hachée dans les fragments qui sont écrits sur disque bloc par bloc.

Le coût de la deuxième phase est de $B_R + B_S$. En effet les relations partitionnées sont lues une fois chacune, fragment par fragment. Le coût total de cet algorithme est donc $3 \times (B_R + B_S)$. Noter que cet algorithme est très gourmand en mémoire. Il est bien adapté aux jointures déséquilibrées pour lesquelles une des tables est petite par rapport à lamémoire RAM disponible. Dans le meilleur des cas où un seul fragment est nécessaire (la table tient entièrement en mémoire) on retrouve tout simplement la jointure par boucles imbriquées décrite précédemment. La jointure par hachage peut être vue comme une généralisation de cet algorithme simple.

Comment implanter cet algorithme de jointure sous forme d’itérateur? Et bien, comme pour le tri, toute la phase de hachage s’effectue dans le open() et cet opérateur est donc bloquant: la phase de hachage correspond à une latence perçue par l’utilisateur qui attend sans que rien (en apparence) ne se passe. La phase de jointure peut, elle, être très rapide, et surtout fournit régulièrement des nuplets à l’application cliente.

Concluons cette section avec deux remarques:

Excepté les algorithmes basés sur une boucle imbriquée avec ou sans index, les algorithmes montrés ont été conçus pour le prédicat d’égalité. Naturellement, indépendamment de l’algorithme, le nombre des enregistrements du résultat est vraisemblablement beaucoup plus important pour de telles jointures que dans le cas d’égalité.

Cette section a montré que l’éventail des algorithmes de jointure est très large et que le choix d’une méthode efficace n’est pas simple. Il dépend notamment de la taille des relations, des méthodes d’accès disponibles et de la taille disponible en mémoire centrale. Ce choix est cependant fondamental parce qu’il a un impact considérable sur les performances. La différence entre deux algorithmes peut dans certains cas atteindre plusieurs ordres de grandeur.

La tendance est à l’utilisation de plus en plus fréquente de la joiunture par hachage qui remplace l’algorithme de tri-fusion qui était privilégié dans les premiers temps des SGBD relationnels. La taille atteinte par les mémoires RAM est sans doute le principal facteur explicatif de ce phénomène.

Quiz¶

Pourquoi la clé primaire d’une table doit-elle être indexée (plusieurs réponses possibles) :

Parce que la plupart des requêtes SQL portent sur la valeur de la clé primaire.

Pour vérifier rapidement la contrainte d’unicité lors d’une insertion.

Pour vérifier rapidement la contrainte d’intégrité référentielle lors de l’insertion d’un clé étrangère.

Pour vérifier rapidement la contrainte d’intégrité référentielle lors de la destruction d’une clé primaire.

Considérons les tables des employés et des départements suivantes. Les clés primaires sont indexées.

Enum

Nom

Dnum

E1

Benjamin

D1

E2

Philippe

D2

E3

Serge

D1

Enum	Nom	Dnum
E1	Benjamin	D1
E2	Philippe	D2
E3	Serge	D1

Dnum

Dnom

D1

INRIA

D2

CNAM

Pour une jointure avec index, combien de parcours d’index doit-on effectuer ?

1

2

3
Supposons que l’attribut Dnum dans la table Employé soit indexé. Combien de parcours d’index devrait-on effectuer en prenant la table Dept comme table directrice (à gauche).

1

2

3
Dans la requête suivante, peut-on appliquer la jointure par boucles imbriquées indexées, f() et g() étant des fonctions quelconques ?
select * from Emp, Dept where f(E.dnum) = g(Dept.dnum)
Oui

Non
Soit la jointure entre deux tables T(ABCD) et S(MNO) dans la requête suivante :
select * from T, S where T.A=S.M
À quels attributs faut-il appliquer la fonction de hachage pour la jointure ?

Aux clés primaires.

Aux attributs A de T et M de S.

À l’attribut A de T, et à la clé primaire de S.

À la clé primaire de T, à l’attribut M de S.
Pourquoi 2 nuplets à joindre sont-ils forcément dans des fragments associés ?

Parce que les fragments sont de taille proportionnelle à la table, ce qui garantit l’alignement des nuplets à joindre.

Parce que les valeurs des attributs de jointure étant les mêmes, le résultat de la fonction de hachage est le même.
Peut-on appliquer la jointure par hachage à la requête suivante :
select * from T, S where T.A <= S.M
Oui

Non

Dnum	Dnom
D1	INRIA
D2	CNAM

Exercices¶

Exercice ex-iter1: définition d’itérateurs

Définir sous forme de pseudo-code (open() et next()) un itérateur min qui renvoie le nuplet de sa source ayant la valeur minimale pour un attribut att_min.

Définir un itérateur distinct qui élimine les doublons de sa source.

Correction

L’itérateur Min prend comme source de données un autre itérateur $source. Voici la spécification en pseudo-code.

#  Initialisation de l'itérateur
function open
{
  $source.open(); # On exécute le open() sur la source
  $courant = $source.next(); # On récupére le premier nuplet
  $valeur_min =  $courant['att_min'] # Initialisation de la valeur min
}

# Le next parcourt tous les enregistrements et conserve le min
# (on aurait pu le faire dans l'open)
function next
{
  $nouveau = $source.next();
  if ($nouveau == NULL) then # On a parcouru toute la source
     return $valeur_min;
  fi

  if ($nouveau['att_min'] < $valeur_min) then
        # On a trouvé une valeur plus petite
        $valeur_min = $nouveau['att_min'];
  fi
}

Voici la spécification presque complète du distinct en pseudo-code. Quelques améliorations à apporter, et notamment la gestion de la fin et de la fermeture. Important: ne fonctionne que si la source est triée.

function open
{
  $source.open();
  $courant = $source.next(); # Premier nuplet
}

function next
{
   #  On prend le nuplet suivant de la source
  $suivant = $source.next()
  # On continue le parcours de la source jusqu'à trouver un nuplet différent
  while ($suivant == $courant) do
    $suivant = $source.next()
  done

  # Ici, on a trouvé un nuplet $suivant qui est différent de $courant
  $retour = $courant # Le nuplet à renvoyer
  $courant = $suivant # Le nouveau nuplet courant
  return $retour
 }

On peut aussi obtenir l’élimination des doublons avec la hachage.

Exercice ex-iter2: plans d’exécution

Donner des plans d’exécution pour les requêtes suivantes:
Avec clause order by
select titre from Film order by annee
Recherche d’un élément minimal
select min(annee) from Film
Elimination des doublons
select distinct genre from Film

Correction

Un itérateur de parcours séquentiel, suivi d’un itérateur de tri, suivi d’un itérateur pour la projection.
Un itérateur de parcours séquentiel, suivi de notre itérateur Min, suivi d’un itérateur pour la projection. Autre possibilité: on trie, et on ne garde que le premier.
Un itérateur de parcours séquentiel, suivi d’un itérateur de tri, suivi de notre itérateur distinct.

Exercice ex-opalgo1: comprendre le tri externe

Soit un fichier de 10 000 blocs et une mémoire cache de 3 blocs. On trie ce fichier avec l’algorithme de tri-fusion.

Combien de fragments sont produits pendant la première passe?

Combien d’étapes de fusion faut-il pour trier complètement le fichier?

Quel est le coût total en entrées/sorties?

Combien faut-il de blocs en mémoire faut-il pour trier le fichier en une fusion seulement.

Répondre aux mêmes questions en prenant un fichier de 20 000 blocs et 5 blocs de mémoire cache.

Correction

Pour un fichier de 10,000 blocs et 3 blocs de buffer.

il faut lire $\lceil \frac{10000}{3} \rceil = 3 334$ fois 3 blocs, que l’on trie à chaque fois.

ensuite on associe 2 fragments pour en produire un troisième, deux fois plus gros. La taille des fragments est de 3, puis de 6 après la seconde passe, puis de 12 après la troisième, plus généralement de $3 \times 2^(n-1)$ après l’étape n.

On cherche n tel que $3 \times 2^{n-1} \geq 10\,000$. On trouve $n = \lceil \log (\frac{10000}{3}) \rceil + 1 = 13$.

Nombre d’entrées/sorties: $2 \times 10\,000 \times n$

On veut que $m \times (m - 1) \geq 10\,000$, donc $m = \sqrt{10\,000} = 100$.

Exercice ex-join1: coût des jointures par boucles imbriquées

Soit deux relations R et S, de tailles respectives |R| et |S| (en nombre de blocs). On dispose d’une mémoire mem de taille M, dont les blocs sont dénotés $mem[1], mem[2], \ldots, mem[M]$.

Donnez la formule exprimant le coût d’une jointure $R \Join S$, en nombre d’entrées/sorties, pour l’algorithme suivant:

$posR = 1   # On se place au début de R
while [$posR <= |R|] do
    Lire  R[$posR] dans $mem[1] # On lit les blocs 1 par 1
    $posS = 1  # On se place au début de S
    while ($posS <= |S|)  do
       Lire  S[$posS] dans $mem[2] # On lit les blocs 1 par 1
       # JoinList est l'algorithme donné en cours
       JoinList (mem[1], mem[2])
      done
      $posS = $posS + 1 # Bloc suivant de S
    done
   $posR = $posR + 1 # Bloc suivant de R
 done

Même question avec l’algorithme suivant

$posR = 1   # On se place au début de R
while [$posR <= |R|] do
   Lire  R[p$osR..($posR+M-1)] dans $mem[1..M-1] # On lit M-1 blocs de R
   $posS = 1
   while ($posS <= |S|) do
       Lire  S[$posS] dans $mem[2] # On lit les blocs 1 par 1
       # JoinList est l'algorithme donné en cours
      JoinList (mem[1], mem[2])
   done
   $posS = $posS + 1 # Bloc suivant de S
  done
  $posR = $posR + M # On lit les M blocs suivants de R
 done

Quelle table faut-il prendre pour la boucle extérieure? La plus petite ou la plus grande,?

Correction

Le premier algorithme est une jointure par boucle imbriquée qui exploite très mal la mémoire puisque seuls les deux premiers blocs de m sont utilisés. Le coût est de $|R| + |R| \times |S|$.
le second est en fait celui illustré par la Fig. 6.11. La mémoire m est utilisée pour réduire le nombre d’itérations sur R, avec un coût de $|R| + \lceil \frac{R}{M-1} \rceil \times |S|$.
Au vu des formules de coût il faut prendre la petite table comme table directrice.

Exercice ex-joincost: coût des jointures

On suppose que $|R| = 10\,000$ blocs, $|S|=1\,000$ et M=51. On a 10 enregistrements par bloc, b est la clé primaire de S et on suppose que pour chaque valeur de R.a on trouve en moyenne 5 enregistrements dans R. On veut calculer $\pi_{R.c} (R \Join_{a=b} S)$.

Donnez le nombre d’entrée-sorties dans le pire des cas pour les algorithmes par boucles imbriquées de l’exercice ex-join1.

Même question en supposant (a) qu’on a un index sur R.a, (b) qu’on a un index sur S.b, (c) qu’on a deux index, sachant que dans tous les cas l’index a 3 niveaux.

Même question pour une jointure par hachage.

Même question avec un algorithme de tri-fusion.

Correction

Premier algorithme: 10 001 000 blocs. Second algorithme on lit S (il faut mettre la table la plus petite à l’extérieur de la boucle) en 20 fragments, et pour chacun on lit R: $1\,000 + (20 \times 10\,000) = 201\,000$.
Avec un index sur R.a: on parcourt S (1 000 blocs). S contient 10 000 enregistrements donc au pire if faut 30 000 accès pour parcourir l’index de hauteur 3. Pour chaque valeur de S.b on trouve en moyenne 5 enregistrement dans R, donc 50 000 lectures directes dans R. Soit 81 000 lectures.

Avec un index sur S: on parcourt R (10 000 blocs). Au pire il faut 100 000 accès par l’index: 300 000 blocs + 100 000 accès directs. Soit 500 000 lectures.

Avec deux index: il faut se ramener au cas d’un index sur R.

Ces coûts sont théoriques. En pratique, les index sont le plus souvent déjà en mémoire, ainsi qu’une bonne partie des blocs de données. Cela réduit considérablement le nombre de lectures physiques (retirer le facteur lié au parcours d’index dans les analyses ci-dessus).
Par hachage: le mieux est de hacher la table S sur S.b en 20 fragments de 50 blocs chacun. On hache ensuite R sur R.a, avec la même fonction de hachage en 20 fragments d’environ 500 blocs chacun.

Ensuite on applique la jointure par boucles imbriquées sur chaque paire de fragments: on lit le fragment de S dans 50 blocs, on fait défiler le fragment correspondant de R dans le bloc restant.

Coût: pour le hachage on lit et on écrit une fois S et R (22 000 E/S). Pour la jointure il suffit de lire une fois R et S, soit 33 000 blocs lus ou écrits en tout.
Avec un algo. de tri-fusion. On commence par trier chaque table:
- la table $R$ se décompose en 197 (10 000/51) fragments triés de 51 blocs chacun (sauf le dernier qui fait 4 blocs),; on les fusionne en 4 gros fragments: les 3 premiers font $51 \times 50 = 2\,550$ blocs, le dernier fait 2 350 blocs. Une dernière fusion et le fichier est trié. Coût : 60 000 blocs.
  
  La table $S$ se trie en une seule phase de fusion: coût 4 000 blocs.
  
  Il reste à fusionner les deux tables triées, pour un coût final de 11 000 blocs lus. Donc le coût total est de 75 000 blocs.
  
  Remarque: en pratique certaines astuces permettent d’améliorer la performance du tri (notez par exemple que la mémoire est très mal utilisée dans la seconde phase de fusion de la table $R$), ce qui rapproche le coût de celui du hachage.

6. Opérateurs et algorithmes¶

S1: Modèle d’exécution: les itérateurs¶

Matérialisation et pipelinage¶

Opérateurs bloquants¶

Itérateurs¶

Quiz¶

S2: les opérateurs de base¶

Parcours séquentiel¶

Parcours d’index¶

Accès par adresse¶

Opérateurs de sélection et de projection¶

Exécution de requêtes mono-tables¶

Quiz¶

S3: Le tri externe¶

Phase de tri¶

Phase de fusion¶

Coût du tri-fusion¶

L’opérateur de tri-fusion¶

Quiz¶

S4: Algorithmes de jointure¶

Jointure avec un index¶

Jointure avec deux index¶

Jointure par boucles imbriquées¶

Jointure par tri-fusion¶

Jointure par hachage¶

Quiz¶

Exercices¶

Table Of Contents

Recherche