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

De Cuba-Wiki
Saltar a: navegación, buscar
Back.png Volver a la página de la materia

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

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