0% ont trouvé ce document utile (0 vote)

238 vues107 pages

BDA Cours Handout

Le document décrit les principes d'optimisation dans un SGBD, notamment la minimisation des accès au disque, plus lent que la mémoire. Il présente également les types de données et leur taille de stockage.

Transféré par

Laradj CHELLAMA

Nous prenons très au sérieux les droits relatifs au contenu. Si vous pensez qu’il s’agit de votre contenu, signalez une atteinte au droit d’auteur ici.

Formats disponibles

Téléchargez aux formats PDF, TXT ou lisez en ligne sur Scribd

0% ont trouvé ce document utile (0 vote)

238 vues107 pages

BDA Cours Handout

Transféré par

Laradj CHELLAMA

Nous prenons très au sérieux les droits relatifs au contenu. Si vous pensez qu’il s’agit de votre contenu, signalez une atteinte au droit d’auteur ici.

Formats disponibles

Téléchargez aux formats PDF, TXT ou lisez en ligne sur Scribd

Opérations Plans

Bases de Données Avancées

IS3012AB
Optimisation de Bases de Données

Nicolas Travers

Département Informatique - Equipe ISI

Laboratoire CEDRIC - Equipe Vertigo

1 / 177

Nicolas Travers
c Ecole Centrale Paris - IS3012AB

Opérations Plans

Plan

1 Optimisation : Opérations

2 Optimisation : Plans d’exécutions

2 / 177

Nicolas Travers
c Ecole Centrale Paris - IS3012AB
Opérations Plans Intro Indexes Opérations Sel Sort Proj Join

1 Optimisation : Opérations
Principes de l’Optimisation
Indexes
Algorithmes des Opérateurs
Algorithmes de Sélection
Algorithme de tri
Algorithmes de projection
Algorithmes de jointure

3 / 177

Nicolas Travers
c Ecole Centrale Paris - IS3012AB

Opérations Plans Intro Indexes Opérations Sel Sort Proj Join

Qu’est-ce que l’optimisation dans un SGBD

Requête ⇒ Arbre d’opérateurs (algèbre relationnelle)

Opérateur ⇒ Accès aux données
Coût en mémoire (place prise en mémoire)
Coût en accès aux données (I/O coûte cher)
⇒ Minimiser les accès au disque

4 / 177

Nicolas Travers
c Ecole Centrale Paris - IS3012AB
Opérations Plans Intro Indexes Opérations Sel Sort Proj Join

Disque dur

5 / 177

Nicolas Travers
c Ecole Centrale Paris - IS3012AB

Opérations Plans Intro Indexes Opérations Sel Sort Proj Join

Lecture d’un disque

Délai rotationnel (rpm)

rpm latency (ms)
15 000 2
10 000 3
7 200 4,16
5 400 5,55
4 800 6,25
Temps total ∼ 9ms
Dépend de :
Fragmentation des données
Changement de piste
Taux de transfert : 125 Mo/s
∼ 300 Mo/s en SATA avec buffer

6 / 177

Nicolas Travers
c Ecole Centrale Paris - IS3012AB
Opérations Plans Intro Indexes Opérations Sel Sort Proj Join

Entrées/Sorties

Une entrée-sortie (I/O) ⇒ Page disque

En anglais : Block
' Secteur sur le disque
= 8 Ko (par défaut sous Oracle)
Un fichier de données : plusieurs pages disques
Plusieurs tuples par pages (dépend de la taille d’un tuple)

7 / 177

Nicolas Travers
c Ecole Centrale Paris - IS3012AB

Opérations Plans Intro Indexes Opérations Sel Sort Proj Join

Exemple de stockage de Cours

Le fichier de cours peut être découpé de cette manière :

P1 2014-02-28 18h15 Travers 30 Introduction
2014-03-15 18h15 Travers 32 Indexes
P2 2014-03-22 18h30 Travers 28 Optimisation
2014-03-29 18h00 Hamdi 27 Dénormalisation
P3 2014-05-15 18h15 Travers 22 Tuning

8 / 177

Nicolas Travers
c Ecole Centrale Paris - IS3012AB
Opérations Plans Intro Indexes Opérations Sel Sort Proj Join

Page dique

Une page 1 contient :

En-tête 2 :
Type de données (Relation, index, cluster. . . )
Schéma de données (attributs, null, blob. . . )
Pointeurs sur places vides, page suivante et précédente
Place vide pour mises à jour
PCTFREE 3 / PCTUSED
Les données
Tuples en entier
En-tête de tuple 4 (identification, valeurs NULL, verrous)
À chaque attribut s’associe sa taille 5

1. Par défaut 8 ko : 8192 o

2. Entre 100 et 200 octets. Dans ce cours, nous utiliserons 192 o
3. Par défaut 10%
4. Variable, mais en moyenne 3 octets
9 / 177
5. Taille de colonne entre 1 et 3 octets. En moyenne 1 octet
Nicolas Travers
c Ecole Centrale Paris - IS3012AB

Opérations Plans Intro Indexes Opérations Sel Sort Proj Join

Pages et Taille d’une table

Cours(Date, heure, nom, nb,

intitule)
5000 tuples
Nb, Dates et heures : 4 o
Texte : 50 o en moyenne.
Block : 8 ko ⇒ 8192 o
|DataBlock| =
100−PCTFREE
(8192 − 192) × 100
=
7200 o
|Tuple| :
3 + 3 × (4 + 1) + 2 × (50 + 1) =
120 o
Nb
7200tuples
par page :
120
= 60t/p
5000
Nb pages : 60
= 84pages
10 / 177

Nicolas Travers
c Ecole Centrale Paris - IS3012AB
Opérations Plans Intro Indexes Opérations Sel Sort Proj Join

Types de données

Types numériques
Type Taille Interval de valeurs
TINYINT 1 octet 0 à 255 ou -128 à 127
SMALLINT 2 octets -32768 à 32767 ou 0 à 65535
MEDIUMINT 3 octets -8388608 à 8388607 ou 0 à 16777215
INT, INTEGER 4 octets -2147483648 à 2147483647 ou 0 à 4294967295
BIGINT 8 octets ∼ 1019
FLOAT(p) 4 octets if 0≤p≤24, nombre de décimales
8 octets if 25≤p≤53
FLOAT 8 octets Par defaut, 53 décimales
DOUBLE(p), REAL 8 octets
DECIMAL(M,D), NUM(M,D) Variable
BIT(M) ∼ (M + 7)/8 octets
Types Dates et Heures Types textuel
Type Taille Type Taille
DATE 3 octets CHAR(M) M octets ou ou M x 2 octets, 0≤M≤255
TIME 3 octets BINARY(M) M octets, 0≤M≤255
DATETIME 8 octets VARCHAR(M) M + 1o (0-255 o), M + 2o (> 255 o)
TIMESTAMP 4 octets BLOB, TEXT L + 2 octets, where L≤215
YEAR 1 octet ENUM(’v1’,’v2’,...) 1o (255 valeurs), 2o (65 535 valeurs)
SET(’v1’,’v2’,...) 1, 2, 3, 4, or 8 octets (64 valeurs maximum)

11 / 177

Nicolas Travers
c Ecole Centrale Paris - IS3012AB

Opérations Plans Intro Indexes Opérations Sel Sort Proj Join

Exemple simple d’accès

πDate (σIntitule=0 Introduction0 (Cours))

SELECT date FROM Cours WHERE Intitule=’Introduction’
Opérateur de sélection nécessaire.
Si pas d’index sur l’attribut Intitule :
Parcours chaque page (physique) de la relation Cours :
TABLE ACCESS FULL
Si le tuple contient ’Introduction’, le tuple est projeté
Coût de l’opération : Nombre de pages de Cours

12 / 177

Nicolas Travers
c Ecole Centrale Paris - IS3012AB
Opérations Plans Intro Indexes Opérations Sel Sort Proj Join

Notations

Tables :
|R| : Nb de pages de la relation R
|R0 | : Nb de pages de la relation R après modification
||R|| : Nb de n-uplets de la relation R
||R0 || : Nb de n-uplets de la relation R après sélection
Index :
|I| : Nb de pages à lire pour une tranversée d’index
(ie. hauteur de l’arbre)
k : Ordre du l’arbre B
φ : clustering factor (cf. indexation)
Sel : Sélectivité d’un attribut
∆ : Nb de feuilles de I sélectionnées
|M| : Nb de pages tampons en MC pour la lecture

13 / 177

Nicolas Travers
c Ecole Centrale Paris - IS3012AB

Opérations Plans Intro Indexes Opérations Sel Sort Proj Join

1 Optimisation : Opérations
Principes de l’Optimisation
Indexes
Algorithmes des Opérateurs
Algorithmes de Sélection
Algorithme de tri
Algorithmes de projection
Algorithmes de jointure

14 / 177

Nicolas Travers
c Ecole Centrale Paris - IS3012AB
Opérations Plans Intro Indexes Opérations Sel Sort Proj Join

Plan

Qu’est-ce qu’un index ?

Index dense versus Index non dense
Arbre-B+
Index de hachage
Index Bitmap

15 / 177

Nicolas Travers
c Ecole Centrale Paris - IS3012AB

Opérations Plans Intro Indexes Opérations Sel Sort Proj Join

Principe d’indexation : Exemple de fichier

Soit le fichier Cours contenant des données

Cours (CODE, Intitule, Responsable, nb auditeur)
On souhaite accéder :
Au Responsable/Intitule d’un cours grâce à son CODE
Aux intitulés des cours d’un responsable
Aux nombre de cours ayant un certain nombre d’auditeurs
⇒ Besoins d’accès particuliers

16 / 177

Nicolas Travers
c Ecole Centrale Paris - IS3012AB
Opérations Plans Intro Indexes Opérations Sel Sort Proj Join

Principe d’indexation : Exemple du fichier Cours

Page CODE Intitule Responsable NB auditeurs

P1 NFE106 Ingénierie de Base de Données Nicolas Travers 30
NFP107 Initiation à la Base de Données Michel Crucianu 100
NFE204 Base de Données Avancées 1 Philippe Rigaux 30
P2 NFE205 Base de Données Avancées 2 Michel Crucianu 20
NSY135 ORM et Framework Philippe Rigaux 15
NFA011 Approfondissement bases de Elisabeth Métais 55
données
P3 NFE102 Infrastructures Technologiques Philippe Rigaux 70
pour le Commerce Electronique
NSY218 Vision par Ordinateur 2D Valérie Gouet-Brunet 20
NSY219 Vision par Ordinateur 3D Valérie Gouet-Brunet 20
Fichier stocké sur 3 pages disques.

17 / 177

Nicolas Travers
c Ecole Centrale Paris - IS3012AB

Opérations Plans Intro Indexes Opérations Sel Sort Proj Join

Exemple d’index

nfe106 nfe205

nfa011 nfe102 nfe106 nfe204 nfe205 nfp107 nsy122 nsy218 nsy219

@ @ @ @ @ @ @ @ @

18 / 177

Nicolas Travers
c Ecole Centrale Paris - IS3012AB
Opérations Plans Intro Indexes Opérations Sel Sort Proj Join

Principe d’indexation : Index

Un index est stocké dans un autre fichier I

Besoin d’une clé d’accès K : CODE
Besoin d’un pointeur sur les données (ROWID) : @
Caractéristiques :
I ne contient pas les données
A chaque K correspond un ou plusieurs ROWIDS @
I est ordonné sur les valeurs de K
Entrée de I : (K, @)
Si I plus gros qu’une page, on indexe de la même manière
chaque page de I

19 / 177

Nicolas Travers
c Ecole Centrale Paris - IS3012AB

Opérations Plans Intro Indexes Opérations Sel Sort Proj Join

Accès aux données

Deux étapes pour faire une recherche :

1 INDEX RANGE SCAN : Parcours de l’index

Donne l’adresse d’une page P

On traverse l’arbre jusqu’aux feuilles de I
Complexité : hauteur de l’arbre (Nb de pages)
Retour : liste de ROWIDS correspondant
2 TABLE ACCESS BY ROWIDS : Accès direct aux données
Ouverture de la page @
Parcours séquentiel de la page pour retrouver la(les) valeur(s)
de K

20 / 177

Nicolas Travers
c Ecole Centrale Paris - IS3012AB
Opérations Plans Intro Indexes Opérations Sel Sort Proj Join

Index dense versus Index non dense

Index non dense 6 : Une page = un pointeur

Valeurs ordonnées physiquement sur la clé K
Une clé de l’index = premier tuple de chaque page
Très peu d’accès
Peu de place : ||K|| = |R|
Un seul ordonnancement = un seul index non dense
Index dense : Une clé = un pointeur
ROWID des feuilles très hétérogènes
Volumineux : ||K|| = ||R||
Temps de parcours lent pour des valeurs multivaluées
⇒ Quel est le type de l’index précédent ?
⇒ Comment insérer un nouveau tuple dans l’index non dense ?

21 / 177
6. Organization Index (Oracle), Clustered index (SQLServer/DB2)
Nicolas Travers
c Ecole Centrale Paris - IS3012AB

Opérations Plans Intro Indexes Opérations Sel Sort Proj Join

Arbre B+

Balanced Tree : Arbre équilibré

Implanté dans tous les SGBD relationnels (index par défaut)
Les feuilles de l’arbre contiennent les pointeurs
Principe des Arbres Binaires de Recherche
⇒ Optimise les requêtes d’égalité
(avec peu de valeurs, et les inéquations)

22 / 177

Nicolas Travers
c Ecole Centrale Paris - IS3012AB
Opérations Plans Intro Indexes Opérations Sel Sort Proj Join

Arbre B+ : caractéristiques

Noeud : clés + ROWID

Noeuds intermédiaires : ROWID sur d’autres noeuds
Noeuds feuilles : ROWID sur tuples du fichier indexé
Taille d’un noeud : 2 * k valeurs (k est l’ordre de l’arbre)
Quel est l’ordre de l’arbre de l’exemple ?

23 / 177

Nicolas Travers
c Ecole Centrale Paris - IS3012AB

Opérations Plans Intro Indexes Opérations Sel Sort Proj Join

Arbre B+ : Recherche

Recherche récursive de K à partir de la racine

Soit C1 à Cn les valeurs des clés de la page
1 Si κ ≤ C1 , recherche sur le noeud référencé P1
2 Si κ > Cn , recherche sur le noeud référencé Pn+1
3 Si Ci < κ ≤ Ci+1 , recherche sur le noeud référencé Pi+1

24 / 177

Nicolas Travers
c Ecole Centrale Paris - IS3012AB
Opérations Plans Intro Indexes Opérations Sel Sort Proj Join

Arbre B+ : Recherche de nfe106

25 / 177

Nicolas Travers
c Ecole Centrale Paris - IS3012AB

Opérations Plans Intro Indexes Opérations Sel Sort Proj Join

Arbre B+ : Insertion

Insertion de (κ, @), dans Arbre B+ d’ordre k :

1 Recherche de la feuille correspondant à K
2 Insertion ordonnée.
Si Nb de clés de la page p = 2 * k + 1 :
1 Allocation d’une nouvelle page p 0
2 Les k + 1 premiers articles sont mis dans p
3 Les k derniers articles sont mis dans p 0
4 La clé k + 1 est insérée au père de p.
Pointeur gauche sur p, pointeur droit sur p 0 .
5 Si père de p déborde, recommencer l’étape insertion sur père
de p.

26 / 177

Nicolas Travers
c Ecole Centrale Paris - IS3012AB
Opérations Plans Intro Indexes Opérations Sel Sort Proj Join

Arbre B+ : Exemple de création

NFE106, NFP107, NFE204, NFE205, NSY122, NFA011, NFE102,

NSY218, NSY219

27 / 177

Nicolas Travers
c Ecole Centrale Paris - IS3012AB

Opérations Plans Intro Indexes Opérations Sel Sort Proj Join

Arbre B+ : Exemple de création

NFE106, NFP107, NFE204, NFE205, NSY122, NFA011, NFE102,

NSY218, NSY219

27 / 177

Nicolas Travers
c Ecole Centrale Paris - IS3012AB
Opérations Plans Intro Indexes Opérations Sel Sort Proj Join

