46.1. Gestion des requêtes comme un problème complexe d'optimisation

Parmi 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 inclus. 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 R-tree, B-tree, découpage dans PostgreSQL) comme chemins d'accès des relations.

L'implémentation de l'optimiseur de 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 >>, 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é les problèmes décrits car ces employés voulaient utiliser le DBMS 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.

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.