Cours complet pour apprendre les différents types de bases de données et le langage SQL


précédentsommairesuivant

X. Résolution des requêtes

X-A. Introduction

L'accès à une BD relationnelle est réalisé au travers d'un langage de requêtes (SQL, le plus souvent). Les performances de l'évaluateur de requêtes sont donc cruciales.

Un langage de requêtes est déclaratif : l'utilisateur exprime sa requête, mais pas la façon d'y répondre.

Or, pour une requête donnée, il existe en général plusieurs stratégies pour construire la réponse. C'est au SGBD de choisir la stratégie optimale.

X-B. Les 3 phases de la résolution d'une requête

La résolution d'une requête à une BD relationnelle se déroule en trois phases :

  1. Traduction de la requête en un arbre d'opérateurs relationnels (sélection, jointure, projection, etc.) : l'arbre de requête.
  2. Optimisation. Il s'agit de déterminer un plan d'exécution de coût minimal. Deux procédures sont principalement mises en œuvre :

    1. transformation de l'arbre de requête en un arbre équivalent, basée sur les propriétés d'associativité et de commutativité de l'algèbre relationnelle,
    2. évaluation du coût de résolution de chaque opérateur.
  3. Évaluation du plan d'exécution produit par la phase 2.

X-C. Arbre de requête

Image non disponible

X-D. Évaluation des opérateurs relationnels

Nous étudierons quelques méthodes d'évaluation des opérateurs :

  • de sélection ;
  • de jointure ;
  • de projection.

X-D-1. Méthodes d'évaluation d'une sélection

Simple boucle (parcours séquentiel)

Indexée

  • utilisation d'un index primaire pour retrouver un n-uplet dont la clé est donnée ou appartient à un intervalle donné ;
  • utilisation d'un index secondaire pour retrouver un ensemble de n-uplets dont la clé est donnée ou appartient à un intervalle donné.

X-D-2. Méthodes d'évaluation d'une jointure

Sur une condition quelconque :

  • boucles imbriquées

Equi-jointure :

  • pas d'index sur les constituants de jointure :

    • boucles imbriquées
    • tri-fusion
    • hachage
  • index sur l'un des constituants de jointure :

    • indexée
  • index triés sur les deux constituants de la jointure :

    • fusion des feuilles des deux index

X-D-3. Méthodes d'évaluation d'une projection

Simple boucle

Tri puis simple boucle, si les doubles doivent être éliminés.

X-E. Étude de quelques méthodes

On supposera que chaque relation est stockée dans un fichier qui contient les n-uplets de cette relation.

Le coût d'une opération sera mesuré en nombre de transferts de pages entre disque et mémoire centrale.

Ce coût peut se décomposer en deux parties :

  • un coût de production de la relation résultat ;
  • un coût d'écriture de cette relation.

Le coût de production dépend de la méthode choisie pour réaliser l'opération alors que le coût d'écriture en est indépendant.

Dans le cas d'une évaluation pipeline d'une suite d'opérations :

  • op1, ..., opn

les résultats des opérations op1, ..., opn-1 ne sont pas stockés sur disque, car les n-uplets produits sont directement transmis à l'opérateur suivant :

  • les coûts de lecture d'une relation opérande ou d'écriture des résultats d'un opérateur peuvent donc être nuls.

X-E-1. Coût de production d'une opération

Le coût de production de la relation résultat dépend :

  • de la méthode utilisée pour résoudre l'opération ;
  • des paramètres d'implantation des relations opérandes.

Le jeu de paramètres utilisé sera le suivant :

card(R)

cardinalité de la relation R

nb(R)

nombre de blocs occupés par le fichier R

nbatt(R)

nombre d'attributs de la relation R

nv(R, X)

nombre de valeurs différentes du constituant X de la relation R

X-E-2. Coût d'écriture du résultat

Le coût d'écriture de la relation résultat est indépendant de la méthode de résolution utilisée.

Cette écriture est réalisée au travers du tampon de la façon suivante :

  • Une case C du tampon est affectée à la relation résultat initialisée avec une page vide P.
  • Pour chaque n-uplet t produit :

    • Si la page P est pleine, l'écrire sur un bloc du disque.
    • Placer une nouvelle page vide P dans la case C.
    • Écrire t dans P.

Le coût d'écriture du résultat est donc égal à nb(relation résultat).

X-F. Sélection par simple boucle

S:= σcond(R)

Image non disponible
Tampon

Algorithme