Arbre B+ : Exemple de création

NFE106, NFP107, NFE204, NFE205, NSY122, NFA011, NFE102,

NSY218, NSY219

27 / 177

Nicolas Travers
c Ecole Centrale Paris - IS3012AB

Opérations Plans Intro Indexes Opérations Sel Sort Proj Join

Arbre B+ : Exemple de création

NFE106, NFP107, NFE204, NFE205, NSY122, NFA011, NFE102,

NSY218, NSY219

27 / 177

Nicolas Travers
c Ecole Centrale Paris - IS3012AB
Opérations Plans Intro Indexes Opérations Sel Sort Proj Join

Arbre B+ : Exemple de création

NFE106, NFP107, NFE204, NFE205, NSY122, NFA011, NFE102,

NSY218, NSY219

27 / 177

Nicolas Travers
c Ecole Centrale Paris - IS3012AB

Opérations Plans Intro Indexes Opérations Sel Sort Proj Join

Arbre B+ : Exemple de création

NFE106, NFP107, NFE204, NFE205, NSY122, NFA011, NFE102,

NSY218, NSY219

Exercice :insérer NFA025, NFE212, NSY012, NFE207, NFE231,

NFA032

27 / 177

Nicolas Travers
c Ecole Centrale Paris - IS3012AB
Opérations Plans Intro Indexes Opérations Sel Sort Proj Join

Arbre B+ : Ordre et Hauteur

L’ordre k : dépend de la taille du noeud (nb de clés)

K : taille de la clé à indexer
Case : entete + entete d’attribut
j + Kk+ ROWID 7
|DataBlock|
Nb de cases par noeud : 3+x +|cle|+10
NbCases
Ordre k : 2
Hauteur de l’index :
Dépend du nombre de clés : ||K||
Division de l’ensemble par k à chaque niveau
Division récursive = logarithme
I = logordre (||K||)
Index dense 8 : ||K|| ≤ ||R||
Index non-dense : ||K|| = |R|

7. ROWID = 10 octets sous Oracle

28 / 177
8. Les valeurs nulles ne sont pas indexées
Nicolas Travers
c Ecole Centrale Paris - IS3012AB

Opérations Plans Intro Indexes Opérations Sel Sort Proj Join

Creation d’un BTree

Btree dense :
CREATE INDEX Cours nom ON Cours (nom) ;
Btree non-dense sous Oracle :
CREATE TABLE Cours (. . . ) ORGANIZATION INDEX ;
Entrainement (Applet Java) :
http: // cedric. cnam. fr/ ˜ traversn/ teaching/ btree/

29 / 177

Nicolas Travers
c Ecole Centrale Paris - IS3012AB
Opérations Plans Intro Indexes Opérations Sel Sort Proj Join

Hachage

Partitionnement des données

Très peu de place en mémoire
Fonction de hachage
Table d’adresses de partitions
Collisions : plusieurs clés K par partitions
Divise le temps de parcours par le nombre de partitions (en
moyenne)
⇒ Optimise les requêtes d’égalité.
(Avec de nombreuses valeurs identiques)

30 / 177

Nicolas Travers
c Ecole Centrale Paris - IS3012AB

Opérations Plans Intro Indexes Opérations Sel Sort Proj Join

Hachage : Caractéristiques

Fonction de hachage : h(K) = α

1≤α≤β
β = Nb de partitions
h est une fonction uniforme 9 : P(h(κ) = α) = β1
Si φ(K) = α, alors on ajoute la clé K (+ données) à la page α
Table de hachage T en MC 10
T [α] = Adresse du bloc α
l m
|R|
Taille d’une partition : β

9. Par défaut, ORA HASH sous Oracle

http://docs.oracle.com/cd/B28359_01/server.111/b28286/
functions112.htm
31 / 177
10. Mémoire Centrale
Nicolas Travers
c Ecole Centrale Paris - IS3012AB
Opérations Plans Intro Indexes Opérations Sel Sort Proj Join

Hachage : Exemple

0 1 2

nfe106 … nfe204 …

nfp107 … nfe205 …

nsy122 … nsy218 …

nsy219 …

La clé de hachage prend la valeur numérique de l’UE.

32 / 177

Nicolas Travers
c Ecole Centrale Paris - IS3012AB

Opérations Plans Intro Indexes Opérations Sel Sort Proj Join

Partitionnement

Plusieurs typles de partitionnement :

Hachage
Intervalles de valeurs
Liste de valeurs
Composition des précédentes
Exemple de création :
CREATE TABLE Cours (. . . )
PARTITION BY HASH (RESPONSABLE) PARTITIONS 20 ;

33 / 177

Nicolas Travers
c Ecole Centrale Paris - IS3012AB
Opérations Plans Intro Indexes Opérations Sel Sort Proj Join

Bitmap

Permet de compter le nombre de tuples ayant une certaine

valeur
Très peu de place en mémoire
Evite de parcourir les données
⇒ Optimise les requêtes d’agrégats.
(Ayant une cardinalité faible)

34 / 177

Nicolas Travers
c Ecole Centrale Paris - IS3012AB

Opérations Plans Intro Indexes Opérations Sel Sort Proj Join

Bitmap : Motivation

On cherche à optimiser les requêtes :

SELECT count(*) FROM Cours WHERE responsable =
’Nicolas Travers’ ;
Faible cardinalité de la valeur recherchée (comparé au nombre
de n-uplets)
Arbre B+ :
Beaucoup de n-uplets ayant même valeur
Feuilles de l’arbre très grande
Risque d’accès aux données de chaque pointeur !
Table de hachage :
Beaucoup de collisions dans les partitions

35 / 177

Nicolas Travers
c Ecole Centrale Paris - IS3012AB
Opérations Plans Intro Indexes Opérations Sel Sort Proj Join

Bitmap : Structure

Bitmap sur l’attribut responsable

||R|| : Nombre de tuples
cardresp : Cardinalité de l’attribut Responsable (nb valeur
distinctes)
Création de cardresp vecteurs bitmap de ||R|| bits
Si le i eme tuple a pour valeur ’Nicolas Travers’, alors le i eme bit
du vecteur ’Nicolas Travers’ a pour valeur 1
Le i eme bit des autres vecteurs a pour valeur 0

36 / 177

Nicolas Travers
c Ecole Centrale Paris - IS3012AB

Opérations Plans Intro Indexes Opérations Sel Sort Proj Join

Bitmap : Exemple

Nicolas Tra- Michel Cru- Michel Valérie Elisabeth François-

vers cianu Scholl Gouet- Métais Yves Ville-
Brunet min
1 0 0 0 0 0
0 1 0 0 0 0
0 0 1 0 0 0
0 1 0 0 0 0
0 0 0 1 0 0
0 0 0 0 1 0
0 0 0 0 0 1
0 0 0 1 0 0
0 0 0 1 0 0
Index Bitmap sur Responsable
Les tuples de la 2eme colonne (vecteur de bits), ont pour responsable Michel
Cruciannu

37 / 177

Nicolas Travers
c Ecole Centrale Paris - IS3012AB
Opérations Plans Intro Indexes Opérations Sel Sort Proj Join

Bitmap : Caractéristiques

Stockage :
Codage par tranche de 8 bits
Page de taille 8ko (moins l’en-tête)
l m
Taille d’un vecteur en octets : ||R||
l 8 m
||R||
Taille d’un vecteur en pages : 8×8000
l m
||R||
Taille de l’index : cardresp × 64000 pages
Création d’un Bitmap :
CREATE BITMAP INDEX Cours Nom bitmap ON Cours (NOM) ;

38 / 177

Nicolas Travers
c Ecole Centrale Paris - IS3012AB

Opérations Plans Intro Indexes Opérations Sel Sort Proj Join

Bitmap : Requêtes d’agrégat

SELECT count(*) FROM Cours WHERE responsable = ’Nicolas Travers’ ;

Il suffit de compter le nombre de bits à 1 dans la première
colonne
SELECT count(*) FROM Cours WHERE responsable = ’Nicolas Travers’ OR
responsable = ’Michel Crucianu’ ;
⇒ OU logique avec les deux vecteurs de Responsable
SELECT count(*) FROM Cours WHERE responsable = ’Nicolas Travers’
AND NB auditeur = 20 ;
⇒ ET logique entre vecteur de Responsable et vecteur de
NB auditeur

39 / 177

Nicolas Travers
c Ecole Centrale Paris - IS3012AB
Opérations Plans Intro Indexes Opérations Sel Sort Proj Join

Bitmap : Requêtes d’agrégat (2)

SELECT count(*) FROM Cours WHERE NB auditeurs

> 20 ;
⇒ OU logique entre les vecteurs NB auditeurs ayant valeur > 20
SELECT count(*) FROM Cours WHERE responsable =
’Nicolas Travers’ AND NB auditeur > 20 ;
⇒ ET logique entre vecteur de Responsable et résultat du
vecteur NB auditeur > 20

40 / 177

Nicolas Travers
c Ecole Centrale Paris - IS3012AB

Opérations Plans Intro Indexes Opérations Sel Sort Proj Join

Index : Récapitulatif

Requêtes très sélectives

Arbre B+ dense (ie. clé primaire)
Arbre B+ non-dense (ie. beaucoup de données statiques ou
incrémentales)
Requêtes sélectives
Arbre B+ (ie. peu multivaluée)
Hachage (ie. beaucoup de valeurs)
Requêtes avec intervalle
Arbre B+
Requêtes avec agrégats
Bitmap

41 / 177

Nicolas Travers
c Ecole Centrale Paris - IS3012AB
Opérations Plans Intro Indexes Opérations Sel Sort Proj Join

Index : Bonus

Index couvrant
Ajoute une donnée associée à la clé
Permet d’éviter un accès aux données
Prend plus de place
Requêtes multi-critères
1 un Arbre B+ pour chaque attribut du prédicat
(2x INDEX RANGE SCAN)
2 Intersection des pointeurs retournés (AND-EQUAL)
3 Accès aux pages du résultat (TABLE ACCESS BY ROWIDS)

42 / 177

Nicolas Travers
c Ecole Centrale Paris - IS3012AB

Opérations Plans Intro Indexes Opérations Sel Sort Proj Join

1 Optimisation : Opérations
Principes de l’Optimisation
Indexes
Algorithmes des Opérateurs
Algorithmes de Sélection
Algorithme de tri
Algorithmes de projection
Algorithmes de jointure

43 / 177

Nicolas Travers
c Ecole Centrale Paris - IS3012AB
Opérations Plans Intro Indexes Opérations Sel Sort Proj Join

Opérateurs Relationnels

Une requête SQL est transformée en Plan d’exécution

Le plan est composé d’opérateurs
Chaque opérateur à un coût d’évaluation
Coût en Entrées/Sorties
Dépend des statistiques (taille des tables, nb tuples,
cardinalité, sélectivité. . . )

44 / 177

Nicolas Travers
c Ecole Centrale Paris - IS3012AB

Opérations Plans Intro Indexes Opérations Sel Sort Proj Join

1 Optimisation : Opérations
Principes de l’Optimisation
Indexes
Algorithmes des Opérateurs
Algorithmes de Sélection
Algorithme de tri
Algorithmes de projection
Algorithmes de jointure

45 / 177

Nicolas Travers
c Ecole Centrale Paris - IS3012AB
Opérations Plans Intro Indexes Opérations Sel Sort Proj Join

Sélection : Algorithmes

Opération : σa=0 x 0 (R)

Sélection Séquentielle : TABLE ACCESS FULL
Sélection avec Index Arbre B+ : INDEX RANGE SCAN
Sélection par Hachage : PARTITION HASH SINGLE

46 / 177

Nicolas Travers
c Ecole Centrale Paris - IS3012AB

Opérations Plans Intro Indexes Opérations Sel Sort Proj Join

TABLE ACCESS FULL : Sélection Séquentiel

Appliquer si aucun index sur R(a)

Pour chaque page b de R
Pour chaque tuple t de b
Si t.a =0 x 0
Ajouter t dans S
⇒ Complexité ? |R|

47 / 177

Nicolas Travers
c Ecole Centrale Paris - IS3012AB
Opérations Plans Intro Indexes Opérations Sel Sort Proj Join

TABLE ACCESS FULL : σProf =0 MichelCrucianu0 (Cours))

Page CODE Intitule Responsable

P1 NFE106 Ingénierie de Base de Données Nicolas Travers
NFP107 Initiation à la Base de Données Michel Crucianu
NFE204 Base de Données Avancées 1 Michel Scholl
P2 NFE205 Base de Données Avancées 2 Michel Crucianu
NSY122 Analyse des images et des sons numériques Valérie Gouet-Brunet
NFA011 Approfondissement bases de données Elisabeth Métais
P3 NFE102 Infrastructures Technologiques pour... Francois-Yves Villemin
NSY218 Vision par Ordinateur 2D Valérie Gouet-Brunet
NSY219 Vision par Ordinateur 3D Valérie Gouet-Brunet

Tampon de sortie
CODE Intitule Responsable
NFP107 Initiation à la Base de Données Michel Crucianu

48 / 177

Nicolas Travers
c Ecole Centrale Paris - IS3012AB

Opérations Plans Intro Indexes Opérations Sel Sort Proj Join

TABLE ACCESS FULL : σProf =0 MichelCrucianu0 (Cours))

Page CODE Intitule Responsable

Tampon de sortie
CODE Intitule Responsable
NFP107 Initiation à la Base de Données Michel Crucianu
NFE205 Base de Données Avancées 2 Michel Crucianu

48 / 177

Nicolas Travers
c Ecole Centrale Paris - IS3012AB
Opérations Plans Intro Indexes Opérations Sel Sort Proj Join

TABLE ACCESS FULL : σProf =0 MichelCrucianu0 (Cours))

Page CODE Intitule Responsable

Tampon de sortie
CODE Intitule Responsable
NFP107 Initiation à la Base de Données Michel Crucianu
NFE205 Base de Données Avancées 2 Michel Crucianu

48 / 177

Nicolas Travers
c Ecole Centrale Paris - IS3012AB

Opérations Plans Intro Indexes Opérations Sel Sort Proj Join

INDEX RANGE SCAN + TABLE ACCESS BY INDEX ROWID

Sélection par index appliqué si I sur R(a)

INDEX RANGE SCAN
Ouvrir la page P racine de I
Tant que P n’est pas une feuille
Parcourir l’arbre de P avec a=’x’
P = nouvelle page cible
Sortie : L = liste de ROWIDS
Selectivité de l’attribut a : Sel
Pourcentage de sélection : 0 < Sel < 1
⇒ ||L|| = ||ROWID|| × Sel
TABLE ACCESS BY INDEX ROWID
Pour chaque l de L
Ouvrir la page p pointée par l
Pour chaque tuple t de p
Si t.a = ’x ’
Ajouter t dans le tampon de sortie
49 / 177
⇒ Complexité : |I| + ||ROWID|| × Sel
Nicolas Travers
c Ecole Centrale Paris - IS3012AB
Opérations Plans Intro Indexes Opérations Sel Sort Proj Join

INDEX RANGE SCAN + TABLE ACCESS BY INDEX ROWID : Exemple index

dense

50 / 177

Nicolas Travers
c Ecole Centrale Paris - IS3012AB

Opérations Plans Intro Indexes Opérations Sel Sort Proj Join

INDEX RANGE SCAN

Parcours de l’index
1 Ordre du BTree
Dépend de la taille de la clé
Un noeud = une page (8ko + metadata + PCTFREE)
Contient 2 × k cases
Une case : Cléj+ ROWID (|cle| k + 10o)
(8192−192)×90%
ordre 11 : k = 3+x +|cle|+10
÷2
2 Hauteur du BTree
Division de l’espace par l’ordre à chaque niveau
⇒ logk (||ROWID||)
Index dense : ||ROWID|| = ||R||
Index non-dense : ||ROWID|| = |R|
Plusieurs ROWIDS en sortie (L)
Si ||L||
l > k ⇒ plusieurs
m feuilles : ∆
||ROWID||×Sel
∆= ordre − 1 12
11. A chaque case une entête est nécessaire, comme pour les tuples (3+x)
51 / 177
12. -1 car le parcours de la hauteur compte déjà une feuille de l’arbre
Nicolas Travers
c Ecole Centrale Paris - IS3012AB
Opérations Plans Intro Indexes Opérations Sel Sort Proj Join

