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). 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.
48.3.1. Tâches pour la future implémentation de GEQO pour
PostgreSQL
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
