actividad # 16

optimización de consultas

El objetivo del procesamiento de consultas en un ambiente distribuido es transformar una consulta sobre una base de datos distribuida en una especificación de alto nivel a una estrategia de ejecución eficiente expresada en un lenguaje de bajo nivel sobre bases de datos locales.

Así, el problema de optimización de consultas es minimizar una función de costo tal que

función de costo total = costo de I/O + costo de CPU + costo de comunicación

Los diferentes factores pueden tener pesos diferentes dependiendo del ambiente distribuido en el que se trabaje. Por ejemplo, en las redes de área amplia (WAN), normalmente el costo de comunicación domina dado que hay una velocidad de comunicación relativamente baja, los canales están saturados y el trabajo adicional requerido por los protocolos de comunicación es considerable. Así, los algoritmos diseñados para trabajar en una WAN, por lo general, ignoran los costos de CPU y de I/O. En redes de área local (LAN) el costo de comunicación no es tan dominante, así que se consideran los tres factores con pesos variables.

Operación Complejidad

La complejidad de las operaciones sugiere dos principios:

1. Dado que la complejidad es con base en las cardinalidades de las relaciones, las operaciones más selectivas que reducen las cardinalidades deben ser ejecutadas primero.

2. Las operaciones deben ser ordenadas en el orden de complejidad creciente de manera que el producto Cartesiano puede ser evitado o, al menos, ejecutado al final de la estrategia.

Tipo de optimización

El problema de optimización de consultas es altamente demandante en tiempo de ejecución y, en el caso general, es un problema de la clase NP. Así existen dos estrategias para su solución: búsqueda exhaustiva o el uso de heurísticas. Los algoritmos de búsqueda exhaustiva tienen una complejidad combinatorial en el número de relaciones de la consulta. Obtienen la transformación óptima, pero sólo se aplican a consultas simples dado su tiempo de ejecución.

Por otro lado, los algoritmos heurísticos obtienen solo aproximaciones a la transformación óptima pero lo hacen en un tiempo de ejecución razonable. Las heurísticas más directas a aplicar son el agrupamiento de expresiones comunes para evitar el cálculo repetido de las mismas, aplicar primero las operaciones de selección y proyección, reemplazar una junta por una serie de semijuntas y reordenar operaciones para reducir el tamaño de las relaciones intermedias.

Granularidad de la optimización

Tiempo de optimización

Una consulta puede ser optimizada en tiempos diferentes con relación a tiempo de ejecución de la consulta. La optimización se puede realizar de manera estática antes de ejecutar la consulta o de forma dinámica durante la ejecución de la consulta. 

La optimización estática se hace en tiempo de compilación de la consulta. Así, el costo de la optimización puede ser amortizada sobre múltiples ejecuciones de la misma consulta. 

Durante la optimización de consultas dinámica la elección de la mejor operación siguiente se puede hacer basado en el conocimiento exacto de los resultados de las operaciones anteriores. Por tanto, se requiere tener estadísticas acerca del tamaño de los resultados intermedios para aplicar esta estrategia. 

Un tercer enfoque, conocido como híbrido, utiliza básicamente un enfoque estático, pero se puede aplicar un enfoque dinámico cuando los tamaños de las relaciones estimados están alejados de los tamaños actuales.

Optimización Global de Consultas: El objetivo de esta capa es hallar una estrategia de ejecución para la consulta cercana a la óptima. La estrategia de ejecución para una consulta distribuida puede ser descrita con los operadores del álgebra relacional y con primitivas de comunicación para transferir datos entre nodos. Para encontrar una buena transformación se consideran las características de los fragmentos, tales como, sus cardinalidades.

Optimización Local de Consultas: El trabajo de la última capa se efectúa en todos los nodos con fragmentos involucrados en la consulta. Cada subconsulta que se ejecuta en un nodo, llamada consulta local, es optimizada usando el esquema local del nodo. Hasta este momento, se pueden eligen los algoritmos para realizar las operaciones relacionales. La optimización local utiliza los algoritmos de sistemas centralizados.

Estrategias de procesamiento de consultas distribuidas

Transformaciones equivalentes

Cuando una base de datos se encuentra en multiples servidores y distribuye a un numero determinado de nodos tenemos:

1.-el servidor recive una peticion de un nodo

2.-el servidor es atacado por el acceso concurrente a la base de datos cargada localmente

3.-el servidor muestra un resultado y le da un hilo a cada una de las maquinas nodo de la red local.