INDEX RANGE SCAN + TABLE ACCESS BY INDEX ROWID : Delta

52 / 177

Nicolas Travers
c Ecole Centrale Paris - IS3012AB

Opérations Plans Intro Indexes Opérations Sel Sort Proj Join

INDEX RANGE SCAN : Sélectivité

Pourcentage de ROWID pour une valeur cherchée

Dépend de la répartition des données de l’attribut
Par défaut :
1 13
Sel(R (a)) = Card(R(a))
Exemple :
R (a) est réparti sur 20 valeurs différentes (cardinalité = 20)
1
Statistiquement : Sel(R (a)) = 20 = 5%
1
Clé primaire : Sel = ||R|| (INDEX UNIQUE SCAN)
Statistiques
Histogramme de fréquences par valeur (R(a))
NFA011 NFE102 NFE106 NFE204 NFE205 NFP107 NSY218
5% 2% 6% 4% 3% 2.5% 1.2%
Coût de calcul / mise à jour

53 / 177
13. Card(R(a)) : nb de valeurs distinctes
Nicolas Travers
c Ecole Centrale Paris - IS3012AB
Opérations Plans Intro Indexes Opérations Sel Sort Proj Join

TABLE ACCESS BY INDEX ROWID

Accès aux données via ROWIDS

1 ROWID = 1 page
Optimisation :
Si 2 ROWIDS sur une même page = 1 accès
Tri des ROWIDS par page, puis accès
clustering factor 14 : φ
Degré de distribution aléatoire des données dans R
|R| ≤ φ ≤ ||R||
φ = |R| (Index non-dense)
φ = ||R|| (Très aléatoire/dispersé) - valeur par défaut
Possibilité de trier les données physiquement
φ
⇒ Nombre de pages accédées : ||R|| × Sel × ||R|| = Sel × φ

54 / 177
14. facteur de foisonnement / regroupement des ROWIDS par page
Nicolas Travers
c Ecole Centrale Paris - IS3012AB

Opérations Plans Intro Indexes Opérations Sel Sort Proj Join

INDEX RANGE SCAN + TABLE ACCESS BY INDEX

ROWID : Clustering Factor

55 / 177

Nicolas Travers
c Ecole Centrale Paris - IS3012AB
Opérations Plans Intro Indexes Opérations Sel Sort Proj Join

INDEX RANGE SCAN + TABLE ACCESS BY INDEX

ROWID : Complexité

Parcours de l’index : |I| (hauteur : logk (||cle||))

l m
||cle||×Sel
Nombre de feuilles : ∆ = k −1
Accès aux données : Sel × φ
Coût moyen : |I| + ∆ + Sel × φ
1
Coût index unique : Sel = ||R|| , ∆=0
Coût index non dense : φ = |R|

56 / 177

Nicolas Travers
c Ecole Centrale Paris - IS3012AB

Opérations Plans Intro Indexes Opérations Sel Sort Proj Join

PARTITION HASH SINGLE : Sélection par Hachage

Appliquer si index Hash H sur R(a)

P partitions
Données placées sur les partitions en fonction de H
Hacher la clé 0 x 0 : H(0 x 0 ) = v (1 ≤ v ≤ P)
Recherche :
Pour chaque page p de la partition R(v )
Pour chaque tuple t de p
Sit.a =0 x 0
Ajouter t dans S
l m
|R|
⇒ Complexité ? Taille d’une partition ≈ P

57 / 177

Nicolas Travers
c Ecole Centrale Paris - IS3012AB
Opérations Plans Intro Indexes Opérations Sel Sort Proj Join

PARTITION HASH SINGLE : Exemple

58 / 177

Nicolas Travers
c Ecole Centrale Paris - IS3012AB

Opérations Plans Intro Indexes Opérations Sel Sort Proj Join

PARTITION HASH SINGLE : Partitionnement

Répartition des clés en fonction de la fonction de hachage 15

N-uplets uniforméments répartis sur les P partitions
Problème de répartition
Fonction inadaptée
Répartition inégale des redondances (reste meilleur qu’un
Arbre B+)
⇒ Combinaison de hachage
⇒ Partitionnement par intervalles

59 / 177
15. Sous Oracle : ORA HASH. Peut être surchargée
Nicolas Travers
c Ecole Centrale Paris - IS3012AB
Opérations Plans Intro Indexes Opérations Sel Sort Proj Join

1 Optimisation : Opérations
Principes de l’Optimisation
Indexes
Algorithmes des Opérateurs
Algorithmes de Sélection
Algorithme de tri
Algorithmes de projection
Algorithmes de jointure

60 / 177

Nicolas Travers
c Ecole Centrale Paris - IS3012AB

Opérations Plans Intro Indexes Opérations Sel Sort Proj Join

SORT : Tri physique

Nécessaire pour :
Ordonner le résultat (Order By)
Agrégation (Group By / Count,Sum,Avg . . . )
Éliminer les doublons (Distinct)
Jointure par fusion (Sort Merge Join)

61 / 177

Nicolas Travers
c Ecole Centrale Paris - IS3012AB
Opérations Plans Intro Indexes Opérations Sel Sort Proj Join

SORT : Deux phases

|M| : Tampons en mémoire

|R0 | : Nombre de pages de R en entrée du tri 16
Si |M| < |R0 |
1 Tri :
On découpe R0 en blocs de taille |M|
On trie chaque bloc en mémoire
On écrit 0 les blocs triés
On a |R
|M|
|
partitions triées
2 Fusion :
On fusionne les partitions, |M| − 1 blocs triés en même temps
Récursivement, on obtient au final une seule partition
Cette phase est la plus chère

16. Dépend de l’accès aux données (Full, Index, Hachage)

62 / 177
Calcul de pages normales projetées avec PCTFREE de 0%
Nicolas Travers
c Ecole Centrale Paris - IS3012AB

Opérations Plans Intro Indexes Opérations Sel Sort Proj Join

SORT : Exemple avec |M| = 4

63 / 177

Nicolas Travers
c Ecole Centrale Paris - IS3012AB
Opérations Plans Intro Indexes Opérations Sel Sort Proj Join

SORT : Fusion de deux blocs

Deux blocs L1 et L2 en mémoire, un tampon de sortie S

L1 : 1, 5, 7, 9, 13, 27, 58, 89, 100, 101, 112+ pointeur p1
L2 : 1, 2, 3, 4, 5, 10, 13, 20, 30, 31, 32, 57, 58+ pointeur p2
Tant que p1 6= ∅ | p2 6= ∅
Si S plein ⇒ écrire S sur le disque
Si (p1 6= ∅ & (p2 == ∅ | val(p1 ) <= val(p2 )))
Insérer val(p1 ) dans S
p1 = suivant dans L1
Sinon
Insérer val(p2 ) dans S
p2 = suivant dans L2

64 / 177

Nicolas Travers
c Ecole Centrale Paris - IS3012AB

Opérations Plans Intro Indexes Opérations Sel Sort Proj Join

SORT : Fusion de deux listes (2)

Listes stockées sur plusieurs pages

Algorithme identique, mais lorsque la page est vide, on passe
à la suivante.
Exercice : Fusion de listes sur différentes pages
L1 1, 4, 8 10, 13, 27 29, 55, 60 71, 85
L2 1, 2, 3 4, 5, 10 13, 28, 30 31, 32, 57 80
Coût de lecture ? |L1 | + |L2 |
Coût en ecriture ? |L1 | + |L2 |
Besoin en MC ? nb listes en lecture + 1 liste en écriture

65 / 177

Nicolas Travers
c Ecole Centrale Paris - IS3012AB
Opérations Plans Intro Indexes Opérations Sel Sort Proj Join

SORT : Phase de fusion

A chaque étape
Fusion de |M| − 1 partitions
Les |M| − 1 listes sont fusionnées (et non deux)
Chaque liste fait |M| pages à la première étape
Résultat stocké dans le tampon
Résultat |M| − 1 plus grand que l’étape précédente
|M| − 1 partitions de moins
Lecture et écriture de |R0 | pages
l m
Nombre d’étapes de fusion : log|M|−1 (|R0 |)
l m
Coût de la fusion : 2 × |R0 | × log|M|−1 (|R0 |)

66 / 177

Nicolas Travers
c Ecole Centrale Paris - IS3012AB

Opérations Plans Intro Indexes Opérations Sel Sort Proj Join

SORT : Exercice de tri fusion

18 pages, contenant chacune 3 valeurs. Trier avec |M| = 4

30 28 5 3 2 5 6 30 25 4 2 3 9 2 20 15 21 12
19 32 15 16 20 16 10 40 21 30 39 10 3 8 25 12 42 6
7 18 25 21 12 7 1 42 27 21 20 17 8 9 6 8 39 8
Tri par blocs :
3 15 19 28 1 6 12 30 2 10 21 27 2 8 9 15 6 21
5 16 21 30 2 7 16 40 3 17 21 30 3 8 9 20 8 39
7 18 25 32 5 10 20 42 4 20 25 39 6 8 12 25 12 42
Fusion 1 :
1 3 5 7 10 16 18 20 21 27 30 39 2 6 8 9 15 21
2 3 5 7 12 16 19 21 25 28 30 40 3 8 8 12 20 39
2 4 6 10 15 17 20 21 25 30 32 42 6 8 9 12 20 42
Fusion 2 :
1 2 3 5 6 8 8 10 12 15 17 20 20 21 25 30 32 40
2 3 4 6 7 8 9 10 12 16 18 20 21 21 27 30 39 42
2 3 5 6 7 8 9 12 15 16 19 20 21 25 28 30 39 42

67 / 177

Nicolas Travers
c Ecole Centrale Paris - IS3012AB
Opérations Plans Intro Indexes Opérations Sel Sort Proj Join

Tri : Coût total du tri fusion

Accès à R (Full/Index/Hachage) : ⇒ R0 en sortie

Mémoire Centrale : |M|
|R0 |
Tri de |M| blocs de taille |M| : |R0 |
Fusion par |M| − 1 blocsl m
0 0
Nb de lectures : |R | × log|M|−1 (|R |)
l m
Nb d’écritures : |R0 | × log|M|−1 (|R0 |)
l m
Coût total : (Accès à R + |R0 |)+ (2 × |R0 | log|M|−1 (|R0 |) )

68 / 177

Nicolas Travers
c Ecole Centrale Paris - IS3012AB

Opérations Plans Intro Indexes Opérations Sel Sort Proj Join

1 Optimisation : Opérations
Principes de l’Optimisation
Indexes
Algorithmes des Opérateurs
Algorithmes de Sélection
Algorithme de tri
Algorithmes de projection
Algorithmes de jointure

69 / 177

Nicolas Travers
c Ecole Centrale Paris - IS3012AB
Opérations Plans Intro Indexes Opérations Sel Sort Proj Join

Projection

Intégré dans plusieurs opérateurs :

Sélection séquentielle : TABLE ACCESS FULL
Sélection avec index : TABLE ACCESS BY ROWIDS
Sélection par tri : SORT
Jointures ne tenant pas en mémoire : NESTED LOOPS
Jointures par hachage : HASH JOIN

70 / 177

Nicolas Travers
c Ecole Centrale Paris - IS3012AB

Opérations Plans Intro Indexes Opérations Sel Sort Proj Join

Projection : Avantages

Place mémoire
Taille du tuple minimum
⇒ Plus de tuples par page
⇒ Moins de pages temporaires à écrire et à lire
Peu couteux en traitement
Pipeline 17
⇒ Intégré dans tous les opérateurs lors d’une écriture en
mémoire/disque

71 / 177
17. Transparent 5
Nicolas Travers
c Ecole Centrale Paris - IS3012AB
Opérations Plans Intro Indexes Opérations Sel Sort Proj Join

Projection : Exemple

Table Cours :
5000 tuples de taille 120 o (3 + 3 × (4 + 1) + 2 × (50 + 1))
PCTFREEde 10%
5000
|Cours| = (8192−192)×90% = 64 pages
120

Projection sur la Date (4 o)

Taille des tuples : 8 o (3 + 1 × (1 + 4))
Ecriture temporaire
: PCTFREE=0%

|Cours 0 | = (8192−192)
5000
= 5 pages
8

72 / 177

Nicolas Travers
c Ecole Centrale Paris - IS3012AB

Opérations Plans Intro Indexes Opérations Sel Sort Proj Join

HASH AGGREGATE

Projection, hachage et incrément

SELECT Lettre, COUNT(*) FROM TABLEX GROUP BY
Lettre
|M| Tampons en mémoire centrale
H la fonction de hachage
a l’attribut à projeter, grouper et compter
Algo en 2 phases :
1 Sélection/Projection
Placement des résultats en mémoire dans un des |M| − 1
tampons (partitions)
Tampon choisi par H(a). Une fois plein, on écrit.
2 Lecture de chaque partition générée

73 / 177

Nicolas Travers
c Ecole Centrale Paris - IS3012AB
Opérations Plans Intro Indexes Opérations Sel Sort Proj Join

HASH AGGREGATE : Exercice |M| = 4

Compter l’occurence de chaque lettre
Projeter sur la lettre
Trouver la partition
Incrémenter son occurrence
Capacité après projection : 1 page ⇒ 4 lettres+incrément
Fonction de hachage : indice de la lettre % 3
h(l) = 0 → c, f, i, l, o, r, u, x
h(l) = 1 → a, d, g, j, m, p, s, v, y
h(l) = 2 → b, e, h, k, n, q, t, w, z
Une fois les partitions créées, parcours séquentiel avec somme
des “count” locaux
1A5 4C1 7A1 10 C 1 13 D 0 16 Z 4 19 L 1 22 B 6 25 U 3 28 Z 7 31 A 6 34 A 3
2B7 5H4 8E3 11 F 4 14 X 8 17 H 2 20 K 0 23 C 2 26 N 4 29 H 0 32 L 9 35 X 0
3L3 6E3 9X5 12 G 6 15 Y 0 18 B 6 21 G 3 24 P 6 27 U 6 30 I 5 33 S 4 36 Z 1

Table en mémoire :

74 / 177

Nicolas Travers
c Ecole Centrale Paris - IS3012AB

Opérations Plans Intro Indexes Opérations Sel Sort Proj Join

HASH AGGREGATE : Exercice |M| = 4

Fonction de hachage : indice de la lettre % 3
h(l) = 0 → c, f, i, l, o, r, u, x
h(l) = 1 → a, d, g, j, m, p, s, v, y
h(l) = 2 → b, e, h, k, n, q, t, w, z

1A5 4C1 7A1 10 C 1 13 D 0 16 Z 4 19 L 1 22 B 6 25 U 3 28 Z 7 31 A 6 34 A 3

2B7 5H4 8E3 11 F 4 14 X 8 17 H 2 20 K 0 23 C 2 26 N 4 29 H 0 32 L 9 35 X 0
3L3 6E3 9X5 12 G 6 15 Y 0 18 B 6 21 G 3 24 P 6 27 U 6 30 I 5 33 S 4 36 Z 1

Table en mémoire :
L2 A2 B2
C2 G1 H2
X2 D1 E2
F1 Y1 Z1
Pages disques :

74 / 177

Nicolas Travers
c Ecole Centrale Paris - IS3012AB
Opérations Plans Intro Indexes Opérations Sel Sort Proj Join

HASH AGGREGATE : Exercice |M| = 4

Fonction de hachage : indice de la lettre % 3
h(l) = 0 → c, f, i, l, o, r, u, x
h(l) = 1 → a, d, g, j, m, p, s, v, y
h(l) = 2 → b, e, h, k, n, q, t, w, z

1A5 4C1 7A1 10 C 1 13 D 0 16 Z 4 19 L 1 22 B 6 25 U 3 28 Z 7 31 A 6 34 A 3

2B7 5H4 8E3 11 F 4 14 X 8 17 H 2 20 K 0 23 C 2 26 N 4 29 H 0 32 L 9 35 X 0
3L3 6E3 9X5 12 G 6 15 Y 0 18 B 6 21 G 3 24 P 6 27 U 6 30 I 5 33 S 4 36 Z 1

