Práctica de Optimización y Procesamiento de Consultas (Bases de Datos)
![]() |
Volver a la página de la materia |
Sumario
Ejercicio 01[editar]
Ejercicio 02[editar]
Ejercicio 03[editar]
Ejercicio 04[editar]
Ejercicio 05[editar]
Ejercicio 06[editar]
Ejercicio 07[editar]
Ejercicio 08[editar]
Ejercicio 09[editar]
Ejercicio 10[editar]
Ejercicio 11[editar]
Ejercicio 12[editar]
Ejercicio 13[editar]
Ejercicio 14[editar]
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..
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
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.
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
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!!!