Cuando una base de datos es accesada de esta manera la técnica que se utiliza es la de fragmentación de datos que puede ser hibrida, horizontal y vertical.

En esta fragmentación lo que no se quiere es perder la consistencia de los datos, por lo tanto se respetan las formas normales de la base de datos.

Bueno para realizar una transformación en la consulta primero desfragmentamos siguiendo los estandares marcados por las reglas formales y posteriormente realizamos el envio y la maquina que recibe es la que muestra el resultado pertinente para el usuario, de esta se puede producir una copia que sera la equivalente a la original.

 Métodos de ejecución de join

Sean (R) y s(S) dos relaciones:
Si R S= entonces r s es lo mismo que r x s, y por lo tanto se puede utilizar la estimación del producto cartesiano.
Si R S es una clave de R entonces el número de tuplas en r s no es mayor que el número de tuplas en S. Si R S es una clave externa de R entonces el número de tuplas de r s es exactamente el número de tuplas de S.
Si R S no es clave de R ni de S entonces se supone que cada valor aparece con la misma probabilidad , por lo tanto, sea t una tupla de r y sea R S=Ā, entonces se estima que la tupla t produce :
tuplas en s, por lo tanto se estima el tamaño de r s = (a) al cambiar los papeles de r y s se tiene (b)
Estos valores serán distintos si y sólo si V(A,r) V(A,s), si este es el caso, la más baja estimación de ambas será la más conveniente.
Join en bucles anidados.
Si z = r s, r recibirá el nombre de relación externa y s se llamará relación interna, el algoritmo de bucles anidados se puede presentar como sigue.
para cada tupla tr en rpara cada tupla ts en ssi (tr,ts) satisface la condición entonces añadir tr ts al resultado Algoritmo 5–1 - Join en bucles anidados.
Donde tr ts será la concatenación de las tuplas tr y ts .

Como para cada registro de r se tiene que realizar una exploración completa de s, y suponiendo el peor caso, en el cual la memoria intermedia sólo puede concatenar un bloque de cada relación, entonces el número de bloques a acceder es de . Por otro lado, en el mejor de los casos si se pueden contener ambas relaciones en la memoria intermedia entonces sólo se necesitarían accesos a bloques.

Ahora bien, si la más pequeña de ambas relaciones cabe completamente en la memoria, es conveniente utilizar esta relación como la relación interna, utilizando así sólo accesos a bloques.

Join en bucles anidados por bloques.

Una variante del algoritmo anterior puede lograr un ahorro en el acceso a bloques si se procesan las relaciones por bloques en vez de por tuplas.

para cada bloque Br de rpara cada bloque Bs de spara cada tupla tr en Brpara cada tupla ts en Bssi (tr,ts) satisface la condición entonces añadir tr ts al resultado

Algoritmo 5–2 - Join en bucles anidados por bloques.

La diferencia principal en costos de este algoritmo con el anterior es que en el peor de los casos cada bloque de la relación interna s se lee una vez por cada bloque de r y no por cada tupla de la relación externa, de este modo el número de bloques a acceder es de donde además resulta más conveniente utilizar la relación más pequeña como la relación externa.

Join en bucles anidados por índices.

Este algoritmo simplemente sustituye las búsquedas en tablas por búsquedas en índices, esto puede ocurrir siempre y cuando exista un índice en el atributo de join de la relación interna. Este método se utiliza cuando existen índices así como cuando se crean índices temporales con el único propósito de evaluar la reunión.

El costo de este algoritmo se puede calcular como sigue: para cada tupla de la relación externa r se realiza una búsqueda en el índice de s para recuperar las tuplas apropiadas, sea c = costo de la búsqueda en el índice, el cual se puede calcular con cualquiera de los algoritmos A3, A4 o A5. Entonces el costo del join es ; si hay índices disponibles para el atributo de join en ambas relaciones, es conveniente utilizar la relación con menos tuplas.

Join por mezcla.

El algoritmo de Join por mezcla se pude utilizar para calcular un Join natural o un equi-join. Para tales efectos ambas relaciones deben estar ordenadas por los atributos en común.

Este algoritmo asocia un puntero a cada relación, al principio estos punteros apuntan al inicio de cada una de la relaciones. Según avanza el algoritmo, el puntero se mueve a través de la relación. De este modo se leen en memoria un grupo de tuplas de una relación con el mismo valor en los atributos de la reunión.

link de la informacion