Optimización del Rendimiento de Consultas: Cálculo de Costes I/O en Algoritmos de Join

Cálculo de Costes I/O en Algoritmos de Join

A continuación, se detallan los cálculos de coste de entrada/salida (I/O) para diferentes algoritmos de unión (Join) en bases de datos, considerando las características específicas de las relaciones R1 y R2.

1. Merge Join (Join por Fusión)

El Merge Join requiere que ambas relaciones estén ordenadas por el atributo de unión. Dado que la relación R1 ya está ordenada, solo es necesario ordenar R2.

Fase de Ordenación (R2)

La ordenación se lleva a cabo en 2 fases, donde cada fase implica una lectura y una posterior escritura de la relación:

• Coste de Ordenación de R2: 2 lecturas de R2 + 2 escrituras de R2
• Cálculo: $4 \times B(R2) = 4 \times 100$ bloques de R2 = 400 operaciones I/O

Fase de Fusión (Merge)

La operación de fusión implica únicamente la lectura secuencial de ambas tablas:

• Lectura de R1 + Lectura de R2
• Cálculo: 600 bloques de R1 + 100 bloques de R2 = 700 bloques de I/O

Coste Total del Merge Join

TOTAL = Coste de Ordenación + Coste de Join = $400 + 700$ = 1100 operaciones de I/O

2. Index Join (Join por Índice)

En el Index Join, la relación que actúa como externa en el bucle es aquella que no posee el índice, es decir, R2. Se asume que R1 tiene un índice sobre el atributo de unión C.

Cálculo de la Selectividad (K)

Estimamos el número promedio de filas de R1 (K) que se recuperan por cada valor de C:

$K = T(R1) / V(R1, C) = 3000 / 15 = 200 ext{ filas}$

Cálculo del Coste I/O

El coste total se compone de la lectura de la relación externa (R2) y el coste de acceso a R1 a través del índice por cada fila de R2.

• Coste de lectura de R2: 6000 operaciones de I/O (asumiendo que este valor representa el coste de acceso a las filas de R2).
• Coste de acceso a R1: $T(R2) \times K$ (asumiendo que K representa el coste de I/O por fila de R2).
• Cálculo Total: $6000 ext{ I/O} + (6000 ext{ filas de R2} \times 200 ext{ accesos a R1})$
• TOTAL: $6000 + 1,200,000 = 1,206,000 ext{ operaciones I/O}$

3. Hash Join (Join por Hashing)

El algoritmo de Hash Join requiere una fase inicial de partición (creación de *buckets*) y una fase posterior de unión (*probe*).

Fase de Partición (Creación de Buckets)

Durante este proceso, cada tabla se lee por completo y se escribe dividida en distintos *buckets*. El coste asociado es 2 veces el número de bloques de cada tabla (asumiendo $B(R1)=1000$ y $B(R2)=800$ para este caso):

• Coste R1: $2 \times 1000 = 2000 ext{ I/O}$
• Coste R2: $2 \times 800 = 1600 ext{ I/O}$
• Coste Total de Partición: $2000 ext{ I/O} + 1600 ext{ I/O} = 3600 ext{ I/O}$

Fase de Unión (Probe)

Una vez creados los *buckets*, se leen las dos tablas completas para llevar a cabo la operación de JOIN.

• Lectura de R1: 1000 I/O
• Lectura de R2: 800 I/O
• Coste Total de Unión: $1000 ext{ I/O} + 800 ext{ I/O} = 1800 ext{ I/O}$

Coste Total del Hash Join

Coste Final = Coste de Partición + Coste de Unión

TOTAL: $3600 ext{ I/O} + 1800 ext{ I/O} = 5400 ext{ I/O}$

4. Nested Loop Join (NLJ)

El Nested Loop Join es un algoritmo cuya eficiencia varía drásticamente según la elección de la relación externa y la disponibilidad de memoria.

Caso 4.1: Block Nested Loop Join (BNLJ) con Optimización de Memoria

Se aprovecha la memoria disponible ($M = 300$ bloques) para cargar la relación externa (R1) en paquetes, minimizando las lecturas repetidas de la relación interna (R2).

300 bloques de memoria para R1 equivalen a 1800 filas de R1 por paquete.

Cálculo de Paquetes y Coste I/O

Para acceder a 1800 filas de R1, se requieren $1800 / 3 = 600$ accesos a bloque (asumiendo 3 filas por bloque en este contexto):

• Coste de carga de R1: $2 ext{ paquetes} \times 600 ext{ operaciones de I/O/paquete} = 1200 ext{ operaciones de I/O}$

El coste total se calcula considerando los pases necesarios y la lectura de ambas relaciones:

Cálculo Total: $2 \times (600 ext{ bloques de R1} + 7200 ext{ bloques de R2})$

TOTAL: $2 \times 7800 = 15,600 ext{ operaciones I/O}$

Caso 5.1: NLJ Básico (Uso Mínimo de Memoria)

Se utiliza solo un bloque para cargar filas de R1 y un bloque para R2. Los bloques totales son $B(R1) = 1200$ y $B(R2) = 7200$.

Opción 5.1.1: R1 como relación externa

Por cada fila de R1, se accede a la tabla R2 de manera completa (asumiendo $T(R1) = 3600$ filas):

Coste: $B(R1) + (T(R1) \times B(R2))$

Cálculo: $1200 + (3600 \times 7200) = 25,921,200 ext{ accesos a bloque}$

Opción 5.1.2: R2 como relación externa

Por cada fila de R2, se accede a la tabla R1 de manera completa (asumiendo $T(R2) = 7200$ filas):

Coste: $B(R2) + (T(R2) \times B(R1))$

Cálculo: $7200 + (7200 \times 1200) = 8,647,200 ext{ accesos a bloque}$

TOTAL: $1200 \times 7201 = 8,647,200 ext{ accesos a bloque}$