abd procesamiento consultas (parte1)
DESCRIPTION
Presentacion de la clase de procesamiento de consultas de la materia Administracion de Base de datos - Computacion - 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
El SMBD
Manejo de Memoria
Restauración
Contenido
Marzo 2012 Administración de Base de Datos 2
• 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
El SMBD
Manejo de Memoria
Restauración
Contenido
Marzo 2012 Administración de Base de Datos 3
• 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
El SMBD
Manejo de Memoria
Restauración
Introducción
• Una de las funciones más importantes de los sistemas de Base de datos en la consulta.
• Los SMBD relacionales usan como lenguaje de consulta SQL
• Para tener mayor control de la respuesta de una consulta del DBA debe conocer que hay detrás de esa instrucción en SQL
Marzo 2012 Administración de Base de Datos 4
Consultas
El DBA
Concurrencia
Diccionario Datos
Integridad
Seguridad
Proc. Consultas
El SMBD
Manejo de Memoria
Restauración
Conocimientos previos
• Para el manejo conocimientos de este tema el estudiante debe tener conocimientos de:– Lenguajes de consulta SQL y Algebra Relacional– Manejo de memoria en los SMBD– Diccionario de datos– Complejidad algorítmica– Probabilidad
Marzo 2012 Administración de Base de Datos 5
Consultas
El DBA
Concurrencia
Diccionario Datos
Integridad
Seguridad
Proc. Consultas
El SMBD
Manejo de Memoria
Restauración
Objetivos o competencias
• Al finalizar el tema el estudiante debe ser capaz de:– Traducir una consulta en SQL a una expresión
del Algebra Relacional– Conocer que factores influyen en el
rendimiento de una consulta– Conocer la importancia del diccionario de datos
en el procesamiento de consultas– Optimizar una consulta usando técnicas
heurísticas – Calcular el costo de una consulta– Conocer las utilidades del sistema manejador
para consultas
Marzo 2012 Administración de Base de Datos 6
Consultas
El DBA
Concurrencia
Diccionario Datos
Integridad
Seguridad
Proc. Consultas
El SMBD
Manejo de Memoria
Restauración
Cómo procesar una consulta
Marzo 2012 Administración de Base de Datos 7
SELECT Cuenta, Saldo FROM CuentaWHERE Saldo >40.000
Procesamiento de consulta
Procesamiento de consulta
Consultas
El DBA
Concurrencia
Diccionario Datos
Integridad
Seguridad
Proc. Consultas
El SMBD
Manejo de Memoria
Restauración
Cómo procesar una consulta
Marzo 2012 Administración de Base de Datos 8
Consultas
Consulta de alto nivel
Consulta de alto nivel
Analizador y
traductor
Analizador y
traductor
Expresión en Algebra Relacional
Expresión en Algebra Relacional
Resultado de la
consulta
Resultado de la
consulta
Diccionario de datosOptimi-zador
Optimi-zador
Motor de evaluaciónMotor de
evaluaciónPlan de
ejecuciónPlan de
ejecución
Estadísticas de los datos
Select * From R1 Where Cond
Select * From R1 Where Cond
Silberschatz, Korth, & Sudarshan, 2006
ρCond (R1)ρCond (R1)
Búsqueda binaria
Búsqueda binaria
Base de datos
A1 A2 A3
xx yy zz
xy yy xz
El DBA
Concurrencia
Diccionario Datos
Integridad
Seguridad
Proc. Consultas
El SMBD
Manejo de Memoria
Restauración
Análisis
Marzo 2012 Administración de Base de Datos 9
• 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
Consulta de alto nivel
Analizador y
traductor
Analizador y
traductor
Diccionario de datos
El DBA
Concurrencia
Diccionario Datos
Integridad
Seguridad
Proc. Consultas
El SMBD
Manejo de Memoria
Restauración
Procesamiento de consulta
Marzo 2012 Administración de Base de Datos 10
• 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
Consulta de alto nivel
Analizador y
traductor
Analizador y
traductor
Expresión en Algebra Relacional
Expresión en Algebra Relacional
Diccionario de datos
El DBA
Concurrencia
Diccionario Datos
Integridad
Seguridad
Proc. Consultas
El SMBD
Manejo de Memoria
Restauración
Procesamiento de consulta
Marzo 2012 Administración de Base de Datos 11
• 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)
Consultas
Expresión en Algebra Relacional
Expresión en Algebra Relacional
Optimi-zador
Optimi-zador
Plan de ejecuciónPlan de
ejecución
Estadísticas de los datos
Resultado de la
consulta
Resultado de la
consulta
Motor de evaluaciónMotor de
evaluación
Base de datos
El DBA
Concurrencia
Diccionario Datos
Integridad
Seguridad
Proc. Consultas
El SMBD
Manejo de Memoria
Restauración
Procesamiento de consulta
Marzo 2012 Administración de Base de Datos 12
• 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
Expresión en Algebra Relacional
Optimi-zador
Optimi-zador
Plan de ejecuciónPlan de
ejecución
Estadísticas de los datos
Resultado de la
consulta
Resultado de la
consulta
Motor de evaluaciónMotor de
evaluación
Base de datos
El DBA
Concurrencia
Diccionario Datos
Integridad
Seguridad
Proc. Consultas
El SMBD
Manejo de Memoria
Restauración
Algebra Relacional
Marzo 2012 Administración de Base de Datos 13
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
El SMBD
Manejo de Memoria
Restauración
Algebra Relacional
Marzo 2012 Administración de Base de Datos 14
• PROYECCION– Define una vista que contiene un subconjunto vertical de R,
extrayendo los valores de los atributos especificados y eliminando los duplicados.
– Ejm:
Consultas
)(1 , EmpleadoT SueldoCI
El DBA
Concurrencia
Diccionario Datos
Integridad
Seguridad
Proc. Consultas
El SMBD
Manejo de Memoria
Restauración
Algebra Relacional
Marzo 2012 Administración de Base de Datos 15
• 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
El SMBD
Manejo de Memoria
Restauración
Algebra Relacional
Marzo 2012 Administración de Base de Datos 16
• 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
El SMBD
Manejo de Memoria
Restauración
Algebra Relacional
Marzo 2012 Administración de Base de Datos 17
• 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
El DBA
Concurrencia
Diccionario Datos
Integridad
Seguridad
Proc. Consultas
El SMBD
Manejo de Memoria
Restauración
Algebra Relacional
Marzo 2012 Administración de Base de Datos 18
• 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
El SMBD
Manejo de Memoria
Restauración
Algebra Relacional
Marzo 2012 Administración de Base de Datos 19
• 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
El SMBD
Manejo de Memoria
Restauración
Algebra Relacional
Marzo 2012 Administración de Base de Datos 20
• 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
El SMBD
Manejo de Memoria
Restauración
Árbol de ejecución
Marzo 2012 Administración de Base de Datos 21
• 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
El SMBD
Manejo de Memoria
Restauración
Árbol de ejecución
Marzo 2012 Administración de Base de Datos 22
• EjemploΠ Apellido1, Nombre, Sueldo (σ Sueldo > c (Empleado
Departamento))
Consultas
EmpleadoDepartamento
T1 <-(Empleado Departamento)
Ejecutamos de adentro hacia
afuera
El DBA
Concurrencia
Diccionario Datos
Integridad
Seguridad
Proc. Consultas
El SMBD
Manejo de Memoria
Restauración
Árbol de ejecución
Marzo 2012 Administración de Base de Datos 23
• EjemploΠ Apellido1, Nombre, Sueldo (σ Sueldo > c (Empleado
Departamento))
Consultas
EmpleadoDepartamento
σ Sueldo > c
T1 <-(Empleado Departamento)
T2 <- σ Sueldo > c (T1)
El DBA
Concurrencia
Diccionario Datos
Integridad
Seguridad
Proc. Consultas
El SMBD
Manejo de Memoria
Restauración
Árbol de ejecución
Marzo 2012 Administración de Base de Datos 24
• 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
El SMBD
Manejo de Memoria
Restauración
Árbol lineal izquierdo
Marzo 2012 Administración de Base de Datos
• 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
El DBA
Concurrencia
Diccionario Datos
Integridad
Seguridad
Proc. Consultas
El SMBD
Manejo de Memoria
Restauración
Árbol lineal izquierdo
Marzo 2012 Administración de Base de Datos
• 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
El SMBD
Manejo de Memoria
Restauración
Árbol lineal izquierdo
Marzo 2012 Administración de Base de Datos
• 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
El SMBD
Manejo de Memoria
Restauración
Árbol lineal izquierdo
Marzo 2012 Administración de Base de Datos
• 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
El SMBD
Manejo de Memoria
Restauración
Árbol lineal izquierdo
Marzo 2012 Administración de Base de Datos
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
El SMBD
Manejo de Memoria
Restauración
Ejercicio 1
Marzo 2012 Administración de Base de Datos 30
SELECT CI, Nombre, CodMateriaFROM Estudiante E, inscripcion IWHERE I.CodM = ‘6311’ and semestre=‘2-2011’ and E.CI = I.CI
Consultas
El DBA
Concurrencia
Diccionario Datos
Integridad
Seguridad
Proc. Consultas
El SMBD
Manejo de Memoria
Restauración
Ejercicio 2
Marzo 2012 Administración de Base de Datos 31
• Tarea, envíenla por correo
Consultas
El DBA
Concurrencia
Diccionario Datos
Integridad
Seguridad
Proc. Consultas
El SMBD
Manejo de Memoria
Restauración
Expresiones equivalente
Marzo 2012 Administración de Base de Datos
• Una expresión del AR es equivalente a otra, si el resultado es el mismo.
• Sin embargo una expresión equivalente puede ser mas eficiente que otra en tiempo de respuesta.
• Para hallar expresiones equivalentes se usan reglas o axiomas, los cuales vienen de la teoría de conjuntosConsultas
El DBA
Concurrencia
Diccionario Datos
Integridad
Seguridad
Proc. Consultas
El SMBD
Manejo de Memoria
Restauración
Axiomas del Algebra Relacional
Marzo 2012 Administración de Base de Datos
1. Cascada de selecciones
2. Conmutatividad de la selección
3. Cascada de proyecciones
4. Distributividad de la proyección y la selección
5. Conmutatividad del Join y el Producto Cartesiano
6. Distributividad de la selección con respecto al Join y al producto cartesiano
7. Distributividad de la proyección con respecto al Join y al producto cartesiano
Consultas
El DBA
Concurrencia
Diccionario Datos
Integridad
Seguridad
Proc. Consultas
El SMBD
Manejo de Memoria
Restauración
Axiomas del Algebra Relacional
Marzo 2012 Administración de Base de Datos
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ón
12. Conversión del Producto Cartesiano en JoinConsultas
El DBA
Concurrencia
Diccionario Datos
Integridad
Seguridad
Proc. Consultas
El SMBD
Manejo de Memoria
Restauración
Axiomas del Algebra Relacional
Marzo 2012 Administración de Base de Datos
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
El SMBD
Manejo de Memoria
Restauración
Axiomas del Algebra Relacional
Marzo 2012 Administración de Base de Datos
1. Cascada de selecciones
Donde c1, c2, … cn son condiciones booleanas
Consultas
)...))((...()( 2121 RR cncccnand...andand cc
σ c1 and c2
and c3 σ c3
σ c2
σ c1
El DBA
Concurrencia
Diccionario Datos
Integridad
Seguridad
Proc. Consultas
El SMBD
Manejo de Memoria
Restauración
Axiomas del Algebra Relacional
Marzo 2012 Administración de Base de Datos
Consultas
))(())(( 1221 RR cccc
CI CodB
123 1
234 1
123 2
1codBCI CodB
123 1
234 1
123CICI CodB
123 1
1codBCI CodB
123 1
123 2
123CICI CodB
123 1
El DBA
Concurrencia
Diccionario Datos
Integridad
Seguridad
Proc. Consultas
El SMBD
Manejo de Memoria
Restauración
Axiomas del Algebra Relacional
Marzo 2012 Administración de Base de Datos
2. Conmutatividad de la selección
Consultas
))(())(( 1221 RR cccc
σ c2
σ c1
σ c1
σ c2
El DBA
Concurrencia
Diccionario Datos
Integridad
Seguridad
Proc. Consultas
El SMBD
Manejo de Memoria
Restauración
Axiomas del Algebra Relacional
Marzo 2012 Administración de Base de Datos
Consultas
CI CodB Desc
123 1 Malta
234 1 Malta
254 2 7 up
CodBCI ,
CI CodB
123 1
234 1
254 2
CI
123
234
254
CI
3. Cascada de proyecciones
El DBA
Concurrencia
Diccionario Datos
Integridad
Seguridad
Proc. Consultas
El SMBD
Manejo de Memoria
Restauración
Axiomas del Algebra Relacional
Marzo 2012 Administración de Base de Datos
3. Cascada de proyecciones
Consultas
∏A1
∏A1..An -1
∏A1..An
∏A1
El DBA
Concurrencia
Diccionario Datos
Integridad
Seguridad
Proc. Consultas
El SMBD
Manejo de Memoria
Restauración
Axiomas del Algebra Relacional
Marzo 2012 Administración de Base de Datos
Consultas
CI CodB
123 1
234 1
123 2
4. Distributividad de la proyección y la selección
El DBA
Concurrencia
Diccionario Datos
Integridad
Seguridad
Proc. Consultas
El SMBD
Manejo de Memoria
Restauración
Axiomas del Algebra Relacional
Marzo 2012 Administración de Base de Datos
Consultas
CI CodB
123 1
234 1
123 2
1codB CI CodB
123 1
234 1
CodB CodB
1
1
4. Distributividad de la proyección y la selección
El DBA
Concurrencia
Diccionario Datos
Integridad
Seguridad
Proc. Consultas
El SMBD
Manejo de Memoria
Restauración
Axiomas del Algebra Relacional
Marzo 2012 Administración de Base de Datos
Consultas
CI CodB
123 1
234 1
123 2
1codB CI CodB
123 1
234 1
CodB
1codB
CodB
1
1
CodB CodB
1
1
CodB
1
1
2
4. Distributividad de la proyección y la selección
El DBA
Concurrencia
Diccionario Datos
Integridad
Seguridad
Proc. Consultas
El SMBD
Manejo de Memoria
Restauración
Axiomas del Algebra Relacional
Marzo 2012 Administración de Base de Datos
4. Distributividad de la proyección y la selección
Consultas
∏A1..An
σ c
σ c
∏A1..An
El DBA
Concurrencia
Diccionario Datos
Integridad
Seguridad
Proc. Consultas
El SMBD
Manejo de Memoria
Restauración
Próxima clase
Marzo 2012 Administración de Base de Datos
Próxima clase
• Transformación del árbol canónico (Axiomas del Algebra Relacional) Continuación
• Técnicas de optimización
• Factor de Selectividad
• Costos de los operadores
Consultas