Traitement des requêtes

Database System Concepts, 7th Ed.

©Silberschatz, Korth and Sudarshan
See [Link] for conditions on re-use
 Chapitre 15: Traitement des requêtes

 Aperçu
 Mesures du coût de la requête
 Opération de sélection
 Tri
 Opération de jointure
 Autres opérations
 Évaluation des expressions

Database System Concepts - 7th Edition 15.2 ©Silberschatz, Korth and Sudarshan
 Étapes de base du traitement des requêtes

1. Analyse et traduction
2. Optimisation
3. Évaluation

Database System Concepts - 7th Edition 15.3 ©Silberschatz, Korth and Sudarshan
 Étapes de base du traitement des requêtes
(suite)
 Analyse et traduction
• Analyse: vérifier la syntaxe, vérifier les relations.
• Représentation interne de la requête: mettre la requête en format
d’algèbre relationnelle.
 Optimisation
• Choisir l'expression d'algèbre relationnelle la moins coûteuse (ou
raisonnable).
 Évaluation
• Le moteur d'exécution de requête prend un plan d'évaluation de
requête, exécute ce plan et renvoie les réponses au requête.

Database System Concepts - 7th Edition 15.4 ©Silberschatz, Korth and Sudarshan
 Étapes de base du traitement des requêtes:
optimisation
 Une expression d'algèbre relationnelle peut avoir de nombreuses
expressions équivalentes
• Par exemple, salary75000(salary(instructor)) est équivalent à
salary(salary75000(instructor))
 Chaque opération d'algèbre relationnelle peut être évaluée à l'aide de
différents algorithmes
• En conséquence, une expression d'algèbre relationnelle peut être
évaluée de plusieurs manières.
 L'expression annotée spécifiant une stratégie d'évaluation détaillée est
appelée plan d'évaluation. Par exemple,:
• Utiliser un index sur salary pour trouver des instructeurs avec un
salaire <75000,
• Ou effectuez une analyse complète des relations et éliminez les
instructeurs avec un salaire >= 75000

Database System Concepts - 7th Edition 15.5 ©Silberschatz, Korth and Sudarshan
 Étapes de base: optimisation (suite)

 Optimisation des requêtes: Parmi tous les plans d'évaluation

équivalents, choisir celui dont le coût est le plus bas.
• Le coût est estimé à l'aide des informations statistiques du
catalogue de base de données
 par exemple. nombre de tuples dans chaque relation, taille des
tuples, etc.
 Dans ce chapitre, nous étudions
• Comment mesurer les coûts des requêtes.
• Algorithmes d'évaluation des opérations d'algèbre relationnelle.
• Comment combiner des algorithmes pour des opérations
individuelles afin d'évaluer une expression complète.
 Dans le chapitre 16
• Nous allons étudier comment optimiser les requêtes, c'est-à-dire
comment trouver un plan d'évaluation avec le coût estimé le plus
bas.

Database System Concepts - 7th Edition 15.6 ©Silberschatz, Korth and Sudarshan
 Mesures du coût de la requête
 De nombreux facteurs contribuent au coût du temps
• accès disque, CPU et réseau de la communication
 Le coût peut être mesuré en fonction
• Temps de réponse, c'est-à-dire le temps total écoulé pour répondre à
la requête, ou
• La consommation totale de ressources.
 Nous utilisons la consommation totale de ressources comme une mesure
de coût.
• Le temps de réponse est plus difficile à estimer et la réduction de la
consommation de ressources est une bonne idée dans une base de
données partagée
 Nous ignorons les coûts de processeur (CPU) pour plus de simplicité
• Les vrais systèmes prennent en compte le coût du processeur.
• Les coûts de réseau doivent être pris en compte pour les systèmes
parallèles.
 Nous décrivons comment estimer le coût de chaque opération

Database System Concepts - 7th Edition 15.7 ©Silberschatz, Korth and Sudarshan
 Mesures du coût de la requête
 Le coût d’accès au disque peut être estimé comme suit:
• Nombre de recherches multiplié par le coût moyen de recherche
• Nombre de blocs lus multiplié par le coût moyen de lecture de bloc
• Nombre de blocs écrits multiplié par le coût moyen d'écriture de bloc
 Pour plus de simplicité, nous utilisons le nombre de transferts de blocs à
partir du disque et le nombre de recherches comme des mesures de
coût.
• tT - le temps de transfert d’un bloc de données
 En supposant pour la simplicité que le coût d'écriture est le même
que le coût de lecture.
• tS - temps pour une recherche (dans le disque).
• Coût des transferts de b blocs plus S recherches est:
b * tT + S * tS
 tS et tT dépendent de l'endroit où les données sont stockées; avec des blocs
de 4 Ko:
• Disque magnétique haut de gamme: tS = 4 msec et tT = 0,1 msec
• SSD: tS = 20-90 microsec et tT = 2-10 microsec pour 4 Ko