Table en mémoire :
L2 A2 K1
C3 G2 B1
X2 D1
F1 Y1
Pages disques :
B2
H2
E2
Z1

74 / 177

Nicolas Travers
c Ecole Centrale Paris - IS3012AB

Opérations Plans Intro Indexes Opérations Sel Sort Proj Join

HASH AGGREGATE : Exercice |M| = 4

Fonction de hachage : indice de la lettre % 3
h(l) = 0 → c, f, i, l, o, r, u, x
h(l) = 1 → a, d, g, j, m, p, s, v, y
h(l) = 2 → b, e, h, k, n, q, t, w, z

1A5 4C1 7A1 10 C 1 13 D 0 16 Z 4 19 L 1 22 B 6 25 U 3 28 Z 7 31 A 6 34 A 3

2B7 5H4 8E3 11 F 4 14 X 8 17 H 2 20 K 0 23 C 2 26 N 4 29 H 0 32 L 9 35 X 0
3L3 6E3 9X5 12 G 6 15 Y 0 18 B 6 21 G 3 24 P 6 27 U 6 30 I 5 33 S 4 36 Z 1

Table en mémoire :
L2 P1 K1
C3 B1
X2
F1
Pages disques :
A2 B2
G2 H2
D1 E2
Y1 Z1

74 / 177

Nicolas Travers
c Ecole Centrale Paris - IS3012AB
Opérations Plans Intro Indexes Opérations Sel Sort Proj Join

HASH AGGREGATE : Exercice |M| = 4

Fonction de hachage : indice de la lettre % 3
h(l) = 0 → c, f, i, l, o, r, u, x
h(l) = 1 → a, d, g, j, m, p, s, v, y
h(l) = 2 → b, e, h, k, n, q, t, w, z

1A5 4C1 7A1 10 C 1 13 D 0 16 Z 4 19 L 1 22 B 6 25 U 3 28 Z 7 31 A 6 34 A 3

2B7 5H4 8E3 11 F 4 14 X 8 17 H 2 20 K 0 23 C 2 26 N 4 29 H 0 32 L 9 35 X 0
3L3 6E3 9X5 12 G 6 15 Y 0 18 B 6 21 G 3 24 P 6 27 U 6 30 I 5 33 S 4 36 Z 1

Table en mémoire :
U2 P1 K1
B1
N1
Z1
Pages disques :
L2 A2 B2
C3 G2 H2
X2 D1 E2
F1 Y1 Z1

74 / 177

Nicolas Travers
c Ecole Centrale Paris - IS3012AB

Opérations Plans Intro Indexes Opérations Sel Sort Proj Join

HASH AGGREGATE : Exercice |M| = 4

Fonction de hachage : indice de la lettre % 3
h(l) = 0 → c, f, i, l, o, r, u, x
h(l) = 1 → a, d, g, j, m, p, s, v, y
h(l) = 2 → b, e, h, k, n, q, t, w, z

1A5 4C1 7A1 10 C 1 13 D 0 16 Z 4 19 L 1 22 B 6 25 U 3 28 Z 7 31 A 6 34 A 3

2B7 5H4 8E3 11 F 4 14 X 8 17 H 2 20 K 0 23 C 2 26 N 4 29 H 0 32 L 9 35 X 0
3L3 6E3 9X5 12 G 6 15 Y 0 18 B 6 21 G 3 24 P 6 27 U 6 30 I 5 33 S 4 36 Z 1

Table en mémoire :
U2 P1 H1
I1 A2 Z1
L1 S1
X1
Pages disques :
L2 A2 B2
C3 G2 H2
X2 D1 E2
F1 Y1 Z1
K1
B1
N1
Z1 74 / 177

Nicolas Travers
c Ecole Centrale Paris - IS3012AB
Opérations Plans Intro Indexes Opérations Sel Sort Proj Join

HASH AGGREGATE : Exercice |M| = 4

1A5 4C1 7A1 10 C 1 13 D 0 16 Z 4 19 L 1 22 B 6 25 U 3 28 Z 7 31 A 6 34 A 3

2B7 5H4 8E3 11 F 4 14 X 8 17 H 2 20 K 0 23 C 2 26 N 4 29 H 0 32 L 9 35 X 0
3L3 6E3 9X5 12 G 6 15 Y 0 18 B 6 21 G 3 24 P 6 27 U 6 30 I 5 33 S 4 36 Z 1

Table en mémoire :

Pages disques :
L2 A2 B2
C3 G2 H2
X2 D1 E2
F1 Y1 Z1
U2 P1 K1
I1 A2 B1
L1 S1 N1
X1 Z1
H1
Z1

74 / 177

Nicolas Travers
c Ecole Centrale Paris - IS3012AB

Opérations Plans Intro Indexes Opérations Sel Sort Proj Join

HASH AGGREGATE : Exercice |M| = 4

Pages disques :
L2 A2 B2
C3 G2 H2
X2 D1 E2
F1 Y1 Z1
U2 P1 K1
I1 A2 B1
L1 S1 N1
X1 Z1
H1
Z1

Pages mémoire :
L3 U2
C3 I1
X3
F1
Résultat :

74 / 177

Nicolas Travers
c Ecole Centrale Paris - IS3012AB
Opérations Plans Intro Indexes Opérations Sel Sort Proj Join

HASH AGGREGATE : Exercice |M| = 4

Pages disques :
A2 B2
G2 H2
D1 E2
Y1 Z1
P1 K1
A2 B1
S1 N1
Z1
H1
Z1

Pages mémoire :
A4 P1
G2 S1
D1
Y1
Résultat :
L3 U2
C3 I1
X3
F1
74 / 177

Nicolas Travers
c Ecole Centrale Paris - IS3012AB

Opérations Plans Intro Indexes Opérations Sel Sort Proj Join

HASH AGGREGATE : Exercice |M| = 4

Pages disques :
B2
H2
E2
Z1
K1
B1
N1
Z1
H1
Z1

Pages mémoire :
B3 K1
H3 N1
E2
Z3
Résultat :
L3 U2 D1
C3 I1 Y1
X3 A4 P1
F1 G2 S1
74 / 177

Nicolas Travers
c Ecole Centrale Paris - IS3012AB
Opérations Plans Intro Indexes Opérations Sel Sort Proj Join

HASH AGGREGATE : Exercice |M| = 4

Pages disques :

Pages mémoire :

Résultat :
L3 U2 D1 B3 K1
C3 I1 Y1 H3 N1
X3 A4 P1 E2
F1 G2 S1 Z3
74 / 177

Nicolas Travers
c Ecole Centrale Paris - IS3012AB

Opérations Plans Intro Indexes Opérations Sel Sort Proj Join

HASH AGGREGATE : Complexité

Hachage sur résultat (partitions à créer)

Accès aux données de R : ⇒ |R0 |
Nombre de partition : |M| − 1
|R0 |
l m
Taille d’une partition : |M|−1
|R0 |
Projection/Partitionnement : (|M| − 1) × |M|−1 ' |R0 |
|R0 |
Tri des partitions : (|M| − 1) × |M|−1 ' |R0 |
Coût total : Accès à R + 2 × |R0 |
|R0 |
Problème : |M|−1 > |M|, impossible de faire un tri en
mémoire

75 / 177

Nicolas Travers
c Ecole Centrale Paris - IS3012AB
Opérations Plans Intro Indexes Opérations Sel Sort Proj Join

HASH AGGREGATE : Amélioration

|R0 |
Si |M|−1 > |M|
Hachage récursif sur chaque partition
Fonction h0 différente
Algorithme identique
Coût final : Accès à R + 2 × |R0 | + 2 × α × |R0 |
α ≥ 0 (nombre de hachages successifs)

76 / 177

Nicolas Travers
c Ecole Centrale Paris - IS3012AB

Opérations Plans Intro Indexes Opérations Sel Sort Proj Join

SORT UNIQUE : Tri de données avec DISTINCT

Projection, Tri et suppression des doublons

SELECT DISTINCT Lettre FROM TABLEX GROUP BY
Lettre
|M| Tampons en mémoire centrale
Algo en 2 étapes :
1 Lecture page par page de R
Projection des valeurs dans |M| − 1 pages
Élimination de doublons et tri sur |M| − 1
Quand |M| − 1 plein, écrire sur le disque (une liste pour la
fusion)
2 Tri fusion des blocs projetés
Élimination de doublons lors du parcours

77 / 177

Nicolas Travers
c Ecole Centrale Paris - IS3012AB
Opérations Plans Intro Indexes Opérations Sel Sort Proj Join

SORT UNIQUE : Exercice |M| = 3

On souhaite projeter et éliminer les doublons de la seconde

colonne de la table (lettre)
Capacité après projection : 1 page ⇒ 4 lettres
1A5 4C1 7A1 10 C 1 13 D 0 16 Z 4 19 L 1 22 B 6 25 U 3 28 Z 7 31 A 6 34 A 3
2B7 5H4 8E3 11 F 4 14 X 8 17 H 2 20 K 0 23 C 2 26 N 4 29 H 0 32 L 9 35 X 0
3L3 6E3 9X5 12 G 6 15 Y 0 18 B 6 21 G 3 24 P 6 27 U 6 30 I 5 33 S 4 36 Z 1

Table en mémoire :
ABCE FHLX

78 / 177

Nicolas Travers
c Ecole Centrale Paris - IS3012AB

Opérations Plans Intro Indexes Opérations Sel Sort Proj Join

SORT UNIQUE : Exercice |M| = 3

On souhaite projeter et éliminer les doublons de la seconde

Table en mémoire :
BDGH LXYZ

Stockage temporaire
1) Phase de Tri
ABCE FHLX

78 / 177

Nicolas Travers
c Ecole Centrale Paris - IS3012AB
Opérations Plans Intro Indexes Opérations Sel Sort Proj Join

SORT UNIQUE : Exercice |M| = 3

On souhaite projeter et éliminer les doublons de la seconde

Table en mémoire :
BCGK NPUZ

Stockage temporaire
1) Phase de Tri
ABCE FHLX BDGH LXYZ

78 / 177

Nicolas Travers
c Ecole Centrale Paris - IS3012AB

Opérations Plans Intro Indexes Opérations Sel Sort Proj Join

SORT UNIQUE : Exercice |M| = 3

On souhaite projeter et éliminer les doublons de la seconde

Table en mémoire :
AHIL SXZ

Stockage temporaire
1) Phase de Tri
ABCE FHLX BDGH LXYZ BCGK NPUZ

78 / 177

Nicolas Travers
c Ecole Centrale Paris - IS3012AB
Opérations Plans Intro Indexes Opérations Sel Sort Proj Join

SORT UNIQUE : Exercice |M| = 3

On souhaite projeter et éliminer les doublons de la seconde

Table en mémoire :

Stockage temporaire
1) Phase de Tri
ABCE FHLX BDGH LXYZ BCGK NPUZ AHIL SXZ

78 / 177

Nicolas Travers
c Ecole Centrale Paris - IS3012AB

Opérations Plans Intro Indexes Opérations Sel Sort Proj Join

SORT UNIQUE : Exercice |M| = 3

On souhaite projeter et éliminer les doublons de la seconde

Table en mémoire :

Stockage temporaire
1) Phase de Tri
ABCE FHLX BDGH LXYZ BCGK NPUZ AHIL SXZ

2) Phase de Fusion
ABCD EFGH LXYZ

78 / 177

Nicolas Travers
c Ecole Centrale Paris - IS3012AB
Opérations Plans Intro Indexes Opérations Sel Sort Proj Join

SORT UNIQUE : Exercice |M| = 3

On souhaite projeter et éliminer les doublons de la seconde

Table en mémoire :

Stockage temporaire
1) Phase de Tri
ABCE FHLX BDGH LXYZ BCGK NPUZ AHIL SXZ

2) Phase de Fusion
ABCD EFGH LXYZ ABCG HIKL NPSU XZ

78 / 177

Nicolas Travers
c Ecole Centrale Paris - IS3012AB

Opérations Plans Intro Indexes Opérations Sel Sort Proj Join

SORT UNIQUE : Exercice |M| = 3

On souhaite projeter et éliminer les doublons de la seconde

Table en mémoire :

Stockage temporaire
1) Phase de Tri
ABCE FHLX BDGH LXYZ BCGK NPUZ AHIL SXZ

2) Phase de Fusion
ABCD EFGH LXYZ ABCG HIKL NPSU XZ

2) Phase de Fusion
ABCD EFGH IKLN PSUX YZ

78 / 177

Nicolas Travers
c Ecole Centrale Paris - IS3012AB
Opérations Plans Intro Indexes Opérations Sel Sort Proj Join

SORT UNIQUE : Complexité

Accès à R : ⇒ R0
Écriture des blocs triés sans doublons : |R0 |
l m
Tri fusion des blocs : 2 × |R0 | log|M|−1 (|R0 |)
l m
Coût global : Accès à R + |R0 | +2× |R0 | × log|M|−1 |R0 |

79 / 177

Nicolas Travers
c Ecole Centrale Paris - IS3012AB

Opérations Plans Intro Indexes Opérations Sel Sort Proj Join

Projection : Exercice

Exercice avec le même jeu de données avec |M| = 4

Réaliser HASH UNIQUE
Réaliser SORT AGGREGATE

80 / 177

Nicolas Travers
c Ecole Centrale Paris - IS3012AB
Opérations Plans Intro Indexes Opérations Sel Sort Proj Join

1 Optimisation : Opérations
Principes de l’Optimisation
Indexes
Algorithmes des Opérateurs
Algorithmes de Sélection
Algorithme de tri
Algorithmes de projection
Algorithmes de jointure

81 / 177

Nicolas Travers
c Ecole Centrale Paris - IS3012AB

Opérations Plans Intro Indexes Opérations Sel Sort Proj Join

Jointures

Plusieurs algorithmes de jointures

Présentation d’algorithmes d’égalité
Certains ne marchent pas en inégalité
Tables R et S
Jointure naturelle sur l’attribut a
|M| pages pour l’opération de jointure

82 / 177

Nicolas Travers
c Ecole Centrale Paris - IS3012AB
Opérations Plans Intro Indexes Opérations Sel Sort Proj Join

Jointures : 4 algorithmes

Jointure par Boucles Imbriquées

Simple : NESTED LOOPS (NLJ)
Avec index : NESTED LOOPS + INDEX RANGE SCAN (NLJI)
Jointure par Tri Fusion
MERGE JOIN + SORT JOIN (SMJ)
Jointure par Hachage :
HASH JOIN
Tiens en mémoire : MemoryHashJoin (MHJ)
Sinon : GraceHashJoin (GHJ)

83 / 177

Nicolas Travers
c Ecole Centrale Paris - IS3012AB

Opérations Plans Intro Indexes Opérations Sel Sort Proj Join

NESTED LOOPS : Algorithme

Trois tampons nécessaires :

|M| − 2 pour l’accès à R (table directrice)
Un pour lire séquentiellement S
Un pour les résultats de la jointure T
Algorithme :
Pour chaque bloc de |M| − 2 pages de R
Pour chaque page de S
Joindre en mémoire les tuples
des deux pages sélectionnées dans T

84 / 177

Nicolas Travers
c Ecole Centrale Paris - IS3012AB
Opérations Plans Intro Indexes Opérations Sel Sort Proj Join

NESTED LOOPS : Exemple (|M| = 3)

85 / 177

Nicolas Travers
c Ecole Centrale Paris - IS3012AB

Opérations Plans Intro Indexes Opérations Sel Sort Proj Join

NESTED LOOPS : Exemple (|M| = 3)

85 / 177

Nicolas Travers
c Ecole Centrale Paris - IS3012AB
Opérations Plans Intro Indexes Opérations Sel Sort Proj Join

NESTED LOOPS : Exemple (|M| = 3)

85 / 177

Nicolas Travers
c Ecole Centrale Paris - IS3012AB

Opérations Plans Intro Indexes Opérations Sel Sort Proj Join

NESTED LOOPS : Exemple (|M| = 3)

85 / 177

Nicolas Travers
c Ecole Centrale Paris - IS3012AB
Opérations Plans Intro Indexes Opérations Sel Sort Proj Join

