Index et clés composées

Cette documentation a pour but d’expliquer comment définir de bonnes clés composées afin d’optimiser les accès à la base de données Oxygène. Pour cela, un premier chapitre explique de manière concise, le fonctionnement des index Hash-code et B-Tree. Le deuxième chapitre donne les avantages des clés composées. Enfin, le dernier chapitre explique comment choisir une bonne clé composée.

Les index

La base de données Oxygène est constituée de plusieurs fichiers. Toutes les données d’une table sont dans un seul fichier, chaque table ayant son propre fichier de données. A cela viennent s’ajouter des fichiers d’index : un fichier par index.

Lorsque l’utilisateur désire accéder aux données, Oxygène les recherche dans le fichier de données correspondant. Si aucune méthode d’optimisation n’est utilisée, cela peut être très long. Heureusement, les index interviennent à ce niveau pour accélérer ces accès.

Deux types d’index sont utilisés sous Oxygène. Il s’agit du Hash-code et du Séquentiel indexé (ou B-Tree). Leurs spécificités sont expliquées plus en détail dans les deux paragraphes suivants.

Hash-code

Caractéristiques

Cet index est capable de retrouver de manière très rapide un enregistrement ayant un champ de type Chaine, égal à une certaine valeur. Il ne peut donc être utilisé que lorsque l’on possède un filtre n’ayant que des conditions EgalA.

L’index Hash-code ne peut être calculé qu’à partir d’un seul champ d’une table.

Structure de données

Le fichier d’un index de type Hash-code débute par un tableau dont la taille dépend du nombre d’enregistrements prévus (le NPE est une propriété au niveau de la table). Chaque case du tableau contient un offset permettant d’accéder à un enregistrement. Cet offset est tout simplement la position de l’enregistrement dans le fichier de données.

Voir aussi Recalcul des NPE.

Fonctionnement

Lorsque l’on veut insérer un enregistrement dans une table ayant un index Hash-code, on commence par insérer les données de l’enregistrement dans le fichier de données, puis on calcule une clé à l’aide des données de la colonne qui a été choisie pour la création de l’index. Cette clé est une valeur. Elle peut être calculée de plusieurs manières (longueur des données, type des données, etc.…). Une fois que la méthode de calcul de la clé a été choisie, il est impossible d’en changer, c’est à dire que toutes les clés d’un index doivent être calculées de la même manière.

La clé sert à connaître le numéro de la case du tableau qui va recevoir la position de l’enregistrement dans le fichier de données.

Si deux enregistrements obtiennent la même clé, on dit qu’il y a collision. Une nouvelle clé est alors calculée pour le deuxième enregistrement, sur la base de la première clé.

Exemple :

Le calcul des clés donne :

Clé(“Dupont“) = 3

Clé(“Durand“) = 9

On obtient :

Important dans Oxygène

Seuls les 10 premiers caractères du champ servent à calculer le hashcode, donc si on a par exemple un champ NUMEROS sur 12 caractères, cela ne sera pas optimisé : hashcode(‘00000001|01000’) = hashcode(‘00000001|02000’) = … hashcode(‘00000001|03000’)

On ne devrait donc pas utiliser de HASCODE pour les champs NUMERO !

Séquentiel indexé ou "B-Tree"

Caractéristiques

Cet index permet de trier les positions des enregistrements en fonction des données des champs utilisés pour calculer le séquentiel indexé.

Ce mécanisme permet d’optimiser les filtres ayant des opérateurs SuperieurA, InferieurA, etc… Il permet aussi d’obtenir un classement sans surcoût de calculs.

Structure de données

Il s’agit d’un arbre dont les nœuds contiennent les bornes des sous-intervalles des nœuds sous-jacents. Une feuille contient la position dans le fichier de données, de l’enregistrement dont les champs se situent dans l’intervalle du nœud immédiatement supérieur à la feuille.

La taille d’un nœud est de 4096 octets.

Fonctionnement

La recherche d’un enregistrement débute par le nœud racine. Ce nœud contient les bornes des nœuds immédiatement inférieurs. Il suffit de choisir le nœud fils dont l’intervalle contient l’enregistrement que l’on recherche. Puis recommencer jusqu’à ce que l’on soit sur une feuille de l’arbre où la position de l’enregistrement recherché est inscrit.

Exemple :

Rechercher le premier client dont le prénom commence par D.

Voici le B-Tree :

Dans cet exemple, on choisit l’intervalle [Be ; Je].

Puis on recommence avec le nœud fils en choisissant l’intervalle [Da; Je].

On se trouve alors sur la feuille contenant “Daniel“. En fait, cette feuille contient la position de l’enregistrement “Daniel“ dans le fichier de données.

Limites

La capacité d'un index B-tree est fixe, elle n'évolue pas avec l'augmentation du nombre d'enregistrements.