Database System Concepts - 7th Edition 15.8 ©Silberschatz, Korth and Sudarshan
 Mesures du coût de la requête (suite)

 Les données requises peuvent déjà résider dans la mémoire tampon, en

évitant les E / S de disque
• Mais difficile à prendre en compte pour l'estimation des coûts.
 Plusieurs algorithmes peuvent réduire les E / S disque en utilisant un
espace tampon supplémentaire.
• La quantité de mémoire réelle disponible pour la mise en mémoire
tampon dépend d'autres requêtes simultanées et les processus du
système d'exploitation, connus uniquement pendant l'exécution
 Les estimations dans les pires des cas supposent qu'aucune donnée n'est
initialement dans la mémoire tampon et que seule la quantité minimale de
mémoire nécessaire pour l'opération est disponible.
• Mais des estimations plus optimistes sont utilisées dans la pratique

Database System Concepts - 7th Edition 15.9 ©Silberschatz, Korth and Sudarshan
 Opération de selection: A=V (r)
 Analyse des fichiers (Scannage)
 Algorithme A1 (recherche linéaire). Analysez chaque bloc de fichier et
testez tous les enregistrements pour voir s'ils satisfont à la condition de
sélection.
• Estimation des coûts = br transferts de blocs+ 1 recherche
 br désigne le nombre de blocs contenant des enregistrements de
la relation r
• Si la sélection porte sur un attribut clé, la recherche peut-être
interrompue.
 coût = (br / 2) transferts de blocs+ 1 recherche
• La recherche linéaire peut être appliquée indépendamment de
 condition de sélection ou
 l'ordre des enregistrements dans le fichier, ou
 disponibilité des index.
 Remarque: la recherche binaire n'a généralement pas de sens si les
données ne sont pas stockées consécutivement
• sauf quand il y a un index disponible,
• et la recherche binaire nécessite plus de recherches que la
recherche d'index

Database System Concepts - 7th Edition 15.10 ©Silberschatz, Korth and Sudarshan
 Sélections à l'aide d'indexes

 Balayage (scannage) d'index - algorithmes de recherche utilisant un

index
• la condition de sélection doit être sur la clé de recherche de l'index.
 A2 (indexes groupés, égalité sur la clé). Récupérer un seul
enregistrement qui satisfait la condition d'égalité correspondante
• Coût = (hi + 1) * (tT + tS) = [hi (tT + tS) + (tT + tS)]
 A3 (indexes groupés, égalité sur non-clé) Récupérez plusieurs
enregistrements.
• Les enregistrements seront sur des blocs consécutifs
 Soit b = nombre de blocs contenant des enregistrements
correspondants
• Coût = hi * (tT + tS) + tS + tT * b

Database System Concepts - 7th Edition 15.11 ©Silberschatz, Korth and Sudarshan
 Sélections à l'aide d'indexes

 A4 (index secondaire, égalité sur clé / non-clé).

• Récupérer un seul enregistrement si la clé de recherche est une
candidate clé
 Coût = (hi + 1) * (tT + tS)
• Récupérer plusieurs enregistrements si la clé de recherche n'est pas
une candidate clé
 chacun des n enregistrements correspondants peuvent être sur un
bloc différent
 Coût = (hi + n) * (tT + tS)
• Peut être très cher!

Database System Concepts - 7th Edition 15.12 ©Silberschatz, Korth and Sudarshan
 Sélections impliquant des comparaisons
 Peut implémenter des sélections de la forme AV (r) ou A  V(r) en utilisant
• un scan linéaire de fichier.
• ou en utilisant des indexes de la manière suivante:
 A5 (index groupé, comparaison). (La relation est triée sur A)
 Pour A  V(r) utilise index pour trouver le premier tuple  v et
balayer la relation séquentiellement à partir de là
 Pour AV (r) scanner la relation séquentiellement jusqu'au premier
tuple> v; ne pas utiliser d'index
 Complexité semblable à A3
 A6 (index secondaire, comparaison).
 Pour A  V(r) utilise l’index pour trouver la première entrée d'index
 v et scannez l'index séquentiellement à partir de là, pour trouver
les pointeurs vers les enregistrements.
 Pour AV (r) scannez seulement les feuilles d'index pour trouver
des pointeurs vers des enregistrements, jusqu'à la première
entrée > v
 Dans les deux cas, récupérez les enregistrements pointés.
 Nécessite une E / S par enregistrement; L'analyse linéaire des
fichiers peut être moins chère!
 Complexité semblable à A4

Database System Concepts - 7th Edition 15.13 ©Silberschatz, Korth and Sudarshan
 Implémentation de sélections complexes
 Conjonction: 1 2. . .n(r)
 A7 (sélection conjonctive en utilisant un index).
