48.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 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.
![[Note]](images/note.png)
Écrire un gestionnaire de
langage procédural
