48.3. Optimisation génétique des requêtes (GEQO) avec PostgreSQL

Le module GEQO est la solution du problème d'optimisation des requêtes, une solution similaire au problème du voyageur de commerce (TSP). Les plans de requêtes possibles sont codés comme des chaînes d'entiers. Chaque chaîne représente l'ordre de jointure d'une relation de la requête à une autre. Par exemple, l'arbre de requêtes

   /\
  /\ 2
 /\ 3
4  1

est codé avec la chaîne d'entiers '4-1-3-2', ce qui signifie : première jointure entre les relations '4' et '1', puis '3' et enfin '2', avec 1, 2, 3, 4 les identifiants des relations pour l'optimiseur de PostgreSQL.

Des parties du module GEQO sont adaptées de l'algorithme Genitor de D. Whitley.

Les caractéristiques spécifiques de l'implémentation de GEQO dans PostgreSQL sont :

• Utilisation d'un état d'équilibre du GA (remplacement des individus les moins performants d'une population, pas un remplacement d'une génération complète) qui permet une convergence rapide vers les plans de requêtes améliorés. C'est essentiel pour une gestion des requêtes sur un temps raisonnable ;

• Utilisation d'un croisement de recombinaison de bord qui convient tout spécialement pour garder bas le nombre de pertes aux bords pour la solution du TSP en utilisant un GA;

• La mutation comme opérateur génétique est obsolète d'une telle façon qu'aucun mécanisme de réparation n'est nécessaire pour générer des tours TSP légaux.

Le module GEQO permet à l'optimiseur de requêtes de PostgreSQL de supporter les requêtes disposant de jointures importantes de manière efficace via une recherche non exhaustive.