Une requête SQL est déclarative (Elle détermine le Quoi ?). Elle n'indique pas comment calculer le résultat ⇒ programme
Dans un SGBD le programme qui exécute une requête est appelé plan d’exécution. Ce plan d'exécution est un arbre, constitué d’opérateurs, agissant sur des jeux de données.
TODO image
Source : sys.bdpedia.fr
Selection :
La selection travaille sur R et definit une relation qui ne contient que les tuples de R qui satisfont à la condition (ou prédicat) specifiée.
σ predicat (R)
... FROM R WHERE predicat
Projection :
La projection travaille sur R et definit une relation restreinte à un sous-ensemble des attributs de R, en extrayant les valeurs des attributs specifiés et en supprimant les doublons.
Projection : π a1,...,ak (R)
SELECT a1,...,ak FROM R
Jointure theta :
La theta-jointure définit une relation qui contient les tuples qui satisfont le predicat P du produit cartesien de R et S. Le predicat P est de la forme R.aiθS.bj où θ est l’un des operateurs de comparaison ( <,≤,>,≥,=,!= )
θ-join : R ⋈ predicat S
FROM R INNER JOIN S on predicat
Requête :
SELECT titre FROM Film f INNER JOIN Role r on r.idFilm=f.id WHERE f.annee=1995 AND r.nom_role='John McClane'
Représentation algébrique
TODO image
Le SGDB et l'optimiseur de requêtes trouve les expressions équivalentes, évalue leur coût et choisit la meilleure.
Il est impossible/contre-performant d'énumérer tous les plans possibles (trop long) : on applique des heuristiques.
Heuristique classique : réduire au plus tôt la taille des données
Séparation des sélections :
TODO image
Application des sélections aux tables concernées :
TODO image
Principes essentiels :
De manière
Le plan physique consiste pour l'optimiseur à choisir les opérateurs.
Notion d'itérateur (open(), next(), close() methods)
TODO image
TODO image
Parfois il n’est pas possible d’éviter le calcul complet de l’une des opérations avant de continuer. On est alors en présence d’un opérateur dit bloquant dont le résultat doit être entièrement produit (et matérialisé en cache ou écrit sur disque) avant de démarrer l’opération suivante. Par exemple:
On distingue donc :
Un index est une structure de données permettant d'accélérer les recherches dans une table en associant à une clé d'index (la liste des attributs indexés) l'emplacement physique de l'enregistrement sur le disque.
Les accès effectués sur un index se font sur des structures optimisées pour la recherche (liste triée, B-tree…) au lieu de se faire par parcours séquentiel et intégral des enregistrements.
Intérêt :
R = Nombre de valeurs possibles/Nombre d'enregistrements ⇒ 1
Les index B-TREE sont les plus couramment utilisés.
Ils doivent être utilisés sur les tables qui sont fréquemment soumises à des recherches et sont d'autant plus pertinents que les requêtes sélectionnent un petit nombre d'enregistrements (moins de 25% par exemple).
Les index doivent être utilisés sur les attributs :
Inconvénients :
TODO image
Source : use-the-index-luke.com
Intérêt :
R = Nombre de valeurs possibles/Nombre d'enregistrements ⇒ 0
Les index Bitmap sont destinés à l'indexation de colonnes qui comportent donc peu de valeurs distinctes et beaucoup d'enregistrements pour chacune de ces valeurs.
A l'inverse des index B-Tree, les index Bitmap ne stockent pas un pointeur vers un enregistrement dans un fichier trié sur l'index, mais une valeur codée sur un bit (vrai ou faux) pour chaque valeur de la colonne indexée (2 bits pour une cardinalité 2, 3 pour une cardinalité 3, etc.) dans un fichier trié sur la clé. Ils sont donc moins coûteux en espace disque.
De tels index optimisent la recherche relative à une question du type : “l'enregistrement appartient-il à un sous ensemble du domaine sur l'index ?”.
Inconvénients :
diminuent de manière importante les performances en mise à jour (puisqu'il faut mettre à jour les index en même temps que les données). utilisables uniquement pour peu de valeurs distinctes = le meilleur ratio de valeurs distinctes au nombre total occurrences est d'environ 1 pour 1000.
Les index FullText permettent de faire des recherches sur les champs de type string (CHAR, VARCHAR et TEXT).
CREATE FULLTEXT INDEX ind_full_titre ON Livre (titre);
SELECT *
FROM Livre
WHERE MATCH(titre)
AGAINST ('story');
Permettent de poser un index de manière conditionnelle ⇒ limite la taille de l'index et accélère les recherches :
CREATE INDEX nr_mail
ON mails (subject)
WHERE status = 'NR'
L'utilisation d'un index ne suffit pas à la performance, même si la recherche dans l'index est plus rapide qu'un parcours séquentiel :
Une recherche nécessite les 3 opérations suivantes
L'index n'optimise que le parcours de l'arbre/séquentiel.
La plupart des SGDB possédent un analyseur de requêtes permettant de visualiser le plan d'exécution d'une requête.
PostgreSQL explain :
TODO image
Benchmark avec et sans Index BTree + Analyse des plans de requête (PostGreSQL) sur :