12. Annales des examens

Examen blanc du 20 janvier 2020 (sans concurrence)

Stockage et indexation

On veut stocker un fichier F avec 120000 enregistrements d’une taille fixe de 100 octets par article.

Questions :

  • De combien de blocs a-t-on besoin au minimum pour stocker tout le fichier si la taille d’un bloc est 8192 octets, sachant que chaque bloc contient un entête de 150 octets et qu’un enregistrement ne peut pas chevaucher 2 blocs?

Correction

Un bloc contient 8 042 octets utiles. Donc 80 enregistrements par bloc au maximum. On divise les 120 000 enregistrements par 80 et on obtient 1 500 blocs

  • On suppose maintenant que F est indexé par un index non dense sur A et un index dense sur un autre champ B. On peut stocker 100 entrées dans un bloc d’index et aucune place libre n’est laissée dans les blocs. Combien d’entrées y a-t-il dans les feuilles de l’index non dense? dans les feuilles de l’index dense?

Correction

Le fichier F contient 1 500 blocs et et trié sur A. L’index non dense contient donc 1500 entrées, une par bloc et cet index occupe 15 blocs. L’index dense contient 120000 entrées, une par enregistrement, et occupe 1200 blocs..

  • Supposons que l’index non dense a deux niveaux, racine comprise, et que seule la racine est en mémoire. On se place dans le pire des cas où il faut une lecture physique pour lire une feuille d’index et une autre pour lire un bloc du fichier.

    On cherche les enregistrements pour lesquels la valeur de l’attribut A est comprise entre P1A3 et P3G5. On suppose qu’il y a moins de 100 enregistrements tels que A commençe par P. Combien de lectures coûte la recherche par l’index dans le pire des cas?

Correction

La recherche utilise l’index non dense sur A. Celui-ci tient sur 15 blocs. La traversée de l’index part de la racine et arrive immédiatement à la feuille d’index dont la première entrée est inférieure ou égale à P1A3 et dont la dernière entrée est supérieure ou égale à P1A3. On recherche dans cette feuille l’entrée la plus grande inférieure ou égale à P1A3. Cette entrée contient l’adresse du bloc du fichier qui contient l’article de code P1A3. On accède à ce bloc bloc. Les articles sont triés sur A. Soit tous les articles de code compris entre P1A3 et P3G5 sont dans ce bloc soit ils sont à cheval sur deux blocs adjacents (ils ne peuvent pas être sur plus de 2 blocs adjacents). Dans ce dernier cas, une lecture du bloc adjacent chaîné est nécessaire. Donc la recherche coûte 2 ou 3 accès bloc.

  • Même question avec l’index dense, pour une recherche sur l’attribut B.

Correction

La recherche utilise l’index non dense sur B. La différence essentielle est que le parcours séquentiel s’effectue au niveau des feuilles de l’index. Il n’est plus possible de le faire sur le fichier car ce dernier n’est plus trié.

Pour chaque entrée trouvée dans une feuille, il faut effectuer une lecture de bloc dans le fichier de données. Au pire, il faut lire autant de blocs que d’enregistrements, soit 100 lectures qui viennent s’ajouter aux deux blocs lus dans l’index. Le coût prédominant est donc dans ce cas la multiplication des accès aléatoires au fichier de données, ce qui montre une nouvelle fois qu’une recherche par intervalle avec un index peut s’avérer contre-performante.

Index et optimisation

Soit les tables relationnelles suivantes (les attributs qui forment une clé sont en gras):

  • Produits (code, marque, desig, descr). NB: code : identifiant du produit, marque : marque du produit, desig : désignation du produit, descr : description.
  • PrixFour (code, nom, prix). NB: code : code du produit, nom : nom du fournisseur.
  • NoteMag (code, titre, note). NB: code : code du produit, titre : titre du magazine, note : note entre 1 et 10 du produit dans le magazine)

Voici une instance de la table NoteMag.

Code Titre Note
“A345” “HIFI” 8
“P123” “Audio Expert” 6
“X254” “HIFI” 7
“K783” “Son & Audio” 3
“P345” “HIFI” 6
“P512” “Audio Expert” 8
“L830” “Audio Expert” 8
“M240” “”HIFI”“ 6

La table occupe plusieurs blocs dont chacun peut contenir au maximum 3 n-uplets.

  • Construire un arbre B+ sur l’attribut code, avec 4 entrées par bloc au maximum.

  • Est-il utile d’indexer l’attribut titre? Pourquoi?

  • Soit la requête suivante :

    select *
    from NoteMag
    where code between 'A000' and 'X000';
    

    Pour évaluer cette requête, on suppose que le tampon de lecture ne peut contenir qu’un seul bloc et l” index tient en mémoire. Dans ce cas, est-ce qu’il est préférable d’utiliser l’index ou de parcourir la table séquentiellement ? Pourquoi ?

    Correction

    Une lecture séquentielle est préférable : la sélectivité de l’index est très basse, et comme il s’agit d’un index dense, on risque de lire la même page plusieurs fois.

On donne ci-dessous une requête SQL et le plan d’exécution fourni par Oracle :

select desig, marque, prix
from Produits, PrixFour, NoteMag
where Produits.code=PrixFour.code
and Produits.code=NoteMag.code
and note > 8;

Plan d’exécution :

0 SELECT STATEMENT
   1 MERGE JOIN
      2 SORT JOIN
         3 NESTED LOOPS
            4 TABLE ACCESS FULL NOTEMAG
            5 TABLE ACCESS BY INDEX ROWID PRODUITS
               6 INDEX UNIQUE SCAN A34561
      7 SORT JOIN
         8 TABLE ACCESS FULL PRIXFOUR

Questions:

  • Existe-t-il un index ? sur quel(s) attribut(s) de quel(s) table(s) ?

    Correction

    Il existe un index sur l’attribut code de la table Produits.

  • Algorithme de jointure : Expliquer en détail le plan d’exécution (accès aux tables, sélections, jointure, projections)

  • Ajout d’index : On crée un index sur l’attribut note de la table NoteMag. Expliquez les améliorations en terme de plan d’exécution apportées par la création de cet index.

Correction

Après création d’index le plan est :
Plan d'execution
----------------
0 SELECT STATEMENT
  1 NESTED LOOPS
    2 NESTED LOOPS
      3 TABLE ACCESS FULL PRIXFOUR
      4 TABLE ACCESS BY INDEX ROWID PRODUITS
        5 INDEX UNIQUE SCAN PRODUITS_CODE
    6 TABLE ACCESS BY INDEX ROWID NOTEMAG
      7 INDEX RANGE SCAN NOTE_MAG