∈"> ∉"> ] >
Avant de s'intéresser à l'évaluation complète d'une requête, on étudie l'évaluation des opérateurs et leur coût respectifs
Considérons :
SELECT *
FROM people,role
WHERE people.pid = role.pid;
Opération fondamentale utilisée
par toutes les applications BD.
L'AR nous dit que R &join; S = σ=(R x
T), mais c'est très inefficace, on veut optimiser ce cas!
On suppose dans la suite M enregistrements dans R, PR enregistrements/page, N enregistrement dans S, PS enregistrements/page.
On pose pour les exemples: M=1000, N=500, PR=120, PS=100
L'attribut commun est a.
Le coût est toujours le nombre d'E/S (en ignorant l'écriture du résultat)
On effectue une double boucle imbriquée:
for each record r ∈ R do
for each record s ∈ S do
if r.a = s.a then res += r &join; s #jointure élémentaire de
done #2 enregistrements
done
Pour chaque enregistrement de la relation externe (R) on
scanne entièrement la relation interne (S)
Coût: M + PR * M * N
Exemple: 1000 + 120*1000*500 = 60 001 000 E/S!
On effectue une double boucle imbriquée:
for each page P ∈ R do
for each page Q ∈ S do
res += P &join; Q #jointure entre 2 pages
done # peut être faite de manière simple
done
Pour chaque page de la relation externe (R) on scanne entièrement la relation interne (S)
Coût: M + M * N
Exemple: 1000 + 1000*500 = 501 000 E/S!
Optimisation: mettre la relation la plus petite à
l'extérieur:
500 + 500*1000 = 500 500
On effectue une double boucle imbriquée:
for each record r ∈ R do
for each record s ∈ S where r.a = s.a do
#l'index doit permettre un accès rapide à la colonne a
res += r &join; s
done
done
On exploite l'existence d'un index sur l'une des relation pour en faire la relation interne.
Coût: M + PR * M * (coût d'accès index + coût
index ↦ données)
Plusieurs variantes: B+-tree/Hash-index, groupant/non-groupant,…
On exploite le buffer (de taille B+2 pages, B = 10) de la manière suivante:
for each block b of size B ∈ R do
for each page Q ∈ S do
res += b &join; Q #en utilisant la méthode simple
done
done
Coût: M + N * ⌈M/B⌉
Exemple: 1000 + 500 * 1000/10 = 51 000
Variante: blocs sur R et S
Idée: « l'intersection » de deux listes est aisée si les deux listes sont triées
sort R on a as Rs
sort S on a as Ss
r := Rs.next(); #On suppose R et S non vides
s := Ss.next(); #Sinon jointure vide directement
while Rs and Ss are not empty do
while r.a != s.a do #avance jusqu'à trouver la même valeur
while r.a < s.a do
if Rs.hasNext() then r:= Rs.next() else finished
done
while s.a < r.a do
if Ss.hasNext() then s:= Ss.next() else finished
done
done
val := r.a #on prend la liste des enregistrements
#ayant la même valeur d'attribut de jointure
P, Q := empty pages
while r.a = val do P += r; r:= Rs.next() done
while s.a = val do Q += s; s:= Ss.next() done
res += P &join; Q
done
Coût: M·log2 M + N·log2 N + M + N
Exemple: 1000* (1+log2 1000) + 500 *
(1+log2 500) = 15492
Le tri n'est pas toujours nécessaire:
On choisit une fonction de hachage h et on partitionne R selon h(r.a) pour obtenir K partitions
On partitionne S selon h(s.a) pour obtenir K partitions
K choisi en fonction de la taille du buffer
Coût: 2(M+N) + M+N (pourquoi ?)
Taux de sélectivité d'une condition φ (ou d'une requête) pour une relation donnée:
# d'enregistrement
sélectionnés
#d'enregistrements
Le choix de certains algorithmes dépend de la sélectivité
On ne connait la « vraie » valeur de la sélectivité qu'après avoir évalué la requête
On utilise des statistiques sur les relations pour tenter une approximation du taux de sélectivité
Le SGBD concerve, entre autres, les statistiques suivantes pour chaque relations R:
Sélection simple, égalité avec une constante : Scan ou Index (si groupant)
Sélection simple avec index non groupant : Index + tri des adresses de pages, parcours ordonné. Très efficace si l'ensemble des adresses à trier tiens en mémoire
Sélection généralisés, deux approches:
Plusieurs techniques :
On parle ici de la projection, π de l'algèbre relationnelle, donc avec élimination des doublons :
SELECT DISTINCT a,b FROM t
Repose sur l'utilisation de deux fonctions de hachage
h et g distinctes
Permet d'effectuer « DISTINCT» sans tri!
L'algèbre relationnelle est simple (quelques opérateurs pour exprimer l'ensemble des requêtes)
Chaque opérateur peut être réalisé de plusieurs manières différentes, avec différents compromis
Tout celà est encore complexifié quand on considère les compositions d'opérateurs (prochain cours)
Tout est encore plus complexifié si on considère que le SGBD gère plusieurs requêtes en parallèle (hors programme)
En pratique, une part importante du moteur de requête des SGBD est l'implantation d'heuristiques pour faire les meilleurs choix (ou plutôt, les moins pires).