Pour chaque bloc du fichier R faire
    Transférer la page contenue dans ce bloc, dans la case 1.
    Pour chaque n-uplet t de cette page faire
        si cond(t) alors écrire t dans la page de la case 2
        ou le transmettre à l'opérateur suivant.

Coût de production
nb(R)

X-G. Sélection indexée

S := σA = v(R)

A est un attribut de R
Il existe un index I sur l'attribut A de R

Image non disponible
Tampon

Image non disponible

X-H. Comparaison des deux méthodes

Soit une relation livre telle que :

  • card(livre) = 12000
  • nb(livre) = 2400
  • nv(livre, année) = 50
  • Il existe un index I sur l'attribut année

Le coût de production de l'opération :

  • σannée = 2000(livre)

est égal à :

  • sélection par boucle :

    • 2400
  • sélection indexée :

    • ⌈2400/50⌉ = 48, si l'index est groupant,
    • min(⌈12000/50⌉, 2400) = 240, si l'index est non groupant.

X-I. Jointure par boucles imbriquées

J := P joincond Q

Image non disponible
Tampon

Algorithme

pour chaque suite de M blocs de P faire
    Transférer les pages contenues dans ces blocs dans les cases 1 à M.
    pour chaque chaque bloc de Q faire
        Transférer la page contenue dans ce bloc dans la case M + 1.
        pour chaque n-uplet t' de cette page faire
            pour chaque page contenue dans les cases 1 à M
              et pour chaque n-uplet t de cette page faire
                si cond(t conc t') est vraie alors
                    Écrire le n-uplet t conc t' dans la page de la case M + 2
                    ou le transmettre à l'opérateur suivant.

Coût de production

kitxmlcodelatexdvpnb(P) + \left\lceil \frac{nb(P)}{M} \right\rceil \times nb(Q)finkitxmlcodelatexdvp

Si nb(P) ≤ M, c.-à-d. si la relation P tient en mémoire, le coût est égal à :

kitxmlcodelatexdvpnb(P) + nb(Q)finkitxmlcodelatexdvp

Le coût est minimum si l'on choisit la relation de cardinalité minimum comme relation externe.

X-J. Jointure indexée

J := P joinA = B Q

A est un attribut de
B est un attribut de Q
Il existe un index I sur l'attribut B de Q

Image non disponible
Tampon

Algorithme

pour chaque bloc de P faire
    Transférer dans la case 1 la page p contenue dans ce bloc.
    pour chaque n-uplet t de p faire
        v = t.A
        Effectuer la sélection indexée σB = v(Q) (index I)
        pour chaque n-uplet t' sélectionné par cette opération faire
            Écrire le n-uplet t conc t' dans la page de la case 2
            ou le transmettre à l'opérateur suivant.

Coût de production

kitxmlcodeinlinelatexdvpnb(P) + card(P) \times \left\lceil \frac{nb(Q)}{nv(Q,B)} \right\rceilfinkitxmlcodeinlinelatexdvp Si l'index I est groupant

kitxmlcodeinlinelatexdvpnb(P) + card(P) \times min\left( \left\lceil \frac{card(Q)}{nv(Q,B)} \right\rceil, nb(Q)\right )finkitxmlcodeinlinelatexdvp Si l'index I est non groupant

X-K. Équi-jointure par hachage

J := P joinA = B Q

A est un attribut de P
B est un attribut de Q
h est une fonction de hachage sur les valeurs de A et B

Image non disponible

Algorithme

pour chaque bloc de P faire
    Transférer dans la case M + 1 la page contenue dans ce bloc.
    Hacher ses n-uplets.
pour chaque bloc de Q faire
    Transférer dans la case M + 1 la page contenue dans ce bloc.
    Hacher ses n-uplets.
pour chaque chaîne de pages liée à la case i du tampon faire
    Charger les pages de cette chaîne dans les M cases du tampon.
    Effectuer la jointure dans la case M + 1.

Condition

Il faut que le nombre de pages liées à une case du répertoire soit ≤ M pour qu'elles tiennent dans le tampon.
Si on suppose que la répartition des n-uplets est uniforme, on doit avoir :

kitxmlcodeinlinelatexdvpnb(P) + nb(Q) \le M^2finkitxmlcodeinlinelatexdvp

Coût de production
kitxmlcodeinlinelatexdvp3 \times (nb(P) + nb(Q))finkitxmlcodeinlinelatexdvp

X-L. Comparaison des trois méthodes

Soit une relation livre(ISBN, nom_auteur) telle que :

  • card(livre) = 24000, nb(livre) = 2400 ;
  • nv(livre, nom_auteur) = 6000 ;
  • il existe un index I non groupé sur l'attribut nom_auteur.

et une relation auteur(nom, pays) telle que :

  • card(auteur) = 6000, nb(auteur) = 600
  • nv(auteur, nom) = 6000

102 cases sont disponibles dans le tampon.

Le coût de production de l'opération :

  • auteur joinnom = nom_auteur livre

est égal à :

  • jointure par boucles imbriquées :

    • 600 + ⌈600 / 100⌉ × 2400 = 15000
  • jointure indexée :

    • 600 + 6000 × min(⌈24000 / 6000⌉, 2400) = 24600
  • jointure par hachage :

    • 3 × (2400 + 600) = 9000 qui est donc, dans ce cas, la meilleure solution.

X-M. Projection sans élimination des doublons

P := πA1, ..., Ak(R)

Coût de production
kitxmlcodeinlinelatexdvpnb(R)finkitxmlcodeinlinelatexdvp

X-N. Évaluation de la taille de la relation résultat

La taille de la relation produite par un opérateur est mesurée en nombre de n-uplets et en nombre de blocs.

Cette évaluation n'est pas toujours simple. Elle nécessite de disposer de connaissances statistiques sur les données.

Nous ne traitons ici que les cas les plus simples.

On suppose que :

  • les valeurs d'un attribut sont réparties uniformément sur les n-uplets d'une relation ;
  • tous les attributs d'une même relation ont la même taille.

X-N-1. Taille du résultat d'une sélection

kitxmlcodelatexdvpcard(\sigma_{A=v}(R)) = \left\lceil \frac{card(R)}{nv(R,A)} \right\rceilfinkitxmlcodelatexdvp kitxmlcodelatexdvpnb(\sigma_{A=v}(R)) = \left\lceil \frac{nb(R)}{nv(R,A)} \right\rceilfinkitxmlcodelatexdvp kitxmlcodelatexdvpcard(\sigma_{c1\wedge c2}(R)) = card(\sigma_{c1}(\sigma_{c2}(R)))finkitxmlcodelatexdvp kitxmlcodelatexdvpnb(\sigma_{c1 \wedge c2}(R)) = nb(\sigma_{c1}(\sigma_{c2}(R)))finkitxmlcodelatexdvp kitxmlcodelatexdvpcard(\sigma_{A1=v1\wedge A2=v2}(R)) = \left\lceil \frac{card(R)}{nv(R,A_1) \times nv(R, A_2)} \right\rceilfinkitxmlcodelatexdvp kitxmlcodelatexdvpnb(\sigma_{A1=v1\wedge A2=v2}(R)) = \left\lceil \frac{nb(R)}{nv(R,A_1) \times nv(R, A_2)} \right\rceilfinkitxmlcodelatexdvp

X-N-2. Taille du résultat d'une jointure

Dans le cas où nv(P, A) ≤ nv(Q, B), on peut faire l'hypothèse que chaque n-uplet de P se joint avec au moins un n-uplet de Q et inversement.

kitxmlcodelatexdvpcard(P\ join_{A=B}(Q)) = \left\lceil \frac{card(P) \times card(Q)}{\max(nv(P,A), nv(Q,B))} \right\rceilfinkitxmlcodelatexdvp kitxmlcodelatexdvpnb(P\ join_{A=B}(Q)) = \left\lceil \frac{card(P) \times nb(Q) + card(Q)\times nb(P)}{\max(nv(P,A), nv(Q,B))} \right\rceilfinkitxmlcodelatexdvp

X-N-3. Taille du résultat d'une projection

On suppose que les valeurs des attributs d'une relation ont la même taille (ce qui est très approximatif).

kitxmlcodelatexdvpcard(\pi_{A1, \dots, Ak}(R)) = card(R)finkitxmlcodelatexdvp kitxmlcodelatexdvpnb(\pi_{A1, \dots, Ak}(R)) = \left\lceil \frac{k}{nbatt(R)} \times nb(R) \right\rceilfinkitxmlcodelatexdvp

X-O. Propriétés des opérateurs relationnels

Image non disponible
T1 : éclatement et regroupement des sélections

Image non disponible
T2 : Permutation projection-sélection

Image non disponible
T3 : Permutation sélection-jointure

Image non disponible
T4 : Permutation projection-jointure

Image non disponible
T5 : Commutativité de la jointure

Image non disponible
T6 : Associativité de la jointure

X-P. Choix d'un plan d'exécution

En théorie, le choix d'un plan d'exécution peut être effectué de la façon suivante :

  • Traduire la requête sous forme d'un arbre de requête initial : dans le cas où la requête est un bloc SELECT … FROM … WHERE …, l'arbre de requête initial est obtenu en réalisant la jointure ou le produit cartésien des relations impliquées (clause FROM), suivi d'une sélection (clause WHERE), suivie d'une projection (clause SELECT).
  • Construire l'ensemble des arbres équivalents à l'arbre initial en appliquant les propriétés de commutativité et d'associativité des opérateurs.
  • À partir de chacun de ces arbres, générer tous les plans d'exécution possibles en associant à chaque opérateur chacune des méthodes de résolution applicable.
  • Évaluer le coût de chaque plan d'exécution.
  • Choisir le plan de coût minimal.

L'inconvénient majeur de cette méthode est que le nombre de plans d'exécution à examiner croît très vite avec le nombre de relations sur lesquelles porte la requête.

Par exemple, on peut montrer que le nombre d'ordres de jointures de n relations est :

  • (2 × (n — 1)) ! / (n — 1) !

Ce nombre croît donc très vite quand n augmente. Il est égal à 12 pour n = 3, 1680 pour n = 5, 665280 pour n = 7...

En pratique, on utilise des règles heuristiques pour diminuer le nombre de plans d'exécution à évaluer.

X-Q. Arbres linéaires de jointure

  • Pour minimiser le nombre d'ordres de jointure à considérer, on se limite en général aux arbres de requêtes dits arbres linéaires gauches de jointure où les sous-arbres droits sont des arbres de requête sans opérateurs de jointure.
  • Pour n relations, il y a n! arbres linéaires gauches de jointure. Ce qui est beaucoup moins que le nombre total d'ordres de jointure.
  • Par exemple, il y 1680 ordres de jointure de 5 relations dont 120 correspondent à des arbres de jointure linéaires gauches.
  • Un arbre linéaire gauche de jointure est particulièrement intéressant lorsqu'il existe un index sur l'attribut de jointure ou en cas de résolution pipeline.

Image non disponible

X-R. Étude de cas

Schéma :

  • livre(isbn, titre, auteurs, nom_éditeur, année, prix)
  • éditeur(nom, adresse, pays)

Requête :

  • Titres des livres publiés en 2000 édités par un éditeur espagnol ?
 
Sélectionnez
1.
2.
3.
4.
5.
SELECT titre
FROM livre, editeur
WHERE nom = nom_editeur
  AND pays = 'Espagne'
  AND année = 2000;

X-S. Paramètres

Tables

 

nbatt

card

nb

nv(titre)

nv(nom_éditeur)

nv(année)

livre

6

12000

2400

12000

300

20

 

nbatt

card

nb

nv(nom)

nv(pays)

éditeur

3

300

60

300

30

Index ; Tampon 52 cases

 

index groupant ?

livre(isbn)

oui

livre(nom_éditeur)

non

livre(année)

non

éditeur(nom)

oui

éditeur(pays)

non

X-T. Arbre de requêtes initial

Image non disponible

X-U. Arbres de requêtes équivalents

Image non disponible

Par application des règles T1, T3 et T5 à l'arbre initial R11

l = livre
e = éditeur
a = année = 2000
p = pays = 'Espagne'

X-V. Étude de 4 plans d'exécution

On évalue les plans d'exécution correspondant aux arbres de requête R12, R22, R32 et R42.

Ces plans consistent à réaliser la jointure en choisissant comme relation externe la relation éditeur qui est beaucoup moins volumineuse que la relation livre et à traiter les relations en pipeline chaque fois que c'est possible.

L'étiquette (c, b) de chaque arête indique la cardinalité et le nombre de blocs pour la relation associée à cette arête.

Une arête en trait épais indique que la relation est traitée en pipeline.

X-V-1. Plan n° 1 (arbre de requête R12)

Image non disponible

Coût total estimé = 4860 + 2 = 4862 transferts de pages

X-V-2. Plan n° 2 (arbre de requête R22)

Image non disponible

Coût total estimé = 10 + 720 + 120 + 2 = 852 transferts de pages

X-V-3. Plan n° 3 (arbre de requête R32)

Image non disponible

Coût total estimé = 720 + 300 + 2 = 1022 transferts de pages

X-V-4. Plan n° 4 (arbre de requête R42)

Image non disponible

Coût total estimé = 10 + 400 + 2 = 412 transferts de pages éditeur (300, 60)

X-V-5. Choix du meilleur plan

The winner is : le plan n° 4 !


précédentsommairesuivant

Vous avez aimé ce tutoriel ? Alors partagez-le en cliquant sur les boutons suivants : Viadeo Twitter Facebook Share on Google+