Les développeurs qui sont familiers d’Oracle ou de Microsoft SQL Server trouvent que les index, le modèle concurrentiel et la récupération des pannes de Firebird ne fonctionnent pas comme avec les bases de données qu’ils connaissent. Comprendre et travailler avec ces différences vous aidera à réussir votre transition vers Firebird en la rendant moins stressante. Cet article s’arrête sur quelques caractéristiques méconnues des index de Firebird.

Les types d’index

Firebird ne supporte qu’un seul type d’index : une variante de b-tree. Les index peuvent être uniques ou autoriser des doublons, ils peuvent être simples ou composés, ascendants ou descendants.

Stockage des enregistrements

Beaucoup de bases de données regroupent les enregistrements sur l’index de la clé primaire, soit directement en stockant les données dans l’index ou en utilisant la clé pour grouper les enregistrements. Dans un système correctement balancé, le regroupement sur les clés primaires rend les recherches sur les clés primaires très efficaces. Si tout l’enregistrement est stocké dans l’index, les données finissent par prendre beaucoup de place et rendent l’index complet très profond et plus coûteux à traverser qu’un index plus dense, peu profond. Le regroupement des enregistrements peut avoir pour conséquences la fragmentation du stockage ou des débordements en fonction des spécifications du modèle et de la distribution des données.

Firebird stocke les enregistrements dans les pages de données, utilisant la page la plus accessible disposant de la place suffisante. Les index sont stockés dans les pages d’index et les feuilles des noeuds de l’index contiennent un lien vers l’enregistrement.

Coûts d’accès des index primaires et secondaires.

Quand les données sont groupées sur les clés primaires, l’accès d’après la clé primaire est très rapide. L’accès par les index secondaires est plus lent, spécialement lorsque l’index de la clé secondaire utilise la clé primaire comme lien vers l’enregistrement. Dans ce cas la recherche avec l’index secondaire se transforme en deux recherches d’index.

Dans Firebird, le coût des recherches par les index primaires et secondaires est identique.

Stratégie d’accès des index

Beaucoup de systèmes de bases de données lisent un noeud d’index puis récupèrent les données. Cette technique amène à sauter d’une page d’index à une page de données, ce problème peut-être résolu en contrôlant correctement le placement des pages, en supposant que l’Administrateur de Base de Données ait le temps et les compétences pour le faire. Pour les index qui ne regroupent pas les données, cette technique conduit aussi à la relecture de pages de données.

Firebird parcoure les liens d’enregistrements pour les enregistrements sélectionnés d’après l’index, construit une carte des liens d’enregistrements et ensuite lit les enregistrements dans l’ordre de stockage physique.

Optimisation des Index

Puisque leur stratégie d’accès lie étroitement les accès indexés et l’accès aux enregistrements, dans beaucoup de bases de données, les optimiseurs doivent choisir un seul index par table comme chemin d’accès aux données. Firebird peut utiliser plusieurs index sur une même table en faisant des opérations booléennes ET et OU sur les cartes des liens d’enregistrements qu’il crée d’après les index avant d’accéder aux données.

Si vous avez une table dans laquelle plusieurs champs différents sont utilisés pour restreindre les données récupérées par une requête, la plupart des bases de données demandent que vous définissiez un seul index qui inclus tous les champs. Par exemple, si vous cherchez un film sorti en 1964, réalisé par Stanley Kubrick et distribué par Columbia vous aurez besoin d’un index sur les champs Année, Réalisateur et Distributeur. Si jamais vous vouliez trouver tous les films réalisés par Stanley Kubrick vous aurez aussi besoin d’un index sur le champ Réalisateur seul etc. Avec Firebird, vous n’aurez à définir qu’un index sur Réalisateur, un sur Distributeur et un sur DateDeSortie et ils pourront être utilisés dans différentes combinaisons.

Longues chaînes de doublons

Certaines bases de données (Firebird 2 en est une) sont meilleures que d’autres (comme par exemple Firebird 1.x) pour dédoubloner les enregistrements dans les longues (> 10000) chaînes de doublons. Si vous avez besoin d’un index sur un champ à faible sélectivité pour une base de données Firebird 1.x, vous devez créer une clé composée avec le champ que vous voulez indexer en premier et un champ plus sélectif en second. Par exemple, si vous avez un index sur DateDePaiement dans la table Factures, et que chaque enregistrement est créé avec la valeur NULL pour ce champ quand une facture est envoyée, et qui est ensuite modifié quand la facture est payée, vous devriez créer un index composé sur DateDePaiement et NumeroDeClient à la place d’un index simple sur DateDePaiement.

Lire l’index au lieu des données

