1. Costo de clasificación:
* Algoritmo: Por lo general, las bases de datos utilizan un tipo de fusión externa. Esto se debe a que las relaciones que se unen a menudo son demasiado grandes para caber en la memoria.
* Costo de E/S (factor dominante):
* El tipo de fusión externa implica múltiples pases a través de los datos.
* Número de pases: El número de pases depende del tamaño de las relaciones y la cantidad de memoria disponible (el "búfer"). Digamos que tenemos:
* `B` =número de bloques (páginas) en la relación.
* `M` =Número de bloques de memoria disponibles (tamaño del búfer).
* El número de pases es aproximadamente `log_m (b)` o un poco más que esto si desea ser extremadamente preciso.
* Costo de E/S por pase: Cada pase lee y escribe toda la relación, por lo que cuesta operaciones de `2b` I/O (B para leer y B para escribir).
* Costo total de E/S para clasificar: `2b * Número de pases =2b * log_m (b)`. Con más detalle, el costo de clasificación para cada relación `R` y` S` es:
* Sort (r) =2 * `b (r)` * log m (`B (r)`) (donde `b (r)` es el número de bloques para la relación r)
* Sort (s) =2 * `b (s)` * log m (`B (s)`) (donde `b (s)` es el número de bloques para las relaciones s)
* Costo de CPU: Si bien la clasificación está principalmente limitada por E/S, hay un costo de CPU asociado con la comparación de tuplas, fusionar corridas clasificadas, etc. Este costo generalmente es más bajo que el costo de E/S y a menudo se ignora en modelos de costos simplificados.
2. Costo de fusión:
* Costo de I/o: Después de que se clasifican las relaciones, la fase de fusión requiere leer cada bloque de ambas relaciones ordenadas una vez.
* `B (R) + B (S)` (donde `B (R)` y `B (S)` son el número de bloques para las relaciones R y S, respectivamente)
* Costo de CPU: El costo de la CPU de comparar tuplas durante la fase de fusión es relativamente pequeño en comparación con los costos de clasificación y E/S.
Costo total:
El costo total de la unión de la fama de clasificación es aproximadamente la suma de los costos de clasificación y el costo de fusión:
Costo ≈ 2 * b (r) * log m (B (r)) + 2 * b (s) * log m (B (s)) + b (r) + b (s)
Costo simplificado (aproximación común):
Si el costo de clasificación domina (que generalmente es el caso), una aproximación simplificada es:
Costo ≈ 2 * b (r) * log m (B (r)) + 2 * b (s) * log m (B (s))
Consideraciones importantes:
* memoria (m): La cantidad de memoria disponible afecta significativamente el número de pases requeridos para la clasificación. Más memoria significa menos pases y menor costo.
* Datos prefresionados: Si cualquiera de las relaciones ya * ya * se clasifica en la tecla de unión, puede omitir el paso de clasificación para esa relación. Esto reduce drásticamente el costo. El costo se convierte en el costo de clasificar solo la relación sin clasificar más el costo de fusión.
* Duplicados: Si las claves de unión contienen duplicados, la fase de fusión puede ser más compleja, lo que puede requerir E/S y CPU adicionales. La fórmula supone que el manejo duplicado se incorpora dentro de cada lectura de un bloque.
* Tamaño del bloque: El tamaño del bloque (tamaño de la página) afecta el número de bloques en una relación.
* Modelo de costos: La fórmula exacta utilizada para la estimación de costos varía entre los sistemas de bases de datos. Algunos pueden incluir el costo de la CPU de manera más explícita, tiempos de búsqueda de disco, etc. Este es un modelo simplificado para comprender los costos relativos.
* hash Join vs. Sort-Merge Join: En muchos casos, el hash unión es más eficiente que la unión de la fusión, especialmente cuando una de las relaciones se ajusta completamente en la memoria. Sin embargo, Sort-Merge Join puede ser más eficiente cuando los datos ya están ordenados, o cuando los datos no dividen uniformemente.
* Enfoques híbridos: Algunas bases de datos utilizan enfoques híbridos que combinan aspectos de la unión hash y la unión de la mérima.
* Rendimiento real: Estos son costos teóricos. El rendimiento real puede verse afectado por factores como el rendimiento de E/S del disco, la velocidad de la CPU, la concurrencia y el ajuste de la base de datos.
Ejemplo:
Digamos:
* `B (r) =1000` bloques
* `B (s) =500` bloques
* `M =100` bloques de memoria
Entonces:
* Log 100 (1000) ≈ 1.5
* Log 100 (500) ≈ 1.35
Costo estimado ≈ 2 * 1000 * 1.5 + 2 * 500 * 1.35 + 1000 + 500
≈ 3000 + 1350 + 1500
≈ 5850 Operaciones de E/S.
Esto es solo una estimación, y el costo real en un sistema de base de datos real podría ser diferente. La comparación relativa es que el costo de clasificación es más alto que el costo de fusión.
En resumen, el costo de la unión de la fusión está dominado por el costo de E/S de clasificar las relaciones. El número de pases requeridos para la clasificación depende del tamaño de las relaciones y la cantidad de memoria disponible. Reducir el tamaño de las relaciones (por ejemplo, a través del filtrado o proyección) o aumentar la memoria disponible puede mejorar significativamente el rendimiento.