De l’intérêt des index (2)

pages de navigation de l’index cluster sont surnuméraires. Il y a un inconvénient à l’index cluster. En effet, si cet index cluster est bâti sur une colonne dont les données arrivent chronologiquement, à l’insertion, dans le désordre le plus complet, il faut en permanence retrier toutes les lignes de la table. En revanche, si cet index est bâti sur une colonne chrono ordonnée, alors l’effort de tri est quasi nul ! Or quels types de colonnes s’avèrent naturellement chrono ordonnés ?

Les clefs auto incrémentées31 ! Nous en concluons qu’un index cluster est très intéressant sur une clef primaire auto incrémentée, mais qu’il peut s’avérer néfaste pour d’autres types de données composant la clef. Autrement dit, réfléchissez au comportement par défaut de SQL Server qui propose un index cluster pour toute clef primaire, ce n’est pas toujours la panacée… Nous avons dit qu’un index faisait référence à la clef de la table. Mais qu’en est-il d’une table sans clef, dans laquelle on créé quelques index ? Dans ce cas il est nécessaire que SQL Server retrouve la ligne de la table qui peut d’ailleurs être un doublon. Contrairement à quelques SGBDR qui numérote les lignes à l’insertion, SQL Server agit sur une logique parfaitement ensembliste et considère que c’est à vous d’agir !

Mais pour résoudre ce cas de figure SQL Server utilise une coûteuse combinaison d’informations : le numéro du fichier, le numéro de la page et le numéro de la ligne soit 12 octets. Une telle information doit aussi se retrouver dans toutes les entrées de tous les index secondaires… Ce qui fait dire à certains auteurs anglo-saxons "every table should have a key". Sous entendu, un index cluster unique et not null ! Posons-nous maintenant la question des index multicolonnes. Sont-ils intéressants ? Oui et non. En fait dans un index multicolonnes, l’information est vectorisée, c’est à dire que chaque colonne affine la précision de la précédente. Pour réaliser cela, l’information est concaténée. Ceci fait que des recherches ne peuvent pas s’effectuer par le parcours de l’index si ces informations sont à l’intérieur de l’index.

Par exemple si l’index est composé des colonnes NOM, PRENOM et DATE_NAISSANCE, alors toute recherche efficace sur cet index ne peut utiliser que les combinaisons suivante : NOM ou NOM + PRENOM ou NOM + PRENOM + DATE_NAISSANCE. Ainsi la recherche d’un prénom ou d’une date de naissance seule ne pourra bénéficier de l’apport que constitue un index. Si un index multicolonnes n’est pas efficace dans certains cas, il peut cependant s’avérer payant du fait de sa couverture… Nous savons qu’un index est redondant. Il porte en lui toutes les informations des colonnes indexées et s’il s’agit d’un index secondaire sur une table dotée d’une clef primaire, ce même index contient aussi la valeur de la clef. Dès lors toute requête portant sur des données uniquement contenues dans l’index n’a pas besoin de lire les informations de la table. Nous avons là un index dit "couvrant" pour la requête considérée.

SQL Server 2005 a étendu cette notion en permettant lors de la définition d’un index d’ajouter des colonnes d’informations qui, bien que ne participant pas à la définition proprement dite de l’index, permet de couvrir certaines requêtes… Autrement dit, il est possible d’ajouter à un index une ou plusieurs colonnes informatives de manière à assurer une couverture artificielle ! On pourrait encore parler des heures des index. Alors, continuons, le sujet n’est pas inépuisable, mais presque… Une idée pour aller plus vite dans la recherche des index, est de réduire la taille des données. Mais comment faire ? Un vieil outil mathématico informatique permet de transformer une donnée littérale en un code numérique. C’est ce que l’on appelle clef de hachage. SQL Server, et en particulier depuis la version 2005, offre la possibilité d’utiliser différents algorithmes pour calculer une correspondance numérique avec un littéral.

Pour avoir mis cela en place dans une base de données comportant quelques millions d’adresses e-mail, je peux vous affirmer que le gain peut être impressionnant ! Dès lors il suffit de combiner une colonne calculée dans la définition de la table et d’indexer cette colonne. Voire d’externaliser la clef de hachage dans une table en relation avec la table originale. D’autres systèmes permettant de réduire la masse des informations à chercher sont possibles, comme le partitionnement, aidé en cela par des fonctions particulières. Ainsi en matière de nom de personnes, on peut utiliser des mécanismes de consonnance (Soundex, Metaphone, Phonex…) ou encore des tables de Cutter Sanborn. Mais il y a mieux.

L’arme absolue en matière de performances apportées par l’indexation est constituée par la vue indexée. Dans un cours d’optimisation que je donne de manière régulière, je montre comment passer de requêtes dont l’exécution provoque la lecture de 98 000 pages de données à 2 en allant de la table non indexée, aux index, simples puis composites pour aboutir à la vue indexée, clou du spectacle ! Dernier élément dont je voudrais vous parler, en matière d’indexation.

Je vous ai dit que l’inconvénient de l’index est son coût en matière de mise à jour des données (INSERT, UPDATE, DELETE). Ce coût peut être notablement amoindri en utilisant un facteur à la création de l’index. Ce paramètre s’appelle le fill factor. Un facteur de remplissage de 100 % qui signifie que lors de la création les pages de l’index sont remplies au maximum, implique que toute nouvelle insertion provoquera une réorganisation de l’index, et en particulier la césure d’une page en deux, avec mise à jour de l’ensemble des pointeurs faisant référence à l’ancienne page. Cette réorganisation a un coût exorbitant… C’est elle qu’il faut éviter. Cela s’appelle un split de page.

En jouant sur le facteur de remplissage et en créant des index dont les pages ne seront pas remplies à plus de 80% lors de la création de l’index, on se réserve 20% d’insertions qui ne devraient pas entraîner de split de page, et cela au prix d’un index dont le surcroît en volume n’est que de 20%… Mais au bout du compte il faudra bien un jour reconstruire ces index car le facteur de remplissage ira inexorablement en diminuant au fur et à mesure des insertions. Cela est une autre histoire, elle s’appelle maintenance !

Je m’aperçois que j’ai oublié de vous parler de l’indexation textuelle, sujet d’une richesse incalculable… Comment trouver un mot rapidement dans un texte ? Et pour, les pluriels ? Les conjugaisons ? Les synonymes ? Les homonymes ? Comment proposer à l’utilisateur un mot qui existe alors qu’il a commis une faute de frappe, une erreur orthographique ? Des solutions efficaces existent pour toutes ces questions. Et en matière de proposition de correction orthographique, il existe des solutions plus ou moins efficaces qui s’appellent algorithme du dictionnaire de Knuth, différence de Hamming, distance de Levenshtein, inférence directe, index rotatifs…