Universidad Central de Venezuela Facultad de Ciencias Escuela de Computación ADMINISTRACION DE BASES DE DATOS Tema 5: P
Views 46 Downloads 7 File size 1MB
Universidad Central de Venezuela Facultad de Ciencias Escuela de Computación ADMINISTRACION DE BASES DE DATOS
Tema 5: Procesamiento y Optimización de Consultas
Mercy Ospina Torres Mayo de 2010
Centro de investigación en Sistemas de Información CISI Pág. 1
Contenido CONTENIDO.......................................................................................................................... 1 1
INTRODUCCIÓN ............................................................................................................ 2
2
PROCESAMIENTO DE CONSULTAS............................................................................ 3
3
TRADUCCIÓN DE CONSULTAS SQL AL ALGEBRA RELACIONAL .......................... 4 3.1.1
Arboles de ejecución................................................................................................................................ 7
3.2 Axiomas o reglas del Algebra Relacional ...............................................................................9 3.2.1 Definición de los Axiomas........................................................................................................................ 9 3.2.2 Tamaño del espacio de posibilidades de ejecuciones de una consulta lógica .................................. 10
4
TÉCNICAS PARA OPTIMIZAR CONSULTAS ........................................................... 11
4.1
Optimización basada en heurísticas ................................................................................... 11
4.2
Factor de selectividad: ..................................................................................................... 14
4.3 Operadores físicos y cálculo de costos ................................................................................ 16 4.3.1 Información del catálogo del sistema utilizada para estimar costos. ................................................ 16 4.3.2 Cálculo del espacio en disco requerido por una relación. .................................................................. 17 4.3.3 Operación Selección .............................................................................................................................. 18 4.3.4 Operación ordenamiento ...................................................................................................................... 20 4.3.5 Operación proyección............................................................................................................................ 22 4.3.6 Operación Reunión (Join) ...................................................................................................................... 23 4.3.7 Árbol de ejecución físico........................................................................................................................ 26 4.4 Evaluación de expresiones ................................................................................................ 27 4.4.1 Materialización....................................................................................................................................... 27 4.4.2 Encauzamiento (Pipeline) ...................................................................................................................... 27 4.4.3 Ejercicio de Ejemplo............................................................................................................................... 28
5
BIBLIOGRAFÍA ........................................................................................................... 32
Pág. 1
Procesamiento y Optimización de Consultas
1 Introducción La optimización representa tanto un reto como una oportunidad para los sistemas relacionales, un reto ya que se requiere que un sistema de esta naturaleza tenga un desempeño aceptable, y una oportunidad debido a que el enfoque relacional permite que las expresiones relacionales estén en un nivel semántico que permita optimizarlas. De lo contrario, en sistemas donde las peticiones de los usuarios son expresadas en un nivel semántico más bajo, cualquier optimización debe ser realizada por el usuario de forma manual, por lo que si el usuario toma una mala decisión no hay nada que el sistema pueda hacer para mejorar las cosas. La optimización llevada a cabo por el sistema se denomina automática y tiene como ventaja que los usuarios no tienen que preocupase por formular las consultas de la mejor manera, ya que existe la posibilidad real de que el optimizador pueda hacerlo mejor que un usuario humano, por varias razones entre las que se encuentran las siguientes: 1. Un buen optimizador cuenta con una gran cantidad de información disponible que por lo general no tienen los usuarios humanos; en particular información estadística como: a. Cantidad de valores de un dominio b. Cantidad actual de tuplas en cada relación base c. Cantidad actual de valores distintos en cada atributo de estas relaciones d. Cantidad de veces que estos valores se dan en estos atributos. Toda esta información se mantiene en el catálogo del sistema, y con ella el optimizador es capaz de valorar la eficiencia de cualquier estrategia dada para implementar una petición y por tanto más probable que pueda seleccionar la implementación más eficiente. 2. Si las estadísticas de la base de datos cambian con el tiempo, tal vez sea necesario seleccionar una estrategia diferente, es decir realizar una reoptimización, la cual es trivial en los sistemas relacionales ya que simplemente involucra un reprocesamiento de la petición original 3. El optimizador es un programa al que no se le agota la paciencia, por lo que literalmente puede considerar cientos de estrategias diferentes para una petición, en cambio un usuario humano es probable que solo llegue a considerar más de tres o cuatro. 4. En el optimizador se han implementado las habilidades y servicios de los mejores programadores humanos. Como consecuencia, tiene el efecto de poner a disposición de todos los usuarios estas habilidades y servicios. Entonces el propósito del optimizador es seleccionar una estrategia eficiente para la evaluación de una expresión relacional dada. En el desarrollo de este tema se explicara el proceso de optimización y algunos de los principios y técnicas fundamentales involucrados en este. Se muestra un proceso muy importante que es el de transformación de una expresión o reescritura de consultas, por último es importante aclarar que el término optimización es un poco engañoso, ya que no hay ninguna garantía de que la estrategia elegida en realidad sea óptima en cualquier sentido, lo único que se sabe con certeza es que es una mejora de la versión original.
Pag. 2
Procesamiento y Optimización de Consultas
2 Procesamiento de consultas El procesamiento de consultas hace referencia a una serie de actividades que tienen como objetivo la extracción de datos de una Base de Datos (Silberschatz, Korth, & Sudarshan, 2006). En la figura 1 se muestran los pasos involucrados en el procesamiento de una consulta, los pasos básicos son: 1. Análisis y traducción 2. Optimización 3. Evaluación
Consulta de alto nivel
Analizador y traductor
Expresión del algebra relacional
Optimizador Diccionario de Datos Resultado de la consulta
Motor de Evaluación
Plan de Ejecución
Estadísticas de los datos
Datos
Figura 1 Pasos en el procesamiento de la consulta (Silberschatz, Korth, & Sudarshan, 2006)
Análisis: Una consulta de alto nivel debe ser en primer lugar analizada. El analizador hace un análisis léxico, un análisis sintáctico y una validación:
Análisis léxico: Identifica los elementos del lenguaje como por ejemplo, las palabras reservadas de SQL, si están bien formados los nombres de los atributos y relaciones en el texto de la consulta. Análisis sintáctico: Comprueba la sintaxis de la consulta de acuerdo a las reglas sintácticas del lenguaje de consulta. Validación: Comprueba que los nombres de las relaciones, atributos sean válidos semánticamente dentro del esquema de la base de datos sobre la cual se realiza la consulta y si los tipos de datos se están usando correctamente.
Pag. 3
Procesamiento y Optimización de Consultas Traductor: Crea una representación interna de la consulta, mediante una estructura de árbol denominado árbol de consulta, el cual está basado en el álgebra relacional extendido. Entonces la primera acción que el sistema tiene que realizar para procesar una consulta es traducirla a su formato interno, si la consulta esta expresada en términos de una vista la fase de traducción sustituye todas las referencias a la vista por las expresiones que las definen. Optimización: El SMBD debe desarrollar una estrategia de ejecución para obtener el resultado de la consulta. Ya que una consulta puede disponer de muchas estrategias distintas, basadas en el álgebra relacional, y cada operador del algebra relacional puede tener varias implementaciones físicas. El optimizador debe determinar la estrategia más adecuada, y especificar completamente como evaluar la consulta, indicando las instrucciones, y que estructuras adicionales usar (índices). Motor de ejecución: recibe el plan de evaluación, lo ejecuta y devuelve la respuesta de la consulta. El término optimizador resulta en realidad “inapropiado” ya que en algunos casos el plan de ejecución elegido no resulta ser la estrategia más optima, sino una estrategia “razonablemente eficiente” para ejecutar la consulta, ya que por lo general la búsqueda de la estrategia más óptima consume demasiado tiempo, excepto en el caso de consultas muy sencillas.
3 Traducción de consultas SQL al algebra relacional En la práctica SQL es el lenguaje de consultas que se utiliza en la mayoría de los SMBDR comerciales. Las consultas SQL se descomponen en bloques de consulta que forman las unidades básicas que pueden traducirse al álgebra relacional. Un bloque está compuesto por una única expresión SELECT – FROM – WHERE y también clausulas GROUP BY y HAVING si las hubiere. Por lo tanto las consultas anidadas se identifican como bloques independientes y se ejecutan de manera independiente (Elmasri & Navathe, 2007). Debido a que SQL incluye operadores de agregación como MAX, MIN, SUM y COUN T, estos también deben ser incluidos en el álgebra relacional extendida. En general una consulta SQL es de la forma SELECT FROM WHERE Donde la lista de tablas representa las tablas o archivos involucrados en la consulta, las
), las condiciones de igualdad de atributos sobre diferentes tablas (o la operación JOIN) representa operaciones JOIN del algebra relacional, y la lista de atributos representa operaciones PROJECT del AR. condiciones sobre atributos de las tabla representan operaciones SELECT del AR (
Pag. 4
Procesamiento y Optimización de Consultas Por ejemplo, veamos la siguiente consulta SELECT E.Apellido1, E.Nombre, E.Sueldo FROM Empleado E, Departamento D WHERE D.nombre =ventas and E.sueldo > 2000 and E.CodDpto = D.CodDpto; Se puede traducir de la siguiente manera Se hace la selección sobre las tablas
Se hace la reunión natural de las tablas temporales
Por ultimo se hace una proyección de los atributos solicitados
La expresión completa queda de la siguiente manera
Las expresiones SQL anidadas dan como resultado tantas expresiones del AR como anidamentos tenga la consulta, por ejemplo. SELECT Apellido1, Nombre, Sueldo FROM Empleado WHERE Sueldo > ( SELECT MAX (Sueldo) FROM Empleado WHERE Dno = 5); Esta consulta incluye una subconsulta anidada por lo tanto es descompuesta en dos bloques SELECT MAX (Sueldo) FROM Empleado WHERE Dno = 5 SELECT Apellido1, Nombre, Sueldo FROM Empleado WHERE Sueldo >c Donde c es el resultado del bloque interno. Podríamos traducir los bloques a expresión del algebra relacional extendida.
C TMAX Sueldo (σDno=5 (Empleado)) Y
El optimizador seleccionará un plan para cada bloque, lo cual en algunos casos sería más sencillo de optimizar si el optimizador tuviera que optimizar un solo plan.
Pag. 5
Procesamiento y Optimización de Consultas Estas consultas en AR aun son declarativas o se denominan planes de ejecución lógicas, ya que aunque son más detalladas no especifican todavía como obtener los datos desde las estructuras de almacenamiento, este último es el plan de ejecución físico, el cual se explicará detalladamente en la optimización basada en costos. Existen diferentes maneras de convertir una consulta SQL a una expresión del AR. A continuación se mostrará un método para esta traducción utilizando el concepto de árboles, por lo que en primer lugar se definirán los conceptos necesarios para la realización del proceso de traducción.
Pag. 6
Procesamiento y Optimización de Consultas
3.1 Arboles de ejecución 3.1.1
Árbol de ejecución lógico
Con la consulta en algebra relacional se puede construir un árbol de ejecución lógico de consulta el cual se construye de las hojas a la raíz. Def: Un árbol de ejecución P, es un árbol que tiene a lo más paridad 2 (binario), por cada hoja del árbol corresponde una tabla, y cada nodo interno representa a un operador del Algebra Relacional. Caso Base Es un árbol binario lógico
T
Caso inductivo Si P1 y P2 son árboles lógicos y θ es un operador que pertenece a los operadores binarios {X, U, }, y cond es una condición booleana. θ
σcond
∞con
ΠAtt
d
P1
P2
P1
P2
P1
P1
Ejemplo: la siguiente consulta en AR
ΠApellido1, Nombre, Sueldo (σSueldo > c (Empleado)) Se traduce al siguiente árbol de ejecución lógica
ΠApellido1, Nombre, Sueldo σSueldo > c
Empleado 3.1.2
Árbol de ejecución físico
Es el mismo árbol de ejecución lógico, pero en los nodos internos se cambian los operadores lógicos a alguno de sus correspondientes operadores físicos
Pag. 7
Procesamiento y Optimización de Consultas 3.1.3
Árbol de ejecución lineal izquierdo
B es un árbol de ejecución lineal izquierdo sii es un árbol de ejecución y para cualquier nodo de aridad 2, el hijo derecho es una tabla. 3.1.4
Árbol canónico
Sea S una expresión en SQL SELECT FROM WHERE Un árbol canónico para S es un árbol lineal izquierdo donde cada nodo binario corresponde al producto cartesiano sobre dos tablas o sobre un subárbol y una tabla, la raíz a la proyección sobre la lista de atributos, seguida por un nodo selección con la condición cond. Por ejemplo si la lista de tablas es T1… Tn, se tendrá el siguiente árbol canónico ΠlistaAtt σcond X Tn X X T1
T3 T2
Planes de ejecución lógic os Dada una consulta hay generalmente distintos métodos para obtener una respuesta, por ejemplo la consulta exterior anterior se puede ejecutar de las siguientes maneras
o
Y cada una de ellas representa un plan de ejecución lógico distinto. Para construir los diferentes planes que representan una consulta en SQL, el SMBDR utiliza los axiomas del álgebra relacional.
Pag. 8
Procesamiento y Optimización de Consultas
3.2 Axiomas o reglas del Algebra Relacional 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. 3.2.1
Cascada de selecciones Conmutatividad de la selección Cascada de proyecciones Distributividad de la proyección y la selección Conmutatividad del Join y del producto cartesiano Distributividad de la selección con respecto al join/producto cartesiano Distributividad de la proyección sobre el join/producto cartesiano Conmutatividad de la unión y la intersección Asociatividad de la unión y la intersección Distributividad de la selección con respecto a la unión o la intersección. Distributividad de la proyección con respecto a la unión o la intersección. Conversión del producto cartesiano en join. Definición de los Axiomas Dadas las Relaciones R, R1 y R2
1. Cascada de selecciones
Donde c1, c2, …, cn son condiciones booleanas 2. Conmutatividad de la selección
3. Cascada de proyecciones
4. Distributividad de la proyección y la selección
Si no
5. Conmutatividad del Join y del producto cartesiano
Pag. 9
Procesamiento y Optimización de Consultas 6. Distributividad de la selección con respecto al join/producto cartesiano
Nota: Este axioma permite empujar las selecciones hacia abajo en el árbol
7. Distributividad de la proyección sobre el join/producto cartesiano
8. Conmutatividad de la unión y la intersección
9. Asociatividad de la unión y la intersección
10. Distributividad de la selección con respecto a la unión o la intersección.
11. Distributividad de la proyección con respecto a la unión o la intersección.
12. Conversión del producto cartesiano en join.
3.2.2
Tamaño del espacio de posibilidades de ejecuciones de una consulta lógica
Dada una consulta con n relaciones y n-1 joins para relacionarlas, cuantos planes distintos se pueden construir (considerar parametrizaciones). Se deben tomar en cuenta. 1) Los ordenamientos diferentes: n relaciones se pueden ordenar de n! formas distintas. 2) Las asociaciones o paréntesis entre joins. Se usa el número de catalán que cuantifica expresiones perfectamente parentizadas.
Donde m es el número de paréntesis (es decir el número de joins en este caso). Pag. 10
Procesamiento y Optimización de Consultas
4 Técnicas para optimizar consultas 1. Optimización basada en heurísticas. 2. Optimización basada en costos (la cual no se tratará en la presente guía)
4.1 Optimización basada en heurísticas Se define heurística como el métodos exploratorios durante la resolución de problemas en los cuales las soluciones se descubren por la evaluación del progreso logrado en la búsqueda de un resultado final (por experiencia). En informática, se utilizan algoritmos heurísticos para obtener soluciones sub-óptimas de problemas cuya optimización no es factible en tiempos polinómicos. Esta técnica busca obtener un plan de ejecución lógico, cuyo costo sea minimal, basado en las siguientes hipótesis:
Hipótes is: -
Realizar las operaciones de selección y proyección lo más cercano posible a las hojas de los árboles para reducir resultados intermedios. La evaluación de un join es más económica que la evaluación de un producto cartesiano.
Para ello se construye un árbol inicial y se realiza el reordenamiento de las operaciones usando los axiomas del álgebra relacional.
Pasos: Construir un árbol canónico Aplicar los axiomas (si aplican) 1) Aplicar el axioma o regla 1, para descomponer cualquier operación SELECT con condiciones conjuntivas en una cascada de selecciones. 2) Aplicar axiomas 2, 4, 6 y 10, relativas a la conmutatividad del SELECT o distributividad del SELECT con otras operaciones, para desplazar cada operación SELECT hacia abajo en el árbol de ejecución, tan lejos como lo permitan los atributos incluidos 3) Aplicar axiomas 5 y 9, relativas a la conmutatividad y asociación de las operaciones binarias para reordenar los nodos hoja utilizando el siguiente criterio: a. Posicionar las relaciones con los SELECT más restrictivos de forma que sean ejecutadas en primer lugar. Se puede decir que los Select más restrictivos son los que tienen un factor de selectividad más pequeño, y este se puede calcular con el catálogo del sistema. b. Verificar que las ordenaciones no produzcan productos cartesianos que no puedan convertirse en JOIN 4) Aplicar axioma 12, para conbinar los SELECT con los PRODUCTOS CARTESIANOS, para formar una operación de JOIN 5) Aplicar axiomas 3, 4, 7, 11 para bajar en el árbol las operaciones PROJECT lo más que se pueda.
Pag. 11
Procesamiento y Optimización de Consultas Ejemplo: Seleccionar los estudiantes que pasaron Administración de base de datos en el semestre 2-2009 Select Nombre From Estudiante E, Cursar C, Materia M Where E.CI = C.CI and Nota >=10, and M.Cod_Mat =C.Cod_Mat and M.Nombre = ‘Administración de base de datos’ and semester_cursa = ’2-2009’
Arbol canónico de la consulta SQL
πNombre Cond = Estudiante.CI = Cursa.CI and Nota >=10, and Materia.Cod_Mat = Cursa.Cod_Mat and Materia.Nombre = ‘Administración de base de datos’ and semester_cursa = ’2-2009’
σcond X
X Estudiante
Materia Cursa
Aplicando el axioma 1 y 2 (cascada de selecciones y conmutatividad de la selección)
Pag. 12
Procesamiento y Optimización de Consultas
πNombre
X X Estudiante
Materia Cursa
Aplicando los axiomas 6 y 12, bajamos las selecciones respectivas a los productos cartesianos y a las hojas,y convertimos los productos cartesianos en Reuniones naturales (Join)
πNombre
Materia Estudiante Cursa
Luego se aplicar el axioma 5 Para que las selecciones más restrictivas queden a la izquierda (ver factor de selectividad) Pag. 13
Procesamiento y Optimización de Consultas Actividad: Como se pueden aplicar los axiomas referidos a las proyecciones
Planes de ejecución f ísic os Una vez que se ha determinado un plan de ejecución lógico, el sistema debe construir el plan de ejecución físico correspondiente, para determinar el costo de evaluación de la consulta ejecutada con dicho plan seleccionado, para ello es necesario definir los operadores físicos asociados a los operadores lógicos del Algebra Relacional, estudiados anteriormente. Para determinar el costo de estos operadores, se deben conocer los algoritmos que implementan cada uno de estos a nivel físico, y el tamaño de las relaciones temporales resultantes, para lo cual es necesario utilizar el factor de selectividad, que será definido a continuación.
4.2 Factor de selectividad: Es una función que estima la probabilidad de que una tupla en una relación, satisfaga una condición booleana dada. La estimación se realiza en función de la hipótesis de uniformidad e independencia. A través de este factor se determina el tamaño estimado de la relación resultante.
Uniformidad Es igualmente probable que una tupla Ti tenga un valor C en el atributo Aj.
Los valores de Aj están distribuidos uniformemente entre las tuplas.
Indepen dencia Al ejecutarse la siguiente consulta
se asume que la satisfacibilidad de que la
condición cond1 es independiente a la satisfacibilidad de la condición cond2.
¿Cómo calcu lar el factor de s electivida d? Caso base: a)
b)
min(At 1) = C1
C2
Ci
max(At 1)=Cn
Se hace la suposición de que el dominio de At 1 es finito y discreto, además existe una enumeración de los valores en el dom(At1).
Pag. 14
Procesamiento y Optimización de Consultas
b) c)
Factor de selectividad del join d) Casos inductivos: Sean P1 y P2 expresiones booleanas de una selección o un join. a) b) c) Cardinalidad de la selección = fs*numero de tuplas de R
Pag. 15
Procesamiento y Optimización de Consultas
4.3 Modelo de costos El modelo de costos es una herramienta estadística formal que permite estimar el costo de evaluar un plan de ejecución físico. La metaheurística permite recorrer porciones del espacio de búsqueda donde se encuentran buenos planes de ejecución El costo de evaluación de una consulta se mide en tiempo y puede expresar en términos de diferentes recursos, incluyendo:
Los accesos a disco,
El tiempo de CPU, El costo de comunicación (en sistemas distribuidos), El tiempo de respuesta para un plan de evaluación de una consulta
En sistemas de bases de datos centralizadas, el costo más importante es el de acceso a disco ya que los accesos a disco son mucho más lentos que los accesos a memoria principal y los tiempos de CPU. Aunque los optimizadores reales consideran los costos de CPU, aquí se ignoran y solo se considerarán los costos de acceso a disco. Para obtener los costos de acceso a disco se debe calcular el costo de los diferentes algoritmos, llamados operadores físicos, en función del tiempo de transferencia de un bloque, por lo que se debe conocer la cantidad de bloques que ocupan los datos y su organización, y la cantidad de acceso a los índices. 4.3.1
Información del catálogo del sistema utilizada para estimar costos.
En primer lugar se debe conocer el tamaño de cada archivo de datos, el numero de registros (cardinalidad), el tamaño (medio) de los registros, el numero de bloques, el factor de bloqueo, el método de acceso primario, la organización y el atributo de ordenamiento (si están ordenados), los índices del archivo de datos, el numero de niveles de cada índice, el tipo (primario, secundario, agrupado) y el numero de bloques de índice de primer nivel, el tamaño de cada atributo y el número de valores distintos o su selectividad.
Pag. 16
Procesamiento y Optimización de Consultas 4.3.2
Cálculo del espacio en disco requerido por una relación.
En el tema de Manejo de memoria se conoció que cada relación se almacena en bloques de disco, donde un bloque es la unidad mínima de transferencia entre memoria principal y secundaria, también se conoció como calcular el tamaño de estas relaciones, haciendo un repaso de esto último se definieron los siguientes casos: -
Registros de longitud fija: Todos los registros ocupan el mismo número de bytes. Registros de longitud variable: cada registro puede tener una longitud diferente y existen delimitadores para indicar cuando comienza o termina un registro. Registros extendibles: un registro puede picarse y almacenarse en distintos bloques (si no cabe en el actual) Registros no extendibles: El registro debe ser almacenado completamente en un bloque.
Para determinar el número de bloques necesarios para almacenar un archivo, debemos conocer el número de registros del archivo, el tamaño de los registros y el tamaño de cada bloque de disco. 1. -
Registros No Extensibles / tamaño fijo N el número de registros del archivo A. Ra el tamaño en bytes de cada registro B Tamaño en bytes de cada bloque
El factor de bloqueo y el numero de bloques de un archivo se definen: ; 2. Extendibles / tamaño fijo En este caso no se puede definir un tamaño de bloqueo sino que definimos el número de bloques que ocupa el archivo
3. No Extensible / tamaño variable = tamaño promedio de un registro de A, estimado con técnicas de muestreo. y 4. Extensible / tamaño variable
Una vez que se conoce el tamaño de las relaciones se puede calcular el costo de ejecución de cada una de las operaciones del álgebra relacional.
Pag. 17
Procesamiento y Optimización de Consultas Los costos de las operaciones que se darán a continuación expresarán en número de accesos a disco, por lo que para tener el costo en tiempo se deberán multiplicar por D 4.3.3
4.3.3.1
Operación Selección
Selección sin índices
Considere una operación selección en una relación A cuyas tuplas se almacenan juntas en un archivo y BA es el tamaño que ocupa la relación en bloques de disco y D es el tiempo de acceso a disco.
Búsqueda lineal: Se explora cada bloque de la relación y se comprueban todos los registros para determinar si satisfacen o no la condición de selección Si la condición es sobre la clave ==> solo un registro cumple la condición Caso promedio: Costo = Si la condición no es sobre la clave Costo = BA
==> se debe recorrer todo el archivo
Búsqueda binaria: si el archivo está ordenado según un atributo clave y la condición de la selección es una igualdad sobre dicho atributo, se puede usar la búsqueda binaria, la cual se realiza sobre los bloques de disco. log2(BA) Si la selección no es de igualdad, o no es sobre un atributo clave (y el archivo está ordenado según este atributo), es posible que más de un bloque contenga los registros requeridos, si Bf en el numero de bloques que cumple la condición. Log2BA
4.3.3.2
+ (Bf-1)
Selección con índice
Las estructuras de índice se denominan caminos de acceso, ya que proporcionan un camino a través del cual se pueden localizar y acceder a los datos, se utilizará el predicado de la selección como clasificación de estos algoritmos. Se asumirá que los índices usados son los B+ y la longitud del camino de acceso es siempre la altura del árbol. En este material se asumirá que los índices usados son árboles B+, donde los valores necesarios para calcular el costo de explorar el árbol es la altura del árbol (h), el tipo (primario, secundario o agrupado), y si no es primario,la cantidad de bloques de datos apuntados por cada nodo hoja. Pag. 18
Procesamiento y Optimización de Consultas
índice B+
Archivo de datos
Selecc ión de igualdad
Índice primario: Se obtiene el número de niveles del índice + 1
Índice agrupado: Dado que s registros cumplirán la condición, siendo s la cardinalidad de selección del atributo de indexación Costo =
+ numero de niveles del índice
Índice secundario Al igual que el caso anterior s registros cumplen la condición de igualdad, sin embargo al no estar agrupado cada registro puede estar localizado en un bloque distinto, por lo tanto en el peor caso Costo = s + numero de niveles del árbol.
Selecc iones de comparac ión
Índice primario o agrupado Si la comparación es Atr > v o Atr ≥ v, se puede usar un índice primario o agrupado sobre el atributo Atr para obtener el (primer) valor de v en el archivo de datos, y de allí se explora hasta el final Si la comparación es Atr < v o Atr ≤ v no es necesario usar el índice.
Índice secundario Atr > v o Atr ≥ v Al estar el índice secundario ordenado (a nivel de hojas) solo es necesario hallar el primer apuntador a v y recorrer la lista formada por las hojas para obtener los aputadores a los diferentes bloques del archivo de datos. El costo son los mismos que en el caso anterior, lo que cambia es s.
Selecc iones comp lejas (con juntivas o dis yunt ivas ) Selección conjuntiva (cond1 AND cond2 … AND condn)
Utilizando un índice simple:
Pag. 19
Procesamiento y Optimización de Consultas Se verifica si hay un índice sobre alguno de los atributos, se hace la búsqueda sobre este y se verifica si se cumplen las demás condiciones. Es mas económico si el altributo que tiene el índice es el que tiene el fs mas bajo. Si hay un índice por cada atributo, se utilizan los distintos índices se recuperan los elementos y luego se hace una intersección de los tres conjuntos obtenidos.
Utilizando un índice compuesto Solo se puede usar, si cada uno de los atributos están en la condición de la selección, el tipo de índice determina el uso de los algoritmos de selecciones simples.
Selección disyuntiva Si se dispone de índices sobre cada uno de los atributos, se hace cada búsqueda y se realiza la unión de estas. Sin embargo el que un solo atributo no tenga índice implica una búsqueda lineal en el archivo de datos.
4.3.4
Operación ordenamiento
La ordenación es uno de los algoritmos principales usados en el procesamiento de consultas, por ejemplo si en la consulta SQL se especifica la clausula ORDER BY, o para algunas estrategias de ejecución del JOIN, la UNION o la INTERSECTION, o en el algoritmo de eliminación de duplicados en el PROJECT (cuando se especifica en la consulta SQL la opción DISTINCT. La ordenación se podría conseguir usando un índice de ordenación del atributo de búsqueda, y utilizar luego ese índice para leer la relación de manera ordenada, sin embargo con esto se logra solo se logra un ordenamiento lógico lo que es muy costoso debido a implica un acceso a disco para cada tupla,por esta razón es mas deseable ordenar las tuplas físicamente. Si la relación cabe completamente en memoria principal se pueden utilizar algoritmos de ordenación rápida (quick-sort). Costo = BA*Log(BA) Si no caben en memoria principal se usa el algoritmo de ordenación mezcla externa Si se tienen M bloques de memoria disponible, se lee el archivo en porciones de tamaño M bloques y se ordena cada unai=0 repeat leer M bloques de A; Ordenarlo en memoria; Escribir los datos en un archivo de secuencias Si; i = i + 1;} until fin de la relación A Pag. 20
Procesamiento y Optimización de Consultas
En la segunda etapa se mezclan los distintos archivos de secuencia, N será el numero de archivos de secuencia, si N End Ordenar B’ en base a los atributos de proyección For each tupla t in B’ Guardar t en B’’ sii no existe t en B’’ End Resultado tabla o relación donde los duplicados son eliminados Costo BB = #Bloques de B N = # bloques de B’ BB Leer B
+
N
escribi r B’
+ Ordena r B’
NlogN
+
2N
leer B’ y genera r B’’
Basado en Hash Se crea B’ For each tupla tj in B’ Aplicar f(tj) #se contruye una tabla hash en mp Si tupla tj en f(ti) / ti = tj Descartar ti Si no Guardar ti en f(ti) Fsi Retornar tuplas en tabla hash End Pag. 22
Procesamiento y Optimización de Consultas Costo Suposición B’’ en función de f se puede almacenar en memoria la tabla hash (memoria principal) BB + 2N Si no BB + 4N Aunque 4N es menor que 3N + NlogN requiere de memoria principal el cual es un recurso externo. Si no se eliminan duplicados el costo es 2*B B 4.3.6
Operación Reunión (Join)
La operación JOIN es una de las operaciones que más tiempo consumen durante el procesamiento de una consulta, en este caso nos estamos refiriendo al NATURAL JOIN o reunión natural, los algoritmos mas usados son:
Reunión de buc le anidado (NES TED LOOP JOIN) Dadas dos relaciones A,B, por cada tupla de A se lee cada tupla de B y se verifica que cum pla la condición del JOIN
For each tupla tA in A For each tupla tB in B If satisfy (tA, tB, Cond) Return (tA. tB) End End End La relación A se denomina la relación externa y la relación B la relación interna, t A.tB denota la tupla construida por la concatenación de los valores de los atributos de las tuplas t A y las tuplas tB Esta operación es muy costosa debido a que examina cada pareja de tuplas de las dos relaciones, para realizar el cálculo se debe considerar que la relación interna se lee secuencialmente por lo que solo necesita una exploración de A y un total de RA (numero de tuplas de A) exploraciones para leer B completamente, entonces: Si A ocupa BA bloques, B ocupa BB bloques y A tiene RA tuplas Costo = BA + RA*BB
Pag. 23
Procesamiento y Optimización de Consultas
Reunión de buc le anidado por bloques (BLOK NES TED LOOP JOIN) Se puede lograr un ahorro si se procesan las dos relaciones por bloques en lugar que por tuplas, en este algoritmo se empareja cada bloque de la relación interna, con cada bloque de la relación externa y por cada par de bloques se emparejan las tuplas de cada relación. Si solo se lleva un bloque a memoria por cada Relacion, el costo de este algoritmo sería Costo = BA + BA*BB Sin embargo se puede tener un ahorro mayor si se aprovechan todos los bloques de memoria intermedia disponibles, entonces si T es el tamaño de memoria intermedia disponible, se reservan 2 bloques para entrada y salida. Costo = BA +
x BB
Vemos que si A cabe completamente en memoria principal el costo es minimo. En ambos algoritmos de bucle anidado es más económico si la relación más pequeña está a la izquierda (relación externa)
Reunion de buc le anidado In dexa do Si se cuenta con un índice para la tabla interna
A
B
Costo = BA + RA*CostoBuscar(B, CondicionJoin)
Reunión de ordenación -mezcla (S OR T-M ERG E JOIN)
Ambas tablas están ordenadas (o se pueden ordenar) sobre los atributos del Join Costo Máximo (ordenar primero) MA . log MA + MB log MB Ordenar A Ordenar B + MA +MB => Costo Optimal Costo Mezclar
Pag. 24
Procesamiento y Optimización de Consultas
Reunión asoc iativa (HAS H JOIN) La idea de este algoritmo es dividir las tuplas de cada relación en conjuntos con el mismo valor usando una función h la cual asocia un valor (clave hash) a cada uno de los datos existentes en los atributos del join y se tiene que: h es una función de asociación que asigna a los atributos de Join los valores {0, 1, .., n}
HA0 … HAn denota las particiones de las tuplas de A, inicialmente vacias. Cada tupla t A se pode en la partición HA donde i = h (tA [Atributos Join]) HB0 .. HBn denotan las particiones de las tuplas de B, inicialmente vacias. Cada tupla de t B se pone en la partición HB donde i = h (tA [Atributos Join]) Como se aplica la misma función para construir ambos particionamientos, cada tupla de A y de B que tengan el mismo resultado en la función h estarán en una partición con el mismo número es decir
Fase de partición For each tA in A i = h (tA [Atributos Join]) HAi = HAi U tA End For each tB in B i = h (tB [Atributos Join]) HBi = HBi U tB End Fase de Carga For each Ha i #para cada partición de A For each tHA Є HAi # para cada tupla de la partición i de A f(tHA) y salvar en memoria # construir un índice asociativo sobre la partición A end for each tHB Є HAB # para cada tupla de la partición i de B explorar el índice asociativo de HAi y localizar todas las tuplas tales que satisface (c, tHA , tHB ) retornar (c, tHA , tHB ) end end Costo MA = # Bloques de A MB = # Bloques de B El costo es la suma del costo de partición y el costo de carga 2(MA + MB) + MA + MB = 3(MA + MB) fase carga fase prueba Pag. 25
Procesamiento y Optimización de Consultas
Cuadro Resumen del costo de las operacion es
Operación A ∞c B
Nested-loop Join MA + Ra x MB Block Nested-Loop Join MA +
ΠB1..Bi B
x MB
Costo de los operadores físicos Index Nested-Loop Join Sort-Merge Join MA + CostoBuscar(B) MA . log MA + MB log MB Ordenar A Ordenar B Hash Join 3(MA + MB) + MA +MB => Costo Optimal Costo Mezclar
Basado en ordenamiento MB + 3N + NlogN
Basado en hashing Si B’’ se puede almacenar en memoria la tabla hash MB + 2N Si no MB + 4N
σc B Depende la de la implementación física de B Ra = # tuplas de A MA = # bloques de A Rb = # tuplas de MB = # bloques de B T = # de Bloques disponibles en memoria principal. 4.3.7
Árbol de ejecución físico
Se denomina asi al árbol de evaluación lógico al que a los nodos internos se les asigna un operador físico y sus índices asociados
Pag. 26
Procesamiento y Optimización de Consultas
πNombre Sin Ordenar
BNLJ T=200
Indice 3 INLJ índice 2 Indice 1
Materia Cursa
Estudiante
4.4 Evaluación de expresiones Hasta ahora se han determinado los costos para llevar a cabo operaciones individuales ahora se considerará evaluar una expresión con varias operaciones. 4.4.1
Materialización
La manera evidente de evaluar una expresión es evaluar cada operación en un orden apropiado. Luego el resultado se materializa en una relación temporal para su utilización inmediata por el siguiente operador. El inconveniente de este método, es que estas materializaciones temporales (a menos que sean muy pequeñas) se tienen que escribir en disco. Para aplicar este enfoque se debe comenzar con las operaciones del nivel más bajo del árbol (las hojas), luego estas relaciones temporales serán la entrada para las operaciones del siguiente nivel del árbol. Se repite este proceso hasta que se llega a la raíz del árbol. 4.4.2
Encauzamiento (Pipeline)
Es un enfoque alternativo donde se evalúan varias operaciones de manera simultánea en un cauce, en el que se pasan los resultados de una operación a la siguiente operación de encauzamiento Permite mejorar la eficiencia de la evaluación de consultas mediante la reducción del número de archivos temporales que se producen.
Pag. 27
Procesamiento y Optimización de Consultas 4.4.3
Ejercicio de Ejemplo
Vamos a calcular los costos de diferentes planes de la siguiente consulta usando la estrategia de materialización Cursar CI
Cod_Mat
Nota
Cardinalidad: 10.000.000 tuplas
Semestre
-----------------------------------------------25 bytes
25 bytes
Estudiante CI
25 bytes
Nombre
25 bytes
Dirección
Telf
Correo
…..
-----------------------------------------------1.000 bytes Cardinalidad 10.000 tuplas Consulta Nombre de los estudiantes que aprobaron la materia 6311 en el Semestre 1-2009 Select Nombre From Estudiante E, Cursar C Where E.CI = C.CI and Nota >=10, and Cod_Mat = ‘6311’ and C.Semestre= ’1-2009’ Algebra Relacional Peor plan
Arbol de ejecución
Πnombre (ordenamiento)
σcondi ción
∞ (Block nested loop join) Estudiante
Cursar
Pag. 28
Procesamiento y Optimización de Consultas
Calculo de costo del plan Se asume: Registros de tamaño fijo y no extendibles para las relaciones Registros extendibles para resultados intermedios
Bloques de 1000 bytes Bloques disponibles en memoria principal 12
Cursar (caben 10 registros en cada bloque) (cursar necesita 1.000.000 bloques) Estudiante (cabe un registro en cada bloque) (Estudiante necesita 10.000 bloques) Costo del Join Costo (Sp0 )
1,0010E+09
Cardinalidad de la Salida (Sp0) Tamaño del registro 100 bytes de cursar + 1000 bytes de estudiante 25 bytes de CI (atributo común) 1075 bytes Cardinalidad 10.000.000 tuplas Costo de Guardar Spo (Resultado intermedio)
Costo del select Esta es una consulta sobre un resultado intermedio donde no hay orden, ni índices, se usa el enfoque de archivos secuenciales de montículo (Heap files). Costo (Sp1 ) = 10.750.000 bloques Costo Guardar (SP1 ) = 2 bloques (resultado de evaluar la consulta 1 registro) Costo del Project Costo (Sp2 ) = 2 + 1 + 1log1 + 1 = 4 Costo Guardar (Sp2 ) 1 bloque. Costo total =
= 1,0010E+09 + 1,075E+07 + 2 + 4 + 1 = 1,0118E+09 Pag. 29
Procesamiento y Optimización de Consultas
Plan 2 Πnombre (ordenamiento)
σcondi ción
∞ (Block nested loop join) Cursar
Estudiante
Todos los costos se mantienen menos el del join Costo (Sp0 ) =
1,00001E+09
Con lo que el costo total es 1,0108E+09 Por lo que podemos concluir que aunque el join es conmutativo, a nivel de costo, no lo es, y que resulta más económico tener la tabla más pequeña del lado izquierdo. Plan 3 Πnombre (ordenamiento)
∞ (Block nested loop join) Πnombre,carnet (ordenamiento)
σcondi ción
Estudiante
Cursar
Implementación de cursar: Cursar tiene un índice no clustered por trimestre y cod_mat, son 10 los estudiantes que cumplen estas dos condiciones. La altura del árbol es de 4 niveles y cada nodo interno ocupa un bloque. Costo de la selección Costo (Sp0 ) = 4 + 10 = 14 bloques Recorrer el arbol
data entry
Costo Guardar (SPo) = 1 bloque. Costo proyección 1 Necesitamos el número de bloques ocupado por B’ Pag. 30
Procesamiento y Optimización de Consultas Long del registro = 50 bytes Cardinalidad 10.000 tuplas (la misma de Estudiante) = 500 bloques Costo (Sp1 ) = 10000 + 500 + 500log500 +500 = 12849,485 Costo guardar (Sp1) = 500 bloques. Costo Join Costo (Sp2 )= Costo guardar (Sp2) = Costo proyección 2 Costo (Sp3 ) = 1 + 1 + 1log1 + 2 = 4 Costo guardar (Sp3) = 1 Costo total = 15 + 500 + 501 + 5 + 12849,485 = 1,3870E+04 Comparando con los otros dos planes el costo de este plan tiene 5 órdenes de magnitud menos.
Pag. 31
Procesamiento y Optimización de Consultas
5 Bibliografía Elmasri, R., & Navathe, S. (2007). Fundamentos de Sistemas de Bases de Datos (5ta ed.). Madrid, España: Pearson Educacion. Silberschatz, A., Korth, H., & Sudarshan, S. (2006). Fundamentos de bases de datos (Quinta ed.). Madrid: McGraw-Hill/Interamericana.
Pag. 32