From: Kim Nguyễn Date: Mon, 10 Feb 2014 10:58:42 +0000 (+0100) Subject: Ajout cours 4. X-Git-Url: http://git.nguyen.vg/gitweb/?p=hacks%2FsimpleWebSlides.git;a=commitdiff_plain;h=1420d1fffe006dda548df75b1d6837f9f802af02 Ajout cours 4. --- diff --git a/bd/bd04.xhtml b/bd/bd04.xhtml new file mode 100644 index 0000000..127462c --- /dev/null +++ b/bd/bd04.xhtml @@ -0,0 +1,392 @@ + +â"> + â"> + + +] + > + + + Optimisation des opÃ©rateurs + + + + + + + + + + + + + + + + + + + + +

Bases de donnÃ©es

Polytech Paris-Sud

Apprentis 4^Ã¨me annÃ©e

Cours 4 : Optimisation des opÃ©rateurs

+ kn@lri.fr
+ http://www.lri.fr/~kn +

+ +

Motivation

Principe d'Ã©valuation d'une requÃªte

Parsing de la requÃªte
Traduction en arbre + d'opÃ©rateurs de l'algÃ¨bre + relationnelle (π, + σ, â¨, â¦ )
Optimisation : +
1. GÃ©nÃ©ration de plans + d'Ã©valuation (en + rÃ©ordonnant les opÃ©rations Ã©lÃ©mentaires)
2. Estimation du coÃ»t de chacun des + plans (en fonction du coÃ»t + des opÃ©rations Ã©lÃ©mentaires)
3. Choix du plan le plus efficace
+
Ãvaluation du plan choisi
(Ãventuellement mise Ã jour des statistiques)

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

Algorithmes de jointure

Jointure naturelle sur une colonne

ConsidÃ©rons :

          SELECT *
+          FROM people,role
+          WHERE people.pid = role.pid;
+

OpÃ©reeation 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, + P_R enregistrements/page, N enregistrement dans S, + P_S enregistrements/page. +

On pose pour les exemples: M=1000, N=500, P_R=120, P_S=100

L'attribut commun est a.

Le coÃ»t est toujours le nombre d'E/S (en ignorant l'Ã©criture + du rÃ©sultat)

Jointure itÃ©rative simple

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 + P_R * M * N
+ Exemple: 1000 + 120*1000*500 = 60 001 000 E/S!

Jointure itÃ©rative page Ã page

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 +

Jointure itÃ©rative avec index

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 + P_R * M * (coÃ»t d'accÃ¨s index + coÃ»t + index ↦ donnÃ©es)
+ Plusieurs variantes: B+-tree/Hash-index, groupant/non-groupant,â¦ +

Jointure par bloc (avec pages bufferisÃ©es)

On exploite le buffer (de taille B+2 pages, B = 10) de la + maniÃ¨re suivante:

1 page du buffer pour l'Ã©criture du rÃ©sultat
1 page du buffer pour la relation interne (S)
B pages du buffer pour la relation externe


+      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 +

+ +

Jointure par tri-fusion 1/2

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
+

Jointure par tri & fusion 2/2

CoÃ»t: MÂ·log₂ M + NÂ·log₂ N + M + N
+ Exemple: 1000* (1+log₂ 1000) + 500 * + (1+log₂ 500) = 15492 +

Le tri n'est pas toujours nÃ©cessaire:

si on a un index de type B+-tree sur l'attribut de + jointure (pour l'une des relations)
si R ou S (ou les deux) sont dÃ©jÃ le rÃ©sultat de tris + (ORDER BY)

Jointure par hachage

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 ?)

Jointures gÃ©nÃ©ralisÃ©es

ÃgalitÃ© sur plusieurs attributs (R.a = S.a AND R.b = + S.b) : +
- Jointure itÃ©rative par index: on peut crÃ©er un index + pour S sur (a,b) ou utiliser des indexes existants sur l'un + ou l'autre
- On peut aussi utiliser jointure par tri-fusion et + hachage en utilisant (a,b) comme clÃ© de tri/hachage
+
conditions d'inÃ©galitÃ©: +
- Pour les jointures par index, il faut un arbre + B+ groupant (sinon surcout pour aller chercher les + donnÃ©es) +
- Jointure par tri-fusion et hachage impossible
- Jointure itÃ©rative par bloc est la meilleure option en gÃ©nÃ©ral
+

Autres opÃ©rateurs

SelectivitÃ©

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Ã©

Statistiques sur les relations

Le SGBD concerve, entre autres, les statistiques + suivantes pour chaque relations R:

Nombre d'enregistrements (N), taille d'un + enregistrement, nombre d'attributs/page (P)
Nombre de pages de la relation (les pages ne sont pas + toutes remplies de maniÃ¨re optimale)
V(a) : nombre de valeurs distinctes pour l'attribut a + (dans la relation R)
Estimation de selectivitÃ© pour l'attribut a: V(a)/N
Profondeur pour les arbres B+
Nombre de page pour les feuilles d'un arbre B+
Nombre de valeurs distinctes pour la clÃ© de recherche d'un index