NESTED LOOPS : Exemple (|M| = 3)

85 / 177

Nicolas Travers
c Ecole Centrale Paris - IS3012AB

Opérations Plans Intro Indexes Opérations Sel Sort Proj Join

NestedLoopJoin : Complexité

Accès à R : Table Access Full/By rowids, Partition Hash

Ici SelSeq : |R| ⇒ |R0 |
|R0 |
l m
Lecture séquentielle de S : |M|−2 × |S|
|R0 |
l m
Coût de l’opération : Accès à R + |M|−2 × |S|
Coûte cher si les tables sont grosses

86 / 177

Nicolas Travers
c Ecole Centrale Paris - IS3012AB
Opérations Plans Intro Indexes Opérations Sel Sort Proj Join

NESTED LOOPS + INDEX RANGE SCAN : Algorithme

1 Tampon pour les n-uplets de R

1 Tampon pour l’index I (sur attribut de jointure)
1 Tampon pour les accès à S
Pour chaque n-uplet t de R
Accès à I avec t.a
Tri des ROWIDs (clustering factor)
Accès aux pages pointées

87 / 177

Nicolas Travers
c Ecole Centrale Paris - IS3012AB

Opérations Plans Intro Indexes Opérations Sel Sort Proj Join

NESTED LOOPS + INDEX RANGE SCAN : Exemple

88 / 177

Nicolas Travers
c Ecole Centrale Paris - IS3012AB
Opérations Plans Intro Indexes Opérations Sel Sort Proj Join

NESTED LOOPS + INDEX RANGE SCAN : Exemple

88 / 177

Nicolas Travers
c Ecole Centrale Paris - IS3012AB

Opérations Plans Intro Indexes Opérations Sel Sort Proj Join

NESTED LOOPS + INDEX RANGE SCAN : Complexité

Accès à R + ||R0 ||×(|I| + ∆ + Sel × φ) 18

1
Coût index unique : Sel = ||S|| ,∆=0
Coût index non dense : φ = |R|
1
Sélectivité de la jointure : ||R|| (en moyenne 19 )
Coût de traversée de l’index à chaque n-uplet de R

18. Formule d’accès via index

89 / 177
19. Pas d’arrondis
Nicolas Travers
c Ecole Centrale Paris - IS3012AB
Opérations Plans Intro Indexes Opérations Sel Sort Proj Join

MERGE JOIN + SORT JOIN : Jointure par Tri-Fusion

SORT JOIN : Projection et Tri de R

