Unidad3

Función principal de un procesador de consultas relacionales: transformar una consulta en una especificación de alto nivel, especialmente en cálculo relacional, a una consulta equivalente en una especificación de bajo nivel, típicamente alguna variación del álgebra relacional.
La transformación debe ser correcta y eficiente.

Es correcta: si la consulta de bajo nivel tiene la misma semántica que la consulta original, esto es, si ambas consultas producen el mismo resultado.

¿Dónde incide la optimización?
1. El coste de comunicación de acceso a almacenamiento secundario.
2. El coste de almacenamiento.
3. El coste de computación.
4. El optimizador interviene también en las actualizaciones y borrados.

3.2 Estrategias de procesamiento de consultas distribuidas.

Objetivo del procesamiento de consultas en un ambiente distribuido: 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.

Aspectos importantes que debe cumplir el proceso de optimización:

1. Representación interna de consultas.
2. Conversión a forma canónica.
3. Elección de procedimientos de bajo nivel.
4. Generación y elección de planes de consulta

Representación interna de consultas

Características:
·Ser relacionalmente completo.
·Suministrar un punto de partida sólido para las siguientes fases.
·Proporcionar un grado de libertad suficiente para realizar las posibles optimizaciones.

Sistemas de representación:
Álgebra relacional - Cálculo relacional - El árbol sintáctico abstracto o árbol de consulta.

Conversión a forma canónica: En ella encontramos que hay optimizaciones previas que tienen un resultado positivo seguro. En este paso debemos encontrar la expresión equivalente de una consulta dada en la que se mejore de alguna manera el rendimiento.

Elección de procedimientos de bajo nivel: se debe evaluar la consulta previamente transformada, también encontraremos existencia de índices u otras rutas de acceso y la distribución de los valores de los datos almacenados.

Procedimientos que debe tener un optimizador para una operación de Join:

Un procedimiento para el caso en que la condición sea a través de una clave candidata.
Un procedimiento para el caso en que el campo de restricción (en alfa unión) esté indexado.
Un procedimiento para el caso en que el campo de restricción no esté indexado pero sí agrupados los datos físicamente.

Generación y elección de planes de consulta

Cuando elegimos un plan una de las primeras cosas que debemos tener en cuenta para escogerlo es la estimación de costes. Estos costes dependen de muchos aspectos tales como: el nº de operaciones de entrada/salida del disco requeridas, la utilización de la CPU.

Una consulta suele implicar la generación de resultados intermedios, estos resultados estarán directamente relacionados con el número de E/S.

3.2.1.- Arboles de consulta.
En ciencias de la computación, un árbol de sintaxis abstracta (AST), o simplemente un árbol de sintaxis, es una representación de árbol de la estructura sintáctica abstracta (simplificada) del código fuente escrito en cierto lenguaje de programación. Cada nodo del árbol denota una construcción que ocurre en el código fuente.

Diferencia de los arboles de sintaxis abstracta: no representa cada detalle que aparezca en la sintaxis verdadera.

Árboles de sintaxis concreta (de parser): son a menudo construidos por la parte parser de la traducción del código fuente y el proceso de compilación.

3.2.2.- Transformaciones equivalentes. Cuando una base de datos se encuentra en múltiples servidores y distribuye a un número determinado de nodos tenemos:
1.-el servidor recibe una petición 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.

Realizar una transformación en la consulta: primero desfragmentamos siguiendo los estándares marcados por las reglas formales y posteriormente realizamos el envió y la maquina que recibe es la que muestra el resultado pertinente para el usuario, de esta se puede producir una copia que será la equivalente a la original.

3.3 Optimización de Consultas

Optimización global de consultas: es la tercera etapa del procesamiento de consultas distribuidas.

Objetivo de esta capa: hallar una estrategia de ejecución para la consulta cercana a la óptima.

Salida de la capa de optimización global: es una calendarización de una consulta optimizada en el álgebra relacional la cual indica el orden en que se ejecutan los operadores e incluye operaciones de comunicación sobre los fragmentos.

Objetivo del optimizador: encontrar la mejor estrategia, no necesariamente óptima, para ejecutar la consulta.

Proceso de optimización: selecciona el mejor miembro x de un conjunto que optimiza la función de costo. A este conjunto de posibles soluciones se le conoce como el conjunto solución.

Algoritmos, llamados de búsqueda (Optimización): se mueven de elemento a elemento en este espacio hasta encontrar una buena solución.

Técnicas para el desarrollo de algoritmos de búsqueda: búsqueda ávida - programación dinámica - algoritmos heurísticos - mejoramiento iterativo - recocido simulado - algoritmos genéticos - búsqueda tabú, etc.

Modelo de costo: El costo de una estrategia de ejecución distribuida se puede expresar con respecto al costo total (tiempo de ejecución) o al tiempo de respuesta.

Costo total: suma de todas sus componentes (I/O, CPU y comunicación). El tiempo de respuesta es el tiempo transcurrido desde el inicio de la consulta hasta su terminación.

Función de costo total: trata de reducir el costo de cada componente haciendo que éstas sean tan rápidas como sea posible,

