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

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

L'implantation de l'optimiseur de PostgreSQL™ réalise une recherche quasi-exhaustive sur l'ensemble des stratégies alternatives. Cet algorithme, tout d'abord introduit à l'origine dans la base de données « System R » d'IBM, produit un ordre de jointure quasi-optimal mais peut prendre beaucoup de temps et d'espace mémoire à mesure que le nombre de jointures grandit. L'optimiseur ordinaire de requêtes de PostgreSQL™ devient donc inapproprié pour les requêtes qui joignent un grand nombre de tables.

L'Institut de Contrôle Automatique de l'Université des Mines et de Technologie, basé à Freiberg, en Allemagne, a rencontré des difficultés lorsque ses employés ont voulu utiliser le SGBD PostgreSQL™ comme moteur pour leur système de support pour la maintenance d'une grille de courant électrique. Le SGBD avait besoin de gérer des requêtes comprenant de nombreuses jointures pour la machine d'inférence du système de connaissances.

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.

La suite du document décrit le codage d'un algorithme génétique de résolution de l'ordonnancement des jointures efficace pour les requêtes à jointures nombreuses.