49. 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 de requêtes possibles croît exponentiellement avec le nombre de jointures de la requête. Un effort supplémentaire d'optimisation est nécessité par le support de différentes méthodes de jointure (boucles imbriquées, jointures de hachage, jointures de fusion...) pour exécuter des jointures individuelles et différents index (B-tree, hash, GiST et GIN...) pour accéder aux relations.

L'optimiseur standard de requêtes pour PostgreSQL™ réalise une recherche quasi-exhaustive sur l'ensemble des stratégies alternatives. Cet algorithme, introduit à l'origine dans la base de données System R d'IBM, produit un ordre de jointure quasi-optimal mais peut occuper beaucoup de temps et de mémoire à mesure que le nombre de jointures d'une requête augmente. 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, Allemagne, a rencontré des difficultés lorsqu'il s'est agi d'utiliser PostgreSQL™ comme moteur d'un système d'aide à la décision reposant sur une base de connaissance utilisé pour la maintenance d'une grille de courant électrique. Le SGBD devait gérer des requêtes à nombreuses jointures pour la machine d'inférence de la base de connaissances. Le nombre de jointures de ces requêtes empêchait l'utilisation de l'optimiseur de requête standard.

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