Función del tiempo de respuesta: trata de hacer tantas cosas en forma simultánea (paralela) como sea posible lo que puede conducir a un incremento en el tiempo total de ejecución de la consulta.
Costo Total El costo total es la suma de todos los factores de costo y puede expresarse como
Costo total = costo de I/O + costo de CPU + costo de comunicación en donde,
Costo de CPU = costo de una instrucción * no. de instrucciones.
Costo de I/O = costo unitario de una operación de I/O a disco * no. de accesos
Costo de comunicación = (tiempo de iniciación + tiempo de transmisión) * no. de mensajes
Tiempo de Respuesta: tiempo transcurrido desde el inicio de la consulta hasta su terminación y se puede expresar como: Costo total = costo de I/O + costo de CPU + costo de comunicación
En donde: costo de CPU = costo de una instrucción * no. de instrucciones secuenciales
Costo de I/O = costo unitario de una operación de I/O a disco *no. de accesos secuenciales
Costo de comunicación = (tiempo de iniciación + tiempo de transmisión) * no. de mensajes secuenciales.

3.3.1 OPTIMIZACIÓN GLOBAL DE CONSULTAS DISTRIBUIDAS
Optimización de consultas distribuidas: En esta sección se ilustrará brevemente el uso de las técnicas presentadas previamente en las extensiones distribuidas de INGRES y System R. Algoritmo Distribuido de INGRES

Algoritmo de optimización de consultas para INGRES distribuido: se deriva del algoritmo usado en INGRES centralizado. Toma ventaja de la fragmentación, pero únicamente considera fragmentación horizontal. La función objetivo del algoritmo pretende minimizar la combinación del costo de comunicación junto con el tiempo de respuesta.

Algoritmo R* de optimización de consultas distribuidas: es una extensión sustancial a las técnicas desarrolladas para el optimizador de System R. La función de costo considera el costo de procesamiento local así como el costo de comunicación.

El optimizador del maestro: hace todas las decisiones entre nodos, tales como la selección de los nodos de ejecución así como el método de transferencia de datos.

Para juntar dos relaciones existen tres nodos candidatos: el nodo de la primera relación, el nodo de la segunda relación o un tercer nodo que surge de la unión con una tercera relación.
En R*, se utilizan dos métodos para las transferencias de datos entre nodos.

Transfiere todo: La relación completa es transferida al nodo donde se realiza la junta y almacenada en una relación temporal antes de hacer la junta.

Lee conforme lo necesita: La relación externa es recorrida secuencialmente y, para cada tuplo, el valor de la junta se envía al nodo de la relación interna, el cual selecciona los tuplos internos que satisfacen el predicado de la junta y envía los tuplos seleccionados al nodo con la relación externa.

Estrategias para realizar la junta:
Estrategia 1. Se transfiere la relación externa completa al nodo con la relación interna.
Estrategia 2. Se transfiere la relación interna completa al nodo con la relación externa.
Estrategia 3. Se obtienen los tuplos de la relación interna conforme se necesitan para cada tuplo de la relación externa.
Estrategia 4. Se mueven las relaciones a un tercer nodo y se calcula la junta ahí.

3.3.2. Optimización Local de Consultas
Optimización centralizada de consultas: En esta sección se revisa el proceso de optimización de consultas para ambientes centralizados. Esta presentación es un prerrequisito para entender la optimización de consultas distribuidas por tres razones:
1.- una consulta distribuida se transforma a varias consultas locales cada una de las cuales se procesa en forma centralizada.
2.- Las técnicas para optimización distribuida son, por lo general, extensiones de técnicas para optimización centralizada.

Algoritmo de INGRES INGRES: usa un algoritmo de optimización dinámico que recursivamente divide una consulta en el cálculo relacional en piezas más pequeñas. Combina dos fases de la descomposición cálculo-álgebra relacional y optimización. No requiere información estadística de la base de datos.

Fases generales del algoritmo System R:
1.- Descompone cada consulta con múltiples variables en una secuencia de consultas con una sola variable común.
2.- Procesa cada consulta mono-variable mediante un procesador de consultas de una variable el cual elige, de acuerdo a algunas heurísticas, un plan de ejecución inicial.

Algoritmo de System R: ejecuta una optimización de consultas estática basada en búsqueda exhaustiva del espacio solución. La entrada del optimizador es un árbol del álgebra relacional que resulta de una consulta en SQL. La salida es un plan de ejecución que implementa el árbol del álgebra relacional "óptimo".
El optimizador asigna un costo a cada árbol candidato y obtiene aquel con costo menor.
Los árboles candidatos se obtienen permutando el orden de las juntas de la n relaciones de una consulta usando las reglas de conmutatividad y asociatividad.

El costo de una estrategia candidato es una combinación pesada de costos de I/O y CPU.
El algoritmo de optimización consiste de dos grandes pasos:

Las consultas simples se ejecutan de acuerdo al mejor camino de acceso (basada en un predicado de selección).

Para cada relación R, se estima el mejor ordenamiento de juntas, en donde R se accesa primero usando el mejor método de acceso a una sola relación.

Para la junta de dos relaciones: la relación cuyos tuplos se leen primero se llama externa, mientras que la otra, cuyos tuplos se encuentran de acuerdo a los valores obtenidos de la relación externa, se llama relación interna.