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). L'approche du module GEQO concernant le problème d'optimisation de requêtes revient au problème bien connu du marchand 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 jointure
/\ /\ 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.
Un gros travail est toujours nécessaire pour améliorer les paramètres de l'algorithme génétique. Dans le fichier src/backend/optimizer/geqo/geqo_main.c, pour les routines gimme_pool_size et gimme_number_generations, nous devons trouver un compromis dans les paramètres pour satisfaire deux demandes concurrentes :
Plan de requête optimum
Temps de calcul
À un niveau plus basique, il n'est pas clair que résoudre l'optimisation d'une requête avec un algorithme GA conçu pour TSP soit appropriée. Dans le cas TSP, le coût associé avec toute sous-chaîne (tour partiel) est indépendant du reste du tour mais ceci n'est certainement pas vrai pour l'optimisation de requêtes. Du coup, la question reste posée quant au fait que la recombinaison soit la procédure de mutation la plus efficace.
Algorithmes génétiques
