Projet IDAPA

Accueil > Bases de données relationnelles et indexation du contenu > Rapport - Partie 3

Rapport - Partie 3

Etude des solutions techniques pour un entrepôt de données

vendredi 6 février 2009, par Yoann Moreau

5 Les solutions techniques d’entrepôt de données

5.1 MySQL et Sphinx

En se basant sur la structure de données détaillée auparavant, il est facile de créer une table MyISAM de 3 colonnes (id, attribut, valeur) à laquelle on ajoutera autant de lignes qu’il y a de valeurs. L’insertion de donnée dans cette table serait simple et rapide. Les colonnes d’id et d’attribut seraient clés primaires de la table. La colonnes des valeurs seraient indexées par l’index fulltext de MySQL pour optimiser les recherches. Cet index avancé se met à jour automatiquement lors des modifications de la table, il tient compte de la rareté des mots pour leur donner une plus grande importance. La recherche peut trier les résultats par pertinence. Il est possible de paramétrer les tailles minimum de mots à indexer. Mais ces fonctions avancées ne sont pas utiles dans le cas du cube, les performances ne seraient donc peut être pas optimales. De plus dans le cas de masses de données à indexer très importantes (lorsque l’index est de taille supérieure à la mémoire vive) l’efficacité est considérablement réduite. On peut précharger tout ou une partie des index dans le cache (en mémoire) avec la requêtes LOAD INDEX INTO CACHE, cela permet de mettre les index en mémoire de manière plus efficace car séquentielle.

Ajout de données

L’ajout de données peut s’effectuer par la requête INSERT ou par la requête LOAD DATA INFILE, cette seconde étant beaucoup plus rapide mais impliquant que les données soient dans un fichier. Ce fichier peut être lu par le client et envoyé automatiquement par la requête, ou lu directement sur le serveur, ce qui est plus rapide. La requête permet de spécifier les séparateurs de champs, on peut donc importer les données d’un simple fichier tabulé. Si l’on ajoute les données dans une table vide que l’on ne modifiera plus à l’avenir l’insertion peut être optimisée en créant les index seulement après, et les données peuvent être compressées pour réduire la taille sur disque.

Opération de projection

Pour sélectionner les attributs à conserver, il suffirait d’une autre table contenant comme clé le nom de l’attribut et une valeur booléenne indiquant si l’attribut doit être conservé ou pas. L’utilisateur effectuant la projection devra alors mettre à jour la table des attributs avant de lancer l’opération de projection.

L’opération en elle même consistera à un SELECT renvoyant toutes les lignes (complètes) dont l’attribut est présent dans la table d’attributs et qui est placé à vrai. Le retour de ce SELECT donne directement la table représentant le sous cube voulu. On peut écrire le résultat de la requête dans un fichier avec la requête SELECT … INTO OUTFILE en précisant les séparateurs de champs (comme pour la requêtes LOAD DATA INFILE). Pour éviter un parcours complet de la table, on utilisera un index classique sur les attributs, on peut forcer l’utilisation de l’index avec la clause FORCE INDEX. On peut vérifier comment MySQL effectue une requête avec la clause EXPLAIN.

Opération de coupe

La coupe s’effectue en 2 temps, d’abord on teste les conditions sur les attributs concernés en récupérant la liste des id correspondant aux conditions, puis on récupère les valeurs associées à ces id. Une fois la liste des id à garder construite, il ne reste plus qu’à effectuer une projection sur les id (contrairement à la projection sur les attributs de l’opération de projection) qui peut être optimisée avec un index classique sur les id. Cette seconde étape pourrait facilement inclure une opération de projection étant donné que l’on parcourt les valeurs. Dans ce cas il faudra choisir si l’on utilise l’index des id ou l’index des attributs (sur le principe expliqué en partie 4 Les points sensibles), ce choix est fait automatiquement par MySQL mais le forcer pourrait éviter des calculs.

C’est le test des conditions qui est la partie la plus lourde car les valeurs sont éparpillées. Pour optimiser ce point on peut utiliser l’indexation sur les valeurs ou sur les attributs, cela dépend de la nature de l’entrepôt de données. Dans notre cas les valeurs sont rares et donc l’indexation des valeurs est la plus adaptée. Pour cette indexation particulière (indexation de texte) on utilise un index FULLTEXT, la fonction MATCH permet ensuite de récupérer toutes les lignes où l’argument de la fonction correspond à la valeur. Il faut ensuite tester l’attribut (avec une simple clause conditionnelle en plus) pour vérifier que la valeur trouvée soit associée à l’attribut voulu. En utilisant SELECT DISTINCT avec ces conditions on récupère la liste des id.

Le moteur d’indexation Sphinx

