48. Optimiseur génétique de requêtes (Genetic Query Optimizer)

Parmi tous les opérateurs relationnels, le plus difficile à exécuter et à optimiser est la jointure (join). Le nombre de plans de requêtes possibles croît de façon exponentielle avec le nombre de jointures inclus dans la requête. Un effort supplémentaire d'optimisation est dû au support d'une variété de méthodes de jointure (par exemple les boucles imbriquées, les jointures de découpage, les jointures d'assemblage dans PostgreSQL™) pour exécuter des jointures individuelles et une diversité d'index (par exemple B-tree, hash, GiST et GIN dans PostgreSQL™) comme chemins d'accès des relations.

L'optimiseur standard de requêtes pour PostgreSQL™ réalise une recherche pratiquement exhaustive sur tout l'espace des stratégies alternatives. Cet algorithme, tout d'abord introduit dans la base de données System R d'IBM, produit un ordre de jointure presque optimal mais peut prendre beaucoup de temps et d'espace mémoire lorsque le nombre de jointures dans une requête devient important. Ceci rend inapproprié l'optimiseur ordinaire de requêtes de PostgreSQL™ pour les requêtes établissant une jointure entre un grand nombre de tables.

L'institut de contrôle automatique de l'université des mines et de technologie, basé à Freiberg, Allemagne, a rencontré quelques problèmes quand ces employés ont voulu utiliser PostgreSQL™ comme moteur pour leur système de support pour la maintenance d'une grille de courant électrique. Le DBMS avait besoin de gérer des requêtes comprenant des jointures larges pour la machine d'inférence du système de connaissances. Le nombre de jointures dans ces requêtes ont rendu impossible l'utilisation de l'optimiseur standard de requêtes.

Les difficultés en terme de performance pour l'exploration des plans de requêtes possibles ont créé la demande du développement d'une nouvelle technique d'optimisation.

Dans la suite, nous décrivons l'implémentation d'un algorithme génétique pour résoudre le problème des ordres de jointure d'une façon efficace pour les requêtes impliquant un grand nombre de ces jointures.