SÃ©lection

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

On choisit une sous-condition (qui concerne le moins de + pages = la plus sÃ©lective) et on applique les autres + sous-conditions au rÃ©sultat intermÃ©diaire
Si on a deux sous-conditions Â« AND Â» avec 2 indexes (types 2 ou 3) + sÃ©parÃ©s, calcul des ensembles de rid et intersection + des rÃ©sultats. On applique ensuite les autres critÃ¨res. +

Plusieurs techniques :

Utilisation d'un index (type B+-tree) si groupant ou si + coÃ»t d'accÃ¨s au donnÃ©es Â« raisonnable Â» (rÃ©sultat dans l'index + ou peu de rÃ©sultats + accÃ¨s aux donnÃ©es)

Projection

+ SELECT DISTINCT a,b FROM t + +

Si index sur (a,b) disponible, utilisation + directe de l'index
Sinon tri et projection durant la phase de tri
Double partitionnement par hachage

Double partitionnement

Repose sur l'utilisation de deux fonctions de hachage + h et g ~~distinctes~~

On partitionne R en K partitions en + utilisant h
En suite pour chaque partition entre 1 et K, on crÃ©e une + table de hachage en mÃ©moire (avec g comme fonction) + pour pour Ã©liminer les doublons de la partition

Permet d'effectuer Â« DISTINCTÂ» sans tri!

UNION DISTINCT et EXCEPT sont + similaires. 2 approches: +
1. Par tri. On tri les deux relations sur tous les + attributs et on fusionne en Ã©liminant les doublons. RÃ©sultat + triÃ©
2. Par hachage. Technique du double partitionnement. On + partitionne R et S avec h. Pour chaque partition + de S et R, on ajoute les Ã©lÃ©ments dans une table H, en + Ã©liminant les doublons
+

Sans GROUP BY: +
- En gÃ©nÃ©ral, il faut faire un scan de la + relation
- Si les attributs agrÃ©gÃ©s sont dans un index, on peut + faire un scan d'index uniquement (en espÃ©rant que l'index + est plus petit)
+
Avec GROUP BY: identique au cas sans GROUP + BY mais tri prÃ©alable pour dÃ©terminer les groupes, et + scan Â« groupe par groupe Â» pour calculer la fonction + d'agrÃ©gat

+ +

Conclusion

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).

