abd procesamiento consultas
DESCRIPTION
Clases de procesamiento de consultas de Administracion de Base de datos UCVTRANSCRIPT
Administración de Base de Datos
Procesamiento y Optimización de Consultas
Prof Mercy Ospina Torres [email protected] Renny A. Hernandez
El DBA
Concurrencia
Diccionario Datos
Integridad
Seguridad
Proc. Consultas
Administración de Base de Datos 2
El SMBD
Manejo de Memoria
Restauración
Contenido
Marzo 2012
• Cómo se procesa una consulta• Traducir una consulta de SQL a AR
– Repaso Algebra Relacional
• Árbol de ejecución– Árbol de ejecución lógico– Árbol de ejecución lineal izquierdo– Árbol canónico– Axiomas del Algebra relacional
• Técnicas para optimizar consultas– Basada en heurísticas– Basada en costos.
Concurrencia
El DBA
Concurrencia
Diccionario Datos
Integridad
Seguridad
Proc. Consultas
Administración de Base de Datos 3
El SMBD
Manejo de Memoria
Restauración
Contenido
Marzo 2012
• Modelo de costos– Factor de selectividad– Costo de los operadores del Algebra Relacional
• Select• Project.• Join• Order• Árbol de ejecución físico
– Evaluar el árbol de ejecución físico.• Materialización• Encausamiento
Concurrencia
El DBA
Concurrencia
Diccionario Datos
Integridad
Seguridad
Proc. Consultas
Administración de Base de Datos 4
El SMBD
Manejo de Memoria
Restauración
Cómo procesar una consulta
Marzo 2012
SELECT Cuenta, Saldo FROM CuentaWHERE Saldo >40.000
Procesamiento de consulta
Consultas
El DBA
Concurrencia
Diccionario Datos
Integridad
Seguridad
Proc. Consultas
Administración de Base de Datos 5
El SMBD
Manejo de Memoria
Restauración
Cómo procesar una consulta
Marzo 2012
Consultas
Consulta de alto nivel
Analizador y
traductor
Expresión en Algebra Relacional
Resultado de la
consulta
Diccionario de datosOptimi-zador
Motor de evaluación
Plan de ejecución
Estadísticas de los datos
Select * From R1 Where Cond
Silberschatz, Korth, & Sudarshan, 2006
ρCond (R1)
Búsqueda binaria
Base de datos
A1 A2 A3
xx yy zz
xy yy xz
El DBA
Concurrencia
Diccionario Datos
Integridad
Seguridad
Proc. Consultas
Administración de Base de Datos 6
El SMBD
Manejo de Memoria
Restauración
Análisis
Marzo 2012
• 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.
Consultas
Consulta de alto nivel
Analizador y
traductor
Diccionario de datos
El DBA
Concurrencia
Diccionario Datos
Integridad
Seguridad
Proc. Consultas
Administración de Base de Datos 7
El SMBD
Manejo de Memoria
Restauración
Procesamiento de consulta
Marzo 2012
• Traductor: Crea una representación interna de la consulta, mediante una estructura de árbol llamado árbol de consulta, el cual está basado en el álgebra relacional extendido
Consultas
Consulta de alto nivel
Analizador y
traductor
Expresión en Algebra Relacional
Diccionario de datos
El DBA
Concurrencia
Diccionario Datos
Integridad
Seguridad
Proc. Consultas
Administración de Base de Datos 8
El SMBD
Manejo de Memoria
Restauración
Procesamiento de consulta
Marzo 2012
• Optimización: desarrolla una estrategia de ejecución para obtener el resultado de la consulta, evaluando cientos de estrategias distintas basadas en el álgebra relacional, y sus operadores físicos, escogiendo alguna de las estrategias menos costosa (plan de ejecución)
• Motor de ejecución: recibe el plan de evaluación, lo ejecuta y devuelve la respuesta de la consulta.
Consultas
Expresión en Algebra Relacional
Optimi-zador
Plan de ejecución
Estadísticas de los datos
Resultado de la
consulta
Motor de evaluación
Base de datos
El DBA
Concurrencia
Diccionario Datos
Integridad
Seguridad
Proc. Consultas
Administración de Base de Datos 9
El SMBD
Manejo de Memoria
Restauración
Algebra Relacional
Marzo 2012
Select <lista de atributos>
From <lista de tablas>
Where <condiciones>
Operadores del Algebra Relacional
Consultas
Lenguaje de consulta de alto nivel
Lenguaje de consulta de bajo nivel
• Proyección• Selección• Ordenación
• Unión• Intersección• Producto cartesiano• Reunión Natural• Resta• División
Unarios
Binarios
El DBA
Concurrencia
Diccionario Datos
Integridad
Seguridad
Proc. Consultas
Administración de Base de Datos 10
El SMBD
Manejo de Memoria
Restauración
Algebra Relacional
Marzo 2012
• PROYECCION– Define una vista que contiene un subconjunto vertical de R,
extrayendo los valores de los atributos especificados y eliminando los duplicados.
– Ejm:
Select <lista de atributos>
From <lista de tablas>
Where <condiciones>Consultas
CI Nombre Sueldo
123 Andrea Rojas 1500
234 Humberto Perez
2400
254 Camilo Diaz 1600
)(1 , EmpleadoT SueldoCI
El DBA
Concurrencia
Diccionario Datos
Integridad
Seguridad
Proc. Consultas
Administración de Base de Datos 11
El SMBD
Manejo de Memoria
Restauración
Algebra Relacional
Marzo 2012
• SELECCIÓN– Define una vista que contiene todas las tuplas de R que
satisfacen la condición especificada.– Ejm:
Select <lista de atributos>
From <lista de tablas>
Where <condiciones>
Consultas
CI Nombre Sueldo
123 Andrea Rojas 1500
234 Humberto Perez
2400
254 Camilo Diaz 1600
)(1 1500 EmpleadoT Sueldo
El DBA
Concurrencia
Diccionario Datos
Integridad
Seguridad
Proc. Consultas
Administración de Base de Datos 12
El SMBD
Manejo de Memoria
Restauración
Algebra Relacional
Marzo 2012
• PRODUCTO CARTESIANO– Define una relación que es la concatenación de cada tupla
de la relación R con cada tupla de la relación S.– R X S
Select <lista de atributos>
From <lista de tablas>
Where <condiciones>
Consultas
CI CodB
123 1
234 1
254 2
CodB Desc
1 Malta
2 7 up
R.CI R.CodB S.CodB Desc
123 1 1 Malta
234 1 1 Malta
254 2 1 Malta
123 1 2 7 up
234 1 2 7 up
254 2 2 7 up
El DBA
Concurrencia
Diccionario Datos
Integridad
Seguridad
Proc. Consultas
Administración de Base de Datos 13
El SMBD
Manejo de Memoria
Restauración
Algebra Relacional
Marzo 2012
• REUNION NATURAL (JOIN)– Es una combinación entre dos relaciones donde se verifica
la condición de igualdad sobre los atributos comunes entre ambas relaciones. Del resultado se elimina una de las dos apariciones de cada atributo
Select <lista de atributos>
From <lista de tablas>
Where <condiciones> andT1.a1=t2.a1 and ….
Consultas
CI CodB
123 1
234 1
254 2
CodB Desc
1 Malta
2 7 upR.CI R.CodB S.CodB Desc
123 1 1 Malta
234 1 1 Malta
254 2 1 Malta
123 1 2 7 up
234 1 2 7 up
254 2 2 7 up
El DBA
Concurrencia
Diccionario Datos
Integridad
Seguridad
Proc. Consultas
Administración de Base de Datos 14
El SMBD
Manejo de Memoria
Restauración
Algebra Relacional
Marzo 2012
• REUNION NATURAL (JOIN)– Es una combinación entre dos relaciones donde se verifica
la condición de igualdad sobre los atributos comunes entre ambas relaciones. Del resultado se elimina una de las dos apariciones de cada atributo
Select <lista de atributos>
From <lista de tablas>
Where <condiciones> andT1.a1=t2.a1 and ….
Consultas
CI CodB
123 1
234 1
254 2
CodB Desc
1 Malta
2 7 up
CI CodB Desc
123 1 Malta
234 1 Malta
254 2 7 up
El DBA
Concurrencia
Diccionario Datos
Integridad
Seguridad
Proc. Consultas
Administración de Base de Datos 15
El SMBD
Manejo de Memoria
Restauración
Árbol de ejecución
Marzo 2012
• Representa una consulta en algebra relacional
• Es un árbol de orden 2– Cada nodo interno representa una tabla vista o
resultado intermedio producido por una operación
– Cada hoja representa una tabla base
P1 y P2 sub arboles
Op operador AR
Consultas
Case Base
T
Case Inductivo
Op
P1 P2
Op
P1
- ,X ,, ,
O
El DBA
Concurrencia
Diccionario Datos
Integridad
Seguridad
Proc. Consultas
Administración de Base de Datos 16
El SMBD
Manejo de Memoria
Restauración
Árbol de ejecución
Marzo 2012
• EjemploΠ Apellido1, Nombre, Sueldo (σ Sueldo > c (Empleado
Departamento))
Consultas
EmpleadoDepartamento
Π Apellido1, Nombre,
Sueldo
σ Sueldo > c
T1 <-(Empleado Departamento)
Tr <- Π Apellido1, Nombre, Sueldo (T2)
T2 <- σ Sueldo > c (T1)
El DBA
Concurrencia
Diccionario Datos
Integridad
Seguridad
Proc. Consultas
Administración de Base de Datos
El SMBD
Manejo de Memoria
Restauración
Árbol lineal izquierdo
Marzo 2012
• Es un árbol de ejecución donde en cada nodo binario el hijo derecho es una tabla
• Arbol canónico: Es un árbol lineal izquierdo donde cada nodo binario corresponde a un producto cartesiano, la selección es sobre toda la condición y la proyección sobre todos los atributos
Nota: es el mas rápido deconstruir pero el más costoso
Consultas
SELECT <Lista Atributos>FROM T1, T2, … TnWHERE <Condición>
El DBA
Concurrencia
Diccionario Datos
Integridad
Seguridad
Proc. Consultas
Administración de Base de Datos
El SMBD
Manejo de Memoria
Restauración
Árbol lineal izquierdo
Marzo 2012
Ejercicios
Construya el árbol canónico de las sig. consultas
SELECT CI, Nombre, CodMateriaFROM Estudiante E, inscripcion IWHERE I.CodM = ‘6311’ and semestre=‘2-2011’ and E.CI =
I.CI
SELECT E.CI, E.Nombre, M.Nombre, I.semestreFROM Estudiante E, Inscripcion I, Materia MWHERE I.CodM = ‘6311’ and I.semestre=‘2-2011’ and E.CI =
I.CI and M.CodM = I.CodM Consultas
El DBA
Concurrencia
Diccionario Datos
Integridad
Seguridad
Proc. Consultas
Administración de Base de Datos
El SMBD
Manejo de Memoria
Restauración
Árbol lineal izquierdo
Marzo 2012
Próxima clase
• Transformación del árbol canónico (Axiomas del Algebra Relacional)
• Técnicas de optimización
• Factor de Selectividad
• Costos de los operadores
Consultas
El DBA
Concurrencia
Diccionario Datos
Integridad
Seguridad
Proc. Consultas
Administración de Base de Datos
El SMBD
Manejo de Memoria
Restauración
Axiomas del Algebra Relacional
Marzo 2012
1. Cascada de selecciones
Donde c1, c2, … cn son condiciones booleanas
Consultas
)...))((...()( 2121 RR cncccnand...andand cc
El DBA
Concurrencia
Diccionario Datos
Integridad
Seguridad
Proc. Consultas
Administración de Base de Datos
El SMBD
Manejo de Memoria
Restauración
Axiomas del Algebra Relacional
Marzo 2012
2. Conmutatividad de la selección
Consultas
))(())(( 1221 RR cccc
El DBA
Concurrencia
Diccionario Datos
Integridad
Seguridad
Proc. Consultas
Administración de Base de Datos
El SMBD
Manejo de Memoria
Restauración
Axiomas del Algebra Relacional
Marzo 2012
3. Cascada de proyecciones
Consultas
El DBA
Concurrencia
Diccionario Datos
Integridad
Seguridad
Proc. Consultas
Administración de Base de Datos
El SMBD
Manejo de Memoria
Restauración
Axiomas del Algebra Relacional
Marzo 2012
4. Distributividad de la proyección y la selección
Consultas
El DBA
Concurrencia
Diccionario Datos
Integridad
Seguridad
Proc. Consultas
Administración de Base de Datos
El SMBD
Manejo de Memoria
Restauración
Axiomas del Algebra Relacional
Marzo 2012
5. Conmutatividad del Join y del Producto cartesiano
Consultas
El DBA
Concurrencia
Diccionario Datos
Integridad
Seguridad
Proc. Consultas
Administración de Base de Datos
El SMBD
Manejo de Memoria
Restauración
Axiomas del Algebra Relacional
Marzo 2012
6. Distributividad de la selección con respecto al Join y al Producto cartesiano
Este axioma permite empujar las selecciones hacia abajo en el arbol.
Consultas
El DBA
Concurrencia
Diccionario Datos
Integridad
Seguridad
Proc. Consultas
Administración de Base de Datos
El SMBD
Manejo de Memoria
Restauración
Axiomas del Algebra Relacional
Marzo 2012
7. Distributividad de la proyección con respecto al Join y al Producto cartesiano
Este axioma permite empujar las proyecciones hacia abajo en el arbol.
Consultas
El DBA
Concurrencia
Diccionario Datos
Integridad
Seguridad
Proc. Consultas
Administración de Base de Datos
El SMBD
Manejo de Memoria
Restauración
Axiomas del Algebra Relacional
Marzo 2012
7. Distributividad de la proyección con respecto al Join y al Producto cartesiano
Este axioma permite empujar las proyecciones hacia abajo en el arbol.
Consultas
El DBA
Concurrencia
Diccionario Datos
Integridad
Seguridad
Proc. Consultas
Administración de Base de Datos
El SMBD
Manejo de Memoria
Restauración
Axiomas del Algebra Relacional
Marzo 2012
8. Conmutatividad de la unión y la intersección
9. Asociatividad de la union, la intersección, y el producto cartesiano
10. Distributividad de la selección con respecto a la Unión y la Intersección
11. Distributividad de la proyección con respecto a la Unión y la IntersecciónConsultas
El DBA
Concurrencia
Diccionario Datos
Integridad
Seguridad
Proc. Consultas
Administración de Base de Datos
El SMBD
Manejo de Memoria
Restauración
Axiomas del Algebra Relacional
Marzo 2012
12. Conversión del Producto Cartesiano en Join
Si cond es una igualdad de atributos de R1 y R2
Consultas
El DBA
Concurrencia
Diccionario Datos
Integridad
Seguridad
Proc. Consultas
Administración de Base de Datos
El SMBD
Manejo de Memoria
Restauración
Técnicas de optimización
Marzo 2012
Consultas
• Se refiere a las mejores prácticas• Viene de la experiencia de los expertos
Heurísticas
• Transforma el árbol de ejecución usando diferentes técnicas (n transformaciones)
• Estima los costos de cada transformación y se queda con la que tiene costo mínimo
Costo
El DBA
Concurrencia
Diccionario Datos
Integridad
Seguridad
Proc. Consultas
Administración de Base de Datos 31
El SMBD
Manejo de Memoria
Restauración
Técnicas de control de concurrencia
Marzo 2012
• Heurísticas– Se construye el árbol canónico– Se transforma usando los axiomas del AR en el
siguiente orden1. Aplicar el axioma o regla 12. Aplicar axiomas 2, 4, 6 y 10, para desplazar cada
operación SELECT hacia abajo en el árbol de ejecución.
3. Aplicar axiomas 5 y 9, 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.
El DBA
Concurrencia
Diccionario Datos
Integridad
Seguridad
Proc. Consultas
Administración de Base de Datos 32
El SMBD
Manejo de Memoria
Restauración
Técnicas de control de concurrencia
Marzo 2012
• Heurísticas (continuación)
3. Aplicar axiomas 5 y 9, para reordenar los nodos hoja utilizando el siguiente criterio: b) Verificar que las ordenaciones no produzcan productos
cartesianos que no puedan convertirse en JOIN
4. Aplicar axioma 12, para combinar 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.
El DBA
Concurrencia
Diccionario Datos
Integridad
Seguridad
Proc. Consultas
Administración de Base de Datos 33
El SMBD
Manejo de Memoria
Restauración
Técnicas de control de concurrencia
Marzo 2012
• Ejercicio– 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’
El DBA
Concurrencia
Diccionario Datos
Integridad
Seguridad
Proc. Consultas
Administración de Base de Datos 34
El SMBD
Manejo de Memoria
Restauración
Factor de selectividad
Marzo 2012
• Una vez que se ha construido el árbol de ejecución lógico se debe construir el físico
• Es una técnica de estimación del tamaño de los resultados intermedios o vistas (cantidad de registros), por medio de una función de probabilidad
• Se asume independencia y uniformidad en los valores de los atributos
• Se aplica para las selecciones y los join
El DBA
Concurrencia
Diccionario Datos
Integridad
Seguridad
Proc. Consultas
Administración de Base de Datos 35
El SMBD
Manejo de Memoria
Restauración
Factor de selectividad
Marzo 2012
• 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.
• Independencia – 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.
Se lee la probabilidad de que las tuplas
de Ti cumpla la condición Ai= c
El DBA
Concurrencia
Diccionario Datos
Integridad
Seguridad
Proc. Consultas
Administración de Base de Datos 36
El SMBD
Manejo de Memoria
Restauración
Factor de selectividad
Marzo 2012
• Casos Base
Los que cumplen la condición
Valores totales
El DBA
Concurrencia
Diccionario Datos
Integridad
Seguridad
Proc. Consultas
Administración de Base de Datos 37
El SMBD
Manejo de Memoria
Restauración
Marzo 2012
• Casos base– Factor de selectividad del Join
El DBA
Concurrencia
Diccionario Datos
Integridad
Seguridad
Proc. Consultas
Administración de Base de Datos 38
El SMBD
Manejo de Memoria
Restauración
Ejemplo del uso del fs
Marzo 2012
• Ejemplo– ¿Cuál es el factor de selectividad la condición
sexo = ‘F’ en la tabla empleado?
– Si la tabla empleados contiene 300.000 registros ¿cuántos registros tiene la siguiente vista?
)(1 '' EmpleadoT FSexo
5,02
1),''( EmpleadoFSexofs
000.1505,0000.3001
),''(1
T
EmpleadoFSexofsEmpleadoT
El DBA
Concurrencia
Diccionario Datos
Integridad
Seguridad
Proc. Consultas
Administración de Base de Datos 39
El SMBD
Manejo de Memoria
Restauración
Costo de un Árbol de ejecución
Marzo 2012
• Próxima clase– Costo de los Operadores físicos
• Join• Order by• Project• Select
– Evaluar el árbol de ejecución físico.• Materialización• Encausamiento
El DBA
Concurrencia
Diccionario Datos
Integridad
Seguridad
Proc. Consultas
Administración de Base de Datos 40
El SMBD
Manejo de Memoria
Restauración
Clase de hoy
Marzo 2012
– Modelo de costo– Costo de los operadores del Algebra Relacional
• Select• Project.• Order By
El DBA
Concurrencia
Diccionario Datos
Integridad
Seguridad
Proc. Consultas
Administración de Base de Datos 41
El SMBD
Manejo de Memoria
Restauración
Modelo de Costos
Marzo 2012
• Es una herramienta estadística formal para evaluar el costo de un plan físico de ejecución.
• Se mide en función del tiempo y puede expresarse en términos de:– Accesos a disco– Tiempo del CPU– Costo de comunicación (Sist. Dist)– Tiempo de respuesta para un plan de
evaluación de una consulta.
El DBA
Concurrencia
Diccionario Datos
Integridad
Seguridad
Proc. Consultas
Administración de Base de Datos 42
El SMBD
Manejo de Memoria
Restauración
Modelo de Costo
Marzo 2012
¿Cuál es el costo más importante en las bases de datos centralizadas?Acceso a disco
El DBA
Concurrencia
Diccionario Datos
Integridad
Seguridad
Proc. Consultas
Administración de Base de Datos 43
El SMBD
Manejo de Memoria
Restauración
Marzo 2012
• Para calcular el costo de acceso a disco necesitamos.– Tamaño a cada archivo de datos y vistas
• Número de registros• Tamaño de los atributos y los registros• Tamaño de los bloques
– Factor de selectividad• Número de valores distintos, • mínimo y máximo de los atributos de búsqueda,
– Métodos de acceso (organización del archivo)– Índices del archivo
• números de niveles (altura)• Tipo (primario, secundario, agrupado)
El DBA
Concurrencia
Diccionario Datos
Integridad
Seguridad
Proc. Consultas
Administración de Base de Datos 44
El SMBD
Manejo de Memoria
Restauración
Cálculo del espacio en disco requerido por una relación
Marzo 2012
1. Registros de longitud fija y no extensibleN: el número de registro del archivo ARa: el tamaño en bytes de cada registroB: Tamaño en bytes de cada bloque
aR
Bfdb
fdb
NANumBloques )(
Se usa para las tablas base
El DBA
Concurrencia
Diccionario Datos
Integridad
Seguridad
Proc. Consultas
Administración de Base de Datos 45
El SMBD
Manejo de Memoria
Restauración
Estimación de costos
Marzo 2012
2. Extensibles / Tamaño Fijo
B
RNANumBloques a)(
Se usa para las tablas vista o resultados intermedios
El DBA
Concurrencia
Diccionario Datos
Integridad
Seguridad
Proc. Consultas
Administración de Base de Datos 46
El SMBD
Manejo de Memoria
Restauración
Estimación de Costos
Marzo 2012
4. Tamaño variable se usan las mismas fórmulas pero se
calcula un promedio de tamaño del registro
muestreo. de ascon técnic
A, registroun de promedio tamañoAR
El DBA
Concurrencia
Diccionario Datos
Integridad
Seguridad
Proc. Consultas
Administración de Base de Datos 47
El SMBD
Manejo de Memoria
Restauración
Costo de operadores físicos
Marzo 2012
• Selección• Ordenamiento• Proyección• Reunión
El DBA
Concurrencia
Diccionario Datos
Integridad
Seguridad
Proc. Consultas
Administración de Base de Datos 48
El SMBD
Manejo de Memoria
Restauración
Estimación de costos en operaciones físicas: Selección
Marzo 2012
• Operación Selección
– Selección sin índices– Selección con índices– Selección de igualdad– Selección de comparación– Selecciones complejas (Conjuntivas o
Disyuntivas)
)(Rcondicion
El DBA
Concurrencia
Diccionario Datos
Integridad
Seguridad
Proc. Consultas
Administración de Base de Datos 49
El SMBD
Manejo de Memoria
Restauración
Selección sin índices
Marzo 2012
• Considere una operación selección sobre un archivo A y:
disco a acceso de tiempo:
disco de bloquesen
A relación la ocupa que tamaño:
D
TBA
El DBA
Concurrencia
Diccionario Datos
Integridad
Seguridad
Proc. Consultas
Administración de Base de Datos 50
El SMBD
Manejo de Memoria
Restauración
Selección sin índices
Marzo 2012
• Búsqueda lineal
A
A
TBCosto
TBCosto
:clave la sobre es nocondición la Si
2
El DBA
Concurrencia
Diccionario Datos
Integridad
Seguridad
Proc. Consultas
Administración de Base de Datos 51
El SMBD
Manejo de Memoria
Restauración
Selección sin índice
Marzo 2012
• Busqueda binaria– Si el archivo se ordena según el atributo clave
y la condición es una igualdad.
– Si la selección no es de igualdad, o no es sobre un atribudo clave (y el archivo está ordenado según éste atributo)
)(log2 ATBCosto
fs)con calculan (secondición lacon
cumplen que bloques de Número :
)1()(log2
f
fA
TB
TBTBCosto
El DBA
Concurrencia
Diccionario Datos
Integridad
Seguridad
Proc. Consultas
Administración de Base de Datos 52
El SMBD
Manejo de Memoria
Restauración
Selección con índices
Marzo 2012
• Asumimos que los índices son de tipo árbol B+ y la longitud del camino es siempre la altura del árbol.
El DBA
Concurrencia
Diccionario Datos
Integridad
Seguridad
Proc. Consultas
Administración de Base de Datos 53
El SMBD
Manejo de Memoria
Restauración
Selección de igualdad
Marzo 2012
• Índice primarioSe obtiene el número de niveles de índice + 1
• Índice agrupado
• Índice secundarioindexación de atributo del selección de adCardinalid:
),(
__cos
snrRcfss
indicedelnivelesfdb
sto
indicedelnivelessto __cos
El DBA
Concurrencia
Diccionario Datos
Integridad
Seguridad
Proc. Consultas
Administración de Base de Datos 54
El SMBD
Manejo de Memoria
Restauración
Selección de comparación
Marzo 2012
• Índice primario o agrupado– Si la comparación es Att > v o Att ≥ v se
puede obtener el primer valor de v en el archivo de datos, de allí se explora hasta el final
– Si la comparación Att < v o Att ≤ v no es necesario usar el índice.
• Índice secundario– Sólo es necesario hallar el primer apuntador a v
y recorrer la lista formada por las hojas para obtener los apuntadores a los diferentes bloques del archivo de datos.
El DBA
Concurrencia
Diccionario Datos
Integridad
Seguridad
Proc. Consultas
Administración de Base de Datos 55
El SMBD
Manejo de Memoria
Restauración
Selecciones complejas
Marzo 2012
• Conjuntivas (c1 and c2)- Índices Simples (índices diferentes por cada
atributo)- Se verifica si hay un índice sobre alguno de los
atributos, se busca sobre éste y se verifica si cumple las demás condiciones
- El más económico es el que tiene el fs más bajo
- Si hay un índice por cada atributo, se utilizan los distintos índices, se recuperan los elementos y luego se interceptan los tres conjuntos obtenidos.
El DBA
Concurrencia
Diccionario Datos
Integridad
Seguridad
Proc. Consultas
Administración de Base de Datos 56
El SMBD
Manejo de Memoria
Restauración
Selecciones Complejas
Marzo 2012
• Conjuntivas (Cont)• Índices Compuestos
• Sólo puede utilizarse si cada uno de los atributos están en la condición de selección
• El tipo de índice determina el uso de algoritmos de selección simples
• Disyuntiva– Se realiza una búsqueda y se realiza la unión
de éstas.– El hecho de que un sólo atributo no tenga
índice implica una búsqueda lineal de datos.
El DBA
Concurrencia
Diccionario Datos
Integridad
Seguridad
Proc. Consultas
Administración de Base de Datos 57
El SMBD
Manejo de Memoria
Restauración
Operación Proyección
Marzo 2012
• Con duplicados
For each tupla t in B Guardar en B’ < t.At1, t.At2, …, t.Ati > End Resultado tabla o relación con registros
duplicados
• Costo = TBB (recorrer la tabla B)
• Costo de resultado intermedio– TBB’ (guardar la tabla proyectada)
B
B’
El DBA
Concurrencia
Diccionario Datos
Integridad
Seguridad
Proc. Consultas
Administración de Base de Datos 58
El SMBD
Manejo de Memoria
Restauración
Operación Proyección
Marzo 2012
• Sin duplicados • Basado en ordenamiento
For each tupla t in B Guardar en B’ < t.At1, t.At2, …, t.Ati > 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
El DBA
Concurrencia
Diccionario Datos
Integridad
Seguridad
Proc. Consultas
Administración de Base de Datos 59
El SMBD
Manejo de Memoria
Restauración
Operación Proyección
Marzo 2012
• Costo de proyección
• Costo de almacenamiento
)log( ''' BBBB TBTBTBTB
Recorrer B
Generar B’
Ordenar B’
''BTB Tabla proyectada sin duplicados
El DBA
Concurrencia
Diccionario Datos
Integridad
Seguridad
Proc. Consultas
Administración de Base de Datos 60
El SMBD
Manejo de Memoria
Restauración
Operación Proyección
Marzo 2012
• Basado en HASHSe 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 sino
Guardar ti en f(ti) fsi Retornar tuplas en tabla hash
end
El DBA
Concurrencia
Diccionario Datos
Integridad
Seguridad
Proc. Consultas
Administración de Base de Datos 61
El SMBD
Manejo de Memoria
Restauración
Operación Proyección
Marzo 2012
• Basado en HASH (costo)– Suponiendo que
– se puede almacenar en la tabla hash
Sino
Aunque este costo puede ser menor que el de ordenamiento, requiere memoria principal
+ Costo de almacenar B’’
'
'
3 BB
BB
TBTB
TBTB
B
El DBA
Concurrencia
Diccionario Datos
Integridad
Seguridad
Proc. Consultas
Administración de Base de Datos 62
El SMBD
Manejo de Memoria
Restauración
Operación Join
Marzo 2012
• El operador Join se puede evaluar de varias maneras distintas– Nested loop join– Block Nested Loop Join– Merge sort join– Index Join– Hash Join
El DBA
Concurrencia
Diccionario Datos
Integridad
Seguridad
Proc. Consultas
Administración de Base de Datos 63
El SMBD
Manejo de Memoria
Restauración
Nested Loop Join
Marzo 2012
For each tupla tA in A For each tupla tB in B
If satisfy (tA, tB, Cond) Return (tA. tB)
End End
End
Costo = TBA + RA*TBB
RA = cantidad de registro de A
El DBA
Concurrencia
Diccionario Datos
Integridad
Seguridad
Proc. Consultas
Administración de Base de Datos 64
El SMBD
Manejo de Memoria
Restauración
Block Nested Loop Join
Marzo 2012
Este algorito se puede mejorar si se aprovechan los bloques de memoria disponibles
Si se carga A por bloques el costo seria
Costo = TBA + TBA*TBB
Si se tienen T bloques disponibles se dejan dos para entrada/salida
A B
BA
A *TBT-
TB TBCosto
2
El DBA
Concurrencia
Diccionario Datos
Integridad
Seguridad
Proc. Consultas
Administración de Base de Datos 65
El SMBD
Manejo de Memoria
Restauración
Sort-Merge Join
Marzo 2012
Si ambas tablas están ordenadas sobre los atributos del Join, el costo es el menor
Costo = TBA + TBB
Si no hay que agregar el costo de ordenación
Costo = TBA Log(TBA )+ TBB Log(TBB ) +TBA +TBB
A B
El DBA
Concurrencia
Diccionario Datos
Integridad
Seguridad
Proc. Consultas
Administración de Base de Datos 66
El SMBD
Manejo de Memoria
Restauración
Index Join
Marzo 2012
Se usa si la tabla de la derecha tiene un índice sobre el atributo del Join, el costo es el de leer A y buscar cada registro de A por el índice
Costo = TB(A) + CostoBuscar*Ra
El costo de buscar depende del indice (ver operador select)
A B
El DBA
Concurrencia
Diccionario Datos
Integridad
Seguridad
Proc. Consultas
Administración de Base de Datos 67
El SMBD
Manejo de Memoria
Restauración
Hash Join
Marzo 2012
• Se dividen las tuplas de cada relación utilizando una función hash tal que:
)()( .. ),(),(/, bababa ththeitBparttApartBtAt
El DBA
Concurrencia
Diccionario Datos
Integridad
Seguridad
Proc. Consultas
Administración de Base de Datos 68
El SMBD
Manejo de Memoria
Restauración
Hash Join
Marzo 2012
• h es una función que asigna a los atributos de join los valores {0,1,..,n-1}
• Ha0 .. Ha(n-1) denota las particiones de A inicialmente vacías. Se colocan las tuplas en Hai con i = h(ta[atributos join])
• Hb0 .. Hb(n-1) denota las particiones de B inicialmente vacías. Se colocan las tuplas en Hbi con i = h(tb[atributos join])
• Al aplicar la misma función para ambos particionamientos, cada tupla de A y B que tengan resultados iguales de la función de asociación, estarán en la misma partición
El DBA
Concurrencia
Diccionario Datos
Integridad
Seguridad
Proc. Consultas
Administración de Base de Datos 69
El SMBD
Manejo de Memoria
Restauración
Hash Join
Marzo 2012
El DBA
Concurrencia
Diccionario Datos
Integridad
Seguridad
Proc. Consultas
Administración de Base de Datos 70
El SMBD
Manejo de Memoria
Restauración
Video Join
Marzo 2012
• Videos– Video 1– Video 2
El DBA
Concurrencia
Diccionario Datos
Integridad
Seguridad
Proc. Consultas
Administración de Base de Datos 71
El SMBD
Manejo de Memoria
Restauración
Calcular el costo de un árbol de ejecución
Marzo 2012
• Una vez que el árbol este optimizado– Se cambian los operadores lógicos por físicos
p.e join por index join– Si hay mas de un operador posible se debe
verificar el menos costoso– Se calculan los costos de las operaciones por
nodo, y el costo de almacenar resultados intermedios
– Se suman los costos de todos los nodos
El DBA
Concurrencia
Diccionario Datos
Integridad
Seguridad
Proc. Consultas
Administración de Base de Datos 72
El SMBD
Manejo de Memoria
Restauración
Ejercicio
Marzo 2012
Jugador (DI, Nombre, Apellidos, FechaNac, Direccion)DI: 9 bytesNombre: 40 bytesApellidos: 40 bytesFechaNac: 8 bytesDireccion: 50 bytes
Num registros: 250.000
Equipo( CodEq, NombreEq, FechaFund, Ciudad, Liga, Estadio)CodEq: 4 bytesNombreEq: 40 bytesFechaFund: 8 bytesLiga: 2 bytes (Nacional =0, Americana=1)Estadio: 50 bytes
Num registros: 30
Juegos(CodEq1, CodEq2, Temporada, Fecha, Resultado, CodEquipoGana)CodEq1: 4 bytesCodEq2: 4 bytesTemporada: 4 bytes, min : 1902, máximo 2011, valores diferentes, 110Fecha: 8 bytes (162 valores distintos)Resultado: 8 bytesCodEquipoGana: 4 bytes (INDICE)
Num registros: 18.000
Juega (DIJugador, CodEq, FechaIni, FechaFin, Posicion)DIJugador: 9 bytesCodEq: 4 bytesFechaIni: 8 bytes (un promedio de 20 jug por año)FechaFin: 10 bytesPosición: 20 bytes (9 valores distintos)
Num registros: 875.000
El DBA
Concurrencia
Diccionario Datos
Integridad
Seguridad
Proc. Consultas
Administración de Base de Datos 73
El SMBD
Manejo de Memoria
Restauración
Marzo 2012
• Consulta: Nombre, apellido y equipo de los jugadores que han participado en la temporada 2009 en juegos ganados, y que han jugado en primera base.– Dé el árbol canónico para q. – Dé el árbol optimizado heurísticamente.
El DBA
Concurrencia
Diccionario Datos
Integridad
Seguridad
Proc. Consultas
Administración de Base de Datos 74
El SMBD
Manejo de Memoria
Restauración
Marzo 2012
• Suponga que el SMBD se caracteriza por– Disponer de 20 bloques de memoria principal
para las operaciones AR– Cada bloque ocupa 1024 bytes– Disponer de los operadores físicos vistos en
clase– Materializar los resultados intermedios. Asuma
registros fijos extensibles para las tablas intermedias y no extensibles para las relaciones base
– Indices primarios para las claves primarias, todos tienen 4 de altura
El DBA
Concurrencia
Diccionario Datos
Integridad
Seguridad
Proc. Consultas
Administración de Base de Datos 75
El SMBD
Manejo de Memoria
Restauración
Ejemplo de plan de ejecuciónCaso Oracle
Marzo 2012
SELECT e.employee_id, e.last_name, e.salary, d.department_name, l.cityFROM employees e, departments d, locations lWHERE e.department_id = d.department_id
AND d.location_id = l.location_idAND l.city = 'Oxford'AND e.salary > 10500 AND e.last_name LIKE '%e%';
El DBA
Concurrencia
Diccionario Datos
Integridad
Seguridad
Proc. Consultas
Administración de Base de Datos 76
El SMBD
Manejo de Memoria
Restauración
Marzo 2012