abd procesamiento consultas (parte2)

Administración de Base de Datos

Procesamiento y Optimización de Consultas

Prof Mercy Ospina Torres [email protected] Renny A. Hernandez

[email protected]

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 (Visto)

• 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


• 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

En esta clase

Marzo 2012 Administración de Base de Datos

• 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

El SMBD

Manejo de Memoria

Restauración

RepasoClase pasada

• ¿Por qué se dice que SQL es un lenguaje de alto nivel?

• ¿Cuáles son los pasos que lleva a cabo el SMBD para procesar una consulta?

• ¿Qué es un árbol de ejecución?• ¿Qué es un árbol canónico?• ¿Cuál es la utilidad de los axiomas o

reglas del Algebra relacional?


Consultas

El DBA

Concurrencia

Diccionario Datos

Integridad

Seguridad

Proc. Consultas

El SMBD

Manejo de Memoria

Restauración

RepasoCómo procesar una consulta


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

Árbol lineal izquierdo


• 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 X, 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

Expresiones equivalentes


• Una expresión en un algebra es equivalente a otra, si el resultado es el mismo.

Consultas

El DBA

Concurrencia

Diccionario Datos

Integridad

Seguridad

Proc. Consultas

El SMBD

Manejo de Memoria

Restauración

Expresiones equivalente


• 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 del algebra de conjuntosConsultas

El DBA

Concurrencia

Diccionario Datos

Integridad

Seguridad

Proc. Consultas

El SMBD

Manejo de Memoria

Restauración

Axiomas del Algebra Relacional


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



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




Donde c1, c2, … cn son condiciones booleanas