Sphinx est un moteur de recherche fulltext open-source qui peut être utilisé directement sur des fichiers texte ou facilement intégré à des bases de données orientées SQL. Il existe une API pour MySQL qui rendrait la combinaison facile à mettre en place. Sphinx offre les outils d’indexation fulltext et de recherche.

L’indexation fulltext fournie par MySQL a ses limites et selon certains articles ne supporte pas des masses de données trop importante. Etant donné la taille d’un entrepôt de données et les besoins de rapidité en recherche Sphinx fournirait apparemment de bien meilleures performances et serait donc à utiliser directement dans MySQL en lieu et place de l’indexation fulltext native.

5.2 MySQL et Indri

Cette solution utilise MySQL de la même manière que la solution précédente excepté qu’on indexe pas les valeurs (pas d’indexation fulltext dans MySQL). L’indexation fulltext des valeurs est faite en externe par le moteur d’indexation Indri qui lui ne possède pas d’API MySQL. Comme Sphinx ce moteur peut être utilisé directement comme un programme ou par des API de programmation (C++ et Java), il dispose cependant de fonctionnalités supérieures, il a son propre langage de requête permettant d’effectuer des recherches plus complexes qu’avec du SQL. Sa combinaison avec MySQL étant moins évidente qu’avec Sphinx, il faut un programme synchronisant MySQL et l’indexation fulltext d’Indri. L’indexation fulltext serait effectuée lors de l’ajout des données, ces nouvelles données passerait d’abord par Indri pour être indexées sur les valeurs puis seraient ajoutées dans la table de MySQL.

Dans cette solution les opérations sur le cube serait effectuées par le programme synchronisant MySQL et Indri, il fournirait une interface d’utilisation de l’entrepôt de données. Il effectuerait les requêtes SQL selon les opérations appelées et simplifierait l’appel des opérations du point de vue de l’utilisateur. L’opération de coupe s’effectue aussi en 2 temps, mais le test des conditions est appliqué sur l’index d’Indri. Une fois la liste des id récupérée on peut créer le sous cube en utilisant les index de clés primaires de la table MySQL.

5.3 Sans MySQL

Une approche très différente du problème consisterait à ne pas utiliser d’index de recherche mais à simplement parcourir les données de manière séquentielle. Cette solution implique d’avoir des données triées (par rapport à leur id dans notre cas). Dans les autres solutions l’ajout de données était efficace car simplement ajouté à la suite des données existantes ; pour des données triées l’ajout de données implique un tri complet à chaque fois. La taille des données étant très importante ce tri est une opération lourde. L’implémentation de cette solution serait par contre rapide car la commande sort d’UNIX effectue le tri souhaité, il n’y aurait donc que les procédures de parcours et d’ajout de données à implémenter. Les données seraient stockées dans un simple fichier tabulé.

Ajout de données

L’ajout de données est la partie la plus lourde car il faut réordonnancer le fichier à chaque fois. On commence par ajouter les lignes (id – attribut – valeur) en fin de fichier en utilisant les séparateurs choisis (qui doivent être les mêmes pour tout le fichier), puis on effectue la commande sort d’UNIX sur le fichier :

$ sort -t $’\t’ -k 1,1 -o donnees.dat donnees.dat

L’option -t spécifie le séparateur de champ, par défaut c’est un espace. L’option -o spécifie le fichier de sortie, la commande utilise automatiquement un fichier temporaire pour effectuer le tri lorsque le fichier de sortie est le même que le fichier d’entrée. Par défaut le tri s’effectue par rapport au début de la ligne, avec l’option -k on spécifie quel champ est utilisé pour le tri, en ajoutant une autre valeur après une virgule on spécifie à quel champ arrêter les comparaisons. Ici on compare uniquement sur le premier champ (champ des id), en effet trier les attributs est inutile et serait donc une perte de temps.

Opération de projection

Cette opération nécessite un parcours complet des données car les attributs ne sont pas triés. Une solution serait d’avoir les données en double dans un autre fichier trié cette fois sur les attributs, mais autant en espace de stockage qu’en temps d’ajout de données (qui serait doublé) cette solution n’est pas envisageable. Une autre solution serait d’indexer les attributs ce qui revient en fait à mettre en œuvre les solutions MySQL ou Indri. Pour connaître les attributs à conserver, il suffirait d’une liste de noms d’attributs dans un fichier ou directement en argument de la commande.

Opération de coupe

Cette opération consiste en un parcours unique des données, elle se fait donc en une étape contrairement aux autres solutions. En effet les données étant triées par id, on a pas besoin de rechercher les valeurs de chaque id une fois les tests de condition effectués. On se contente de parcourir de façon séquentielle les lignes du fichier, on récupère ainsi par blocs toutes les valeurs d’un id, on peut appliquer facilement les tests de conditions sur ces valeurs et ainsi décider de les conserver ou non. Ajouter une projection par attributs ne serait pas très coûteux en calcul.