Les bases de données non générationnelles résolvent certaines requêtes (les COUNT par exemple) en lisant les index à la place de lire les données. Les index dans Firebird (comme dans Postgres et dans d’autres bases de données nativement générationnelles) contiennent des entrées qui ne sont pas encore visibles pour les autres transactions et des entrées qui ne sont plus pertinentes pour certaines transactions actives. La seule manière de savoir si une entrée de l’index représente une donnée visible pour une transaction donnée est de lire la donnée elle-même.

On peut discuter longtemps au sujet des générations d’enregistrements. En bref, quand Firebird stocke un nouvel enregistrement, il marque l’enregistrement avec l’identifiant de la transaction qui l’a créé. Quand il modifie un enregistrement, il crée une nouvelle génération (version) de l’enregistrement et le marque avec l’identifiant de la transaction qui a fait la modification. Cet enregistrement pointe vers la génération précédente. Jusqu’à ce que la transaction qui a créé la nouvelle version ait été validée, toutes les autres transactions vont continuer à lire l’ancienne version de l’enregistrement.

Dans l’exemple précédent, quand une transaction modifie le champ indexé DateDePaiement, Firebird crée une nouvelle version de l’enregistrement contenant la nouvelle donnée et le marque avec l’identifiant de la transaction qui a fait le changement. L’index sur ce champ a maintenant deux entrées pour cet enregistrement, une pour la valeur NULL d’origine et une pour la nouvelle date de paiement.

L’index ne dispose pas d’assez d’informations pour déterminer seul laquelle des entrées doit être comptée pour répondre à une requête du type "select count(*) from Factures where DateDePaiement is not NULL".

Longueur des clés d’index

Dans les versions 1.x de Firebird, la longueur totale d’une clé d’index doit être inférieure à 252 octets. Les clés d’index composés et les index avec des séquences de tri non binaires sont encore plus restrictives pour les raisons décrites dans la section sur la compression des clés. Firebird 2 autorise des longueurs de clé jusqu’à 1/4 de la taille de la page, soit un maximum de 4Ko.

Représentation des clés d’index

Firebird converti toutes les clés d’index dans un format qui peut être comparé bit-à-bit. Exceptés les champs d’entiers sur 64 bits tous les champs numériques et dates sont stockés comme des clés entières double précision et le nombre double précision est manipulé pour pouvoir être comparé bit-à-bit. Quand on fait une recherche sur un index, Firebird converti la valeur d’entrée dans le même format que la clé stockée. De manière inhérente, cela signifie pour le développeur qu’il n’y a pas de différence de performance entre des index sur des chaines, des nombres ou des dates. Toutes les clés sont comparées bit-à-bit, sans tenir compte des règles applicables à leur type de donnée d’origine.

Compression des clés d’index

Dans Firebird, les clés d’index sont toujours stockées avec une compression préfixe et suffixe.

La compression suffixe supprime les espaces blancs de queue des champs chaînes de caractères et les zéros de queue des champs numériques. Souvenez vous que la plupart des valeurs numériques sont stockées comme des nombres double précision et que par conséquent les zéros de queue ne sont pas significatifs. La compression suffixe est réalisée pour chaque champ d’une clé composée sans perdre les frontières entre les champs de la clé. Après avoir supprimé les blancs ou les zéros de queue, l’algorithme de compression d’index ajuste la longueur du champ sur un multiple de 4 octets et insère un octet marqueur tous les 4 octets pour indiquer la position du champ dans la clé.

Considérons le cas d’une clé composée de trois champs contenant ces données :

Si l’on ne fait qu’éliminer les blancs de queue, les deux ensembles de valeurs sont identiques. A la place, Firebird transforme le premier ensemble de données en "abc 1def 2ghi 3" et le second en "abcd1efgh1i 1 2 3".

La version 1.x de Firebird compresse le préfixe des clés d’index comme elles sont stockées dans les pages de l’index. Elle stocke la première clé sur une page sans compression préfixe. Les clés suivantes sont stockées après avoir remplacé les octets d’en-tête qui correspondent aux octets d’en-tête de la clé précédente avec un seul octet qui indique le nombre d’octets en commun. Les deux clés précédentes devraient alors être stockées comme cela :

Une entrée d’index qui est exactement identique à l’entrée précédente est stockée par un simple octet qui contient sa longueur. Firebird 2 réalise aussi une compression préfixe mais utilise une représentation plus dense.

La combinaison des techniques de compression élimine beaucoup de règles de construction des clés. La compression suffixe s’applique sur tous les segments d’une clé, donc les champs VARCHAR longs peuvent être placés à leur emplacement logique dans une clé composée, il n’est pas obligatoire de les placer à la fin. D’un autre côté, si une partie de la clé à un grand nombre de doublons, elle devrait être placée au début de la clé composée pour tirer parti de la compression préfixe.