Práctica de Optimización y Procesamiento de Consultas (Bases de Datos)

Volver a la página de la materia

Ejercicio 14

Dado lo siguiente:

• Libros (ISBN, Titulo, tipo, precio)
• Ventas (cod_lib, nro_venta, fecha_venta, ISBN, C5, C6)
• Librerias(cod_lib, nombre_lib, telefono, dir_lib)

Todos los campos de todas las tablas tienen una longitud de 128 bytes. La longitud del bloque es de 2.048 bytes. La memoria disponible es de 3 bloques (M=3) para datos.

Las tablas contienen la siguiente cantidad de registros:

• Librerias: 200 registros.
• Libros: 2.000 registros.
• Ventas: 200.000 registros.

Se tiene un índice clustered sobre el campo cod_lib para la tabla Librerías. Se asume que:

• Los títulos de los libros no se repiten.
• El 50% de los registros corresponden a ventas desde el año 2.000.

Consulta : Las librerías que vendieron la publicación ‘Don Quijote de la Mancha’ desde el año 2.000.

SELECT  nombre_lib 
FROM  Libros L, Librerias R, Ventas V 
WHERE  L.ISBN = V.ISBN AND V.cod_lib = R.cod_lib AND  
       L.Titulo = ‘Don Quijote de la Mancha’ AND V.fecha_venta >= ‘01/01/2000’ 

Se pide: A partir del árbol optimizado, derivar dos planes de ejecución distintos, indicando, para cada uno de ellos el número de accesos a bloques que requieren. Justificar la elección de las estrategias, asumiendo que se intenta que ambas sean eficientes.

---

Respuesta

..

	Canonico	Optimizado
Arboles	p{nombre_lib} ' s(L.ISBN=V.ISBN & V.cod_lib=R.cod_lib & L.Titulo=.. & V.fecha_venta>=..) ' X / \ X V / \ L R	Siguiendo los pasos de optimizacion.. Descomponemos Llevamos selecciones a las hojas Permutamos (en este caso R y V) Fusionamos joins Agregamos proyecciones para restringir atributos p(nombre_lib) ' ►◄ (cod_lib) / \ p(cod_lib} ' ' R s(V.fec>=..) ' p(cod_lib,fec) ' ►◄(ISBN) / \ p{ISBN} V ' s{L.Tit=..} ' L
Planes de Ejec.	p(nombre_lib) '(PIPE) s(L.ISBN=V.ISBN & V.cod_lib=R.cod_lib & L.Titulo=.. & V.fecha_venta>=..) '(SCAN) X(BNLJ) / \ X(BNLJ)V / \ L R	p(nombre_lib) '(PIPE) ►◄ (cod_lib) (INLJ,I1) / \ p(cod_lib) ' '(PIPE) R s(V.fec>=..) '(SCAN) p(cod_lib,fec) '(PIPE) ►◄(ISBN) (BNLJ) / \ p(ISBN) V '(PIPE) s(L.Tit=..) '(FILESCAN) L

Cálculo de costos

Cálculo de datos generales

	Libros(L)	Librerías(R)	Ventas(V)	Res(Q)
L=#campos*tam_campo	128*4=512	128*6=768	128*4=512	128*1=128
FB=[tam_bloque/L]	[2048/512]=4	[2048/768]=2	[2048/512]=4	[2048/128]=16
T	2000	200	200000	(!)50
B=[T/FB]	[2000/4]=500	[200/2]=100	[200000/4]=50000	[50/16]=4

(!) Estimemos los registros devueltos. Para ello usaremos algunos cálculos auxiliares:

