Glossaire des plans d'exécution PostgreSQL

En règle générale:

  1. Sélectivité : Une requête est très sélective si elle renvoie un petit nombre de tuples par rapport à la taille totale de la table. Si l’index permet de rapidement identifier ces tuples (par exemple en scannant un petit nombre de feuilles dans un arbre B+), il sera effectivement très utile.
  2. Index couvrant : Un index est dit couvrant s’il contient toutes les colonnes nécessaires à la requête. Ainsi, la requête peut être résolue en ne consultant que l’index sans devoir accéder à la table.
  3. Index groupant : Un index est dit groupant lorsqu’il trie les données d’une manière pertinente pour la requête, permettant ainsi de réduire ou d’optimiser les opérations de tri ou de regroupement.
  4. Peu d’utilité : Si l’index ne remplit aucun des rôles ci-dessus (ni sélectif, ni couvrant, ni groupant), il est en effet probable qu’il n’apportera aucun bénéfice.

Exercice 1

Dans chaque cas ci-dessous, indiquer si l’index create index t_idx on t(a,b) a des chances d’être utile à la requête et le cas échéant pourquoi (lister toutes les raisons).

Q1:

SELECT first_value(c) OVER (ORDER BY b)
FROM t
WHERE a = 12;

Q2:

SELECT * FROM t
WHERE b = 1;

Q3:

SELECT * FROM t
WHERE a = 2 AND b = 3;

Q4:

SELECT * FROM t
WHERE a LIKE 'Par%';

Q5:

SELECT a, b FROM t
ORDER BY a;

Q6:

SELECT * FROM t
ORDER BY a;

Q7:

SELECT a, SUM(c) FROM t
GROUP BY a;

Exercice 2

En l’absence d’index sur la table, comparez les performances des deux requêtes suivantes :

  1. Requête 1 :
SELECT * FROM t
WHERE a = 38;
  1. Requête 2 :
SELECT * FROM t
WHERE a = 38 AND c = 3;

Le fait d’ajouter une condition supplémentaire dans la seconde requête (c = 3) peut-il accélérer, ralentir, ou n’avoir aucun effet significatif sur le temps d’exécution de la requête, sachant qu’il n’y a pas d’index sur la table ? Justifiez votre réponse en termes de scan de table et de filtrage des résultats.

Exercice 3

Contexte :

On vous demande de construire un B-tree d’ordre 3 (chaque noeud peut contenir entre 2 et 5 clés) à partir des clés suivantes, insérées dans cet ordre :

25, 16, 20, 4, 9, 30, 18, 10, 12, 28

À chaque étape, dessinez l’arbre après l’insertion d’une nouvelle clé et expliquez le processus d’insertion (comment sont redistribuées les clés et quand les noeuds sont éclatés).

Étapes de l’exercice :

  1. Insertion de 25 : Commencez par insérer la première clé.
  2. Insertion de 16 et 20 : Insérez les deux clés suivantes dans le même noeud, car il peut contenir jusqu’à 4 clés.
  3. Insertion de 4 : Continuez en insérant la clé 4. Le noeud n’est pas encore plein.
  4. Insertion de 9 : Après avoir inséré la clé 9, le noeud devient plein. Expliquez comment il est éclaté (split) et redistribué.
  5. Insertion de 30, 18, 10, 12, 28 : Continuez le processus d’insertion pour chaque clé, en éclatant les noeuds si nécessaire.

Consignes :

  • Dessinez l’arbre à chaque étape d’insertion.
  • Identifiez quand un éclatement de noeud est nécessaire.
  • Après chaque éclatement, expliquez comment les clés sont redistribuées entre les noeuds.

Question :

Quelle est la hauteur de l’arbre final et pourquoi est-ce important dans le contexte de la recherche de données dans un B-tree ?