• Applicable si quelques conditions ont des indexes disponibles.
 Sélectionnez une combinaison de i et les algorithmes A1 à A7 qui
entraînent le moindre coût pour i (r).
 Testez d'autres conditions sur le tuple après l'avoir récupéré dans la
mémoire tampon.
 A8 (sélection conjonctive en utilisant un index composite).
• Utilisez l'index composite (à plusieurs clés) approprié si disponible.
 A9 (sélection conjonctive par intersection d'identifiants).
• Nécessite des indexes avec des pointeurs d'enregistrement.
 Utilisez l'index correspondant pour chaque condition et prenez
l'intersection de tous les ensembles obtenus de pointeurs
d'enregistrement.
 Ensuite, récupérez les enregistrements du fichier.
 Si certaines conditions n'ont pas d'indexes appropriés, appliquez le test
en mémoire.
Database System Concepts - 7th Edition 15.14 ©Silberschatz, Korth and Sudarshan
 Algorithmes pour les sélections complexes

 Disjonction:1 2 . . .n (r).

 A10 (sélection disjonctive par union d'identifiants).
• Applicable si toutes les conditions ont des indexes disponibles.
 Sinon, utilisez le balayage linéaire.
• Utilisez l'index correspondant pour chaque condition et prenez l'union
de tous les ensembles obtenus de pointeurs d'enregistrement.
• Ensuite, récupérez les enregistrements du fichier
 Négation: (r)
• Utiliser l'analyse linéaire (scannage) sur fichier
• Si très peu d'enregistrements satisfont  et qu'un index est
applicable à 
 Trouvez des enregistrements satisfaisants à l'aide de l'index et
récupérez les non-satisfaisants dans un fichier

Database System Concepts - 7th Edition 15.15 ©Silberschatz, Korth and Sudarshan
 Tri

 Premier algorithme: Nous pouvons construire un index sur la relation,

puis utiliser l'index pour lire la relation dans un ordre trié (ordre logique).
Peut conduire à un accès au bloc de disque pour chaque tuple.
 Algorithme classique: Pour les relations qui tiennent en mémoire, des
techniques de tri interne comme le tri rapide peuvent être utilisées.
• Pour les relations qui ne rentre dans la mémoire, on utilise un tri
externe, par exemple le tri-fusion externe est un bon choix (pour
obtenir un ordre physique).

Database System Concepts - 7th Edition 15.17 ©Silberschatz, Korth and Sudarshan
 Exemple: tri externe à l'aide du tri-fusion

Database System Concepts - 7th Edition 15.18 ©Silberschatz, Korth and Sudarshan
 Tri-fusion externe
M désigne la taille de la mémoire (en blocs).
i stocke le nombre courrant de runs.

1. Créer des runs triés.

Initialiser i = 0 au départ.
Répétez ce qui suit jusqu'à la fin de la relation:
(a) Lire M blocs de la relation en mémoire
(b) Trier les blocs en mémoire
(c) Écrire des données triées dans un "run" Ri sur le disque
(d) incrémenter i

Supposez que la valeur finale de i est N

On a maintenant N runs R1 , …, RN

2. Fusionner tous les runs (diapo suivante) …

Database System Concepts - 7th Edition 15.19 ©Silberschatz, Korth and Sudarshan
 Tri-fusion externe (suite)

2. Fusionner les runs (fusion à N voies). Nous supposons (pour l'instant)

que N < M.
1. Utilisé N blocs de mémoire pour mettre en tampon les entrées et 1
bloc pour tamponner la sortie. Lisez le premier bloc de chaque run
dans sa page tampon.
2. répéter
1. Sélectionnez le premier enregistrement (dans l'ordre de tri)
parmi toutes les pages de tampon
2. Écrivez l'enregistrement dans le tampon de sortie. Si le tampon
de sortie est plein, écrivez-le sur le disque.
3. Supprimez l'enregistrement de sa page de tampon d'entrée.
If la page tampon devient vide then
lire le bloc suivant (le cas échéant) de run dans le tampon.
3. jusqu'à ce que toutes les pages du tampon d'entrée sont vides:

Database System Concepts - 7th Edition 15.20 ©Silberschatz, Korth and Sudarshan
 Tri-fusion externe (suite)

 Si N  M, plusieurs fusions sont requis.

• À chaque passage, des groupes contigus de M - 1 courses sont
fusionnées.
• Une passe réduit le nombre de passages d'un facteur de M -1, et
crée des exécutions plus longues du même facteur.
 Par exemple, si M = 11 et qu'il y a 90 runs, une passe réduit le
nombre d'exécutions à 9, chaque 10 fois la taille des runs
initiales
• Des passes répétées sont effectuées jusqu'à ce que toutes les runs
aient été fusionnées en une seule.

Database System Concepts - 7th Edition 15.21 ©Silberschatz, Korth and Sudarshan
 Tri par fusion externe (suite)

 Analyse de coût:
• 1 bloc par exécution entraîne trop de recherches lors de la fusion
 Utilisez plutôt bb blocs tampons par exécution
 lire écrire bb blocs à la fois
 Peut fusionner M / bb – 1 runs en un seul passage
• Nombre total de passes de fusion requises: log M / bb – 1(br/ M).
• Les transferts de bloc pour la création de l'exécution initiale ainsi que
pour chaque passe sont de 2br
 pour le passage final, on ne compte pas le coût d'écriture
• nous ignorons le coût d'écriture final pour toutes les opérations
car la sortie d'une opération peut être envoyée à l'opération
parent sans être écrite sur le disque
 Ainsi nombre total de transferts de blocs pour le tri externe:
2br (log M / bb – 1 (br / M) + 1)
• Recherche: diapositive suivante

Database System Concepts - 7th Edition 15.22 ©Silberschatz, Korth and Sudarshan
 Tri par fusion externe (suite)

 Coût des recherches

• Pendant la génération de run: on cherche à lire chaque run et on
cherche à écrire chaque run
 2 br / M
• Pendant la phase de fusion
 Avoir besoin 2 br / bb recherche pour chaque passe de fusion
• sauf le dernier qui ne nécessite pas d'écriture
 Nombre total de recherches:
2 br / M + 2 br / bb (logM/ bb – 1(br / M) -1)

Database System Concepts - 7th Edition 15.23 ©Silberschatz, Korth and Sudarshan
 Opération de jointure

 Plusieurs algorithmes différents pour implémenter les jointures

• Jointure en boucles imbriquées
• Jointure en boucles imbriquées à blocs
• Jointure en boucles imbriquées indexée
• Jointure par tri-fusion
• Jointure par hachage
 Choix basé sur l'estimation des coûts
 Les exemples utilisent les informations suivantes
• Nombre d'enregistrements de étudiant: 5 000 takes: 10 000
• Nombre de blocs de étudiant: 100 takes: 400

Database System Concepts - 7th Edition 15.24 ©Silberschatz, Korth and Sudarshan
 Jointure en boucles imbriquées

 Pour calculer la jointure thêta r ⨝  s

for each tuple tr in r do begin
for each tuple ts dans s do begin
tester le pair (tr, ts) pour voir s'ils satisfont à la condition de jointure 
s'ils le font, ajoutez tr • ts au résultat.
end
end
 r s'appelle la relation externe et s la relation interne de la jointure.
 Ne nécessite aucun index et peut être utilisé avec n'importe quel type de condition
de jointure.
 Coûteux car il examine chaque paire de tuples dans les deux relations.

Database System Concepts - 7th Edition 15.25 ©Silberschatz, Korth and Sudarshan
 Jointure en boucles imbriquées (suite)
 Dans le pire des cas, s'il y a suffisamment de mémoire pour contenir un
seul bloc de chaque relation, le coût estimé est
nr  bs + br transferts en bloc, plus nr + br recherches
 Si la plus petite relation tient entièrement dans la mémoire, utilisez-la
comme relation interne.
• Réduit le coût à br + bs transferts de blocs et 2 recherches
 En supposant que l'estimation du coût de disponibilité de la mémoire
dans le pire des cas est
• avec étudiant comme relation extérieure:
 5000  400 + 100 = 2.000.100 transferts en bloc,
 5000 + 100 = 5100 recherches
• avec takes comme relation extérieure
 10000  100 + 400 = 1 000 400 transferts en bloc et 10 400
recherches
 Si une relation plus petite (étudiant) tient entièrement en mémoire, le coût
estimé sera de 500 transferts en bloc.
 L'algorithme de blocage des boucles imbriquées (diapositive suivante)
est préférable.
Database System Concepts - 7th Edition 15.26 ©Silberschatz, Korth and Sudarshan
 Jointure en boucles imbriquées à blocs
 Variante de jointure en boucle imbriquée dans laquelle chaque
bloc de relation interne est associé à chaque bloc de relation
externe.
for each bloc Br of r do begin
for each bloc Bs of s begin
for each tuple tr in Br begin
for each tuple ts in Bs begin
Vérifier si (tr, ts) satisfait la condition
de jointure
si vrai, ajoutez tr • ts au résultat.
end
end
end
end

Database System Concepts - 7th Edition 15.27 ©Silberschatz, Korth and Sudarshan
 Jointure en boucles imbriquées indexée

 Les recherches d'index peuvent remplacer les analyses de fichiers si

• La jointure est un équi-joint ou jointure naturelle et
• un index est disponible sur la relation interne s de la jointure
 Peut construire un index juste pour calculer une jointure.
 Pour chaque tuple tr dans la relation extérieure r, utiliser l'index pour
rechercher des tuples dans s qui satisfont la condition de jointure
avec tuple tr.
 Dans le pire des cas: la mémoire tampon a de l'espace pour une
seule page de r, et, pour chaque tuple dans r, nous effectuons une
recherche d'index sur s.
 Coût de la jointure: br (tT + tS) + nr  c
• Où c est le coût de la traversée de l'index et de la récupération de
tous les tuples correspondantes dans s pour un tuple de r
• c peut être estimé comme le coût d'une seule sélection sur s en
utilisant la condition de jointure.
 Si des indexes sont disponibles sur les attributs de jointure des deux
relations r et s, utilisez la relation avec moins de tuples comme
relation externe.

Database System Concepts - 7th Edition 15.29 ©Silberschatz, Korth and Sudarshan
 Jointure par tri-fusion

1. Trier les deux relations sur leur attribut de jointure (si ce n'est déjà fait sur la
jointure
les attributs).
2. Fusionner les relations triées pour former les jointures.
1. L'étape de jointure est similaire à l'étape de fusion de l'algorithme de tri-
fusion.
2.– La principale différence est la gestion des valeurs dupliquées dans
l'attribut de jointure. Les tuples avec la même valeur sur l'attribut de
jointure doivent être mis en correspondance.

3. Algorithme détaillé dans le livre

Database System Concepts - 7th Edition 15.31 ©Silberschatz, Korth and Sudarshan
 Jointure par tri-fusion (suite)

 Ne peut être utilisé que pour équi-joints et joints naturels

 Chaque bloc ne doit être lu qu'une seule fois (en supposant que tous les
tuples d'une valeur donnée des attributs de jointure tiennent en
mémoire0
 Ainsi, le coût de la jointure par fusion est:
br + bs transferts de blocs + br / bb + bs / bb recherches
+ le coût du tri si les relations ne sont pas triées.
 Jointure par tri-fusion hybride *: Si une relation est triée et que l'autre
a un index secondaire B+-tree sur l'attribut de jointure
• Fusionner la relation triée avec les entrées dans les feuilles de
l’arbre B+.
• Trier le résultat sur les adresses de la relation non triée.
• Analyser la relation non triée dans l'ordre des adresses physiques
et fusionner avec le résultat précédent, pour remplacer les adresses
par les tuples réels.

(*) Voir tutoriel

Database System Concepts - 7th Edition 15.32 ©Silberschatz, Korth and Sudarshan
 Jointure par hachage

 Applicable pour équi-joints et joints naturels.

 Une fonction de hachage h est utilisé pour partitionner les tuples des
deux relations
 h reparti JoinAttrs valeurs à {0, 1, ..., n}, où JoinAttrs désigne les attributs
communs de r et s utilisé dans la jointure naturelle.
• r0, r1,. . .,rn dénotent des partitions de r tuples
 Chaque tuple tr  r est mis en partition ri où i = h (tr [JoinAttrs]).
• r0,, r1. . .,rn désigne des partitions de s tuples
 Chaque tuple ts s est mis en partition si, où i = h (ts [JoinAttrs])
.
 Remarque: Dans le livre, Figure 12.10 ri est noté Hri, si est noté Hsi et
n est noté nh.

Database System Concepts - 7th Edition 15.33 ©Silberschatz, Korth and Sudarshan
 Hash-Join (suite)

Database System Concepts - 7th Edition 15.34 ©Silberschatz, Korth and Sudarshan
 Hash-Join*
Original
Relation OUTPUT Partitions
1

Partitioner les deux 1

INPUT 2
relations avec une fonction hash 2
function
de hachage h: les tuples
dans la partition i de r ne
... h M-1

correspondront qu’aux M-1

tuples dans la partition i de Disk M main memory buffers Disk
s. si
Partitions
Lire une partition de r et la of s & r Join Result
hacher avec h2 (<> h!). Hash table for partition
hash si
Scaner la partition fn
correspondante de s pour h2
trouver le résultat.
h2

Input buffer Output

(*): © Ramakrishnan & for ri buffer
Gherkhe
Disk M main memory buffers Disk
Database System Concepts - 7th Edition 15.36 ©Silberschatz, Korth and Sudarshan
 Algorithme de jointure par hachage

Le hash-join de r et s est calculé comme suit.

1. Partitionner la relation s en utilisant la fonction de hachage h. Lors du
partitionnement d'une relation, un bloc de mémoire est réservé
comme tampon de sortie pour chaque partition.
2. Partitionner r de la même façon.
3. Pour chaque i:
(a) enregistrer si en mémoire et créez un index de hachage en
mémoire à l'aide de l'attribut join. Cet index de hachage utilise
une fonction de hachage différente de la précédente h.
(b) Lisez les tuples dans ri à partir du disque un par un. Pour chaque
tuple tr localiser chaque tuple correspondant ts dans si en utilisant
l'index de hachage en mémoire. Sortie: concaténation de leurs
attributs.

Relation s s'appelle build input et r s'appelle le probe input.

Database System Concepts - 7th Edition 15.37 ©Silberschatz, Korth and Sudarshan
 Algorithme Hash-Join (suite)

 La valeur n et la fonction de hachage h est choisi de telle sorte que

chaque si devrait tenir dans la mémoire.
• Typiquement n est choisi comme bs/ M * f où f est un "facteur de
fudge", généralement autour de 1,2
• Les partitions de relation de sonde si n'a pas besoin de rentrer dans
la mémoire
 Partitionnement récursif requis si nombre de partitions n est supérieur
au nombre de pages M de mémoire.
• au lieu de partitionner n moyens, utiliser M - 1 partitions pour s
• Partitionner davantage le M - 1 partitions utilisant une fonction de
hachage différente
• Utilisez la même méthode de partitionnement sur r
• Rarement requis: par exemple, avec une taille de bloc de 4 Ko, le
partitionnement récursif n'est pas nécessaire pour des relations de
<1 Go avec une taille de mémoire de 2 Mo, ou des relations de <36
Go avec une mémoire de 12 Mo

Database System Concepts - 7th Edition 15.38 ©Silberschatz, Korth and Sudarshan
 Gestion des débordements
 On dit que le partitionnement est biaisé si certaines partitions ont
beaucoup plus de tuples que d'autres
 Débordement de la table de hachage se produit dans la partition si si si
ne rentre pas dans la mémoire. Les raisons pourraient être
• Nombreux tuples en s avec la même valeur pour les attributs de
jointure.
• Mauvaise fonction de hachage.
 Résolution de débordement peut être fait en phase de build
• Partition si est ensuite partitionné en utilisant une fonction de hachage
différente.
• Partition ri doit être partitionné de manière similaire.
 Éviter un débordement effectue le partitionnement avec soin pour éviter
les débordements pendant la phase de construction
• Par exemple, la relation de construction de partition en plusieurs
partitions, puis les combiner
 Les deux approches échouent avec un grand nombre de doublons
• Option de secours: utilisez la jointure de boucles imbriquées par blocs
sur les partitions débordées
Database System Concepts - 7th Edition 15.39 ©Silberschatz, Korth and Sudarshan
 Coût de Hash-Join

 Si le partitionnement récursif n'est pas requis: le coût de la jointure par

hachage est
3 (br + bs) +4  nh transferts en bloc +
2 (br / bb + bs / bb) recherches
 Si un partitionnement récursif est requis:
• nombre de passes nécessaires pour la relation de partitionnement
s pour M blocs est
logM/ bb – 1(bs/ M) 
• Il vaut mieux choisir la relation la plus petite comme la relation de
build.
• L'estimation du coût total est:

2(br + bs) lobM/ bb – 1(bs/ M)  + br + bs transferts en bloc +

2 (br / bb + bs / bb) logM/ bb – 1(bs/ M)  recherches
 Si toutes les entrées de la relation build peut être sauvegardé dans la
mémoire principale, aucun partitionnement n'est requis
• L'estimation des coûts descend à br + bs.
Database System Concepts - 7th Edition 15.40 ©Silberschatz, Korth and Sudarshan
 Jointures complexes

 Jointure d’une condition conjonctive:

r ⨝ 1  2 ...   n s
• Soit utiliser des boucles imbriquées / bloquer les boucles imbriquées,
soit
• Calculez le résultat de l'une des jointures les plus simples r ⨝ i s
 le résultat final comprend les tuples du résultat intermédiaire qui
satisfont aux conditions restantes
1 . . .  i -1  i+1 . . .  n
 Jointure d’une condition disjonctive
r ⨝ 1  2  ...  n s
• Soit utiliser des boucles imbriquées / bloquer les boucles imbriquées,
soit
• Calculer comme l'union des enregistrements dans les jointures
individuelles r ⨝ i s:
(r ⨝ 1 s)  (r ⨝ 2 s) . . .  (r ⨝ n s)

Database System Concepts - 7th Edition 15.43 ©Silberschatz, Korth and Sudarshan
 Autres opérations

 Élimination des doublons peut être implémenté par hachage ou tri.

• Lors du tri, les doublons seront adjacents les uns aux autres, et
tous les ensembles de doublons sauf un peuvent être supprimés.
• Optimisation: les doublons peuvent être supprimés lors de la
génération de runs ainsi qu'aux étapes de fusion intermédiaires
dans le tri-fusion externe.
• Le hachage est similaire - les doublons entreront dans le même
compartiment.
 Projection:
• effectuer une projection sur chaque tuple
• suivi par l'élimination des doublons.

Database System Concepts - 7th Edition 15.45 ©Silberschatz, Korth and Sudarshan
 Autres opérations: agrégation

 Agrégation peut être calculée d'une manière similaire à l'élimination

des doublons.
• Tri ou hachage peut être utilisé pour rassembler les tuples du
même groupe, puis les fonctions d'agrégation peuvent être
appliquées à chaque groupe.
• Optimisation: agrégation partielle
 combiner des tuples dans le même groupe pendant la
génération de runs et les fusions intermédiaires du tri externe
pour calculer des valeurs d'agrégat partielles
 Pour count, min, max, sum: conservez les valeurs agrégées
sur les tuples trouvés jusqu'à présent dans le groupe.
• Lorsque vous combinez un agrégat partiel pour le nombre,
additionnez les agrégats partiels
 Pour avg, conservez la somme et le nombre, et divisez la
somme par le nombre à la fin

Database System Concepts - 7th Edition 15.46 ©Silberschatz, Korth and Sudarshan
 Autres opérations: opérations sur les ensembles

 Operations sur les ensembles (,  et ): peut soit utiliser une
variante de la jointure à tri-fusion, soit une variante de jointure par
hachage.
 Utiliser le hachage:
1. Partitionner les deux relations en utilisant la même fonction de
hachage
2. Traitez chaque partition i comme suit.
1. À l'aide d'une fonction de hachage différente, créez un index de
hachage en mémoire sur ri.
2. Traiter si comme suit
• r  s:
1. Ajouter des tuples dans si à l'index de hachage s'ils ne
s'y trouvent pas déjà.
2. À la fin de si ajoutez les tuples de l'index de hachage au
résultat.

Database System Concepts - 7th Edition 15.47 ©Silberschatz, Korth and Sudarshan
 Autres opérations: opérations sur les ensembles

 Utiliser le hachage:
1. Partitionner r et s comme pour l’union,
2. comme avant, traitez chaque partition comme suit
1. créer un index de hachage sur ri
2. Traiter si comme suit
• r  s:
1. sortie de tuples dans si au résultat s'ils sont déjà
présents dans l'index de hachage
• r - s:
1. pour chaque tuple dans si, s'il est présent dans l'index de
hachage, supprimez-le de l'index.
2. À la fin de si ajoutez les tuples restants dans l'index de
hachage au résultat.

Database System Concepts - 7th Edition 15.48 ©Silberschatz, Korth and Sudarshan
 Autres opérations: jointure externe

 La jointure externe peut être calculée soit comme suit:

• Une jointure suivie de l'ajout de tuples non participants remplis de
null.
• En modifiant les algorithmes de jointure.
 Modification de la jointure à tri-fusion pour calculer r ⟕ s
• Dans r ⟕ s, les tuples non participants sont ceux de r - r(r ⨝ s)
• Modifier la jointure à tri-fusion pour calculer r ⟕ s:
 Lors de la fusion, pour chaque tuple tr de r qui ne
correspondent à aucun tuple dans s, les tr rembourré avec des
nuls.
• La jointure externe droite et la jointure externe complète peuvent
être calculées de la même manière.

Database System Concepts - 7th Edition 15.50 ©Silberschatz, Korth and Sudarshan
 Évaluation des expressions

 Jusqu'à présent: nous avons vu des algorithmes pour des opérations

individuelles
 Quid des expressions complexes qui comprennent plusieurs
opérateurs ?
 Alternatives pour évaluer une arbre d'expression entière
• Matérialisation: générer les résultats d'une expression dont les
entrées sont des relations ou sont déjà calculées, matérialiser
(stocker) sur le disque. Répéter.
• Pipeline: transmettre les tuples aux opérations parents même
lorsqu'une opération est en cours d'exécution
 Nous étudions plus en détail les alternatives ci-dessus

Database System Concepts - 7th Edition 15.52 ©Silberschatz, Korth and Sudarshan
 Matérialisation

 Évaluation matérialisée: évaluer une opération à la fois, en

commençant par le niveau le plus bas. Utilisez les résultats
intermédiaires matérialisés dans des relations temporaires pour
évaluer les opérations de niveau suivant.
 Par exemple, dans la figure ci-dessous, calculer et stocker
 building "Watson " (department )
puis calculez la jointure du résultat sauvegardé avec instructor, et
enfin calculer la projection sur Name.

Database System Concepts - 7th Edition 15.53 ©Silberschatz, Korth and Sudarshan
 Matérialisation (suite)

 L'évaluation matérialisée est toujours applicable

 Le coût d'écriture des résultats sur le disque et de leur lecture peut être
assez élevé
• Nos formules de coût pour les opérations ignorent le coût d'écriture
des résultats sur le disque, donc
 Coût global = somme des coûts des opérations individuelles +
coût d'écriture des résultats intermédiaires sur le disque

 Double tampon: utilisez deux tampons de sortie pour chaque

opération, quand l'un est plein, écrivez-le sur le disque pendant que
l'autre se remplit
• Permet le chevauchement des écritures sur disque avec le calcul et
réduit le temps d'exécution

Database System Concepts - 7th Edition 15.54 ©Silberschatz, Korth and Sudarshan
 Pipeline

 Évaluation pipelinée: évalue plusieurs opérations simultanément, en

transmettant les résultats d'une opération à la suivante.
 Par exemple, dans l’arbre de l'expression précédente, ne pas stocker le
résultat de
 building"Watson" (department )
• à la place, passez directement les tuples à la jointure… ne pas
stocker le résultat de la jointure, passer les tuples directement à la
projection.
 Beaucoup moins cher que la matérialisation: pas besoin de stocker une
relation temporaire au disque.
 Le pipelining n'est pas toujours possible - par exemple, tri, jointure par
hachage.
 Pour que le pipelining soit efficace, utilisez des algorithmes d'évaluation
qui génèrent des tuples de sortie même lorsque des tuples sont reçus
pour les entrées de l'opération.
 Les pipelines peuvent être exécutés de deux manières: demand-driven
et producer-driven

Database System Concepts - 7th Edition 15.55 ©Silberschatz, Korth and Sudarshan
 Pipeline (suite)

 Dans demand-driven ou lazy evaluation

• le système demande à plusieurs reprises le tuple suivant de
l'opération de niveau supérieur.
• Chaque opération demande le prochain tuple des opérations enfants
selon les besoins, afin de sortir son prochain tuple.
• Entre les appels, le fonctionnement doit maintenir l’état du calcul
(state) , ainsi il sait quoi retourner ensuite.
 Dans producer-driven ou eager pipelining
• Les opérateurs produisent des tuples avec impatience et les
transmettent à leurs parents
 Tampon maintenu entre les opérateurs, l'enfant met les tuples
dans le tampon, le parent supprime les tuples du tampon
 Si le tampon est plein, l'enfant attend qu'il y ait de l'espace dans
le tampon, puis génère plus de tuples
• Le système planifie les opérations qui ont de l'espace dans la
mémoire tampon de sortie et peuvent traiter plus de tuples d'entrée
 Nom alternatif: pull et push modèles de pipelining

Database System Concepts - 7th Edition 15.56 ©Silberschatz, Korth and Sudarshan
 Pipeline (suite)

 Implémentation de pipelining demande-driven

• Chaque opération est implémentée comme un itérateur sur des
opérations suivantes
 open()
• Par exemple, analyse de fichiers: initialiser l'analyse de
fichiers
 état: pointeur vers le début du fichier
• Par exemple, fusionner la jointure: trier les relations;
 état: pointeurs vers le début des relations triées
 next()
• Par exemple, pour l'analyse de fichiers: sortie du tuple
suivant, et avance et stockage du pointeur de fichier
• Par exemple, pour la jointure par fusion: continuez la fusion
depuis l'état antérieur jusqu'à ce que le prochain tuple de
sortie soit trouvé. Enregistrez les pointeurs comme état
d'itérateur.
 close()

Database System Concepts - 7th Edition 15.57 ©Silberschatz, Korth and Sudarshan
 Opérations bloquantes

 Opérations bloquantes: ne peut générer aucune sortie tant que toutes

les entrées ne sont pas consommées
• Par exemple: tri, agrégation,…
 Mais peut souvent consommer des entrées d'un pipeline, ou produire
des sorties vers un pipeline
 Idée clé: les opérations bloquantes ont souvent deux sous-opérations
• Par exemple, pour le tri: exécuter la génération des runs et la fusion
• Pour la jointure par hachage: partitionnement et build-probe
 Traitez-les comme des opérations séparées

Database System Concepts - 7th Edition 15.58 ©Silberschatz, Korth and Sudarshan
 Étapes du pipeline

 Étapes du pipeline:
• Toutes les opérations d'une étape s'exécutent simultanément
• Une étape ne peut démarrer qu'après la fin de l'exécution des
étapes précédentes

Database System Concepts - 7th Edition 15.59 ©Silberschatz, Korth and Sudarshan
 Pipeline pour de flux-continu des données

 Flux de données
• Données entrant dans la base de données de manière continue
• Par exemple, réseaux de capteurs, clics d'utilisateurs,…
 Requêtes continues
• Les résultats sont mis à jour lorsque les données en continu entrent
dans la base de données
• L'agrégation sur les fenêtres est souvent utilisée

 Besoin d'utiliser des algorithmes de traitement en pipeline

• Les ponctuations utilisé pour déduire quand toutes les données
d'une fenêtre ont été reçues

Database System Concepts - 7th Edition 15.61 ©Silberschatz, Korth and Sudarshan
 Fin du chapitre 15

Database System Concepts - 7th Edition 15.64 ©Silberschatz, Korth and Sudarshan