Optimizacion de consultas

INTRODUCCIÓN

La mayoría de las bases de datos se utilizan en entornos multi-usuario, en los que muchos clientes utilizando la misma aplicación, o muchas aplicaciones cada una con uno o muchos clientes acceden a la misma base de datos al mismo tiempo para realizar transacciones.

1. INTRODUCCIÓN A LA OPTIMIZACIÓN.
El objetivo del procesamiento de consultas es transformar una consultaescrita en un lenguaje de alto nivel (SQL) en una estrategia de ejecución eficaz expresada en un lenguaje de bajo nivel (que implementa el álgebra relacional), y ejecutar dicha estrategia para recuperar los datos solicitados. Para expresar una consulta en un lenguaje de alto nivel como SQL, primero debe pasar por un examen o análisis léxico, un análisis sintáctico y una validación. El analizadorléxico identifica los componentes del lenguaje (componentes léxicos) en el texto de la consulta, y el analizador sintáctico revisa la sintaxis de la consulta para determinar si está formada de acuerdo con las reglas sintácticas (reglas gramaticales) del lenguaje de consulta. Además la consulta se debe validar, para lo cual ha de comprobarse que todos los nombres de atributos y de relaciones seanválidos y tengan sentido desde el punto de vista semántico.
A continuación se crea una representación interna de la consulta, por lo regular en forma de estructura de árbol o de grafo; esto se denomina árbol (o grafo) de consulta. En seguida, el SGBD debe crear una estrategia de ejecución para obtener el resultado de la consulta a partir de los archivos internos de la base de datos. Por lo regular,una consulta tiene muchas posibles estrategias de ejecución, y el proceso de elegir la más adecuada para procesar una consulta es lo que se conoce como optimización de consultas.
La optimización de consultas es un aspecto importante del procesamiento de consultas. Existen muchas transformaciones equivalentes de la misma consulta de alto nivel, y el objetivo de la optimización de consultas es elegirla estrategia de ejecución que minimiza el uso de los recursos. Generalmente, trataremos de reducir el tiempo total consumido por la consulta, que es el total de los tiempos empleados en ejecutar las operaciones individuales que componen dicha consulta. Sin embargo, el uso de los recursos puede verse como el tiempo de respuesta de la consulta, en cuyo caso nos concentraremos en maximizar elnúmero de operaciones paralelas (el tiempo total no será la suma de los individuales, pues estos ya no ocurren secuencialmente).
Puesto que el problema de realizar el análisis exhaustivo de todas las posibles estrategias de ejecución para obtener la de menor coste (la óptima) es computacionalmente intratable (salvo con consultas muy simples), la estrategia adoptada se reduce generalmente a encontraruna solución cercana a la óptima. No se garantiza que la estrategia elegida por el SGBD sea la óptima, pero seguro que la escogida es una estrategia razonablemente eficiente.

Por lo regular, todo SGBD cuenta con varios algoritmos generales de acceso a la base de datos que implementan operaciones relacionales como SELECCIONAR O REUNIÓN o sus combinaciones. El módulo de optimización de consultassólo puede considerar las estrategias de ejecución que puedan poner en práctica los algoritmos de acceso del SGBD y que se apliquen al diseño particular de la base de datos.

2. OPERACIONES RELACIONALES: SELECCIÓN, ORDENACIÓN, REUNIÓN Y PROYECCIÓN.

Operaciones del Algebra Relacional.
El álgebra relacional es una colección de operaciones que sirven para manipular relaciones enteras. Estasoperaciones sirven, por ejemplo, para seleccionar tuplas de relaciones individuales y para combinar tuplas relacionadas a partir de varias relaciones con el fin de especificar una consulta de la base de datos. El resultado de cada operación es una nueva relación, que podremos manipular de forma futura.
Las operaciones del álgebra relacional suelen clasificarse en os grupos. Uno contiene las...