SQL Server vu par Christian Robert

SQL Server : Hash index ou comment indexer de (très) grosses colonnes

Si vous connaissez un tant soit peu SQL Server, vous saurez que celui-ci ne supporte pas ce qu'on appelle les Hash Index, ce que d'autres moteurs concurrent supportent. Ce « non support » est à relativiser car il est possible de créer « à la main » un mécanisme comparable, et qui est de plus pas très compliqué à mettre en œuvre.

Qu'est-ce que donc que ce Hash Index ? Si vous êtes développeur et familier des tables de hachage vous en comprendrez facilement le concept tant il est proche, sinon voici l'explication.

L'idée est de ne pas utiliser la données directement, mais une représentation de celle-ci, une clef. Cette clef peut être de différent types, par exemple pour une données de type texte une données numérique de type entière ou une données binaire. Il est possible d'avoir la même clef pour plusieurs données, c'est soit voulu ou non suivant le lien souhaité entre la données et sa clef.

Dans mon cas, je vais prendre une données texte, que je stocke dans un nvarchar(max) et ma clef sera un entier signé 32 bits (int). Le lien entre ces 2 données sera la fonction SQL nommée CHECKSUM(). Cette dernière calcule le Checksum de la données qui lui est passé, équivalente à la méthode Checksum que l'on trouve en .Net, attention cependant au fait qu'en fonction la plateforme sur laquelle on tourne est susceptible de renvoyer des résultats différents avec des données identiques en entrée (32 bits vs 64 bits, peut-être même sur des familles de CPU différentes).

Soit la définition de ma table :

CREATE TABLE dbo.MaTable
(
    Id int identity(1, 1) primary key,
    Contenu nvarchar(max),
    Clef AS CHECKSUM(Contenu)
)

J'ai choisi volontairement une colonne calculé pour la colonne « Clef », cette colonne renverra toujours le Checksum de la colonne « Contenu ».

Maintenant que se passe-t-il si j'insère quelques données, et que je souhaite créer un index sur Contenu…

INSERT dbo.MaTable(Contenu)
VALUES(REPLICATE(N'a', 2000))

SELECT * FROM dbo.MaTable

CREATE INDEX IX_Test ON dbo.MaTable(Contenu)

Vous obtiendrez le doux message d'erreur suivant :

Msg 1919, Level 16, State 1, Line 1
Column 'Contenu' in table 'dbo.MaTable' is of a type that is invalid for use as a key column in an index.

La raison en est très simple, il n'est pas possible d'indexer une contenu de plus de 900 octets… Or je viens d'insérer 2000 caractères dans un nvarchar(max) ce qui fait 4000 octets !

Comme il n'est pas possible d'indexer la colonne « Contenu », essayons la colonne « Clef »…

CREATE INDEX IX_Test ON dbo.MaTable(Clef)

Et là, ça marche… Attention cependant l'indexation d'une colonne calculée n'est possible qu'à certaines conditions. Entre autres les options ANSI compatibles activées, l'option Arithabort activé et que le résultat du calcul de la colonne soit déterministe. Par défaut dans SQL Server 2005 et 2008 tout est Ok.

Maintenant que j'ai un index sur ma colonne calculée qui n'est autre qu'une fonction sur ma colonne contenu, je vais pouvoir faire quelques requêtes sympas, mais avant on va ajouter quelques lignes de données.

INSERT dbo.MaTable(Contenu) VALUES(REPLICATE(N'b', 1000))
INSERT dbo.MaTable(Contenu) VALUES(REPLICATE(N'c', 900))
INSERT dbo.MaTable(Contenu) VALUES(REPLICATE(N'd', 800))
INSERT dbo.MaTable(Contenu) VALUES(REPLICATE(N'e', 700))
INSERT dbo.MaTable(Contenu) VALUES(REPLICATE(N'f', 600))

DECLARE @count int
SET @count = 10000

WHILE (@count > 0)
BEGIN
    INSERT dbo.MaTable(Contenu) VALUES(REPLICATE(N'x', @count))
    SET @count = @count - 1 ;
END

Et maintenant les Select avec leur plan…

SELECT * FROM dbo.MaTable WHERE Contenu = REPLICATE(N'b', 1000)

8614 I/O et 62 ms de temps processeur.

Le plan indique un scan de l'index clustered qui est la clef primaire de la table. C'est un table Scan on peut sans doute faire mieux que ce plan.

C'est là qu'on profite de la colonne « Clef »

SELECT * FROM dbo.MaTable WHERE Clef = CHECKSUM(REPLICATE(N'b', 1000))

6 I/O et 0 ms de temps processeur.

La plan indique une recherche dans l'index IX_Test.

Devinez quoi, IX_Test est ce qu'on peut appeler dans SQL Server un « Hash Index », en fait il s'agit d'un index crée sur une colonne calculée, cette colonne calculée étant la réduction de la colonne « Contenu ».

Le seul problème dans ma dernière requête réside dans le fait qu'il est possible d'avoir un Checksum identique entre 2 lignes.

SELECT * FROM dbo.MaTable WHERE Clef = CHECKSUM(REPLICATE(N'x', 255))

Avec mon jeu de données, 62 lignes sont renvoyées, alors qu'une seule ligne qualifie mon critère de recherche, c'est pour cela qu'il faut à la fois combiner la recherche sur le Hash Index et sur la valeur réelle ce qui permettra de supprimer les faux positifs qui risquent d'apparaître.

SELECT * FROM dbo.MaTable WHERE Clef = CHECKSUM(REPLICATE(N'x', 255)) AND Contenu = REPLICATE(N'x', 255)

Avec cette dernière requête, je peux réaliser ma recherche sur mon contenu volumineux tout en profitant de l'index, qui lui est très petit en comparaison du volume de données qu'il sert à indexer.

Petit commentaire concernant la fonction, le checksum a l'avantage d'être rapide et petit en termes de résultat, mais le risque de clefs en double est élevée et il ne serait être utilisé là où il y a un besoin de confidentialité élevé (comme un recherche sur des mots de passe non stockées en clair). Dans ces cas il peut être intéressant de préférer des fonctions de hachage type MD5 ou SHAx.

Bonne indexation…