• Llamemos p al predicado de la selección. Podemos observar que p es de la forma ( pL^pV^pLV^pRV ), donde pX denota un predicado que afecta sólo a atributos de X, y pXY sólo a atributos de X e Y. Utilizando operaciones algebraicas podremos ver que s p(L X R X V)=[s pL(L) ►◄_pLV s pV(V)] ►◄_pRV R
• Calculemos por partes:
  • Sea Q1 = s pL(L); T(Q1)=T(L)/I(L,TITULO)=2000/2000=1
  • Sea Q2 = s pV(V); T(Q2)=sel(pV)*T(V)=0.5*200000=100000
  • Sea Q3 = Q1 ►◄_pLV Q2; Q3 = (T(Q1)*T(Q2)) / max(I(Q1,ISBN),I(Q2.ISBN)) = (1*100000) /max(1,2000) = 50
  • Ahora queda Q = Q3 ►◄_pRV R; T(Q) = (T(Q3)*T(R))/max(I(Q3,cod_lib),I(R,cod_lib)) {como Q3.cod_lib es FK -> I(R.codlib) >= I(Q3.cod_lib)} = (50*200)/200=50
• Veámoslo informalmente:
  • Usando que están distribuidos uniformemente, asumimos #ventas / #libros da la cantidad de ventas que corresponden a cada libro (por lo tanto, ‘Don Quijote de la Mancha’ tiene esa cantidad de ventas). Como se supone que la mitad de las ventas son desde el año 2000 (dato), la cantidad anterior la divido por 2. (#ventas/#libros) / 2 = (200.000 / 2.000) / 2 = 50

Calcularemos los costos sobre los dos planes de ejecución elegidos.

Costo del plan elegido sobre el árbol canónico

	Paso 1 (BNLJ)	Paso 2 (BNLJ)	Paso 3 (FSCAN+PIPE)
Sea	L’=LxR	L’’=L’xV	L’’’=p nom_lib (s…(L’’))
CI	B_L*(1+B_R)=500*(1+100)=50500	B_L’*(1+B_V)=400000*(1+50000)=2000400000	B_L’’=80000000000
L	128*(4+6)=1280	128 * (10+4) = 1792	128 * 1 = 128
FB	[2048/1280]=1	[2048/1792]=1	[2048/128]=16
T	2000*200=400000	400000*200000=80000000000	50 (valor que calculamos antes)
B	[400000/1]=400000	[80000000000/1]=80000000000	[50/16] = 4
CO	B_L’=400000	B_L’’=80000000000	4
CT	CI+CO=450500	CI+CO=82000400000	CI+CO=80000000000

Si sumamos los costos de todos los pasos obtenemos COSTO TOTAL = 162.000.850.504 accesos

Costo del plan elegido sobre el árbol optimizado

	Paso 1 (FSCAN+PIPE)	Paso 2 (BNLJ+PIPE)	Paso 3 (FSCAN+PIPE)	Paso 4 (INLJ+PIPE)
Sea	L’ = p ISBN(s…(L))	L’’=L’xV	L’’’=p cod_lib(s…(L’’))	L’’’’=L’’’xL
CI	B_L=500	B_L’*(1+B_V)=1*(1+50000)=50001	B_L’’=13	B_L’’’+T_L’’’(X_I1+1)=4+50(3+1)=204
L	128*1=128	128*2=256	128*1=128	128*1=128
FB	[2048/128]=16	[2048/256]=8	[2048/128]=16	[2048/128]=16
T	1	200000/2000=100	100/2=50	50
B	1	[100/8]=13	[50/16]=4	4
CO	B_L’=1	B_L’’=13	4	4
CT	CI+CO=501	CI+CO=50014	CI+CO=17	CI+CO=208

Si sumamos los costos de todos los pasos obtenemos COSTO TOTAL = 50740 accesos

Como vemos, el costo total del plan elegido del árbol canónico es más de 3 millones de veces más costoso que el del plan elegido del árbol optimizado. Para hacerlo más gráfico, si suponemos que tenemos capacidad para realizar 1 acceso a disco cada microsegundo, y que toda otra operación consume tiempo 0, la ejecución de la consulta con el plan elegido sobre el árbol optimizado tardaría 0.05 segundos, en tanto que con el plan elegido sobre el árbol canónico tardaría 45 horas!!!