Consultas

)...))((...()( 2121 RR cncccnand...andand cc

CI CodB

123 1

234 1

123 2

'123' 1 CIandcodB

CI CodB

123 1

234 1

CI CodB

123 1

1codB123CI

CI CodB

123 1

El DBA

Concurrencia

Diccionario Datos

Integridad

Seguridad

Proc. Consultas

El SMBD

Manejo de Memoria

Restauración




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



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



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



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


El DBA

Concurrencia

Diccionario Datos

Integridad

Seguridad

Proc. Consultas

El SMBD

Manejo de Memoria

Restauración




Consultas

∏A1

∏A1..An -1

∏A1..An

∏A1

El DBA

Concurrencia

Diccionario Datos

Integridad

Seguridad

Proc. Consultas

El SMBD

Manejo de Memoria

Restauración



Consultas

CI CodB

123 1

234 1

123 2

1codB CI CodB

123 1

234 1

CodB CodB

1

1


El DBA

Concurrencia

Diccionario Datos

Integridad

Seguridad

Proc. Consultas

El SMBD

Manejo de Memoria

Restauración



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


El DBA

Concurrencia

Diccionario Datos

Integridad

Seguridad

Proc. Consultas

El SMBD

Manejo de Memoria

Restauración



5. Conmutatividad del Join y del Producto cartesiano

ConsultasR1 R2 R2 R1

El DBA

Concurrencia

Diccionario Datos

Integridad

Seguridad

Proc. Consultas

El SMBD

Manejo de Memoria

Restauración



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

El SMBD

Manejo de Memoria

Restauración




Consultas

CI CodB

123 1

234 1

234 2

CodB Desc

1 Malta

2 7 up

CI CodB Desc

123 1 Malta

234 1 Malta

234 2 7 up

234CI and Malta''Desc CI CodB Desc

234 1 Malta==

El DBA

Concurrencia

Diccionario Datos

Integridad

Seguridad

Proc. Consultas

El SMBD

Manejo de Memoria

Restauración




Consultas

CI CodB

123 1

234 1

234 2

CodB Desc

1 Malta

2 7 up

´Malta´Desc

=

234CICI CodB

234 1

234 2

CodB Desc

1 Malta

CI CodB Desc

234 1 Malta

El DBA

Concurrencia

Diccionario Datos

Integridad

Seguridad

Proc. Consultas

El SMBD

Manejo de Memoria

Restauración



Consultas

R2 R1

σ c1 and

c2

R1 R2

σ c2

σ c1

R1 R2

σ c2 σ c1

El DBA

Concurrencia

Diccionario Datos

Integridad

Seguridad

Proc. Consultas

El SMBD

Manejo de Memoria

Restauración



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

El SMBD

Manejo de Memoria

Restauración




Consultas

CI CodB Fecha

123 1 10/08/2013

234 1 12/06/2013

234 2 25/10/2013

CodB Desc Vol

1 Malta 500

2 7 up 1500

CI CodB

Fecha Desc Vol

123 1 10/08/2013

Malta 500

234 1 12/06/2013

Malta 500

234 2 25/10/2013

7 up 1500

El DBA

Concurrencia

Diccionario Datos

Integridad

Seguridad

Proc. Consultas

El SMBD

Manejo de Memoria

Restauración




Consultas

CI CodB

Fecha Desc Vol

123 1 10/08/2013

Malta 500

234 1 12/06/2013

Malta 500

234 2 25/10/2013

7 up 1500

DescCodBCI ,,CI CodB Desc

123 1 Malta

234 1 Malta

234 2 7 up

El DBA

Concurrencia

Diccionario Datos

Integridad

Seguridad

Proc. Consultas

El SMBD

Manejo de Memoria

Restauración




Consultas

CI CodB Fecha

123 1 10/08/2013

234 1 12/06/2013

234 2 25/10/2013

CodB Desc Vol

1 Malta 500

2 7 up 1500

CodBCI ,

DescCodB, CodB Desc

1 Malta

2 7 up

CI CodB

123 1

234 1

234 2

El DBA

Concurrencia

Diccionario Datos

Integridad

Seguridad

Proc. Consultas

El SMBD

Manejo de Memoria

Restauración




Consultas

CodB Desc

1 Malta

2 7 up

CI CodB

123 1

234 1

234 2

CI CodB Desc

123 1 Malta

234 1 Malta

234 2 7 up

El DBA

Concurrencia

Diccionario Datos

Integridad

Seguridad

Proc. Consultas

El SMBD

Manejo de Memoria

Restauración



Consultas

R2 R1

∏A1..An

R1 R2

∏B∏A

El DBA

Concurrencia

Diccionario Datos

Integridad

Seguridad

Proc. Consultas

El SMBD

Manejo de Memoria

Restauración



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

Consultas

El DBA

Concurrencia

Diccionario Datos

Integridad

Seguridad

Proc. Consultas

El SMBD

Manejo de Memoria

Restauración



12. Conversión del Producto Cartesiano en Join

Si cond es una igualdad de atributos de R1 y R2

ConsultasX

R2 R1

σ A1=A2

R2 R1

El DBA

Concurrencia

Diccionario Datos

Integridad

Seguridad

Proc. Consultas

El SMBD

Manejo de Memoria

Restauración

Técnicas de optimización


Consultas

El DBA

Concurrencia

Diccionario Datos

Integridad

Seguridad

Proc. Consultas

El SMBD

Manejo de Memoria

Restauración

Técnicas de control de concurrencia


• 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

El SMBD

Manejo de Memoria

Restauración



• 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

El SMBD

Manejo de Memoria

Restauración



• Heurísticas (Resumen)

1. Aplicar Axioma 12. Aplicar axiomas 2, 4, 6 y 103. Aplicar axiomas 5 y 9, 4. Aplicar axioma 12, 5. Aplicar axiomas 3, 4, 7, 11.

El DBA

Concurrencia

Diccionario Datos

Integridad

Seguridad

Proc. Consultas

El SMBD

Manejo de Memoria

Restauración

Optimización por Heurística


Ejemplo

Realice la optimización heurística de la sig. consulta

SELECT CI, Nombre, CodMateriaFROM Estudiante E, inscripcion IWHERE I.CodM = ‘6311’ and E.ciudad=‘Caracas’ and E.CI =

I.CI

Consultas

El DBA

Concurrencia

Diccionario Datos

Integridad

Seguridad

Proc. Consultas

El SMBD

Manejo de Memoria

Restauración

Ejercicio 1


SELECT CI, Nombre, CodMateriaFROM Estudiante E, inscripcion IWHERE I.CodM = ‘6311’ and E.ciudad=‘caracas’ and E.CI = I.CI

Paso 1: Construir el Arbol canónico

Consultas

E I

X

I.CI E.CI and Caracas’‘.E and ‘6311’ I.CodM

ciudad

CodMateriaNombreCI ,,

El DBA

Concurrencia

Diccionario Datos

Integridad

Seguridad

Proc. Consultas

El SMBD

Manejo de Memoria

Restauración

Paso 2: Transformar el Árbol canónico

Axioma 1:: Cascada de selecciones

Ejercicio 1


Consultas

E I

X

I.CI E.CI and Caracas’'E.ciudad and ‘6311’ I.CodM


E I

X

I.CI E.CI


‘6311’ I.CodM

Caracas’‘E.ciudad

El DBA

Concurrencia

Diccionario Datos

Integridad

Seguridad

Proc. Consultas

El SMBD

Manejo de Memoria

Restauración


Axiomas 2, 4, 6, 10

Ejercicio 1


Consultas

E I

X

I.CI E.CI


‘6311’ I.CodM


E I

X

I.CI E.CI CodMateriaNombreCI ,,

‘6311’ I.CodM


El DBA

Concurrencia

Diccionario Datos

Integridad

Seguridad

Proc. Consultas

El SMBD

Manejo de Memoria

Restauración


Axiomas 5 y 9 (Conmutatividad del PC, Join)

Ejercicio 1


Consultas

E I

X


‘6311’ I.CodM Caracas’‘E.ciudad

Ver cual de los resultados intermedios es mas pequeño y colocarlo a la izquierda

El DBA

Concurrencia

Diccionario Datos

Integridad

Seguridad

Proc. Consultas

El SMBD

Manejo de Memoria

Restauración


Axioma 12 (PC => Join)

Ejercicio 1


Consultas

E I

X



E I

I.CI E.CI



El DBA

Concurrencia

Diccionario Datos

Integridad

Seguridad

Proc. Consultas

El SMBD

Manejo de Memoria

Restauración


Axioma 3, 4, 7, 11 (proyecciones)

Ejercicio 1


Consultas

E I

I.CI E.CI



Se evalúa si las tablas base tienen muchos

atributos que no aportan a la consulta

Se debe tomar en cuenta que los

resultados intermedios no tienen

índices

El DBA

Concurrencia

Diccionario Datos

Integridad

Seguridad

Proc. Consultas

El SMBD

Manejo de Memoria

Restauración



Ejercicio 1


Consultas

E I

I.CI E.CI


Ciudad Nombre,CI,CodM

E I

I.CI E.CI

CodMNombre,CI,

‘6311’ I.CodM ‘Juan’E.nombre

CodMNombre,CI,

El DBA

Concurrencia

Diccionario Datos

Integridad

Seguridad

Proc. Consultas

El SMBD

Manejo de Memoria

Restauración

Optimización con heurística


• 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

El SMBD

Manejo de Memoria

Restauración

Árbol de ejecución físico


• Una vez que se ha construido el árbol de ejecución lógico se debe construir el físico

• Consiste en determinar los operadores físicos asociados a cada nodo– Ejemplo: Selección con índice o búsqueda

lineal

• Para seleccionar los operadores necesitamos conocer el tamaño de los resultados intermedios

El DBA

Concurrencia

Diccionario Datos

Integridad

Seguridad

Proc. Consultas

El SMBD

Manejo de Memoria

Restauración

Factor de selectividad


• 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

El SMBD

Manejo de Memoria

Restauración



• 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.

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

El SMBD

Manejo de Memoria

Restauración



• 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.

El DBA

Concurrencia

Diccionario Datos

Integridad

Seguridad

Proc. Consultas

El SMBD

Manejo de Memoria

Restauración



• Casos Base

• Ejemplo– ¿Cuál es el factor de selectividad la condición sexo = ‘F’

en la tabla empleado?

5,02

1),''( EmpleadoFSexofs

El DBA

Concurrencia

Diccionario Datos

Integridad

Seguridad

Proc. Consultas

El SMBD

Manejo de Memoria

Restauración



• Casos Base

• Ejemplo– ¿Cuál es el factor de selectividad la condición Cantidad

> 100 en la tabla Venta? Si Min 5 y Max 250

Los que cumplen la condición

Valores totales

61,0246

150

15250

100250),100(

Ventascantidadfs

El DBA

Concurrencia

Diccionario Datos

Integridad

Seguridad

Proc. Consultas

El SMBD

Manejo de Memoria

Restauración



• Casos Base

• Ejemplo– ¿Cuál es el factor de selectividad la condición Cantidad > 100 y

Región = Norte en la tabla Venta V? Si Min 5 y Max 250 y solo hay 4 regiones

15,04

1*61,0),''(Re*),100( VNortegionfsVcantidadfs

El DBA

Concurrencia

Diccionario Datos

Integridad

Seguridad

Proc. Consultas

El SMBD

Manejo de Memoria

Restauración


• Casos base– Factor de selectividad del Join

CI CodB

123 1

234 1

234 2

CodB Desc Vol

1 Malta 500

2 7 up 1500

Valores distintos (CodB) = 2

Valores distintos (CodB) = 2

5,02

1

)2,2max(

1)..( CodBVCodBCfs

El DBA

Concurrencia

Diccionario Datos

Integridad

Seguridad

Proc. Consultas

El SMBD

Manejo de Memoria

Restauración

Ejemplo del uso del fs


• 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

El SMBD

Manejo de Memoria

Restauración



Ejercicio 1


Consultas

E I

I.CI E.CI

CodMNombre,CI,


Calcular cual resultado intermedio es menor si hay 5000 estudiantes y 30 ciudades distintas y 25.000 inscripciones y son 100 materias distintas

El DBA

Concurrencia

Diccionario Datos

Integridad

Seguridad

Proc. Consultas

El SMBD

Manejo de Memoria

Restauración

Ejemplo del uso del fs


• Resultado

30

1),''( EstudianteCaracasCiudadfs

redondea) (se 16730

1000.51

),''(1

T

EstudianteCaracasciudadfsEstudianeT

100

1),'6311'( InscribeCodMfs

250100

1000.251

),'6311'(1

T

InscribeCodMfsInscribeT

El DBA

Concurrencia

Diccionario Datos

Integridad

Seguridad

Proc. Consultas

El SMBD

Manejo de Memoria

Restauración

Costo de un Árbol de ejecución


• Próxima clase– Costo de los Operadores físicos

• Select• Join• Order by• Project• Select

– Evaluar el árbol de ejecución físico.• Materialización• Encausamiento

– Repasar costo de ordenamiento

abd procesamiento consultas (parte2)

Education