+ + diff --git a/bd/btree_index_00.svg b/bd/btree_index_00.svg new file mode 100644 index 0000000..0df02f0 --- /dev/null +++ b/bd/btree_index_00.svg @@ -0,0 +1,123 @@ + + + + diff --git a/bd/btree_index_01.svg b/bd/btree_index_01.svg new file mode 100644 index 0000000..7d5e9da --- /dev/null +++ b/bd/btree_index_01.svg @@ -0,0 +1,168 @@ + + + + diff --git a/bd/btree_index_02.svg b/bd/btree_index_02.svg new file mode 100644 index 0000000..e320a82 --- /dev/null +++ b/bd/btree_index_02.svg @@ -0,0 +1,382 @@ + + + + diff --git a/bd/btree_index_03.svg b/bd/btree_index_03.svg new file mode 100644 index 0000000..e3292a8 --- /dev/null +++ b/bd/btree_index_03.svg @@ -0,0 +1,393 @@ + + + + diff --git a/bd/btree_index_04.svg b/bd/btree_index_04.svg new file mode 100644 index 0000000..6f9b15e --- /dev/null +++ b/bd/btree_index_04.svg @@ -0,0 +1,558 @@ + + + + diff --git a/bd/btree_index_05.svg b/bd/btree_index_05.svg new file mode 100644 index 0000000..7f30c4a --- /dev/null +++ b/bd/btree_index_05.svg @@ -0,0 +1,851 @@ + + + + diff --git a/bd/btree_index_06.svg b/bd/btree_index_06.svg new file mode 100644 index 0000000..67963c7 --- /dev/null +++ b/bd/btree_index_06.svg @@ -0,0 +1,971 @@ + + + + diff --git a/bd/btree_index_07.svg b/bd/btree_index_07.svg new file mode 100644 index 0000000..a2354ef --- /dev/null +++ b/bd/btree_index_07.svg @@ -0,0 +1,1265 @@ + + + + diff --git a/bd/btree_index_08.svg b/bd/btree_index_08.svg new file mode 100644 index 0000000..b33a681 --- /dev/null +++ b/bd/btree_index_08.svg @@ -0,0 +1,836 @@ + + + + diff --git a/bd/btree_index_09.svg b/bd/btree_index_09.svg new file mode 100644 index 0000000..3a5444e --- /dev/null +++ b/bd/btree_index_09.svg @@ -0,0 +1,820 @@ + + + + diff --git a/bd/btree_index_10.pdf b/bd/btree_index_10.pdf new file mode 100644 index 0000000..244eaf1 Binary files /dev/null and b/bd/btree_index_10.pdf differ diff --git a/bd/btree_index_10.svg b/bd/btree_index_10.svg new file mode 100644 index 0000000..cd8b9d7 --- /dev/null +++ b/bd/btree_index_10.svg @@ -0,0 +1,736 @@ + + + + diff --git a/bd/btree_index_simple.svg b/bd/btree_index_simple.svg new file mode 100644 index 0000000..3e112b5 --- /dev/null +++ b/bd/btree_index_simple.svg @@ -0,0 +1,659 @@ + + + + diff --git a/bd/hash_index_01.pdf b/bd/hash_index_01.pdf new file mode 100644 index 0000000..e30b194 Binary files /dev/null and b/bd/hash_index_01.pdf differ diff --git a/bd/hash_index_01.svg b/bd/hash_index_01.svg new file mode 100644 index 0000000..635f7ff --- /dev/null +++ b/bd/hash_index_01.svg @@ -0,0 +1,463 @@ + + + + diff --git a/bd/hash_index_02.svg b/bd/hash_index_02.svg new file mode 100644 index 0000000..c13b04c --- /dev/null +++ b/bd/hash_index_02.svg @@ -0,0 +1,535 @@ + + + + diff --git a/bd/hash_index_03.svg b/bd/hash_index_03.svg new file mode 100644 index 0000000..dad4006 --- /dev/null +++ b/bd/hash_index_03.svg @@ -0,0 +1,542 @@ + + + + diff --git a/bd/hash_index_04.svg b/bd/hash_index_04.svg new file mode 100644 index 0000000..5871382 --- /dev/null +++ b/bd/hash_index_04.svg @@ -0,0 +1,622 @@ + + + + diff --git a/bd/hash_index_simple.svg b/bd/hash_index_simple.svg new file mode 100644 index 0000000..e927456 --- /dev/null +++ b/bd/hash_index_simple.svg @@ -0,0 +1,232 @@ + + + + diff --git a/bd/hash_join.svg b/bd/hash_join.svg new file mode 100644 index 0000000..22bb265 --- /dev/null +++ b/bd/hash_join.svg @@ -0,0 +1,683 @@ + + + + diff --git a/bd/hash_partition.svg b/bd/hash_partition.svg new file mode 100644 index 0000000..f94f877 --- /dev/null +++ b/bd/hash_partition.svg @@ -0,0 +1,607 @@ + + + + diff --git a/bd/pdf/bd04.pdf b/bd/pdf/bd04.pdf new file mode 100644 index 0000000..5440b35 Binary files /dev/null and b/bd/pdf/bd04.pdf differ diff --git a/bd/pdf/bd04_print.pdf b/bd/pdf/bd04_print.pdf new file mode 100644 index 0000000..c1b9a9f Binary files /dev/null and b/bd/pdf/bd04_print.pdf differ diff --git a/bd/sorted_file_simple.svg b/bd/sorted_file_simple.svg new file mode 100644 index 0000000..7c1020d --- /dev/null +++ b/bd/sorted_file_simple.svg @@ -0,0 +1,337 @@ + + + +

Bases de donnÃ©es

Polytech Paris-Sud

Apprentis 4^Ã¨me annÃ©e

Cours 4 : Optimisation des opÃ©rateurs

Motivation

Principe d'Ã©valuation d'une requÃªte

Algorithmes de jointure

Jointure naturelle sur une colonne

Jointure itÃ©rative simple

Jointure itÃ©rative page Ã page

Jointure itÃ©rative avec index

Jointure par bloc (avec pages bufferisÃ©es)

Jointure par tri-fusion 1/2

Jointure par tri & fusion 2/2

Jointure par hachage

Jointures gÃ©nÃ©ralisÃ©es

Autres opÃ©rateurs

SelectivitÃ©

Statistiques sur les relations

SÃ©lection

RÃ©sultat triÃ©/Ã©limination des doublons

Projection

Double partitionnement

OpÃ©rations ensemblistes

OpÃ©rations d'agrÃ©gat

Conclusion

Bases de donnÃ©es

Polytech Paris-Sud

Apprentis 4Ã¨me annÃ©e

Cours 4 : Optimisation des opÃ©rateurs

Motivation

Principe d'Ã©valuation d'une requÃªte

Algorithmes de jointure

Jointure naturelle sur une colonne

Jointure itÃ©rative simple

Jointure itÃ©rative page Ã page

Jointure itÃ©rative avec index

Jointure par bloc (avec pages bufferisÃ©es)

Jointure par tri-fusion 1/2

Jointure par tri & fusion 2/2

Jointure par hachage

Jointures gÃ©nÃ©ralisÃ©es

Autres opÃ©rateurs

SelectivitÃ©

Statistiques sur les relations

SÃ©lection

RÃ©sultat triÃ©/Ã©limination des doublons

Projection

Double partitionnement

OpÃ©rations ensemblistes

OpÃ©rations d'agrÃ©gat

Conclusion

Apprentis 4^Ã¨me annÃ©e