Upload
others
View
1
Download
0
Embed Size (px)
Citation preview
1
Architecture en couche d’un SGBD
Gestion deMémoire
Gestion deVerrous
Gestion desJournaux
Méthodes d’accès aux données
Opérations relationnelles
Moteur d’exécution
Optimiseur
Analyseur sémantique
Interface
Système opérationnel
Cours 1- Les techniques- Dans Oracle…- Etude de cas
Cours 2- Les techniques- Dans Oracle…- Etude de cas
2
Modèle de stockage
Parties du support empruntées à N. Anciaux, P. Pucheral, P. Bonnet, D. Shasha, Mohammed J. Zaki
3
Architecture en couche d’un SGBD
Gestion deMémoire
Gestion deVerrous
Gestion desJournaux
Méthodes d’accès aux données
Opérations relationnelles
Moteur d’exécution
Optimiseur
Analyseur sémantique
Interface
Système opérationnel
4
Hiérarchie mémoire
10
1
0.01
0.001
1
10
107
10ms
1010
qq sec
Cache processeur
RAM
Disques
Disques optiques
Ratio Prix (approx) Accès (ns)
10 Go/s
1 Go/s(x10-1)
100 Mo/s(x10-2)
10 Mo/s(x10-3)
Débit (Mo/s)
5
Disques Magnétiques (1)• Utilisés comme support de stockage secondaire
• Les accès en lecture/écriture se font– Par pages (ou blocs disque),– et le coût dépend de la localisation de la page…– … par rapport à la position de la tête de lecture
• Les accès disque sont donc– Séquentiels (accès plus rapide à des blocs contigus)…– … et par bloc (déterminé par la taille du bus d’IO)
(NB: bien sur l’accès aléatoire par bloc est possible mais plus coûteux…)
• NB : Comportement très différent des accès RAM, qui sont– Aléatoires (temps d’accès identique pour toutes les cellules)– … et directs (accès unitaire aux mots mémoire, ex. 32b)
le placement sur disque joue sur les performances des SGBDs6
Tout stocker en mémoire ? • La mémoire coûte cher
– Octet 100 fois plus coûteux que sur disque
• Mémoire volatile– Toujours besoin d’un disque (durabilité)
• La hiérarchie typique pour le stockage des données– Mémoire centrale (RAM)
• Données accédées couramment • Stockage primaire
– Disque• Base de données originale • Stockage secondaire
– CD/bandes• Archive des anciennes versions • Stockage tertiaire
7
Disques Magnétiques (2)• Caractéristiques mécaniques
– Vitesse de rotation : 5-10000 tpm– Nombre de plateaux : 1 à 30– Nombre de pistes : jusqu’à 10 000– Nombre d’octets/piste : ≈100 000
Contrôleur
tête de lecture
bras
piste
plateau
arbre
levier
Interface (IDE, SCSI)
© Dennis Shasha, Philippe Bonnet
Plateaux
Arbre
Tête de lecture
Mouvement du bras
Bras
Pistes
Secteur
© Mohammed J. Zaki, Luc Bouganim, Philippe Pucheral 8
Disques Magnétiques (3)• Coûts de lecture/écriture
– Latence = appel au contrôleur + déplacement du bras sur la piste + placement sur le secteur
– Débit = vitesse de transfert des données
• Ordre de grandeur des performances actuelles– Appel au contrôleur = 0.1 ms– déplacement du bras = 5 ms– placement sur le secteur = 5 ms– Transfert des données = 100Mo/s
• Latence très importante à minimiser
Comment optimiser les performance ?
9
Evolutions matérielles• Progression moyenne des disques
– Capacité + 60% par an– Latence + 15% par an la plus faible des progressions …– Débit + 40% par an
• Futures technologies– FLASH NAND
• Capacité ≈ 100 Go• Latence < 1 ms• Débit ≈ 20 Mo/sec• ≈ 100 fois plus cher qu’un disque magnétique
– MEMS/NEMS (Micro/Nano Electro-Mechanical Systems)• Capacité ≈ To• Latence < 1 ms• Débit ≈ 100 Mo/s• Pas encore opérationnel
10
Optimisations logicielles– Prefetching
• Le SGBD peut anticiper les patterns de requêtes• Ainsi, il peut pré-charger (prefetch) des données en RAM• NB: le prefetching doit être géré au niveau du SGBD (vs. OS)
– Clustering• Regroupement physique des blocs de données
– Quand ils contiennent des données souvent utilisées ensemble• Placement de ces blocs sur
– La même piste physique– Le même cylindre physique
• Compromis entre bon placement et trop de perte de place– Allocation d’un ensemble de blocs par «granule»– Calibrer la taille du granule pour chaque objet DB
11
Modèles de stockage des données• Les données sont stockées sous forme de
– attributs, de taille fixe ou variable...– …stockés eux-mêmes sous forme de tuples...– …stockés dans des pages (blocs disques)...– …stockés dans des fichiers
• Rappel : le SGBD gère un cache de pages en RAM àla façon d’une mémoire virtuelle
champs tuples pages fichiers∈ ∈ ∈
12
Stockage des tuples (attributs de taille fixe)
• Les informations concernant les types/tailles d’attributs– Sont partagées par tous les tuples d’un fichier– Sont stockées dans le catalogue système
• Accéder au ième attribut ⇒ la lecture totale du tuple
Adresse de base (B)
T1 T2 T3 T4
Att1 Att2 Att3 Att4
Adresse = B+T1+T2
13
Stockage des tuples (att. de taille variable)• Deux alternatives de stockage (le nombre d’attributs est fixe):
• La deuxième alternative offre – Un accès direct au ième attribut – Un petit coût de stockage supplémentaire (taille de «offset» > taille «$»)
4 $ $ $ $
Le nombre d’attributs
Att1 Att2 Att3 Att4
Att1 Att2 Att3 Att4
Tableau d’offsets des attributs
14
Pages : tuples de taille fixe
• Identifiant d’un tuple (Record id) : Rid = < id page, emplacement #>• Remarque
– la Clé d’un tuple est un «pointeur logique», le Rid est un «pointeur physique»
. . . . . .
N M10. . .
M ... 3 2 1Page compacte
(pas de trou) Bitmap (0=trous)Page éparse
Emplacement 1
Trou
11
Nombre de tuples
Nombre d’emplacements
Emplacement 2
Emplacement N
Emplacement M
Emplacement 1Emplacement 2
Emplacement N
15
Pages: tuples de taille variable
• Déplacement des tuples dans la page sans changer le Rid…
Page iRid = (i,N)
Rid = (i,2)
Rid = (i,1)
Pointeurvers l’espacelibre
Pointeurs d’emplacements
N . . . 2 1N20 16 24
Nombre d’emplacements
16
Fichiers non ordonnés• Soit la table Doctor suivante
• Le modèle de stockage N-aire (N-ary Storage Model)
• Le modèle de stockage décomposé(Decomposition Storage Model) – Optimisation des I/O
• Le modèle de stockage PAX (Partition Attributes Across)– Optimisation du cache
PsychologyFDominique3
DermatologyMAntonio2
Pediatrics
specialtychar(20)
1
idnumber(4)
Maria
first_namechar(30)
F
genderchar(1)
2 Antonio M DermatologyPediatricsFMaria1
ID3 32ID21ID1
ID3 DominiqueAntonioID2MariaID1
ID3 FMID2FID1
ID3 PsychologyDermatologyID2PediatricsID1
Pediatrics DermatologyF M1 2 MariaID2ID1 Antonio
PsychologyF3 DominiqueID3
3 Dominique F Psychology
17
Organisations indexées• Objectifs
– Offrir un accès rapide à tous les tuples d’un fichier satisfaisant un même critère
• A partir d’une clé (mono ou multi-attributs)• Sur des fichiers ordonnés sur cette clé, ou non ordonnés, ou
ordonnés sur une autre clé
• Moyen– Créer une structure de données accélératrice associant des
valeurs de clés aux adresses de tuples
• Index– Table (ou hiérarchie de tables) implantant cet accélérateur
18
Catégories d’index (1)
• Index primaire ou plaçant(primary or clustered)
– Tuples du fichier organisés par rapport à l’index• Les tuples sont stockés «dans» l’index
– 1 seul index primaire par table…• Souvent construit par le SGBD sur la clé primaire
• Index secondaire ou non plaçant(secondary or unclustered)
– Tuples organisés indépendamment de l’index• Seuls les Rid des tuples sont «dans» l’index
– Plusieurs index secondaires possibles par table
…K1…
…K2… …Kn…
Page 1 Page 2 Page i
…K1…
…K2… …Kn…
Page 1 Page 2 Page i
Clé L
↓Tuples triés sur K
Tuples non triés sur L
Clé K
19
Catégories d’index (2)• Index dense (dense)
– Contient toutes les clés– Adresse tous les tuples
• Index non dense (sparse)– Ne contient pas toutes les clés– N’adresse pas tous les tuples
(e.g., adresse une seule fois chaque page)– Nécessite que le fichier soit trié sur les clés
Contient alors la plus grande clé de chaque bloc + l'adresse relative du bloc
• NB : Densité d’un index : nb clés dans l'indexnb clés dans la table
tuple
tuple tuple
Page 1 Page 2 Page i
tuple
tuple tuple
Page 1 Page 2 Page i
20
Catégories d’index (3)
• Mais au fait …– Peut-on créer un index non dense non plaçant ?– Peut-on créer un index dense et plaçant ?– Peut-on créer un index primaire (c.à.d, plaçant) sur une clé
secondaire (c.à.d, non discriminante) ? – Peut-on créer un index secondaire (c.à.d, non plaçant) sur
une clé primaire (c.à.d, discriminante) ?
21
Catégories d’index (4)• Index hiérarchisés ou multi-niveaux
– Permet de gérer de gros index (i.e., très gros fichiers…)
– Principe : chaque index est indexé
• Fonctionnement– L’index est trié
(mais trop gros peu performant…)
– On index l’index • Par un second index non dense
( 2ème niveau)– On peut continuer…
(jusqu’à obtenir un index non dense qui tiennent dans une seule page…)
Pourquoi l’index à indexer doit-il être trié ?
22
Modèles de stockage des index• Rappel : index = table(s) d’association tuples (Rid) – clé
• La question : comment organiser/stocker cette table ?
• Modèle de stockage non ordonné ?– (Peu ou) pas utilisé pour stocker les index dans les SGBD
• Organisation en tas recherche séquentielle de la clé !
• Modèle de stockage ordonné ?– index bitmap, – Join index– Organisation arborescente
• e.g. index B+
– Modèles basés sur du hachage• Beaucoup moins utilisé (prédicats d’inégalité)
23
Index Bitmap– Index Bitmap = index secondaire dense non trié– A chaque clé, on associe un bitmap
• 1 entrée par tuple1/0 = contient oui/non la valeur
– Utilisé si• 1) clé varie sur un domaine de faible cardinalité• 2) requêtes multi-critères sans sélectivité dominante
– Peut être vu comme une façon de compresser les listes inversées (listes de Rid)
ZoukNurseBerthe
Art
000000001
001001000
010010010
100100100↓
… …
… …
… …
… …
… …
… …
… …
… …
… …
Nurse
Zouk
Art
Berthe
Zouk
Art
Berthe
Zouk
Art
… …
… …
… …
… …
… …
… …
… …
… …
… …
24
Join Index
• Utilisé pour retrouver une association (jointure)– Stocké sous forme de 2 tables (1 seule au minimum)
• J1 : clés = clés primaire tuples = clés étrangères
• J2 : clés = clés étrangères tuples = clés primaires
……
……
……
……
……
……
……
……
date
……
……
……
……
……
……
……
……
price
8
7
6
5
4
3
2
1
VisId
2
3
1
1
3
2
2
3
DocId
……
……
……
……
……
……
……
……
……
Visit (v)3
3
3
2
2
2
1
1
DocId
7
4
1
8
3
2
6
5
VisId
J1J2
Ex. v.VisIdEx. v.DocId
Ex. v.DocIdEx. v.VisId
25
Arbre B+• Organisation arborescente
– e.g., index stockés sous forme d’Arbre B+– Peuvent être plaçant ou non plaçant
• Plaçant = les tuples sont stockés «dans» l’index• Non plaçant = les Rid sont stockés «dans» l’index
– Rappel : Arbre-B+• Pour les SGBD disques, l’arbre B+ est le plus utilisé• Arbre B+ = index hiérarchisé (multi-niveaux)
– Clés des noeuds intermédiaires dupliquées dans les feuilles – Feuilles chaînées accès séquentiel trié rapide
26
Utilisation d’index multicritères – cas part.• Construction d’index couvrant une requête
– Accès à l’index (sans accès à la relation) permet de répondre
– Accélération drastique d’un pattern de requêtes particulier• Attributs à mettre dans l’index couvrant
– Tous les attributs nécessaires à la requête…• Attributs intervenant dans les sélections• Attributs intervenant dans les projections
• Exemple– Pattern de requête
SELECT P.nomFROM Personne PWHERE P.salaire > Y;
– Index couvrant • Index sur la clé suivante : P.salaire, P.nom
27
Support emprunté à Pascale Borla Salamet – Oracle France
Oracle
28
29 30
Hiérarchie logique et physique
Base de données
Tablespace
Segment
Extent
Bloc ORACLE Bloc OS
Datafiles
PhysiqueLogique
31 32
33 34
Data blocs• Un data bloc est l’unité de gestion de l’espace disque• Il est la plus petite unité d’E/S
Tuples (row data)
Espace libre (PCTFREE, PCTUSED)
Répertoire de tuples (row directory)Répertoire de tables (table directory)
Entête
35
PCTFREE et PCTUSED• Paramètre PCTFREE
– Pourcentage d’un bloc réservé aux mises à jour futures (ordre SQL UPDATE)– Quand PCTFREE est atteint : le bloc est retiré de la freelist
• Le paramètre PCTUSED – Pourcentage d’un bloc devant être libre pour pouvoir à nouveau insérer des
données dans le bloc – Quand PCTUSED est atteint : le bloc est remis dans la freelist– 40%, par défaut
• Réglage– Par le DBA– Par l’ASS = Automatic Segment Space Management (>Oracle 8i)
Si Oracle remet les bloc dans la liste des blocs libre alors que ces blocs disposent de peu d’espace libre, le coût des insertions nombreuses (de plusieurs tuples) sera très élevé (jusqu’à 1 IO par tuple inséré)
Pourquoi si faible ? La taille moyenne d’un tuple suffirait…
36
Utilisation de PCTFREE et PCTUSEDPCTFREE=20, PCTUSED=40
Si PCTUSED>40, alors les insertions peuvent être effectuées
INSERTION (Max 80% du bloc)
Mise à jour
SUPPRESSION
37
Chaînage des tuples et migration• Un tuple ne tient pas dans un data block
– Car ce tuple est trop grand• Oracle stocke les données en trop dans un espace réservé pour le
segment • Oracle chaîne les données
– Car ce tuple est mis à jour est ne tient plus (plus assez d’espace libre)
• Oracle migre le tuple en entier dans un nouveau data block
38
39 40
41
11
1 1
Index Bitmap: combinaison de critères
42
43
- Gestion de la mémoire- Opérateurs- Exécution de requête
44
Architecture en couche d’un SGBD
Gestion deMémoire
Gestion deVerrous
Gestion desJournaux
Méthodes d’accès aux données
Opérations relationnelles
Moteur d’exécution
Optimiseur
Analyseur sémantique
Interface
Système opérationnel
45
Objectif du module ‘gestion de mémoire’
• Rendre les pages de la BD accessibles en mémoire–Mapping des pages BD en mémoire–Garanti l’adresse de la page pendant un laps de temps–Garanti la cohérence de plusieurs copies de pages
• Optimiser les performances –Cache des pages –Coûts réseau (cohérence)–Forte connexion avec le gestionnaire de verrous et de
journalisation
46
Occupation mémoire sur un serveur BD
• Sur un serveur SGBD, la mémoire est occupée par :– le logiciel–des pages BD–des pages temporaires –des structures de données du SGBD (globales au SGBD)–des structures liées aux transactions
• Si le serveur n’est pas dédié, on a aussi–des données, programmes, etc...
• Intérêt d’un serveur dédié ?
47
Gestion par l’OS vs. par le SGBD• L’OS considère toutes les pages comme équivalentes
– Pas de connexion avec le verouillage/journalisation– Application d’heuristiques (LRU)– Utilisation d’un disque de swap
• Le SGBD a une connaissance du contenu des pages– Il peut utiliser les infos fournies aux modules de gestion de verrous et de
journaux– Il contrôle complètement la mémoire disponible
Influence sur les algorithmes utilisés– Il peut contrôler le swap
Influence sur la journalisation– Les caches peuvent être optimisés suivant d’autres critères
48
BD: Partie chaude / froide / active
• Taille de la base de données– Place sur le disque du fichier BD
• Taille de la base de données active– Taille des pages accédées à un instant donné par toutes les transactions
• Taille de la base de données chaude (80% des accès)– Taille des pages accédées très fréquemment par toutes les transactions
• Taille de la base de données froide (20% des accès)– Taille des pages accédées peu fréquemment par toutes les transactions
• La modélisation des ‘workloads’– est complexe... – et a une grande influence sur les algorithmes à utiliser…
49
Ordres de grandeurTaille de mémoire vive (RAM) disponible pour le SGBD
0,1 Go
1 Go
10 Go
100 Go
1 To
BD personnelles (PC...)
BD PME
BD production (banque, etc..)
BD hautes performances
BD mémoire ... ???
1-10 Ko Pico-BD (carte à puce)50
Mémoire Virtuelle
Zone de swap
Swapping
VirtuelleMémoire
Mémoire Physique
P1 P2 P4P3
système
Systèmes 32 bits4 Go
Systèmes 64 bits18 exa-octets
(18 millions deTera-octets)
51
Option 1 : Single Level Storage
• Le système est responsable du– ‘mapping’ du fichier BD sur la mémoire virtuelle– ‘mapping’ de la mémoire virtuelle sur la mémoire physique– ‘swapping’
VirtuelleMémoire
Mémoire Physique
Fichier BD
52
Option 2 : Mapping OS / Swapping BD
• Le système est responsable du– ‘mapping’ du fichier BD sur la mémoire virtuelle– ‘mapping’ de la mémoire virtuelle sur la mémoire physique– Il peut déléguer une partie des fonctions (external pager)
VirtuelleMémoire
Mémoire Physique
Fichier BD Zone de swap
Swapping
SGBD
53
Option 3: Mapping BD / Swapping BD
Swapping diskDB Disk
Memory CacheManagement Operating system
Virtual Memory
Physical memory
Mapping SwappingSwapping
Working Memory
Swap BD
54
Option 4: Mapping BD / Swapping OS
Zone de swapZone BD
Memory CacheManager système
VirtuelleMémoire
Mémoire Physique
Mapping Swapping
55
Comment répartir la mémoire
Que
ry1
Que
ry2
Entre lesrequêtes
Op.
1O
p. 2
Op.
3
Entre lesopérateurs
Dans un opérateur
Dis
poni
ble
Néc
essa
ire
Approche d’Oracle (8i)• SORT_AREA_SIZE
• HASH_AREA_SIZE
• Tuning
56
Problème de la répartition de la mémoire• Comment répartir la mémoire ?
– Dans un opérateur, entre les opérateurs ?– Entre les requêtes ?– Une moyenne ?– Max au Min ?
• Quand répartir la mémoire ?– Au moment de la compilation de la requête ?– Au démarrage de l’exécution ?– Pendant l’exécution ?
• Problème complexe !!!• Et très important...
57
Adapter les opérateurs à la mémoire !• Le choix de la bonne implémentation d’un opérateur
relationnel (select, project, join, union, etc.) dépend– de la requête qui le contient– des caractéristiques des inputs– de ses paramètres (prédicat de jointure, de sélection, etc.)– des caractéristiques des données– des structures d’indexation existantes– et beaucoup de la quantité de mémoire disponible
• Quels sont les différents choix ? Objet de ce cours• Comment choisir ? Problématique d’optimisation
58
Architecture en couche d’un SGBD
Gestion deMémoire
Gestion deVerrous
Gestion desJournaux
Méthodes d’accès aux données
Opérations relationnelles
Moteur d’exécution
Optimiseur
Analyseur sémantique
Interface
Système opérationnel
59
Les opérateurs• Sélection (σ), sélection d’un sous ensemble des tuples d’une table
– Par Scan, par index
• Projection (π), sélection d’un sous ensemble d’attributs d’une table– Par Scan, par index, par tri ou hachage (si élimination des doublons)
• Jointure (∞), combinaison de deux tables sur critère– Par boucles imbriquées– Par index– Par tri ou hachage
• Autres opérateurs– Groupement, agrégats– Différence (-), Union (∪), Intersection (∩)
• Chaque opérateur prend en entrée une ou deux tables et renvoie une table possibilité de composer les opérateurs pour former des plans (arbres) d’exécution de requêtes
60
Sélection σ: par Scan
• Algorithme Select (R, Q) :For each page p de R do {
Read (p);For each tuple t de p
{ if CheckS (t, Q) then result = result ∪ t ;} ; }
• La solution la plus simple et la meilleure quand la sélectivité est très faible (ex: chaque page contient au moins un tuple qualifié)– ⎜⎜Result ⎜⎜ = S* ⎜⎜R ⎜⎜, avec 0 ≤ S ≤ 1 – ATTENTION: Sélectivité faible = S élevé et vice-versa
61
Sélection σ : utilisation d’un index• Quand utiliser l’index ?
– Si la sélectivité est forte (S très petit)– car coût(I/O aléatoire) >> coût(I/O séquentielle)
• Ex.
– Médicaments = 100.000 tuples, 1000 pages contiguës; – Noms uniformément distribués; I/O = 10ms + nbpages x 0,2ms– Il y a 5 % de médicaments commençant par un N (=‘N%’)
• NB : optimisation des accès aux données par index non plaçant – Trouver dans l’index les Rid qualifiés– Trier les Rid qualifiés– Accéder les tuples sur disque dans l’ordre des Rid
(pour ne pas accéder 2 fois la même page…)
SQL> SELECT *> FROM Medicament > WHERE M.Nom = ‘N%';
Comparer les coûts d’accès:1) Sans index; 2) Avec index plaçant sur Nom; 3) Avec index non plaçant sur Nom
62
Sélection σ : utilisation de plusieurs index• Identification des index les plus sélectifs• Intersection et union de listes de Rid de ces index
– Accès aux tuples dont les identifiants sont retenus– Vérification du reste du critère sur les tuples résultat– Exemple :
• (SPEC=‘Dentiste’ OR SPEC=‘Stomatologie’) AND (ADRESSE = ‘Versailles’) AND (AGE>30)
• L = (S1 ∪ S2) ∩ A1• Accéder aux tuples de L et vérifier le critère AGE
• Index bitmap permettent de combiner efficacementdes critères peu sélectifs
63
Projection• L’opération coûteuse est l’élimination des doublons
– SQL n’élimine pas les doublons (sauf si la clause DISTINCT est spécifiée dans la requête)
• Algorithme– Basé sur du hachage– Basé sur du tri
• Remarques sur l’approche tri– Le résultat est trié– C’est l’implantation standard choisie par les éditeurs de SGBD
SQL> SELECT DISTINCT V.id, V.doc> FROM Visite V ;
64
Coût du Tri• Problème récurrent en base de données
– La table à trier ne tient pas en mémoire– Solution = algorithme de tri-fusion
• Nombre de passes = 1+ ⎡logB-1 ⎡N / B⎤ ⎤ (N = Nbre de pages à trier, B = Nbre de pages mémoire)
• Coût I/Os = 2N x (nombre de passes)– Lecture et écriture (complète) des pages de la table à chaque passe
• Ex. 5 pages en RAM, pour trier 108 pages– Passe 0: ⎡108 / 5⎤ = 22 monotonies triées de 5 pages chacune
(sauf la dernière qui contient 3 pages) – Passe 1: ⎡22 / 4⎤ = 6 monotonies triées de 20 pages chacune (resp. 8 pages) – Passe 2: 2 monotonies triées de 80 pages (et 28 pages)– Passe 3: fichier trié de 108 pages – Coût total = 2*108*4 = 864 I/O
65
Jointure (et opérateurs similaires)• L’opérateur le plus étudié en BD car le plus coûteux• Variations de l’algorithme de jointure
– Par boucle• Jointure par boucles imbriquées (Block Nested Loop Join)• Jointure par boucles imbriquées avec un index (Index Join)
– Par index• Jointure par index (Index Join)
– Par tri• Jointure par tri fusion (Sort Merge Join)
– Par hachage• Jointure par hachage (Hash Join)• Jointure par hachage de Grace (Grace Hash Join)• Jointure par hachage hybride (Hybrid Hash Join)
• NB : ces d’algorithmes peuvent êtres adaptés à d’autres opérateurs binaires (intersection, différence, etc.)
66
Comparaison des algorithmes de jointure• On veut joindre les tables DOCteur et VISite
• Coût = Nombre d’I/O - on ne distingue pas I/O séquentielles et aléatoires- on ne compte pas le coût d’écriture du résultat final (identique pour tous)
• Paramètres– |DOC| = Nombre de pages occupées par DOC– ||DOC|| = Nombre de tuples dans DOC– |DOC| << |VIS|– M = Nombre de pages mémoire disponibles (NB : quelques approximations pour simplifier les formules)
……
……
……
……
……
……
……
……
date
……
……
……
……
……
……
……
……
prix
…
7
6
5
4
3
2
1
id
…
3
1
1
3
2
2
3
docid
……
……
……
……
……
……
……
……
……
……
……
……
……
……
…
1
2
5
Nom
…
Pneumologue
Radiologue
Pédiatre
spécialité
…
3
2
1
idDOC VIS
67
Jointure Brute-Force : Nested Loop
• Algorithme Join(DOC, VIS, Q)– For each page p de DOC– For each page q de VIS– For each tuple tp de p– For each tuple tq de q– if Check (t, Q) then result = result ∪ (tp||tq) ;
• Coût I/O = |DOC| + |DOC| * |VIS| • Fonctionne quel que soit Q et quel que soit M ≥ 3• Très sous-optimal dès que M > 3
68
Jointure : Block Nested Loop• Algorithme
– DOC = table externe (outer relation) de la jointure • Chargement par bloc de M-2 pages• Choisir la table la plus petite comme table externe
– VIS = table interne (inner relation) de la jointure• Chargement par bloc d’une page en RAM
• Coût en I/Os avec M pages de RAM = |DOC| + ⎡|DOC|/M⎤ × |VIS|
… IN 1
IN 2
IN M
-2
OU
T M
…
Page 1
Page 2
Page D
……
Page 1
Page 2
Page K
RAM
IN M
-1
…
Page 1
Page 2
Page V
DOC
VIS
DOC ∞ VIS
69
Jointure par index• Hypothèses
– Un index sur l’attribut de jointure de VIS (ou de DOC)– L’index a n niveaux et tient sur p pages
• Principe (équi-jointure) – Choisir comme table interne celle qui a un index sur l’attribut de jointure
(ex. VIS) et utiliser l’index
– Ex. pour chaque docteur, récupérer la clé de jointure, parcourir l’index sur visite et retrouver les visites partageant cette clé
• Coût– Coût = |DOC| + ||DOC|| × (n+1) si M=3– Coût = |DOC| + p + |VIS| si M = |VIS| + p
FOR EACH tuple tD IN DOCAccède les tuples tV de VIS de clé tD.join_key // index Ajoute tD•tV au résultat
END FOR
70
Jointure par Tri Fusion : Sort-Merge Join• Principe de l’algorithme : (équi-jointure DOC.id = VIS.docid)
– Trier DOC (resp. VIS) sur DOC.id (resp. VIS.docid)– Parcourir simultanément DOC et VIS pour ‘fusionner’ les tuples– Produire les tuples résultat
• Coût du Sort-Merge Join– Tri des deux tables
• 2×|DOC|×(1 + ⎡log M-1 |DOC|/M⎤) // ou 0 si DOC déjà triée• 2×|VIS|×(1 + ⎡log M-1 |VIS|/M⎤) // ou 0 si VIS déjà triée
– Fusion • |DOC| + |VIS|
…………15
…………16
……
……
……
……
……
……
date
…
7
1
4
2
3
id
…
3
3
3
2
2
docid
……
……
……
……
……
……
……
……
……
……
……
……
…
1
2
5
Nom
…
Pneumologue
Radiologue
Pédiatre
spécialité
…
3
2
1
id
DOC
VIS
1
3
2
1
…………16
…………15
……Pédiatre51
……Pédiatre515
2
3
…………22
…………23
……Radiologue22
……Radiologue225
4
4
4
4
Etc.
Etc.
71
Jointure par hachage (Hash Join)• Principe de l’algorithme : (équi-jointure DOC.id = VIS.docid)
– Phase de construction (build) • Charger DOC, hacher en RAM en n paquets, avec n le plus grand possible
– Phase de test (probe)• Parcourir VIS, pour chaque tuple tester la table de hachage et produire les résultats
• Coût– Identique à la jointure (Block-) Nested Loop !– Optimise simplement le coût CPU de la jointure
…
h = 1h = 2
h = ||DOC||
…
Page 1
Page 2
Page D
RAM
DOC
IN 1 h
h=1
h=2
h=||DOC||
…
Page 1
Page 2
Page V
VIS
…
IN 2
IN 3
IN M-1RAM
IN 1 h
h=1
h=2
h=||DOC||
OU
T M ……
Page 1
Page 2
Page D+V
DOC ∞ VIS
M-2 pages
DOC
72
• Principe de l’algorithme : (équi-jointure DOC.id = VIS.docid)– Phase de construction (build) : Hacher DOC et VIS sur disque avec la même fonction h
• Hachage en n partitions, n est calculé de façon à ce que |partition| ≤ M-1
• Coût I/O du Build = 2 × (|DOC| + |VIS|)– Phase de test (probe) : Joindre DOC et VIS par partition
• Les tuples d’1 partition de DOC joignent uniquement avec 1 partition de VIS• Charger 1 partition de DOC (M pages), et le hacher avec h’ ≠ h• Parcourir la partition correspondante de VIS en appliquant h’
• Coût I/O du Probe = |DOC| + |VIS|
Jointure par hachage (Grace Hash Join)
…
Page 1
Page 2
Page V
VIS
…
IN 2
IN 3
IN MRAM
IN 1h
h=1
h=2
h=n
…
Page 1
Page 2
Page D
DOCPage 1 Page 2
Page …
Page 3 Page 4 Page 5
Page D
Page 1 Page 2
Page …
Page 3
Page Vh
h=1
h=nRAM
Page 1 Page 2
Page …
Page 3 Page 4 Page 5
Page D
Page 1 Page 2
Page …
Page 3
Page V
…
IN 2IN 3
IN M-1
RAM
IN 1
h’h’=1
h’=2
h’=m
OUTh’
…
…
Page 1
Page 2
Page D
+V
DOC ∞ VIS
73
Jointure par hachage Hybride (Hybrid Hash Join)• L’approche Hybrid Hash Join est optimiste
– On suppose (espère) que la plus petite table (DOC) tient en mémoire – Build :
• On hache cette table en n paquets comme dans l’algorithme Hash join• Si cette table tient en RAM, build optimal• Sinon, sélectionner des partitions qui vont déborder sur disque
…
Page 1
Page 2
Page D
DOC
RAM
…
IN 2
IN 3
IN …
…
IN …
IN … …
IN …
IN … …
IN …
IN M
IN 1
h=1 h=2 h=n
h
…
IN 2
IN 3
IN …
…
IN …
IN …
74
Jointure par hachage (Hybrid Hash Join)–Probe1
• Appliquer la même fonction de hachage h aux tuples de VIS• Si h(tV) correspond à une partition de DOC en mémoire, produire les
résultats• Sinon, écrire la partition correspondante de VIS sur disque (i.e., Build
partiel)
–Probe 2• Joindre (si besoin) les partitions disque de DOC et de VIS selon
l’algorithme Grace Hash Join
…
Page 1
Page 2
Page V
…
IN 2
IN 3
IN …
…
IN …
IN ……
IN …
IN … …
IN …
IN …
RAM
…
IN …
IN ……
IN …
IN M
h=1 h=2 h=n …
Page 1
Page 2
Page …
DOC ∞ VIS
VIS
IN 1
h
OUT
DOC VIS
75
Coût de la jointure (Hybrid Hash Join)• Coût I/O
– Hypothèse M = |DOC|/k //optimal avec k=1– Build : |DOC| + |DOC|(k-1)/k – Probe1 : |VIS| + |VIS|(k-1)/k– Probe2 : |DOC|(k-1)/k + |VIS|(k-1)/k – Total = (|DOC|+|VIS|) x (1 + 2 (k-1)/k) I/Os
• Avec n = 2 2 × (|DOC|+|VIS|) I/Os
• Technique implantée dans la plupart les SGBD commerciaux– Oracle, MS SQL Server, IBM DB2, …
76
Condition générale de jointure• NB : pour l’instant, equi-jointure mono-attribut…
• Equi-jointure multi-attributs– Jointure par boucle
• Supporte sans modification toute condition de jointure– Jointure par index
• Sans modification si index multi-attributs• Sinon, utilisation de l’index mono-attribut suivi d’un test systématique des
autres prédicats de la condition– Jointure par tri fusion ou hachage
• Prendre en compte la combinaison des attributs comme clé de jointure
• Inequi-jointures– Jointure par boucle
• Sans modification (et probablement optimal pour ce type de jointure)– Jointure par index et tri-fusion adaptables mais avec un coût très – Jointure par hachage inappliquable
77
Autres opérateurs• Groupements et agrégats
– Les tuples peuvent être groupés par tri ou hachage– Optimisation: calculer l’agrégat en même temps que le groupement
• évite une seconde passe et réduit le nb d’I/O du groupement en maintenant en RAM le calcul intermédiaire plutôt que de la liste des tuples membres)
• Union (∪), intersection (∩) et différence (⎯)
– Adaptation des algorithmes de jointure (exemples)• R ∩ S
– Évaluer la condition de jointure sur tous les attributs clé et projeter sur les attributs d’une seule des deux tables
• R ⎯ S– Évaluer la condition de jointure sur tous les attributs clé– Retirer de R tous les tuples qui joignent et produire le résultat
• R ∪ S – Calculer (R ⎯ S) + S, où + est une simple concaténation
78
CONCLUSION
• Pour chaque opérateur de l’algèbre, plusieurs implémentations possibles
• Pas d'algorithme systématiquement meilleur ! – Le bon choix dépend de :
• La taille des tables opérandes• La quantité de RAM affectée à l’opérateur• L’organisation des tables (indexées, hachées)• la sélectivité de la condition de jointure (PS: 90% des jointures sont
des équi-jointures sur clé)
• Nécessité d'un modèle de coût précis et d’unoptimiseur de requêtes– Mais encore faut-il que l’administrateur BD ait produit les
conditions d’un bon choix !
79
Architecture en couche d’un SGBD
Gestion deMémoire
Gestion deVerrous
Gestion desJournaux
Méthodes d’accès aux données
Opérations relationnelles
Moteur d’exécution
Optimiseur
Analyseur sémantique
Interface
Système opérationnel
80
Exécution d’une requête• Combinaison d’opérateurs physiques
– Ex. Implantation physique de la jointure• Deux opérateurs
– Build : construction de la table de hachage– Probe : test avec la table de hachage
• Les opérateurs physique s’interfacent
• Représentation sous forme d’arbre d’opérateurs• 2 alternatives d’exécution d’un arbre d’opérateurs
– Avec matérialisation
– En pipeline
Scan Scan
Build
Probe
DOC VIS
σ
π
81
Exécution pipeline (1)• Plusieurs opérateurs fonctionnent ‘simultanément’
– Sans écrire de résultat intermédiaire (se passe directement les tuples résultats)
– Ils forment alors une chaîne pipeline
• Ex. Dans l’arbre ci-contre– Accéder VIS et construire la table de hachage– Accéder DOC et sélectionner (age > 32)
Passer chaque tuple résultat au probe– Lire les DOC sélectionnés et tester avec la table de hachage
Passer chaque tuple résultat à la projection– Lire le résultat de la jointure et effecteur les projection
• Efficacité du pipeline– Moins de résultat temporaire moins d’I/Os– Les opérateurs produisent des tuples dès qu’ils en consomment
DOC VIS
Scan Scan
Build
Probe
σ
π
Age > 32
82
Implantation sous forme d’itérateur
• Le modèle iterateur– Interface uniforme et générale pour tous les operateurs
physiques– Chaque opérateur est décomposé en trois méthodes
• Open() alloue la mémoire, effectue l’initialisation• Next() renvoie un tuple résultat (ou ‘end of file’ eof)• Close() libère la mémoire et rend la main
83
project.open(){probe2.open{
build2.open() { // hach table de TscanT.open();t = scanR.next()while (! eof) {
t = scanT.next(); insert t in table }
scanT.close();} build2.close(); probe1.open() {
build1.open() {// hash table de R
...} build1.close();scanS.open();
}}
Execution d’un arbre d’itérateurs (1)project
probe2
build2
probe1
build1
scanTT
scanRR
scanSS
84
Execution d’un arbre d’itérateurs (2)project.next(){
probe2.next {probe1.next() {
s = scanS.next();test table de R avec s;return tuple rs;
}test table de T avec rs;return tuple rst;
}rstp=projection(rst); return rstp;
}
project
probe2
build2
probe1
build1
scanTT
scanRR
scanSS
85
L’architecture d’Oracle 8
86
Définition d’une instance Oracle• A chaque démarrage
– Oracle lance des processus, de différents types• Processus utilisateurs• Processus serveurs• Processus background
– Oracle alloue un espace mémoire• Partagé par tous les processus (SGA, System Global Area)• Privé à chaque processus du système (PGA, Program Global Area)
• Ce qui définit une Instance Oracle :– 1 SGA + processus background de cette SGA + leurs PGAs– Une instance peut être dans 4 états
• Stoppée; démarrée; démarrée et montée; démarrée montée et ouverte• BD totalement utilisable instance démarrée montée et ouverte
– NB: 1 instance correspond à N utilisateurs
87
La Structure Mémoire d’Oracle (1)• Décomposée de la façon suivante
– Zone de code logicielle (Software Code Area)• Stocke le code Oracle
– Zone mémoire des Instances Oracle (SGAs) • Zone mémoire partagée par les instances Oracle (Shared Pool)
– Cache de données du dictionnaire– Espace de travail mémoire d’Oracle (requêtes), etc…
• Zone mémoire propre à une instance Oracle– Cache de données de la base (Buffer Cache)– Cache de mises à jour (Redo Log Buffer), etc…
– Zone mémoire privée (PGA) • Zone de tris, infos de sessions, etc…
88
La Structure Mémoire d’Oracle (2)
• Le paramétrage des zones mémoire les performances– En particulier, la taille des Buffers du SGA– Cette tâche incombe au DBA
89
Les Buffers du SGA• Shared Pool : Stocke les méta données
– Structures système, procédures, et autre méta données – Paramétrage : shared_pool_size
• Buffer Cache : Stocke les blocks lus du disque– Paramétrage
• db_block_buffers (≤ Oracle8i)• db_cache_size (≥ Oracle9i)
• Redo log buffer : stocke les modifications (avant report sur le fichier REDO)– Contient uniquement les données modifiées (et pas tout le block)– (NB: le fichier REDO sert à rejouer les transactions perdues)– Paramétrage : log_buffer
90
Fonctionnement du Buffer Cache
• Les blocs de la liste ont 3 états possibles– free : bloc non utilisé actuellement, et non modifié consistant/disque– pinned : en cours d'utilisation ce block ne peut être ré-attribué– dirty : modifié non consistants/disque
• Structures maintenues– Une table de Hachage
• Mapping : adresse block sur disque entrée du block en RAM– Une Liste LRU (blocks free, pinned, dirty)
• Chaînage des blocs du plus récemment utilisé au moins récemment utilisé• NB: utilisé = en consultation (SELECT) ou en modification (UPDATE)
– Une Liste DIRTY (blocks dirty)• Reportée sur le disque par le processus DBWR (DataBase WRiter).
91
Les Processus Background (1)• Une instance est partagée par plusieurs utilisateur
– il faut centraliser les taches (évite les problèmes de concurrence)
• Au démarrage de l’instance– PMON, SMON, DBWR, LGRW, CKPT, ARCH
• PMON (Processus MONitor)– Nettoie les connections terminées de façon anormales
• Libère les verrous• Libère les ressources
– Défait les transactions non consolidées (commit)• À l’aide des Rollback Segment (cf. cours transactions)
• SMON (System MONitor)– Restauration automatique des instances (e.g., sur panne
CPU)92
Les Processus Background (2)– DBWR (DataBase Writer)
• Participe à la gestion du buffer cache – son but est de conserver le cache propre
• Reporte les blocks modifiés (dirty) sur le disque– Dans l’ordre indiqué par la ‘liste DIRTY’– Libère la mémoire correspondante aux blocs reportés
– LGRW (LoG Writer)• Responsable de l’écriture du Redo Buffer sur le disque • Il s’exécute
– à chaque COMMIT– toutes les 3 secondes– quand le buffer est rempli au premier tiers– À chaque intervention du DBWR
93
C’est quoi?
• CKPT (ChecKPoinT)– Gestion des checkpoint
• ARCH (ARCHiver)– Effectue l’archivage du fichier REDO LOG
Les Processus Background (3)
94
Les Processus Serveur• Leur tâche
– Analysent et exécutent les requêtes SQL– Lisent les blocks de données du disque vers les Buffers de la SGA– Ramènent les données pour l’application utilisateur
• NB: Si l’application et Oracle tournent sur la même machine– les processus utilisateur et serveur sont combinés
95 96
Le dictionnaire de données Oracle
Support emprunté à L. Bouganim
97
Contenu du Dictionnaire Oracle• Dictionnaire Oracle = tables systèmes en lecture seule
• Evolution du dictionnaire – Généré au moment de la création de la DB– Mis à jour automatiquement
• Contient des informations sur la structure de la BD– Utilisateurs (privilèges, rôles) – Noms et caractéristiques des objets
(tables, vues, index, clusters, triggers, packages, ...) – Contraintes d'intégrité– Ressources physiques allouées à la base – Valeurs par défaut pour des colonnes– Les autres informations générales sur la base des données
• Structure– Tables de base = tables fondamentales contenant les informations sur la BD
• Conservées dans le tablespace SYSTEM– Vues de ces tables = présentation dépendant du rôle de celui qui consulte… 98
Utilisation du dictionnaire• Accès avec SQL
• Utilisé par le DBA et les utilisateurs–Consultation d’informations sur la structure de la BD –Seulement des droits en lecture sur des vues du dictionnaire–NB: seulement par des requêtes SELECT (lecture seule)
• Utilisé par Oracle–A la connexion et pendant l’exécution des requêtes
• Consultation d’informations sur les utilisateurs et leurs privilèges • Consultation d’informations sur les objets de la BD
–Lors des requêtes SQL DDL (Data Definition Language)• Modification du dictionnaire
99
• La vue ‘DICTIONARY’ permet d’accéder aux noms/desc. des vues DBA, ALL, USER, V$...
Différentes vues
SQL> SELECT table_name, comments > FROM dictionary > WHERE table_name LIKE '%CONSTRAINTS%';
TABLE_NAME COMMENTS----------------------------------------------------------------ALL_CONSTRAINTS Constraint definitions on accessible tablesDBA_CONSTRAINTS Constraint definitions on all tablesUSER_CONSTRAINTS Constraint definitions on user's own tables
3 rows selected.
100
Les vues USER• Description des objets logiques créés par un utilisateur
– Objets logiques = tables, index, vues, triggers, procédures…
• Exemples de vues USER_
– USER_TABLES• Tables créées par l’utilisateur
– USER_INDEXES• Index créés par l’utilisateur
– USER_CONSTRAINTS • Contraintes créées par l’utilisateur
– USER_VIEWS• Informations sur les vues créées par l’utilisateur
– USER_USERS• Information sur l’utilisateur
SQL> SELECT table_name> FROM dictionary > WHERE table_name LIKE '%USER_%';
TABLE_NAME------------------------------…USER_VIEWSUSER_HISTOGRAMS
115 row(s) selected.
101
Les vues ALL• Ces vues décrivent
– les objets créés par l’utilisateur connecté (comme dans user_tables)– Et aussi tous les objets accessibles à cet utilisateur
• Exemples de vues ALL_
SQL> desc all_tables;Nom ------------------------------OWNER …TABLE_NAME ……
SQL> desc user_tables;Nom ------------------------------TABLE_NAME ……
Dans user_tables Dans all_tables
SQL> SELECT table_name FROM all_tables;…SQL> SELECT username FROM all_users;…SQL> SELECT index_name FROM all_indexes;…SQL> SELECT table_name, constraint_name FROM all_constraints;…
102
Les vues ALL : exemple• La vue ALL_CONSTAINTS
– Contraintes des tables accessibles à l’utilisateur
103
Les vues DBA (1)• Décrivent tous les objets de la base
– Sur certains objets, la description est plus complète• Accessibles qu’aux utilisateurs
– Ayant le rôle SELECT_CATALOG_ROLE – Ou ayant le privilège système SELECT ANY DICTIONARY
• Ex. La vue DBA_SEGMENTSSQL> SELECT tablespace_name, sum(bytes)/1024 "OCCUPE (K)"
> FROM dba_segments> GROUP BY tablespace_name;
TABLESPACE_NAME OCCUPE (K)------------------------------ ----------CWMLITE 6080DRSYS 7872EXAMPLE 155904SYSTEM 245712TOOLS 5888UNDOTBS 51480
6 row(s) selected.
104
Les vues DBA (2)• Ex. La vue DBA_TABLES
• Ex. La vue DBA_SYS_PRIVS– Privilèges systèmes octroyés aux utilisateurs et aux rôles
SQL> SELECT table_name, num_rows, blocks, < empty_blocks, avg_space> FROM dba_tables> WHERE table_name=’Livre’;
TABLE_NAME NUM_ROWS BLOCKS EMPTY_BLOCKS AVG_SPACE---------- -------- ------ ------------ ---------LIVRE 6764 180 19 861
1 row(s) selected.
SQL> SELECT * FROM dba_sys_privs> WHERE grantee='DBA';
GRANTEE PRIVILEGE ADM------- -------------------- ---DBA ALTER ANY CLUSTER YESDBA ALTER ANY INDEX YESDBA ALTER ANY LIBRARY YES...
105
Les vues dynamiques V$ (1)• Vues dont les informations sont «dynamiques»
– Evoluent du démarrage de l’instance jusqu’à son arrêt– Décrivent l’activité de la DB et de l’instance– Sont appelées «dynamiques» mais
• en fait, elle externalise l’état de variables internes à Oracle
• Usage de ces données – Principalement pour l’amélioration des performances de la BD
• Ex. V$Session
– Le DBA peut déconnecter les utilisateurs avec la commande suivante
SQL> SELECT sid, serial#, username, type, status> FROM v$session;
SID SERIAL# USERNAME TYPE STATUS----- -------- ------------ ---------- -------1 1 BACKGROUND ACTIVE …8 6 HEURTEL USER INACTIVE
SQL> ALTER SYSTEM KILL SESSION ‘8,6’ ;
106
Les vues dynamiques V$ (2)• Ex. V$SGA (voir premier cours...)
– Informations sur la «System Global Area» (SGA)
• V$LOGFILE : détail des fichiers redo-log
SQL> SELECT * FROM V$SGA;NAME VALUE -------------------- ---------Fixed Size 49152Variable Size 12906496Database Buffers 2048000Redo Buffers 73728
SQL> SELECT * FROM v$logfile;GROUP# STATUS MEMBER------ ------ ------------------------------1 STALE E:\ORANT\DATABASE\LOG4ORCL.ORA2 STALE E:\ORANT\DATABASE\LOG3ORCL.ORA3 STALE E:\ORANT\DATABASE\LOG2ORCL.ORA4 E:\ORANT\DATABASE\LOG1ORCL.ORA
107
Table DUAL• Elle permet de
– récupérer la date système (SYSDATE)– tester le formatage de données de type DATE– tester le bon «parenthésage» d'expressions– etc.
• Possède une seule colonne (DUMMY) et un seul tuple
SQL> SELECT TO_CHAR(SYSDATE,'DD-MM-YYYY HH24:MI')> FROM DUAL;
TO_CHAR(SYSDATE,'DD-MM-YYYY HH24:MI')-------------------------------------23-02-2004 22:05
SQL> SELECT 89456/562 FROM dual;
89456/562----------159.174377
108
Quelques vues intéressantes (1)• Instance Oracle
– V$DATABASE: Statut de la base de données– V$INSTANCE: Détails sur l’instance– V$PARAMETER: Paramètres d’initialisation de l’instance– V$PROCESS: Processus lancés par l’instance et les utilisateurs– V$SGASTAT: Détail de l’occupation mémoire de votre SGA
• Structure logique – DBA_EXTENTS : Description des Extents composant les
Segments de la base de données– DBA_FREE_SPACE : Extensions libres dans tous les Tablespaces– DBA_SEGMENTS : Allocation d’espace disque de tous les
Segments de la base de données
109
Quelques vues intéressantes (2)• Structure physique
– V$CONTROLFILE : Liste des fichiers de contrôle de votre BD– V$DATAFILE: Détail des fichiers de données de la BD– V$TABLESPACE : Tablespaces de la base de données
• Utilisateurs et droits – DBA_ROLE_PRIVS : Rôles reçus et donnés de la BD– DBA_USERS : Informations concernant les utilisateurs
déclarés de la base de données– V$SESSION : Détail de toutes les sessions actives de l’instance
• Objets du schéma – DBA_TABLES : Description des tables relationnelles de la BD– DBA_INDEXES: Description de tous les index de la BD– DBA_CLUSTERS: Description de tous les clusters de la BD
110
Optimisation de Requêtes
• Introduction• Evaluation de requêtes
– Etape 1. Contrôle syntaxique et sémantique– Etape 2. Simplification de requêtes– Etape 3. Restructuration algébrique– Etape 4. Choix du meilleur plan– Etape 5. Exécution
• Difficultés de l’optimisation• L’optimisation dans Oracle• Etude de cas
Support construit à partir des slides de N.Anciaux, P Borlat (Oracle Fr), P. Pucheral et R. Ramakrishnan
111
Architecture en couche d’un SGBD
Gestion deMémoire
Gestion deVerrous
Gestion desJournaux
Méthodes d’accès aux données
Opérations relationnelles
Moteur d’exécution
Optimiseur
Analyseur sémantique
Interface
Système opérationnel
112
Traduction SQL Algèbre
SelectFromWhere
Requête SQL Arbre logique Arbre Physique
Traduction
113
Optimisation « logique » …
π
σ
Patients Visites
π
π
σ
Visites
π
σ
Patients
Select Patients.Nom, Patients.PrénomFrom Patients, VisitesWhere Patients.Id-P = Visites.Id-Pand Patients.Ville = ’Paris’and Visites.Date = ’15 juin’
114
Optimisation « Physique » …
Sélection – FTS (Full Table Scan) ?– Index Scan (B+tree) ?– Index Scan (Bitmap) ?
Jointure – Nested Loop Join ?– Index Join ?– Hash Join ?– Sort Merge Join ?
π
π
σ
Visites
π
σ
Patients
115
Optimiser : pour quoi faire ?• Une question • Plusieurs expressions
équivalentes en SQL• Plusieurs expressions
équivalentes en algèbre• Plusieurs algorithmes
équivalents
Coû
t
Plans sémantiquement équivalentsVariation de performance de plusieurs ordres de magnitude
Ex:5 jointures 1620 plans possibles10 jointures 17 Milliards de plans…
116
Qui optimise ?
• Dans la théorie …– 2 requêtes SQL équivalentes (i.e., donnant le même résultat) doivent,
après optimisation, produire le même plan d’exécution (i.e., le meilleur) !– Seuls les concepteurs de SGBD (noyau) devraient avoir besoin de
comprendre l’optimisation pour développer un bon optimiseur de requêtes
• Mais dans la pratique– Les algorithmes ont leurs limites (2 requêtes équivalentes peuvent ne
pas être identifiées comme telles)– Le bon choix dépend souvent des données (distribution, taille,
sélectivité), dont la connaissance est approximative– Le bon choix dépend également de ce que l’on souhaite optimiser
(ressources, temps d’exécution, latence ?)– Enfin, seuls les plans d’exécution rendus possibles par le schéma
physique de la BD sont évalués
117
Qu’est-ce qu’un plan optimal ?• But de l’optimisation
– Trouver le plan d’exécution optimal pour une requête ?
• Ce qu’on entend par optimal– Donnant les résultats le + vite ….
• Optimisation pour le temps de réponse
– Minimisant la consommation de ressources• Optimisation du travail total
– Minimisant le temps de délivrance des premiers tuples• Optimisation de la latence (temps de retour du premier tuple)
118
Etape 1: Contrôle syntaxique & sémantique
• Analyse syntaxique– Vérification de la syntaxe de la requête– Et sa cohérence vis-à-vis du schéma de la base
• Relations et attributs impliqués, typage, etc.
• Analyse sémantique– Vérification de la ‘signifiance’ de la question
• Voir si la requête est correcte, non contradictoire, faisable, etc…
– 2 notions permettant l’analyse sémantique des requêtes• Graphe de connexion des relations• Graphe de connexion des attributs
119
Exemple• On considère le schéma de base de données suivant
– Visites (vis_id, nom_patient, prénom_patient, adresse, region)– Presc (vis_id,med_id, date, quantité)– Medic (med_id, labo, region, type, label)
• La requête suivante– « Nom et prénom des patients visités dans le Béarn à qui on a prescrit des
médicament du laboratoire ROCHE de type antibiotique de numéro de label < 14 après le 20 août 2006 »
• Exprimée en SQLSELECT nom_patient, prénom_patientFROM Medic M, Presc P, Visites VWHERE M.type = 2076
AND M.label < 14AND M.labo = "ROCHE"AND P.date >= "2006-08-20"AND V.region = "BEARN"AND V.vis_id = P.vis_idAND P.med_id = M.med_id
120
Vérifier la correction de la question (1)• Notion 1 : Construction du graphe de connexion des relations
– Un sommet est associé à chaque relation– Une jointure est représentée par un arc– Une sélection par une boucle sur une relation– Une projection par un arc vers le noeud résultat
• Graphe non connexe Question ‘incorrecte’ (relation isolée…)– Un graphe est connexe si et seulement si
2 points quelconques du graphe sont toujours reliés par un chemin
M.med_id=P.med_idV.vis_id=P.vis_id
P
V M
V.région="Béarn" M.label<14 & M.labo="Roche"
P.date>="2006-08-20"
Résultat
nom_patient, prénom_patient
121
Vérifier la correction de la question (2)
• Notion 2 : Construction du graphe de connexion des attributs– Un sommet est associé à chaque
référence d’attribut ou de constante– Un arc de la forme ai aj
représente ai ≤ aj+c– Une inégalité est matérialisée par
2 arcs valués par 0
• graphe avec un cycle dont la somme des valuations est négative
Question contradictoire
M.label 14
M.labo Roche0
P.date 2006-08-20
V.region BEARN
V.vis_id P.vis_id
P.med_id M.med_id0
0
0
0
0
c
0
0
0
0
122
Vérifier la correction de la question (3)• Ex.
SELECT * FROM Medic M, Presc PWHERE M.type = 1978 AND P.date <= 1976 AND M.type = P.date
• Cycle de valuation -2 sélection infaisable
M.type
0
P.date
1976
0
1978
0
-2
123
Etape 2 : Simplification de requêtes (1)1. Utilisation de la logique des prédicats
• Ex. Requête initiale
SELECT * FROM Medic MWHERE ((M.label = 12) P
OR (M.labo = ‘WHITEHALL') QOR (M.labo = ‘AVENTIS')) RAND NOT ((M.labo = ‘WHITEHALL') QOR (M.labo = ‘AVENTIS ')) ; R
• Critère: ((P ∨ Q ∨ R) ∧ NOT (Q ∨ R)) ≡ P ∧ NOT Q ∧ NOT R
• Requête équivalente avec critère simplifié
SELECT * FROM Medic MWHERE (M.label = 12) PAND NOT (M.labo = ' WHITEHALL') QAND NOT (V.labo = 'AVENTIS'); R
Pourquoi une requête aussi stupide ?
1) c’est une requête sur une vue2) une requête construite par programme3) une requête générée par une IHM avec clics successifs ...
124
Simplification de requêtes (2)2. Utilisation de contraintes d’intégrité
• Contraintes contradictoires avec la qualification• SELECT * FROM Medic WHERE labo = 'Roche‘ AND label < 10• Contrainte d’intégrité sur Medic : labo = 'Roche' label > 12• SELECT * FROM Medic WHERE labo = 'Roche'
AND label < 10 AND label > 12
Inutile d’exécuter la requête : 0 tuple résultat
• Complément de la requête• SELECT * FROM Medic WHERE labo = 'Roche'• Il existe un index sur Medic.label (mais pas sur Medic.labo…)• SELECT * FROM Medic WHERE labo = 'Roche‘ AND label > 12
L’index est utilisable pour évaluer la requête
125
Etape 3 : Restructuration algébrique• Convention de représentation des opérateurs
ProduitCartésien
X
R S
Différence_
SR
Union
R S
U
Jointure
R.a = S.bSR
Projection
V.med_id, V.labo
Selection
M.labo=‘ROCHE’
Intersection_
SR
Group byΞ
R
126
Ex. Plan d’exécution candidat (1)
vis_id
V P M
=
vis_id
med_id med_id
=
V.nom_patient
R
^ Region = “Béarn"^ date > "20/08/2006"
labo = “Roche"
^ label = 17
Plan candidat N°1
« Nom des patients visités dans le Béarn à qui on a prescrit des médicaments du laboratoire ROCHE de numéro de label = 17 après le 20 août 2006 »
Requête
127
Ex. Plan d’exécution candidat (2)
V P M
Region = “Béarn"
date > "20/08/2006"
labo = “Roche" ^ label = 17
vis_id
=
med_id med_id
=
nom_patient prénom_patient
R
vis_id
labo = “Roche" ^ label = 17
V P M
Region = “Béarn"
date> "20/08/2006"
vis_id
med_id med_id
vis_id
=
=
nom_patient prénom_patient
R
Plan candidat N°2 Plan candidat N°3
De ces 3 arbres, lequel est le meilleur ?
Le premier est sûrement moins bon, mais les 2 derniers ?128
Restructuration algébrique : objectif• Problème
– Suivant l’ordre des opérateurs algébriques dans un arbre, le coût d’exécution est différent
• Pourquoi ?– Certains opérateurs diminuent le volume de données alors que d’autres
peuvent l’augmenter– Le coût des algorithmes varie en fonction du volume de données à traiter
(progression logarithmique, linéaire, exponentielle)– Certains opérateurs/algorithmes changent l’organisation (tri, placement)
des tables opérandes
• La restructuration algébrique – Consiste à transformer l’arbre pour en minimiser le coût– En exploitant les équivalences d’expression de l’algèbre relationnelle …
129
Equivalences de l’algèbre relationnelle• Deux expressions algébriques sont équivalentes SSI elles produisent le
même résultat
• Exemples de règles d’équivalence– Sélections σc1(σc2(… σcn(Doc))) ≡ σc1∧c2∧…∧cn(Doc) (Groupement)
σc1(σc2(Doc)) ≡ σc2(σc1 (Doc)) (Commutativité)– Projections πa1(πa2(… πan(Doc))) ≡ πa1, …, an(Doc) (Groupement)– Jointures Doc∞(Vis∞Pres) ≡ (Doc∞Vis)∞Pres (Associativité)
Doc∞Vis ≡ Vis∞Doc (Commutativité) (etc…)
• Ces équivalence permettent notamment de– Changer l’ordre des opérations de jointure– ‘Pousser’ les sélection/projection avant les jointures
130
Autres règles d’équivalence
• Projection commute avec sélection si la projection conserve les attributs utilisés par la sélection (Semi commutativité)– Ex. πNom(σNom>’%D’(Doc)) ≡ σNom>’%D’(πNom(Doc))
• Une sélection sur R commute avec R∞S (distributivité de σ /∞)– σC1(R∞S) ≡ (σC1(R))∞S, avec C1 critère sur attributs de R– σC1(R∞S) ≡ (σC1(R))∞(σC1(S)), avec C1 critère sur attributs de R et S
• Si une projection suit une jointure R∞S, on peut la ‘pousser’ en retenant seulement les attributs de R (et de S) nécessaires à la jointure (ou aux projection finales) (distributivité de π /∞)– Ex. πNom, Date (Doc∞Vis) ≡ πNom(πNom, id (Doc) ∞ πDate, docid (Vis))
131
Bilan sur les règles d’équivalences
• Et aussi…– Distributivité des π / ∞– Distributivité des σ / Unions & différences– Distributivité des π / Unions
SR ≡ RS
Commutativité des ∞
≡SR
T
S T
R
Associativité des ∞
Ai = a
Aj = b
Ai = aetAj = b≡
Groupabilité des σAi
Aj
Ai,Aj≡
Groupabilité des π
A1,..,Ai
Aj = a
AjetA1,..,Ai
Aj = a
A1,..,Ai
≡
Semi commutativité de π avec σ
≡
SR
R.Aj = aetS.Aj = b
R.Ai = a
R S
S.Aj = a
Distributivité des σ / ∞
1 2
3
4
5
67
8 132
Heuristique d'OptimisationAppliquer d'abord les opérations réductrices (sélections
et projections) en les groupant sur chaque relation
1. Dégrouper les sélections (Règle 3)2. Rapprocher les sélections des feuilles (Règles 4, 5 et 7) 3. Grouper les sélections aux feuilles (Règle 3)4. Rapprocher les projections des feuilles (Règles 4, 6 et 8)
• L'ordre des unions, différences et jointures est inchangé !!!
133
V P M
Region = “Béarn"
date > "15-05-2006"
labo = "Roche" ^ Label = 17
vis_id
=
med_idnom_patient prénom_patient
vis_id
med_id med_id
=
nom_patient prénom_patient
R
vis_id
nom_patient prénom_patient
med_idvis_id
med_id
Exemple d'optimisation
vis_id
V P M
=
vis_id
med_id med_id
=
nom_patient prénom_patient
R
^ Region = “Béarn"
^ date > "15-05-2006"
labo = "Roche"
^ Label = 17
134
Etape 4. Optimisation heuristique• Optimisation indépendante des données• Heuristiques classiques:
– Appliquer les heuristiques indiquées précédemment– Utiliser les indexs disponibles– Utiliser les ‘meilleurs’ algorithmes de jointure
1. Hash join2. Sort merge join3. Nested Loop join avec index4. Nested loop join
• L’ordre des opérations dépends de l’expression SQL• Présent dans Oracle (Rule Based Optimizer ou RBO)
135
Etape 4. Optimisation basée coût
Générateur dePlans
Graphe d'opérations
Heuristiquesde choix
Plan d'exécutionOptimal
Schéma interne
Plans d'exécution(espace de recherche)
Statégie deRecherche
Bibliothèque detransformations
Modèle de coût
• Dépend des caractéristiques des données• Présent dans Oracle (Cost Based Optimizer ou CBO)• Plus efficace que le RBO !
136
Difficultés de l’optimisation basée coût
• Espace de recherche très grand (plans candidats)– n algorithmes par opérateur – p ordonnancement pour les opérations binaires
• Modèle de coût (choix du plan)– Difficulté pour estimer le coût de chaque opérateur– Difficulté encore plus importantes pour estimer la taille
des résultats intermédiaires (permettant de calculer l’opérateur suivant)
– Propagation exponentielle des erreurs (dans l’arbre d’exécution) !
137
Modèle de coût
• Paramètres d’entrée– machine (puissance, disques, mémoire, réseau, etc..)– Arbre d’exécution– Algorithmes relationnels– Schéma de la base– Statistiques sur les relations : Taille, Domaine, Nb
valeurs distinctes, Répartition, Histogrammes• Traitement
– Evaluation de la taille des résultats intermédiaires– Evaluation du coût
• Sortie– Un coût en termes d’I/O, CPU, etc... ou un coût global
138
Estimation des sélectivités• TAILLE (σ(R)) = s * TAILLE(R) avec:
– s (A = valeur) = 1 / NDIST(A)– s(A > valeur) = (max(A) - valeur) / (max(A) - min(A))– s (A IN liste valeurs) = (1/NDIST(A)) * CARD(liste valeurs)– s(P et Q) = s(P) * s(Q)– s(P ou Q) = s(P) + s(Q) - s(P) * s(Q)– s( not P) = 1 - s(P)
• TAILLE( R |><| S) = p * TAILLE(R) * TAILLE(S)– p = 1 / MAX(NDIST(A),NDIST(B)) si distribution uniforme des attributs A
et B sur un même domaine– p = 1 si produit cartésien
• Modèle de coût basé sur des hypothèses d’uniformité de distribution et/ou sur des statistiques
139
Les statistiques• Possibilité d’histogrammes
– RunStat(<Table>, <attribut>) construction et stockage d’un histogramme de variation de l’attribut dans la table.
– Utilisation par le modèle de coût– Sinon, hypothèse d ’uniformité
• Exemple :– Personnes ayant un salaire entre 2K€ et 4 K€ ?– Personnes ayant 2 véhicules ?– Personnes ayant 2 véhicules et un salaire entre 2 et K4 K€?
0 0.5 1 1.5 2.0 2.5 3.0 3.5 4
20%
0 1 2 3 4
15%
20%
15%
3% ? Non !
En fait, 14%
140
Espace de recherche• Facteurs jouant sur la taille de l’espace de recherche
– A chaque table correspond plusieurs chemins d’accès– A chaque opérateur correspond plusieurs algorithmes
• Algorithme physiques de jointure, élimination des doubles, etc.– Les opérateurs peuvent être ordonnancés différemment
• En plus : les opérations binaires ne sont pas symétriques – Notion de relation externe / interne (même pour 1 algorithme fixé!)– Notion de pipeline / matérialisation
• Notion de lien bloquant / non bloquant– Convention (du cours) : entrée gauche des opérateurs est matérialisée…
Différentes formes d’arbres sont possibles. Influence sur• La consommation mémoire• Le mode d’exécution• et donc les performances
141
Rappel : pipeline / matérialisation
output bufferR
S
h(R.a)
build
probe
R hash table
Memory
R S
h(S.b)
Table de hachageDOC
VIS Test
Hash Join : bloquant Hash Join : Non bloquant
Scan S
Scan R
Build 1
Probe 1
SR
Table de hachage
Table de hachage
Test
DOC
VIS
Temps d’exécution total (banque)
Temps de latence (recherche Internet)
142
• L’une des tables passe complètement en pipeline • En général, il s’agit de la plus grosse table…• Ex. R passe en pipeline
• La taille mémoire consommée est importante…
Arbre linéaire droit (right deep tree)
Quelle est la taille mémoire nécessaire ? Build1 + Build2 + Build3 = |S| + |T| + |U|
Scan U
Scan T Scan R
Scan S
Build 3
Build 1
Build 2
Probe 2
Probe 3
Probe 1
RS
T
U
143
• Le résultat de chaque jointure est envoyé en pipeline à l’opérateur suivant– Pas de stockage de la sortie de chaque opérateur sur disque
(transmission directe à l’opérateur suivant…)• Le flot grossit : ordonner les jointures selon leur sélectivité
• La taille mémoire consommée est moindre…
Arbre linéaire gauche (left deep tree)
Scan U
Scan T
Scan R
Scan S
Build 3
Build 1
Build 2
Probe 2
Probe 3
Probe 1
R S
T
U
Quelle est la taille mémoire nécessaire ?
MAX(Build1; [Build1+]Build2; [Build2+]Build3)= MAX(|R|; |R|+|R ∞ S|; |R ∞ S|+|R ∞ S ∞ T|) 144
• Mélange des deux stratégies précédentes
• La taille mémoire consommée est intermédiaire…
Arbre bushy (bushy tree)
Scan U
Scan T
Scan R
Scan S
Build 3
Build 1
Build 2
Probe 2
Probe 3
Probe 1
R S T U
Quelle est la taille mémoire nécessaire ?
MAX(Build1; Build1+Build3; Build2+Build3)= MAX(|R|; |R|+|R ∞ S|; |R ∞ S|+|T|)
145
• Sans considérer les différents algorithmes ni la consommation mémoire– Jointure de 5 relations (avec produits cartésiens)
• 120 arbres linéaires différents• 1620 arbres bushy différents
– Jointure de 10 relations (idem)• 3 628 800 arbres linéaires différents• 17 643 225 600 arbres bushy différents !!!
L’espace de recherche est très grand…
Conclusion sur la taille de l’espace de recherche
R S
T
U
ScanU
ScanT
ScanR
Scan S
Build 3
Build 1
Build 2
Probe 2
Probe 3
Probe 1
Arbre Bushy (Bushy tree)
R S T U
ScanU
ScanT
ScanRScanS
Build3
Build1
Build2
Probe 2
Probe 3
Probe 1
Arbre linéaire gauche (left deep tree)
ScanU
ScanT ScanR
ScanS
Build 3
Build1
Build2
Probe 2
Probe 3
Probe 1
RS
T
U
Arbre linéaire droit (right deep tree)
146
Stratégies de recherche• But de la stratégie de recherche
– Minimiser l’espace de recherche – Sans trop réduire l’efficacité du choix…
Stratégie de recherche
Enumérative
Théorie génétique
Augmentation heuristique
Amélioration itérative
Recuit simulé
Aléatoire
Exhaustive
147
Bilan : Qualité de l’optimisation1. Qualité du schéma physique : déterminant
– L'utilisation d'index• accélère les sélections et les jointures (donc le contrôle des
contraintes) mais ralentit les mises à jour et les insertions• offre des informations statistiques à l'optimiseur
– L'organisation des données• égaliser les I/O entre disques (log et bases, index et tables, partitions
de tables sur ° disques) Ex: tablespaces en Oracle
2. Qualité de l'optimiseur (heuristique/coût)– Qualité du modèle de coût utilisé– Qualité de la stratégie de recherche de l'optimiseur
3. Qualité de l’administration– Qualité des traces ou indicateurs générés par le système– Qualité des outils d'aide à l'administration– Qualité de l’administrateur ! 148
Réglage du SGBD – Database Tuning• Réglages du SGBD, amélioration des performances
– Manuel par l’administrateur BD – par des outils externes de diagnostiques– par des outils intégrés automatiques ex. Oracle, SQL Server
149
Exemple : Oracle : Automatic SQL Tuning
Automatic Tuning Optimizer
Analyse des Statistiques
SQL Profiling Analyse des chemins d’accès
Analyse des structures SQL
150
Optimisation dynamique
• L’optimisation peut se faire à la compilation– Optimisation dite statique– Le coût n’est pas imputé à l’utilisateur– Optimisation des requêtes fréquemment posées– On peut ‘prendre son temps’ (dans une certaine mesure)
pour trouver le meilleur plan
• L’optimisation au moment de l’exécution– Dite dynamique
• Peut compléter l’optimisation statique (mises à jours…)– Juste avant l’exécution– Pendant l’exécution
151
Optimisation parallèle• Stratégie ‘one phase optimization’
– On produit un espace de recherche contenant des plans parallèles– Explosion de l’espace de recherche– Complexe (modèle de coût)
• Stratégie ‘two phase optimization’– hypothèse: le meilleur plan parallèle est une parallélisation du meilleur
plan séquentiel– Simple
• Problèmes– Localisation des relations Localisation des opérateurs– Labels de parallélisme ?– Séquençage (scheduling) des opérations ?
152
Optimisation distribuée• Même type de problèmes que pour le parallélisme
– Arbre d’opérateurs– Localisation des opérateurs– Séquençage des opérateurs
• Mais le contexte est différent…– Coût réseau importants– Duplications fréquente– Fragmentation vetricale et horizontale
• Techniques complexes (voir T. Ozsu, P. Valduriez)– Exemple : semi-jointure
153
Conclusion• L’optimisation de requêtes est une tâche cruciale du SGBD
– Fort impact sur les performances du système– Mécanisme puissant mais complexe à maîtriser
• Le SGBD ne peut pas tout– Sans bon DBA, pas de bonne optimisation possible
• De plus en plus d’aide à l’administration– Outils d’audit des performances, ‘explainer’ de plans d’exécution,
outils de recommandation de schéma physique (fragmentation de tables, index, vues concrètes, statistiques …)
• Automatic SQL Tuning dans Oracle 10• Database Tuning Advisor dans SQL Server 2005
– Longue route vers un futur SGBD auto-administrable
154
dans OracleSlides empruntés à Pascale Borlat Salamet – Oracle France
155 156
157 158
159 160
161 162
163 164
165
Index plaçant, quel est le CF ?
CF = le nombre de pages que l’on accède si l’on suit les pointeurs de l’index dans l’ordre
Index non plaçant, quel est le CF ?
Ici, 2 (sans les ‘…’) 3
166
Comment feriez vous un histogrammes du nombre de tuples par valeur de clé ?
0 Max tuples
Valeur = bleu
Valeur = rouge
Valeur = jaune
100 tuples 200 300
167
3 tuples
Sélectivités obtenues avec un histogramme classique ?
0-25 25-50 50-75 75-100
11 0 0 1
168
169 170
Etude de cas
Exécution distribuée de requêtes SQL incluant des fonctions ‘chères’ et manipulant
des objets volumineux (BLOB’s)
171
Etude de cas• But :
– Appliquer les notions introduites sur un cas ‘original’ dans un contexte différent…
• Contexte : – Exécution distribuée de requêtes SQL incluant des fonctions
‘chères’ et manipulant des objets volumineux (BLOB’s)• Problèmes :
– Optimisation de ces requêtes ???– Exécution efficace ???
172
Exemple : Architecture
Data (P,V)
Function(CP)
Function(CV)
Client
serverRio
serverSao Paulo
serverParis
Distributed QueryProcessing
serverBrasilia
173
Exemple : Scenario• Site de Rio:
– Table P contenant les pollutions mesurées : P(regId:int, date:int, value:double, …)
– Table V contenant des images (raster) de regions V(regId:int, image:Blob, …)
• Site de Sao Paulo: – Fonction CP permettant de calculer des indices de pollution en fonction
des données brutes : function CP(double) double
• Site de Paris:– Fonction CV permettant de calculer la couverture végétale sur une
image raster.function CV(Blob) double 174
Exemple : RequêteSelect P.regId, CP(P.value), CV(V.image)From P, VWhere P.regId = V.regId
and CP(P.value) > 1.5and CV(V.image) < 0.3
175
Exemple : Paramètres
Name Description Value
CardP Cardinality of relation P 300 tuples
DistP Number of distinct pollution measurements in P 150 measurements
CardV Cardinality of relation V 50 tuples
DistV Number of distinct images in V 50 images
CardV∞P Cardinality of the result of V join P 200 tuples
DistP_V∞P Number of distinct pollution measurements in V join P 100 measurements
DistV_V∞P Number of distinct images in V join P 40 images
ImgTrans Average image transfer time (with a 1Mb/s network bandwidth) 100 s
CostCP Average per tuple cost of function CP 30 s
CostCV Average per tuple cost of function CV 200 s
σpp Average selectivity for predicate p p (CP (P. value) > 1.5) 0.5
σpv Average selectivity for predicate p v (CV (V. image) < 0.3) 0.8
176
Bibliographie (1)• Site de vulgarisation – Disques durs
– http://www.pcguide.com/ref/hdd/
• Jim gray – Evolution du matériel pour le stockage persistent des données– Présentation : « the five minutes rule »
• Lien : http://research.microsoft.com/~Gray/talks/FiveMinuteRule.ppt– Présentation de Bernard Ourghanlian (Microsoft France)
• Lien : http://projets.etudes.ecp.fr/2003-2004/intranetIT/nvSite/Bibi/Folder.2003-06-27.5856/Folder.2003-03-30.0033/Innovation%20-%20Centrale.pdf/download
• Cours BD– INSA Rouen – Stockage
• http://asi.insa-rouen.fr/enseignement/siteUV/bd/Cours/Supports/BD1/5-Stockage
• Dennis Shasha, Philippe Bonnet – Storage Tuning– Livre : Database Tuning– Lien : http://www.distlab.dk/dbtune/slides/StorageTuning.ppt
• Site industriels – Prix du matériel (nouvelles technologies de stockage)– Sur : http://www.tpc.org/results/individual_results/– Compléments du lien :
• Sun/sunfire.x4100.3.0_tpch.sybaseIQ.100gb.es.pdf• IBM/IBM_595_64_20041118_ESv2.pdf• Sun/sunfire.x4100.3.0_tpch.sybaseIQ.100gb.es.pdf
177
Bibliographie (2)
• Mohammed J. Zaki – Modèle de stockage et d’indexation des données– Présentations (voir en particulier les lectures 7 et 8)– Lien : http://www.cs.rpi.edu/~zaki/cs4380/
• J. L. Griffin et al. – Stockage persistent basé sur la technologie MEMS– Article de recherche : Modeling and Performance of MEMS-Based Storage
Devices (Sigmetrics 2000)– Lien : http://www.pdl.cmu.edu/PDL-FTP/Storage/sigmetrics2000.pdf
• Sites industriels – Stockage persistent basé sur la technologie FLASH– Flash disk 3,5’’ : http://www.bitmicro.com/public_docs/products_edide_
datasheet.3.5.pdf– Flash disk 2.5’’ : http://www.bitmicro.com/public_docs/products_edide_
datasheet.2.5.pdf– Etude de 2005 : http://www.storagesearch.com/semico-art1.html– Latence et débit : http://www.bitmicro.com/products_edisk_35_scsiw.php
178
Bibliographie (3)• Le Noyau Oracle
– Oracle8i, Présentation de Pascale Borlat Salamet, Oracle FranceConférence Bases de Données Avancées 2000http://www.infres.enst.fr/people/saglio/bdas/00/orapbs/index.htm
– Oracle9i et Oracle 10g, Database Concepts www.lc.leidenuniv.nl/awcourse/oracle/server.920/a96524/toc.htmhttp://www-smis.inria.fr/~anciaux/Oracle10_Database_Concepts.pdf
– Rapports Techniques divers• Trivadis : http://www.trivadis.com• Dbspecialists : http://www.dbspecialists.com/presentations/
• Bases de Données – Database Management Systems
Livre de R. Ramakrishnan et J. Gehrke– Livre de G. Gardarin, laboratoire PRiSM
Editions Eyrolles, 2001 http://perso.wanadoo.fr/georges.gardarin