Un index B-tree possédera toujours 65 535 noeuds. Par défaut dans Oxygène un noeud a une taille de 4096 octets. Donc si un champ de longueur 20 (tel qu'un champ CODE) est "séquentiel indexé", son index pourra gérer 4096 / 20 * 65535 = 13 421 568 valeurs (c'est une approximation car on ne peut exploiter tous les 4096 octets d'un noeud). Mettre un index sur un champ de taille 255 nous limitera à un million d'enregistrements, ce qui est facilement atteignable.

Or il n'y a pas de protection, si l'index est trop petit, des valeurs seront écrasées. C'est pourquoi il faut faire attention à la longueur des champs qu'on souhaite indexer.

Afin d'éviter une saturation, on utilise le NPE pour augmenter la taille d'un noeud : si le NPE est supérieur à la moitié de la capacité d'un index, on double la taille du noeud. Bien sûr cela va doubler la taille des fichiers index. La capacité minimale étant de 1 million, la taille des noeuds ne sera doublée que si le NPE est supérieur à 500 000.

Rappels : chaque champ indexé possède son index indépendants des autres. Une clé composée est techniquement un index Séquentiel.

Pourquoi les clés composées ?

Une clé composée est une concaténation de plusieurs champs d’une table. Une clé composé est automatiquement Séquentiel indexé. On obtient alors, des accès rapides aux données en ayant plusieurs critères de recherche.

Cela nous ramène aux filtres ; un choix judicieux des champs qui composent une clé composée optimise sensiblement les accès à une table sur laquelle un filtre a été défini. Pour rappel, lors d'une requête, Oxygène n'utilise au final qu'un seul index.

Choix d’une clé composée

Le choix d’une clé composée est directement en relation avec le ou les filtres qu’il faut optimiser.

Afin de fixer quelques mots de vocabulaire, il est important de définir un filtre comme étant un ensemble de conditions séparées par des opérateurs logiques (“Et“ ou “Ou“). Chaque condition est constituée d’un champ, d’un opérateur et d’une constante.

Voici les règles à suivre :

Les filtres contenant des “Ou” ne sont pas optimisés,
Les conditions ayant des opérateurs qui ne sont pas EgalA, InferieurA, SuperieurA, JusquA, APartirDe ou DebutePar sont écartées de l’optimisation (c'est-à-dire DifferentDe et NeDebutePasPar). Le filtre peut cependant être optimisé sur les autres conditions,
Une condition ayant un opérateur différent de EgalA est écartée de l’optimisation si un classement est spécifié et si le champ sur lequel porte ce classement est différent du champ de la condition,
Mettre les champs ayant des conditions EgalA dans le filtre au début de la clé composée,
Une clé composée ne peut optimiser qu’une seule des conditions suivantes à la fois : InferieurA, SuperieurA, JusquA, APartirDe, DebutePar.
Le champ ayant une condition différente de EgalA dans le filtre, doit être positionné dans la clé, juste après les champs ayant une condition EgalA,
Si un classement est demandé, le champ sur lequel porte ce classement doit forcément être placé au premier emplacement sur la droite des champs faisant partie des conditions du filtre. Ne pas oublier la troisième condition.
Si plusieurs clés composées peuvent optimiser un filtre, celle qui contient le plus grand nombre de champs faisant partie des conditions optimisables est choisie,
Il est possible d’ajouter autant de champs que désiré sur la droite de la clé composée.

Voici quelques exemples :

1. Filtre : Nom = “Dupont“ Et Prénom = “Jean“

Clés composées utilisables :

Nom ; Prénom

Prénom ; Nom

Nom ; Prénom ; Age

Nom ; Prénom ; Age ; Adresse ; …

Clés composée inutilisable :

Age ; Nom ; Prénom

Clé composée non conseillée car non optimale :

Nom

Prénom

2. Filtre : Nom = “Dupont“ Et Age > “25“

Clé composée utilisable :

Nom ; Age

3. Filtre : Nom = “Dupont“ Et (Age < “10“ Ou Age > “20“)

Clé composée utilisable :

Filtre non optimisable

4. Filtre : Nom = “Dupont“ Et (Age > “10“ Et Age < “20“)

Clés composées utilisables :

Nom ; Age

Nom ; Age ; Prénom ; …

5. Filtre : Nom = “Dupont“ Et Prénom = “Jean“, classé par Age

Clés composées utilisables :

Nom ; Prénom ; Age

Nom ; Prénom ; Age ; Adresse ; …

Clés composées non conseillées car non optimales :

Nom ; Age

Age

Prénom

Prénom ; Age

6. Filtre : Prénom > “Je“ Et Nom = “Dupont“, classé par Age

Clés composées utilisables :

Nom ; Age

Nom ; Age ; Adresse ; …

La condition sur le Prénom n’est pas optimisée car Prénom n’est pas le même champ que celui sur lequel porte le classement (Age).

7. Filtre : Nom DebutePar “D“

Clé composée utilisable :

Nom ; …

8. Filtre : Nom DebutePar “D“, classé par Prénom

Clé composée utilisable :

Prénom ; …

9. Filtre : Nom DebutePar “D“ Et Prénom > “J“ Et Age < 20

Clés composées utilisables:

Nom ; …

Prénom ; …

Age ; …

Une seule condition sera optimisée.

Remarque : le programmeur ne doit pas poser un filtre directement sur une clé composée.

Nombre d'enregistrements prévus (NPE)

Le Nombre prévus d'enregistrements que l'on indique au niveau d'une table sert à dimensionner les fichiers d'index selon les volumes maximum attendus. La valeur par défaut est 1000 (enregistrements). Il est important pour les index Hash-code et utile pour les index Séquentiels à partir de 500 000 enregistrements.

Outil d'analyse

L'outil STATMHI permet de détecter les défauts d'accès à la base de données et propose des clés composées à créer pour optimiser vos traitements.

N'oubliez pas que l'optimisation se fait en premier lieu dans le code : par exemple il est parfois préférable de poser moins de filtres et de lire plus d'enregistrements non souhaités que l'on rejette manuellement.