Optimización Genética de Consultas (GEQO) en Postgres

El módulo OGEC esta previsto para solucionar el problema de optimización de consultas similares al problema del viajante (PV). Los planes posibles de consulta son codificados por cadenas de enteros. Cada cadena representa el orden de la una relación de unión de la consulta a la siguiente. P. e., el árbol de la consulta

/\ /\ 2 /\ 3 4 1

esta codificado por la cadena de enteros '4-1-3-2', que significa, la primera relación de unión '4' y '1', después '3', y después '2', donde 1, 2, 3, 4 son relids en Postgres.

Partes del módulo OGEC han sido adaptadas del algoritmo Genitor de D. Whitley.

Las características especificas de la implementación de OGEC en Postgres son:

• El uso de un AG en estado constante (remplazo de los individuos con menor adaptación de la población, no el reemplazo total de un generación) permite converger rápidamente hacia planes mejorados de consulta. Esto es esencial para el manejo de la consulta en un tiempo razonable;

• El uso de cruce de recombinación limitada que esta especialmente adaptado para quedarse con el límite menor de perdidas para la solución del PV por medio de un AG;

• La mutación como operación genética se recomienda a fin de que no sean necesarios mecanismos de reparación para generar viajes legales del PV.

El módulo OGEC proporciona los siguientes beneficios para la DBMS Postgres comparado con la implementación del optimizador de consultas de Postgres:

• El manejo de grandes consultas de tipo unión a través de una búsqueda no-exhaustiva;

• Es necesario una mejora en la aproximación del tamaño del coste de los planes de consulta desde la fusión del plan más corto (el módulo OGEC evalúa el coste de un plan de consulta como un individuo).