SORT JOIN : Projection et Tri de S
MERGE JOIN : Fusion des deux listes de valeurs
Que doit-on projeter pour l’expression suivante :
nR.x =S.x S)
πR.a,S.b (R o

90 / 177

Nicolas Travers
c Ecole Centrale Paris - IS3012AB

Opérations Plans Intro Indexes Opérations Sel Sort Proj Join

MERGE JOIN + SORT JOIN : Complexité

Tri : l m
0 0 0
Accès à R + |R | + 2 × |R | × log|M|−1 (|R |) 20
l m
0 0 0
Accès à S + |S | + 2 × |S | × log|M|−1 (|S |)
Fusion : |R0 | + |S 0 |
Forte domination du tri dans la jointure
Utile pour :
Tables non indexées
Tables déjà triées (suppression du coût de tri)
Elimination des duplicats ou tri

91 / 177
20. Formule du Tri-Fusion
Nicolas Travers
c Ecole Centrale Paris - IS3012AB
Opérations Plans Intro Indexes Opérations Sel Sort Proj Join

HASH JOIN : Join par Hachage

Jointures par égalité (équi-jointures) et Jointures naturelles

Deux possibilités :
1 Une table projetée peut tenir en mémoire :
in Memory Hash Join
2 Une table projetée et partitionnée, peut tenir en mémoire :
Grace Hash Join

92 / 177

Nicolas Travers
c Ecole Centrale Paris - IS3012AB

Opérations Plans Intro Indexes Opérations Sel Sort Proj Join

HASH JOIN : MHJ - Jointure en mémoire

|R0 | < |M| (généralement left-join)

|M| − 1 partitions (1 tampon en lecture)
Principe :
1 Accès à R, puis partitionnement de R sur l’attribut de jointure
2 Accès à S, puis jointure avec le hachage de R

93 / 177

Nicolas Travers
c Ecole Centrale Paris - IS3012AB
Opérations Plans Intro Indexes Opérations Sel Sort Proj Join

HASH JOIN : MHJ - Algorithme

Accès à R
Pour chaque n-uplet t de R0
Placer πa,x (t) dans h(t.a)
Accès à S
Pour chaque n-uplet t de S 0
Vérifier si t.a existe dans la partition h(t.a)
Si oui, joindre les tuples

94 / 177

Nicolas Travers
c Ecole Centrale Paris - IS3012AB

Opérations Plans Intro Indexes Opérations Sel Sort Proj Join

HASH JOIN : MHJ - Complexité

Hachage R : Accès à R
Jointure : Accès à S
Coût total : Accès à R + Accès à S
Limite d’utilisation : |R0 | < |M| − 1

95 / 177

Nicolas Travers
c Ecole Centrale Paris - IS3012AB
Opérations Plans Intro Indexes Opérations Sel Sort Proj Join

HASH JOIN : GHJ - Jointure partiellement en mémoire

Si pour R et S :
Supérieure à |M| − 1 (après projection)
Découpé en |M| − 1 partitions
Taille max d’une partition |M| − 2
Algorithme :
1 Partitionnement de R et S sur l’attribut de jointure
(|M| − 1 partitions)
2 NESTED LOOPS sur chaque partition de même valeur de
hachage

96 / 177

Nicolas Travers
c Ecole Centrale Paris - IS3012AB

Opérations Plans Intro Indexes Opérations Sel Sort Proj Join

HASH JOIN : GHJ - Algorithme

Besoin de |M| − 1 tampon pour le hachage

Pour chaque n-uplet t de R0 (|R0 | et |S 0 |)
Si tampon de h(t.a) plein ⇒ vider dans la partition R|h(t.a)
Placer πa,x (t) dans h(t.a)
Pour chaque couple i de partition
Faire jointure par boucle imbriquée NLJ(PRi , PSi )

97 / 177

Nicolas Travers
c Ecole Centrale Paris - IS3012AB
Opérations Plans Intro Indexes Opérations Sel Sort Proj Join

HASH JOIN : GHJ - Complexité

Hachage : Accès à R + |R0 |+ Accès à S + |S 0 |

|R0 |
Taille d’un partition : |M|−1
|R | 0 |S 0 |
Jointures : |M| − 1 × ( |M|−1 0 0
+ |M|−1 ) ⇒ |R | + |S |
Coût total : Accès à R + 2 × |R0 |+ Accès à S + 2 × |S 0 |
Limite d’utilisation :
|M| − 1 ≤ |πR0 | ≤ (|M| − 1)(|M| − 2)
|M| < |πR0 | < |M|2

98 / 177

Nicolas Travers
c Ecole Centrale Paris - IS3012AB

Opérations Plans Intro Indexes Opérations Sel Sort Proj Join

Jointures : Rappels

1 NESTED LOOPS : Une des tables est petite (projection ?)

2 NESTED LOOPS + INDEX RANGE SCAN : Dépend des
statistiques
3 MERGE JOIN + SORT JOIN : Une relation est ou doit être
triée
4 HASH JOIN : MHJ - Partitionnement d’une table
5 HASH JOIN : GHJ - Partitionnement des deux tables

99 / 177

Nicolas Travers
c Ecole Centrale Paris - IS3012AB
Opérations Plans PEL PEP EXPLAIN PEP Optim Pipeline

Introduction

SQL est déclaratif

On dit ce que l’on veut obtenir
On ne dit pas comment l’obtenir
Optimiseur doit :
Comprendre la requête. Traduction en Plan d’Exécution
Logique 21 (PEL)
Choisir le meilleur Plan d’Exécution Physique 22 (PEP)
Exécuter le PEP

21. Opérateurs de l’algèbre relationnelle

100 / 177
22. Opérateurs implémentés dans le SGBD
Nicolas Travers
c Ecole Centrale Paris - IS3012AB

Opérations Plans PEL PEP EXPLAIN PEP Optim Pipeline

Introduction : Exemple

Soit le schéma :
Cours (CODE, Intitule, Responsable)
Auditeurs (CODE UE, CODE AUDITEUR, Annee, Note)
Soit la requête :
Liste des années où Nicolas Travers a eu des auditeurs ?
⇒ SELECT Annee
FROM Cours, Auditeurs
WHERE Responsable = ’Nicolas Travers’ AND
CODE = CODE UE ;

101 / 177

Nicolas Travers
c Ecole Centrale Paris - IS3012AB
Opérations Plans PEL PEP EXPLAIN PEP Optim Pipeline

Introduction : Exemple PEL

1 πAnnee (σResponsable=0 NicolasTravers 0 (Cours n

oCODE =CODE UE Auditeurs))
2 πAnnee (σResponsable=0 NicolasTravers 0 (Cours) n
oCODE =CODE UE Auditeurs)
3 πAnnee (σResponsable=0 NicolasTravers 0 (Auditeurs n
oCODE =CODE UE Cours))
4 πAnnee (Auditeurs n
oCODE =CODE UE σResponsable=0 NicolasTravers 0 (Cours))
Quel est le meilleur plan d’exécution ?
⇒ Le second PEL

102 / 177

Nicolas Travers
c Ecole Centrale Paris - IS3012AB

Opérations Plans PEL PEP EXPLAIN PEP Optim Pipeline

Introduction : Plan d’Exécution Physique (PEP)

1 Accès via l’index sur Cours.Responsable, Projeter sur CODE

2 Trier le résultat
3 Accès séquentiel à Auditeurs, Projeter sur CODE UE et
Annee
4 Trier le résultat
5 Fusionner les deux listes triées (jointure sur
CODE=CODE UE

103 / 177

Nicolas Travers
c Ecole Centrale Paris - IS3012AB
Opérations Plans PEL PEP EXPLAIN PEP Optim Pipeline

Introduction : Etapes de traitement d’une requête

Traduction
SQL ⇒ ⇒ PEL ⇒ Optimisation ⇒ PEP
algébrique

104 / 177

Nicolas Travers
c Ecole Centrale Paris - IS3012AB

Opérations Plans PEL PEP EXPLAIN PEP Optim Pipeline

Introduction : Optimiser le temps d’évaluation

Minimisation du temps
Temps d’évaluation globale de la requête
Temps de réponse du premier résultat
Point d’intérêt majeur
Nombre de pages Lues et Ecrites (I/O)
Ecriture du résultat final
N’est pas pris en compte dans le calcul

105 / 177

Nicolas Travers
c Ecole Centrale Paris - IS3012AB
Opérations Plans PEL PEP EXPLAIN PEP Optim Pipeline

2 Optimisation : Plans d’exécutions

Plan d’Exécution Logique
Plan d’Exécution Physique
EXPLAIN
Optimisation des Plans d’Exécution
Pipeline

106 / 177

Nicolas Travers
c Ecole Centrale Paris - IS3012AB

Opérations Plans PEL PEP EXPLAIN PEP Optim Pipeline

Rappel sur les plans d’exécution

Deux étapes pour l’optimiseur

1 Traduction de la requête dans PEL
2 Traduction du PEL en PEP

107 / 177

Nicolas Travers
c Ecole Centrale Paris - IS3012AB
Opérations Plans PEL PEP EXPLAIN PEP Optim Pipeline

PEL : Décomposition de la requête

Requête SQL décomposée en blocs

Select From Where
Une seule clause Group By et Having
Optimisation bloc par bloc
Requête imbriquée ⇒ groupe de blocs imbriqué

108 / 177

Nicolas Travers
c Ecole Centrale Paris - IS3012AB

Opérations Plans PEL PEP EXPLAIN PEP Optim Pipeline

PEL : Exemple d’imbrication

SELECT intitule, COUNT(*)

FROM Cours, Auditeur
WHERE CODE UE = CODE
AND Responsable = ’Nicolas Travers’
GROUP BY intitule
HAVING COUNT(*) > (SELECT AVG(COUNT(*))
FROM Cours, Auditeur
WHERE CODE UE = CODE
GROUP BY CODE)

109 / 177

Nicolas Travers
c Ecole Centrale Paris - IS3012AB
Opérations Plans PEL PEP EXPLAIN PEP Optim Pipeline

Forme Normale Conjonctive

Toute requête peut être mise sous forme normale conjonctive

(FNC) :
(A=a ∪ B=b) ∩ (A= a ∪ C=c)
Optimisation de A=a ∪ B=b (blocs indépendants)
Si index sur A et index sur B
⇒ Traverser les deux index et faire l’union
Sinon, balayage séquentiel

110 / 177

Nicolas Travers
c Ecole Centrale Paris - IS3012AB

Opérations Plans PEL PEP EXPLAIN PEP Optim Pipeline

PEL : Exemple de plan

SELECT intitule
FROM Cours, Auditeur
WHERE CODE UE = CODE
AND Responsable = ’Nicolas Travers’
πintitule (σresponsable=0 NT 0 (Cours n
oCODE UE =CODE Auditeur ))

111 / 177

Nicolas Travers
c Ecole Centrale Paris - IS3012AB
Opérations Plans PEL PEP EXPLAIN PEP Optim Pipeline

Règles de réécriture
1 Commutativité de la jointure :
RonS≡So nR
2 Associativité de la jointure :
(R on S) o nT ≡So n (R o nT)
3 Regroupement des sélections :
σA=0 a0 (σB=0 b 0 R) ≡ σA=0 a0 ∧B=0 b 0 R
4 Commutativité de la sélection et de la projection :
πA1 ...An (σAi =0 a0 R) ≡ σAi =0 a0 (πA1 ...An R), i∈1, ..., n
5 Commutativité de la sélection et de la jointure :
σA=0 a0 (R o n S) ≡ σA=0 a0 (R) o nS
6 Distributivité de la sélection sur l’union :
σA=0 a0 (R ∪ S) ≡ σA=0 a0 R ∪ σA=0 a0 S
7 Commutativité de la projection et de la jointure :
nAi =Bj S) ≡ πA1 ...1n R o
πA1 ...An B1 ...Bm (R o nAi =Bj πB1 ...Bm S
i∈1..n, j∈1..m
8 Distributivité de la projection sur l’union : 112 / 177

πA1 ..An (R ∪ S) ≡ 1 ..An R

πATravers
Nicolas c ∪ πEcole nS
A1 ..ACentrale Paris - IS3012AB

Opérations Plans PEL PEP EXPLAIN PEP Optim Pipeline

Heuristique pour le PEL

1 Remonter les sélections le plus tôt possible (règles 4 & 5)

2 Remonter les projections le plus haut possible (règles 4, 7 & 8)
3 Décomposer les sélections en une composition. (règle 3)
⇒ πintitule (
πCODE ,intitule (σresponsable=0 NT 0 (Cours))
o
nCODE UE =CODE
πCODE UE (Auditeur ))

113 / 177

Nicolas Travers
c Ecole Centrale Paris - IS3012AB
Opérations Plans PEL PEP EXPLAIN PEP Optim Pipeline

Exemple 2

SELECT P.nom
FROM Cours C, Auditeur A, Personne P
WHERE C.CODE UE = A.CODE
AND Responsable = ’Nicolas Travers’
AND Cursus = ’Base de Données’
AND A.CODE AUD = P.CODE

⇒ πnom (σresponsable=0 NT 0 ∧cursus=0 BD 0 (

Cours o nCODE UE =CODE (
Auditeur o nCODE AUD=CODE Personne)))

114 / 177

Nicolas Travers
c Ecole Centrale Paris - IS3012AB

Opérations Plans PEL PEP EXPLAIN PEP Optim Pipeline

Exemple 2 équivalent

πnom (
πCODE (σresponsable=0 NT 0 (Cours))
nCODE UE =CODE (
o
πCODE AUD,CODE UE (Auditeur )
o
nCODE AUD=CODE
πCODE ,nom (σcursus=0 BD 0 (Personne))
)
)

115 / 177

Nicolas Travers
c Ecole Centrale Paris - IS3012AB
Opérations Plans PEL PEP EXPLAIN PEP Optim Pipeline

2 Optimisation : Plans d’exécutions

Plan d’Exécution Logique
Plan d’Exécution Physique
EXPLAIN
Optimisation des Plans d’Exécution
Pipeline

116 / 177

Nicolas Travers
c Ecole Centrale Paris - IS3012AB

Opérations Plans PEL PEP EXPLAIN PEP Optim Pipeline

Plan d’Exécution Physique

Génération du PEL nécessaire mais pas suffisant

Besoin des informations physiques
Prendre en compte :
Accès disponibles (index)
Organisation de tables (tri, partition)
Statistiques (nb tuples, pages, cardinalité/sélectivité,
Histogramme, clustering factor)

117 / 177

Nicolas Travers
c Ecole Centrale Paris - IS3012AB
Opérations Plans PEL PEP EXPLAIN PEP Optim Pipeline

PEP : Caractéristiques

Représentation arborescente
Feuilles : Accès aux données
Noeuds internes : Opérateur physique
Arc (bas en haut) : Flot de données, consommé par
l’opérateur du dessus

118 / 177

Nicolas Travers
c Ecole Centrale Paris - IS3012AB

Opérations Plans PEL PEP EXPLAIN PEP Optim Pipeline

2 Optimisation : Plans d’exécutions

Plan d’Exécution Logique
Plan d’Exécution Physique
EXPLAIN
Optimisation des Plans d’Exécution
Pipeline

119 / 177

Nicolas Travers
c Ecole Centrale Paris - IS3012AB
Opérations Plans PEL PEP EXPLAIN PEP Optim Pipeline

EXPLAIN : Outils d’affichage de PEP

Outils de représentation de PEP sous Oracle et MySQL

Représentation arborescente (tabulations)
Estimation du coût d’évaluation
Insertion de statistiques d’évaluation

120 / 177

Nicolas Travers
c Ecole Centrale Paris - IS3012AB

Opérations Plans PEL PEP EXPLAIN PEP Optim Pipeline

EXPLAIN : Exemple

Id Opération Name
0 SELECT STATEMENT
1 TABLE ACCESS BY ROWIDS Cours
2* INDEX RANGE SCAN Cours NB AUDITEUR IDX

(2) : access(NB AUDITEUR BETWEEN 20 AND 30)

121 / 177

Nicolas Travers
c Ecole Centrale Paris - IS3012AB
Opérations Plans PEL PEP EXPLAIN PEP Optim Pipeline

Table EXPLAIN PLAN (Oracle)

Toutes les données sont stockées ⇒ Plans EXPLAIN aussi

Oracle Commande de transformation SQL ⇒ EXPLAIN :
EXPLAIN PLAN [ SET STATEMENT ID = ’ID’ ] 23
[ INTO < table name > ] 24
FOR < Requête SQL >
Commande d’affichage automatique du plan :
SET AUTOTRACE ON
MySQL Commande d’affichage de EXPLAIN : EXPLAIN < Requête
SQL >

122 / 177
23. Identifiant pour retrouver le plan
24. Table par défaut : Nicolas
PLANTravers
TABLE
c Ecole Centrale Paris - IS3012AB

Opérations Plans PEL PEP EXPLAIN PEP Optim Pipeline

Sélection / Accès aux données

Opération Option Description

TABLE ACCESS FULL Sélection séquentielle
BY INDEX ROWID Accès aux ROWIDS
CLUSTER Accès via la clé d’index de clus-
ter

123 / 177

Nicolas Travers
c Ecole Centrale Paris - IS3012AB
Opérations Plans PEL PEP EXPLAIN PEP Optim Pipeline

Accès à un Index

Opération Option Description

INDEX UNIQUE SCAN clé primaire/unique
RANGE SCAN données multivaluées
FULL SCAN toutes les clés de l’index
FAST FULL SCAN toutes les clés de l’index sans
prendre les ROWIDS
FULL SCAN min/max des valeurs de l’index
(MIN/MAX)

124 / 177

Nicolas Travers
c Ecole Centrale Paris - IS3012AB

Opérations Plans PEL PEP EXPLAIN PEP Optim Pipeline

Accès à un Index Hash

Opération Option Description

PARTITION SINGLE Accès à la partition sélectionné
HASH par la clé d’accès (sur le FULL
SCAN)
ALL Accès à toutes les partitions
(pas de filtrage sur la clé
hachée)

125 / 177

Nicolas Travers
c Ecole Centrale Paris - IS3012AB
Opérations Plans PEL PEP EXPLAIN PEP Optim Pipeline

Accès à un Index Bitmap

Opération Option Description

BITMAP INDEX SINGLE Accès à l’index bitmap, retourne les
VALUE numéros des tuples
CONVERSION COUNT Compte le nombre de bit à 1
CONVERSION TO Converti les numéros de tuples en
ROWIDS ROWIDs
AND ET logique entre deux listes bitmap
OR OU logique entre deux listes bitmap
MINUS AND NOT logique
INDEX RANGE SCAN Accès à un ensemble de listes
MERGE Fusionne les listes retournées par un
RANGE SCAN

126 / 177

Nicolas Travers
c Ecole Centrale Paris - IS3012AB

Opérations Plans PEL PEP EXPLAIN PEP Optim Pipeline

Tri vs Hachage

Opération Option Description

SORT ORDER BY Sort pour les résultats
AGGREGATE Tri avec fonction d’aggrégat 25
GROUP BY Tri sans fonction (juste Group By)
UNIQUE DISTINCT
JOIN Étape de tri de l’algo de jointure

Opération Option Description

HASH AGGREGATE Hachage avec fonction d’aggrégat
GROUP BY Hachage sans fonction
UNIQUE DISTINCT

127 / 177
25. avec ou sans Group By
Nicolas Travers
c Ecole Centrale Paris - IS3012AB
Opérations Plans PEL PEP EXPLAIN PEP Optim Pipeline

Jointures

Opération Description
NESTED LOOPS NLJ/NLJI, Boucles imbriquées
MERGE JOIN SMJ, Etape de fusion des tables
HASH JOIN HashJoin, construction des partitions, puis
suite de NLJ
AND-EQUAL Intersection de deux listes de ROWIDs pour
une jointure entre deux indexes
Options : OUTER, ANTI, SEMI, CARTESIAN.

128 / 177

Nicolas Travers
c Ecole Centrale Paris - IS3012AB

Opérations Plans PEL PEP EXPLAIN PEP Optim Pipeline

Bonus (1/3)

Opération Description
CONNECT BY Auto-jointure hiérarchique utilisant le
résultat de l’étape précédente
CONCATENATION Union multiples de Result Sets (cf UNION)
COUNT Compte le nombre tuples d’un résultat
FILTER Opération de sélection
FIRST ROW Premier tuple sélectionné par la requête
FOR UPDATE Blocage des tuples retournés pour des MAJ
ultérieures

129 / 177

Nicolas Travers
c Ecole Centrale Paris - IS3012AB
Opérations Plans PEL PEP EXPLAIN PEP Optim Pipeline

Bonus (2/3)

Opération Description
VIEW Accès à une vue, ou création d’une table
temporaire
UNION Union de deux Result Set, sans doublons
UNION-ALL Union de deux Result Set, avec doublons
INTERSECTION Intersection de deux Result Set, contenant
les mêmes valeurs
MINUS Les tuples du premier Result Set sont re-
tournés, sauf ceux présents dans le second

130 / 177

Nicolas Travers
c Ecole Centrale Paris - IS3012AB

Opérations Plans PEL PEP EXPLAIN PEP Optim Pipeline

Bonus (3/3)

Opération Description
SEQUENCE Oracle Sequence Generator
(auto increment d’ID)
REMOTE Accès à une base de données distante
INLIST OPERATOR Un seul opérateur à la fois. Pas de pipeline

131 / 177

Nicolas Travers
c Ecole Centrale Paris - IS3012AB
Opérations Plans PEL PEP EXPLAIN PEP Optim Pipeline

Lecture de EXPLAIN

Structure arborescente (indentation)

L’opérateur le moins indenté est le résultat
Le plus indenté est l’accès aux données
Si deux indentation de même niveau, le premier est exécuté
d’abord
Exercice sur les plans suivants :
Requête SQL correspondante
Coût d’évaluation

132 / 177

Nicolas Travers
c Ecole Centrale Paris - IS3012AB

Opérations Plans PEL PEP EXPLAIN PEP Optim Pipeline

Exemples de plan EXPLAIN : Sélection séquentielle

Id Opération Name
0 SELECT STATEMENT
1* TABLE ACCESS FULL Auditeurs

(1) : access(Annee = 2014)

Statistiques : |Auditeurs| = 1000

133 / 177

Nicolas Travers
c Ecole Centrale Paris - IS3012AB
Opérations Plans PEL PEP EXPLAIN PEP Optim Pipeline

Exemples : Accès via Index unique

Id Opération Name
0 SELECT STATEMENT
1 TABLE ACCESS BY ROWIDS Cours
2* INDEX UNIQUE SCAN Cours Code IDX

(2) : access(CODE = ’NFE106’)

Statistiques : |Cours| = 20, ||Cours|| = 600, |I| = 2 (dense)

134 / 177

Nicolas Travers
c Ecole Centrale Paris - IS3012AB

Opérations Plans PEL PEP EXPLAIN PEP Optim Pipeline

Exemples : Accès via Index dense

Id Opération Name
0 SELECT STATEMENT
1 TABLE ACCESS BY ROWIDS Cours
2* INDEX RANGE SCAN Cours NB AUDITEUR IDX

(2) : access(NB AUDITEUR BETWEEN 20 AND 30)

1
Statistiques : |Cours| = 20, ||Cours|| = 600, |I| = 2 (dense), Sel = 30

135 / 177

Nicolas Travers
c Ecole Centrale Paris - IS3012AB
Opérations Plans PEL PEP EXPLAIN PEP Optim Pipeline

Exemples : Accès via Table de Hachage

Id Opération Name
0 SELECT STATEMENT
1 PARTITION HASH SINGLE
2* TABLE ACCESS FULL Cours

(2) : access(Responsable = ’Nicolas Travers’)

Statistiques : |Cours| = 20, 10 partitions

136 / 177

Nicolas Travers
c Ecole Centrale Paris - IS3012AB

Opérations Plans PEL PEP EXPLAIN PEP Optim Pipeline

Exemples : Bitmap + Conversion

Id Opération Name
0 SELECT STATEMENT
1 TABLE ACCESS BY INDEX ROWID Auditeurs
2 BITMAP CONVERSION TO ROWIDS
3* BITMAP INDEX SINGLE VALUE Auditeurs Annee BITMAP

(3) : access(Annee = 2014)

Statistiques : |Auditeurs| = 1000, ||Auditeurs|| = 600000, φ = 10000, Sel = 3%

Vecteur bitmap = 2p, Conversion = 28 I/O

137 / 177

Nicolas Travers
c Ecole Centrale Paris - IS3012AB
Opérations Plans PEL PEP EXPLAIN PEP Optim Pipeline

Exemples : boucle imbriquée

Id Opération Name
0 SELECT STATEMENT
1* NESTED LOOPS
2 TABLE ACCESS FULL Cours
3 TABLE ACCESS FULL Auditeurs

(1) : filter(CODE = CODE UE)

Statistiques : |Auditeurs| = 1000, |Cours| = 100, |M| = 52

138 / 177

Nicolas Travers
c Ecole Centrale Paris - IS3012AB

Opérations Plans PEL PEP EXPLAIN PEP Optim Pipeline

Exemples : Boucle imbriquée et accès via index

Id Opération Name
0 SELECT STATEMENT
1* NESTED LOOPS
2 TABLE ACCESS BY INDEX ROWID Cours
3* INDEX RANGE SCAN Cours Responsable IDX
4 TABLE ACCESS FULL Auditeurs

(1) : filter(CODE = CODE UE)

(3) : access(Responsable = ’Nicolas Travers’)

Statistiques : |I| = 2, ||Cours|| = 600, Sel = 0, 4%, |Cours 0 | = 1,

|Auditeurs| = 1000, |M| = 52

139 / 177

Nicolas Travers
c Ecole Centrale Paris - IS3012AB
Opérations Plans PEL PEP EXPLAIN PEP Optim Pipeline

Exemples : Boucle imbriquée avec index

Id Opération Name
0 SELECT STATEMENT
1 NESTED LOOPS
2 TABLE ACCESS BY INDEX ROWID Cours
3* INDEX RANGE SCAN Cours Responsable IDX
4 TABLE ACCESS BY INDEX ROWID Auditeurs
5* INDEX RANGE SCAN Auditeurs CODEUE IDX

(3) : access(Responsable = ’Nicolas Travers’)

(5) : filter(CODE = CODE UE)

Statistiques : |Ic | = 2, ||Cours|| = 600, Sel = 0, 4%, |Cours 0 | = 1

1
|Ia | = 3, ||Auditeurs|| = 600000, φ = 10000, Sel = 600 ,

140 / 177

Nicolas Travers
c Ecole Centrale Paris - IS3012AB

Opérations Plans PEL PEP EXPLAIN PEP Optim Pipeline

Exemples : Jointure par Tri-Fusion

Id Opération Name
0 SELECT STATEMENT
1* MERGE JOIN
2 SORT JOIN
3 TABLE ACCESS BY INDEX ROWID Cours
4* INDEX RANGE SCAN Cours Responsable IDX
5 SORT JOIN
6 TABLE ACCESS FULL Auditeurs

(1) : filter(CODE = CODE UE)

(4) : access(Responsable = ’Nicolas Travers’)

Statistiques : |Ic | = 2, ||Cours|| = 600, Sel = 0, 4%, |Cours 0 | = 1,

|Auditeurs| = 1000, |Auditeurs 0 | = 500, |M| = 51

141 / 177

Nicolas Travers
c Ecole Centrale Paris - IS3012AB
Opérations Plans PEL PEP EXPLAIN PEP Optim Pipeline

Exemples : Jointure par hachage

Id Opération Name
0 SELECT STATEMENT
1* HASH JOIN
2 TABLE ACCESS BY INDEX ROWID Cours
3* INDEX RANGE SCAN Cours Responsable IDX
4 TABLE ACCESS FULL Auditeurs

(1) : filter(CODE = CODE UE)

(3) : access(Responsable = ’Nicolas Travers’)

Statistiques : |Ic | = 2, ||Cours|| = 600, Sel = 0, 4%, |Cours 0 | = 1,

|Auditeurs| = 10000, |Auditeurs 0 | = 1000, |M| = 51

142 / 177

Nicolas Travers
c Ecole Centrale Paris - IS3012AB

Opérations Plans PEL PEP EXPLAIN PEP Optim Pipeline

Exemples : COUNT BITMAP

Id Opération Name
0 SELECT STATEMENT
1 SORT AGGREGATE
2* INDEX RANGE SCAN Cours Responsable IDX

(2) : access(Responsable = ’Nicolas Travers’)

Statistiques : |Ic | = 2, ||Cours|| = 600, Sel = 0, 4%

Id Opération Name
0 SELECT STATEMENT
1 SORT AGGREGATE
2 BITMAP CONVERSION COUNT
3* BITMAP INDEX SINGLE VALUE Auditeurs Annee

(3) : access(Annee = 2014)

Statistiques : Vecteur Bitmap : 2p

143 / 177

Nicolas Travers
c Ecole Centrale Paris - IS3012AB
Opérations Plans PEL PEP EXPLAIN PEP Optim Pipeline

EXPLAIN : Statistiques

EXPLAIN fourni des informations statistiques

Nombre d’appels physiques
Nombre d’accès mémoires
Traitements temporaires
⇒ Permet de comprendre le coût d’évaluation du plan

144 / 177

Nicolas Travers
c Ecole Centrale Paris - IS3012AB

Opérations Plans PEL PEP EXPLAIN PEP Optim Pipeline

Exemple de statistiques

Id Opération Name
0 SELECT STATEMENT
1* NESTED LOOPS
2 TABLE ACCESS FULL Cours
3 TABLE ACCESS FULL Auditeurs

(1) : filter(CODE = CODE UE)

Statistics
0 recursive calls
100 db block gets
2000 consistent gets
300 physical reads

145 / 177

Nicolas Travers
c Ecole Centrale Paris - IS3012AB
Opérations Plans PEL PEP EXPLAIN PEP Optim Pipeline

Différentes Statistiques

Accès mémoire :
consistent gets : Nb d’accès à une donnée consistente en
RAM (non modifiée)
db block gets : Nb d’accès à une donnée en RAM
Accès physiques :
physical reads : Nb total de pages lues sur le disque
recursive calls : Nb d’appels à un sous-plan (requête
imbriquée)
redo size : Taille du fichier de log produit (update)
sorts (disk) : Nb d’opérations de tri avec au moins une
écriture
sorts (memory) : Nb d’opérations de tri en mémoire
physical reads
⇒ Taux d’efficacité du cache : 1 − consistent gets + db block gets
146 / 177

Nicolas Travers
c Ecole Centrale Paris - IS3012AB

Opérations Plans PEL PEP EXPLAIN PEP Optim Pipeline

2 Optimisation : Plans d’exécutions

Plan d’Exécution Logique
Plan d’Exécution Physique
EXPLAIN
Optimisation des Plans d’Exécution
Pipeline

147 / 177

Nicolas Travers
c Ecole Centrale Paris - IS3012AB
Opérations Plans PEL PEP EXPLAIN PEP Optim Pipeline

Choix du meilleur plan d’exécution

L’optimiseur a un PEL
Choix des meilleurs opérateurs
⇒ Besoin de statistiques

148 / 177

Nicolas Travers
c Ecole Centrale Paris - IS3012AB

Opérations Plans PEL PEP EXPLAIN PEP Optim Pipeline

Choix du meilleur opérateur

Accès aux données : Vérification des index

Un ou plusieurs indexes en entrée
Partitions
Jointures : Structure des données en entrée
Tables avec indexes
Tables partitionnées
Données triées
Ordre de la jointure : taille

149 / 177

Nicolas Travers
c Ecole Centrale Paris - IS3012AB
Opérations Plans PEL PEP EXPLAIN PEP Optim Pipeline

Jeu de données

Table Cours
5000 n-uplets
60 pages
Index BTree sur Responsable (Hauteur : 3, Ordre : 56)
Index BTree sur CODE (Hauteur : 2, Ordre : 149)
500 professeurs
Table Auditeurs
100 000 n-uplets
300 pages
Index BTree sur CODE UE (Hauteur : 3, Ordre : 149, φcode = 10000)
Index Bitmap sur Année (2 pages par vecteur)
10 000 auditeurs
10 années différentes (Histogramme)

Page : 8 ko, |M| = 11

150 / 177

Nicolas Travers
c Ecole Centrale Paris - IS3012AB

Opérations Plans PEL PEP EXPLAIN PEP Optim Pipeline

Optimisation d’une requête

SELECT COUNT(*)
FROM Cours C, Auditeurs A
WHERE C.CODE UE = A.CODE
AND Responsable = ’Nicolas Travers’
AND Annee = 2014 ;

151 / 177

Nicolas Travers
c Ecole Centrale Paris - IS3012AB
Opérations Plans PEL PEP EXPLAIN PEP Optim Pipeline

Plan 1 : NESTED LOOPS

Id Opération Name
0 SELECT STATEMENT
1* NESTED LOOPS
2* TABLE ACCESS FULL Cours
3* TABLE ACCESS FULL Auditeurs

(1) : access(CODE = CODE UE)

(2) : access(Responsable = ’Nicolas Travers’)
(3) : access(Annee = 2014)
l m
|Cours 0 |
Formule : |Cours| + |M|−2
× |Auditeurs|
5000
Accès séquentiel, ||Cours 0 || = 500
= 10, |Cours 0 | = 1
1

Formule : 60 + 11−2
× 300 = 360 I/O

152 / 177

Nicolas Travers
c Ecole Centrale Paris - IS3012AB

Opérations Plans PEL PEP EXPLAIN PEP Optim Pipeline

Plan 2 : NESTED LOOPS inversé

Id Opération Name
0 SELECT STATEMENT
1* NESTED LOOPS
2* TABLE ACCESS FULL Auditeurs
3* TABLE ACCESS FULL Cours

(1) : access(CODE = CODE UE)

(2) : access(Responsable = ’Nicolas Travers’)
(3) : access(Annee = 2014)
l m
|Auditeurs 0 |
Formule : |Auditeurs| + |M|−2
× |Cours|
100000
Accès séquentiel, ||Auditeurs 0 || = 10
= 10000, |Auditeurs 0 | = 18
18

Formule : 300 + 11−2
× 60 = 420 I/O

153 / 177

Nicolas Travers
c Ecole Centrale Paris - IS3012AB
Opérations Plans PEL PEP EXPLAIN PEP Optim Pipeline

Remarques

Accès aux données à partir des feuilles du plan

Projection des données pour la jointure
(calcul de pages sans PCTFREE)

154 / 177

Nicolas Travers
c Ecole Centrale Paris - IS3012AB

Opérations Plans PEL PEP EXPLAIN PEP Optim Pipeline

Plan 3 : NESTED LOOPS + INDEX RANGE SCAN

Id Opération Name
0 SELECT STATEMENT
1* NESTED LOOPS
2 TABLE ACCESS BY INDEX ROWID Cours
3* INDEX RANGE SCAN Cours Responsable IDX
4* TABLE ACCESS FULL Auditeurs

(1) : access(CODE = CODE UE)

(3) : access(Responsable = ’Nicolas Travers’)
(4) : access(Annee = 2014)
l m
|Cours 0 |
Formule : |Iresp | + ∆ + φ × Selresp + |M|−2
× |Auditeurs|
1
Accès via index, |I| = 3, ordre : 56, Sel = 500
,φ = ||Cours||
10 5000
1

Formule : 3 + ( 56
− 1) + 500
+ 11−2
× 300 = 313 I/O

155 / 177

Nicolas Travers
c Ecole Centrale Paris - IS3012AB
Opérations Plans PEL PEP EXPLAIN PEP Optim Pipeline

Plan 4 : NESTED LOOPS + INDEX RANGE SCAN

Id Opération Name
0 SELECT STATEMENT
1 NESTED LOOPS
2 TABLE ACCESS BY INDEX ROWID Cours
3* INDEX RANGE SCAN Cours Responsable IDX
4* TABLE ACCESS BY INDEX ROWID Auditeurs
5* INDEX RANGE SCAN Auditeurs CODE UE

(3) : access(Responsable = ’Nicolas Travers’)

(4) : access(Annee = 2014)
(5) : access(CODE = CODE UE)
Formule : |Iresp | + ∆ + φ × Selresp +||Cours 0 || × (|ICODE | + ∆ + φ × SelCODE )
1
Accès via index + Jointure par index, |Iresp | = 3, Sel = 500
, φresp = ||Cours||,
1
|Icode | = 3, ordre = 149, Sel = 5000 , φcode = 10000
l 1
m
10 5000 100000× 5000 10000
Formule : 3 + ( 56
− 1) + 500
+10 × (3 + ( 149
− 1) + 5000
)
= 13 + 10 × (3 + 0 + 2) = 63 I/O
156 / 177

Nicolas Travers
c Ecole Centrale Paris - IS3012AB

Opérations Plans PEL PEP EXPLAIN PEP Optim Pipeline

NESTED LOOPS + INDEX RANGE SCAN : Remarques

Pour chaque cours, il y a 20 ROWID, mais le clustering factor

prevoit que ces cours soit groupés sur 2 pages
Quel est le PEP si la jointure est dirigée par Auditeurs ? Quel
est son coût ?

157 / 177

Nicolas Travers
c Ecole Centrale Paris - IS3012AB
Opérations Plans PEL PEP EXPLAIN PEP Optim Pipeline

Plan 5 : SORT MERGE JOIN

Id Opération Name
0 SELECT STATEMENT
1* MERGE JOIN
2 SORT JOIN
3 TABLE ACCESS BY INDEX ROWID Cours
4* INDEX RANGE SCAN Cours Responsable IDX
5 SORT JOIN
6* TABLE ACCESS FULL Auditeurs

(1) : access(CODE = CODE UE)

(4) : access(Responsable = ’Nicolas Travers’)
(6) : access(Annee = 2014)
Formule :
|Iresp | + ∆ + φ × Selresp + |Cours 0 | + 2|Cours 0 | × log|M|−1 (|Cours 0 |) +

|Auditeurs| + |Auditeurs 0 | + 2|Auditeurs 0 | × log|M|−1 (|Auditeurs 0 |) +
|Cours 0 | + |Auditeurs 0 |
Accès via index, |Cours 0 | = 1 (|Cours 0 | ≤ M), |Auditeurs 0 | = 18

10
Formule : 3 + ( 56 − 1) + 5000
500
+ 0 + 300 + 18 + 2 × 18 × dlog10 (18)e + 1 + 18
= 13 + 390 + 19 = 422 I/O
158 / 177

Nicolas Travers
c Ecole Centrale Paris - IS3012AB

Opérations Plans PEL PEP EXPLAIN PEP Optim Pipeline

SORT MERGE JOIN : Remarques

Coût de lecture d’Auditeurs trop grand

Tri peu couteux car en mémoire (filtrages et projections avant)
Quel est le coût si M = 21 ?

159 / 177

Nicolas Travers
c Ecole Centrale Paris - IS3012AB
Opérations Plans PEL PEP EXPLAIN PEP Optim Pipeline

Plan 6 : HASH JOIN

Id Opération Name
0 SELECT STATEMENT
1* HASH JOIN
2 TABLE ACCESS BY INDEX ROWID Cours
3* INDEX RANGE SCAN Cours Responsable IDX
4* TABLE ACCESS FULL Auditeurs

(1) : access(CODE = CODE UE)

160 / 177

Nicolas Travers
c Ecole Centrale Paris - IS3012AB

Opérations Plans PEL PEP EXPLAIN PEP Optim Pipeline

Composition d’index

Utilisation de deux indexes

Deux listes de ROWIDs
AND-EQUAL entre les listes
Accès aux données résultantes
Quel index peut être utilisé ? Bitmap sur les années

161 / 177

Nicolas Travers
c Ecole Centrale Paris - IS3012AB
Opérations Plans PEL PEP EXPLAIN PEP Optim Pipeline

PLAN 7 : NESTED LOOPS + INDEX + AND-EQUAL

Id Opération Name
0 SELECT STATEMENT
1 NESTED LOOPS
2 TABLE ACCESS BY INDEX ROWID Cours
3* INDEX RANGE SCAN Cours Responsable IDX
4* TABLE ACCESS BY INDEX ROWID Auditeurs
5 AND-EQUAL
6* INDEX RANGE SCAN Auditeurs CODE UE
7 BITMAP CONVERSION TO ROWIDS
8* BITMAP INDEX SINGLE VALUE Auditeurs Annee

(3) : access(Responsable = ’Nicolas Travers’)

(6) : access(CODE = CODE UE)
(8) : access(Annee = 2014)

Formule : |Iresp | + ∆ + φ × Selresp + |Vecteurauditeurs | + Conversion +

||Cours 0 || × (|ICODE | + ∆ + φ × SelCODE × Selannee )
1 1
Accès via index, |I| = 3, ordre : 56, SelCODE = 500
, Selannee = 10
,φ = ||Cours||,
|VecteurAuditeurs | = 2, Conversion ∼ 3

10
Formule : 3 + ( 56 − 1) + 5000
500
+ 2 + 3 + 10 × (3 + 0 + 10000
5000×10
)
= 13 + 5 + 10 × (3 + 0 + 0, 2) = 50 I/O 162 / 177

Nicolas Travers
c Ecole Centrale Paris - IS3012AB

Opérations Plans PEL PEP EXPLAIN PEP Optim Pipeline

AND-EQUAL : Remarques

Intersection de liste empêche l’accès aux données inutiles

Nécessaire avec beaucoup de données et plusieurs restrictions
A-ton encore besoin d’accéder aux données Auditeurs ?
SELECT COUNT(*)... Donc il suffit de compter le nombre de
ROWIDs, sans accès aux données

163 / 177

Nicolas Travers
c Ecole Centrale Paris - IS3012AB
Opérations Plans PEL PEP EXPLAIN PEP Optim Pipeline

PLAN 8 : - TABLES ACCESS BY INDEX ROWID

Id Opération Name
0 SELECT STATEMENT
1 SORT AGGREGATE
2 NESTED LOOPS
3 TABLE ACCESS BY INDEX ROWID Cours
4* INDEX RANGE SCAN Cours Responsable IDX
5 AND-EQUAL
6* INDEX RANGE SCAN Auditeurs CODE UE
7 BITMAP CONVERSION TO ROWIDS
8* BITMAP INDEX SINGLE VALUE Auditeurs Annee

(3) : access(Responsable = ’Nicolas Travers’)

(6) : access(CODE = CODE UE)
(8) : access(Annee = 2014)

Formule : |Iresp | + ∆ + φ × Selresp + |Vecteurauditeurs | + Conversion +

||Cours 0 || × (|ICODE | + ∆) + Tri
1 1
Accès via index, |I| = 3, ordre : 56, SelCODE = 500 , Selannee = 10 , φ = ||Cours||,
|VecteurAuditeurs | = 2, Conversion ∼ 3, Sorti < |M| ⇒ Tri = 0

10
Formule : 3 + ( 56 − 1) + 5000
500
+ 2 + 3 + 10 × (3 + 0) + 0
= 13 + 5 + 10 × (3 + 0) + 0 = 48 I/O 164 / 177

Nicolas Travers
c Ecole Centrale Paris - IS3012AB

Opérations Plans PEL PEP EXPLAIN PEP Optim Pipeline

Conclusion sur l’optimiseur

Vérification des méthodes d’accès

L’accès aux données n’est pas toujours requis
Choix de l’algorithme de jointure
Combinaison des indexes
Dépendant des statistiques sur les données
⇒ Nécessaire de bien choisir :
Indexes (clé primaire, couvrant, combinaison)
Taille/Type des attributs (Stockage, Projection, Index)
Organiser physiquement les données (Non-dense, hachage,
tri/clustering factor)

165 / 177

Nicolas Travers
c Ecole Centrale Paris - IS3012AB
Opérations Plans PEL PEP EXPLAIN PEP Optim Pipeline

2 Optimisation : Plans d’exécutions

Plan d’Exécution Logique
Plan d’Exécution Physique
EXPLAIN
Optimisation des Plans d’Exécution
Pipeline

166 / 177

Nicolas Travers
c Ecole Centrale Paris - IS3012AB

Opérations Plans PEL PEP EXPLAIN PEP Optim Pipeline

Pipeline

Besoin de minimiser les écritures temporaires

Chaque opérateur à une sortie
Éviter l’écriture du résultat
Besoin de minimiser la Mémoire Centrale
Affecter la mémoire sur tout un plan
À chaque opérateur nécessite une partie de M
Prenons deux opérateurs o1 et o2 en séquence
Que faire du résultat de o1 ?
⇒ Stocker sur le disque puis relire pour o2
Peut couter cher si le résultat grand
⇒ Pipeliner o1 avec o2
Résultat de o1 directement passé dans o2
Pipeline impossible sur opérateurs bloquants.
Quels sont les opérateurs bloquants ?
SortMerge (+Join), Dédoublonnage, GroupBy, Agrégats 167 / 177

Nicolas Travers
c Ecole Centrale Paris - IS3012AB
Opérations Plans PEL PEP EXPLAIN PEP Optim Pipeline

Principe

Durant l’évaluation de o1
A chaque n-uplet de sortie de o1
Donné directement en entrée de o2
Production de o1 consommé par o2
Création d’une grande séquence d’opérateur en même temps
(le plus possible)

168 / 177

Nicolas Travers
c Ecole Centrale Paris - IS3012AB

Opérations Plans PEL PEP EXPLAIN PEP Optim Pipeline

Illustration

169 / 177

Nicolas Travers
c Ecole Centrale Paris - IS3012AB
Opérations Plans PEL PEP EXPLAIN PEP Optim Pipeline

Illustration

169 / 177

Nicolas Travers
c Ecole Centrale Paris - IS3012AB

Opérations Plans PEL PEP EXPLAIN PEP Optim Pipeline

Illustration

169 / 177

Nicolas Travers
c Ecole Centrale Paris - IS3012AB
Opérations Plans PEL PEP EXPLAIN PEP Optim Pipeline

Illustration

169 / 177

Nicolas Travers
c Ecole Centrale Paris - IS3012AB

Opérations Plans PEL PEP EXPLAIN PEP Optim Pipeline

Avantages

Évite les lectures / écritures temporaires

Optimise le traitement d’un tuple
Allocation mémoire
Unique pour une séquence
Libérée plus rapidement

170 / 177

Nicolas Travers
c Ecole Centrale Paris - IS3012AB
Opérations Plans PEL PEP EXPLAIN PEP Optim Pipeline

Exemple : double boucle imbriquée

Id Opération Name
0 SELECT STATEMENT
1 NESTED LOOPS
2 NESTED LOOPS
3 TABLE ACCESS BY INDEX ROWID Cours
4* INDEX RANGE SCAN Cours Responsable IDX
5* TABLE ACCESS BY INDEX ROWID Auditeurs
6* INDEX RANGE SCAN Auditeurs CODE UE
7 TABLE ACCESS BY INDEX ROWID Personne
8* INDEX UNIQUE SCAN Personne ID

(4) : access(Responsable = ’Nicolas Travers’)

(5) : access(Annee = 2010)
(6) : access(CODE = CODE UE)
(8) : access(CODE AUDITEUR = ID

171 / 177

Nicolas Travers
c Ecole Centrale Paris - IS3012AB

Opérations Plans PEL PEP EXPLAIN PEP Optim Pipeline

Illustration

172 / 177

Nicolas Travers
c Ecole Centrale Paris - IS3012AB
Opérations Plans PEL PEP EXPLAIN PEP Optim Pipeline

Illustration

172 / 177

Nicolas Travers
c Ecole Centrale Paris - IS3012AB

Opérations Plans PEL PEP EXPLAIN PEP Optim Pipeline

Illustration

172 / 177

Nicolas Travers
c Ecole Centrale Paris - IS3012AB
Opérations Plans PEL PEP EXPLAIN PEP Optim Pipeline

Illustration

172 / 177

Nicolas Travers
c Ecole Centrale Paris - IS3012AB

Opérations Plans PEL PEP EXPLAIN PEP Optim Pipeline

Illustration

172 / 177

Nicolas Travers
c Ecole Centrale Paris - IS3012AB
Opérations Plans PEL PEP EXPLAIN PEP Optim Pipeline

Itérateurs

À chaque opérateur est affecté un Itérateur

Permet de produire / consommer à la demande
Possibilité de créer des opérateurs ’Table’ en pipeline :
Pipe-lined Functions
Besoins :
Type de n-uplet retourné
Type table contenant ces n-uplets
Fonction f retournant cette table en pipeline
Requête SQL avec TABLE(f ()) dans le FROM

173 / 177

Nicolas Travers
c Ecole Centrale Paris - IS3012AB

Opérations Plans PEL PEP EXPLAIN PEP Optim Pipeline

Création de types

DROP TYPE pipelined table ;

DROP TYPE pipelined row ;

CREATE TYPE pipelined row AS OBJECT (

cours CHAR(5),
NB auditeur NUMBER(3,0)
);
/
CREATE TYPE pipelined table IS TABLE OF pipelined row ;/

174 / 177

Nicolas Travers
c Ecole Centrale Paris - IS3012AB
Opérations Plans PEL PEP EXPLAIN PEP Optim Pipeline

Création de la fonction en pipeline

CREATE OR REPLACE FUNCTION pipelined function

(pcours IN CHAR(5), pannee IN NUMBER)
RETURN pipelined table PIPELINED AS
CURSOR c (ccours CHAR(5), cannee NUMBER) AS
SELECT COUNT(*) AS NB
FROM Auditeur WHERE cours = ccours AND annee = cannee ;
BEGIN
FOR i IN c(pcours, pannee) LOOP
PIPE ROW(pipelined row(pcours, i.NB)) ;
END LOOP ;
RETURN ;
END ;
/

175 / 177

Nicolas Travers
c Ecole Centrale Paris - IS3012AB

Opérations Plans PEL PEP EXPLAIN PEP Optim Pipeline

Utilisation de la fonction en pipeline

SELECT *
FROM TABLE(pipelined function(’NFE106’, 2014)) ;

176 / 177

Nicolas Travers
c Ecole Centrale Paris - IS3012AB
Opérations Plans PEL PEP EXPLAIN PEP Optim Pipeline

Conclusion

Pipeline
1 Permet d’optimiser le résultat du premier tuple
2 Réduit le nombre d’écriture intermédiaire
3 Possibilité de créer des résultats localement optimisés
(Pipe-lined Functions)

177 / 177

Nicolas Travers
c Ecole Centrale Paris - IS3012AB

Vous aimerez peut-être aussi

Optimisationrequetes
Pas encore d'évaluation
Optimisationrequetes
18 pages
Annales Examens Informatique 2010
Pas encore d'évaluation
Annales Examens Informatique 2010
22 pages
BDD Sujet 19-20 (1) USTHB
Pas encore d'évaluation
BDD Sujet 19-20 (1) USTHB
3 pages
Cours D'encadrement SQL
Pas encore d'évaluation
Cours D'encadrement SQL
12 pages
Atelier C: Maîtrisez les Conditions
Pas encore d'évaluation
Atelier C: Maîtrisez les Conditions
4 pages
Presentation SQL
Pas encore d'évaluation
Presentation SQL
31 pages
Exercices Optimisation Répartie
Pas encore d'évaluation
Exercices Optimisation Répartie
1 page
Cours Complet sur le Langage SQL
Pas encore d'évaluation
Cours Complet sur le Langage SQL
23 pages
Structure de la base Tour
Pas encore d'évaluation
Structure de la base Tour
4 pages
Analyse Cahier Charge
Pas encore d'évaluation
Analyse Cahier Charge
3 pages
CNN (Convolutional Neural Network) : Universit e de SKIKDA 20 AOUT 1955 D Epartement de L'informatique
Pas encore d'évaluation
CNN (Convolutional Neural Network) : Universit e de SKIKDA 20 AOUT 1955 D Epartement de L'informatique
15 pages
Chapitre3-P2 (Plan Physique)
Pas encore d'évaluation
Chapitre3-P2 (Plan Physique)
35 pages
Bda TD
Pas encore d'évaluation
Bda TD
8 pages
Chapitre5 - Liste Chaînée
Pas encore d'évaluation
Chapitre5 - Liste Chaînée
25 pages
Sujet Correction Algorithme Tableau
Pas encore d'évaluation
Sujet Correction Algorithme Tableau
2 pages
Chapitre 3-BD-Langage SQL
Pas encore d'évaluation
Chapitre 3-BD-Langage SQL
34 pages
Projet Test2
Pas encore d'évaluation
Projet Test2
12 pages
SQL Entretien
Pas encore d'évaluation
SQL Entretien
15 pages
Requêtes SQL pour l'Atelier Base de Données
Pas encore d'évaluation
Requêtes SQL pour l'Atelier Base de Données
5 pages
Enregistrements en C : Structures et Syntaxe
Pas encore d'évaluation
Enregistrements en C : Structures et Syntaxe
36 pages
Controle 1 Théorique
Pas encore d'évaluation
Controle 1 Théorique
2 pages
3 OLAP 4p
Pas encore d'évaluation
3 OLAP 4p
12 pages
Cours IA
Pas encore d'évaluation
Cours IA
58 pages
Analyse Et Conception Orientées Objet
Pas encore d'évaluation
Analyse Et Conception Orientées Objet
14 pages
ASD3-Chap1Complexité Des Algorithmes
Pas encore d'évaluation
ASD3-Chap1Complexité Des Algorithmes
6 pages
Introduction à Cassandra et CQL
Pas encore d'évaluation
Introduction à Cassandra et CQL
8 pages
Rapport Du TP
100% (1)
Rapport Du TP
17 pages
TP Miage L3 - 1
Pas encore d'évaluation
TP Miage L3 - 1
3 pages
Transactions et Contrôle de Concurrence
Pas encore d'évaluation
Transactions et Contrôle de Concurrence
45 pages
Gestion Disque
Pas encore d'évaluation
Gestion Disque
16 pages
SQL Avancé (PDFDrive)
Pas encore d'évaluation
SQL Avancé (PDFDrive)
370 pages
Gestion Des Utilisateurs en MySQL
Pas encore d'évaluation
Gestion Des Utilisateurs en MySQL
12 pages
Trigers
Pas encore d'évaluation
Trigers
34 pages
Big Data
Pas encore d'évaluation
Big Data
48 pages
Cha 5
Pas encore d'évaluation
Cha 5
59 pages
CorrectionDevoir 4 SMI4 - 2022
Pas encore d'évaluation
CorrectionDevoir 4 SMI4 - 2022
17 pages
Transaction Et Acces Concurrents
Pas encore d'évaluation
Transaction Et Acces Concurrents
18 pages
Chapitre 10 Partie 1 Vue Sequence Indexes
Pas encore d'évaluation
Chapitre 10 Partie 1 Vue Sequence Indexes
52 pages
Cours BD2012 Cours3 PDF
Pas encore d'évaluation
Cours BD2012 Cours3 PDF
13 pages
Serie - TD2 2021
Pas encore d'évaluation
Serie - TD2 2021
1 page
Tests et Vérification en Informatique
Pas encore d'évaluation
Tests et Vérification en Informatique
2 pages
Chapitre 3
Pas encore d'évaluation
Chapitre 3
20 pages
Bases de Donnees Distribuees
100% (1)
Bases de Donnees Distribuees
31 pages
Cours3 - Gestion Des Index
Pas encore d'évaluation
Cours3 - Gestion Des Index
2 pages
TP - Conteneurs en C++: Imad Kissami
Pas encore d'évaluation
TP - Conteneurs en C++: Imad Kissami
4 pages
INDM-2020-2021-Chaoui-Chapitre 2-OCL-Slides - 2
Pas encore d'évaluation
INDM-2020-2021-Chaoui-Chapitre 2-OCL-Slides - 2
31 pages
SQL Server
100% (1)
SQL Server
114 pages
Séance3 - Introduction Aux Systèmes D'information Décisionnels - SID - MP1 - IDIRIA
Pas encore d'évaluation
Séance3 - Introduction Aux Systèmes D'information Décisionnels - SID - MP1 - IDIRIA
20 pages
TD1 Correction
Pas encore d'évaluation
TD1 Correction
5 pages
Administration Programmation BDD
Pas encore d'évaluation
Administration Programmation BDD
85 pages
Bda TD
Pas encore d'évaluation
Bda TD
15 pages
CR Complt
Pas encore d'évaluation
CR Complt
50 pages
Mémoires Relationnelles
Pas encore d'évaluation
Mémoires Relationnelles
49 pages
AdminBD Optimisation PDF
Pas encore d'évaluation
AdminBD Optimisation PDF
46 pages
5.chapitre 2 - Optimisation
Pas encore d'évaluation
5.chapitre 2 - Optimisation
80 pages
Optimisation des Index et Plans d'Exécution
Pas encore d'évaluation
Optimisation des Index et Plans d'Exécution
38 pages
Cours 3 Optimisation
Pas encore d'évaluation
Cours 3 Optimisation
38 pages
2 Memoire Rel
Pas encore d'évaluation
2 Memoire Rel
28 pages
Dunod Base de Donnees 3ed
Pas encore d'évaluation
Dunod Base de Donnees 3ed
699 pages
Documentation 13-11-2022
Pas encore d'évaluation
Documentation 13-11-2022
16 pages
Architecture SPARC-ANSI et BD
Pas encore d'évaluation
Architecture SPARC-ANSI et BD
46 pages
Devoir Archi
Pas encore d'évaluation
Devoir Archi
10 pages
Modèles de Bases de Données
Pas encore d'évaluation
Modèles de Bases de Données
44 pages
Transactions
Pas encore d'évaluation
Transactions
19 pages
Correction Mémoire
Pas encore d'évaluation
Correction Mémoire
70 pages
6 Sujets Concours Doctorat en Informatique
100% (3)
6 Sujets Concours Doctorat en Informatique
32 pages
Introduction au langage Scilab
Pas encore d'évaluation
Introduction au langage Scilab
25 pages
Introduction à la Programmation Dynamique
Pas encore d'évaluation
Introduction à la Programmation Dynamique
14 pages
BDAexos Estampillage
Pas encore d'évaluation
BDAexos Estampillage
8 pages
Feuilletage 205
Pas encore d'évaluation
Feuilletage 205
27 pages
TD03 BDDR 2020
Pas encore d'évaluation
TD03 BDDR 2020
2 pages
Comprendre la bande passante réseau
100% (1)
Comprendre la bande passante réseau
6 pages
Cours D'informatique General g1 Info
Pas encore d'évaluation
Cours D'informatique General g1 Info
80 pages
Outils Mathématiques en Thermodynamique
Pas encore d'évaluation
Outils Mathématiques en Thermodynamique
46 pages
s06 CPP
100% (1)
s06 CPP
2 pages
INFORMATIQUE 1ère Année Algo
100% (1)
INFORMATIQUE 1ère Année Algo
41 pages
QCM Info Parlons Peu 2
Pas encore d'évaluation
QCM Info Parlons Peu 2
25 pages
Correction QCM Architecture Ordinateurs
88% (17)
Correction QCM Architecture Ordinateurs
4 pages
Chapitre 3 PPT
Pas encore d'évaluation
Chapitre 3 PPT
21 pages
Resumé BD
Pas encore d'évaluation
Resumé BD
10 pages
Cours Informatique Appliquee
Pas encore d'évaluation
Cours Informatique Appliquee
18 pages
TD3 Mémoire Corr
Pas encore d'évaluation
TD3 Mémoire Corr
37 pages
Analyse et Optimisation de Convolution 3x3
Pas encore d'évaluation
Analyse et Optimisation de Convolution 3x3
21 pages
TD Ao
Pas encore d'évaluation
TD Ao
4 pages
Msdos
Pas encore d'évaluation
Msdos
42 pages
Examen Informatique : Systèmes Numériques
Pas encore d'évaluation
Examen Informatique : Systèmes Numériques
2 pages
Exercices Informatique: Bases et Concepts
Pas encore d'évaluation
Exercices Informatique: Bases et Concepts
2 pages
I-Td: Competences Informatiques Et Internet
Pas encore d'évaluation
I-Td: Competences Informatiques Et Internet
13 pages
Cours 2 (Algorithmique)
Pas encore d'évaluation
Cours 2 (Algorithmique)
24 pages
Syllabus Info& Bureautique
Pas encore d'évaluation
Syllabus Info& Bureautique
38 pages
Évolution des Supports de Stockage
Pas encore d'évaluation
Évolution des Supports de Stockage
4 pages
Introduction aux Protocoles Réseaux
Pas encore d'évaluation
Introduction aux Protocoles Réseaux
36 pages
Chapitre 2
Pas encore d'évaluation
Chapitre 2
31 pages
B11 TP
Pas encore d'évaluation
B11 TP
15 pages
Création et gestion de bases Oracle 11g
Pas encore d'évaluation
Création et gestion de bases Oracle 11g
19 pages
s71200 Easy Book FR-FR
Pas encore d'évaluation
s71200 Easy Book FR-FR
133 pages
Ex Dut1 Gapmo Oi SN Correc
Pas encore d'évaluation
Ex Dut1 Gapmo Oi SN Correc
2 pages
Examen Final: Architecture Des Ordinateurs #ADO
100% (1)
Examen Final: Architecture Des Ordinateurs #ADO
3 pages
Pid Obd-Ii
Pas encore d'évaluation
Pid Obd-Ii
17 pages
Guide Réseau Local pour Débutants
Pas encore d'évaluation
Guide Réseau Local pour Débutants
37 pages
8-Représentation Des Nombres
Pas encore d'évaluation
8-Représentation Des Nombres
9 pages