Lección 5.9: Algoritmos de Join — Cómo el Base de Datos Ejecuta Joins

En lecciones anteriores, escribimos joins en SQL y nos enfocamos en qué datos devuelven. Pero, ¿cómo ejecuta realmente el base de datos un join en su interior? Entender los algoritmos físicos que utiliza el motor es clave para escribir consultas que funcionen bien en conjuntos de datos grandes.

Los tres principales algoritmos de join son:

1. Nested Loop Join
2. Hash Join
3. Merge Join (también llamado Sort-Merge Join)

El planificador de consultas elige uno automáticamente en función del tamaño de las tablas, los índices disponibles y la memoria. No podemos forzar un algoritmo específico en SQL estándar, pero entender las compensaciones nos permite escribir consultas y crear índices que guíen al planificador hacia la mejor opción.

1. Nested Loop Join

Cómo Funciona

El Nested Loop Join es el algoritmo más simple. El base de datos selecciona una tabla como la tabla externa (controladora) y la otra como la tabla interna. Luego itera sobre cada fila en la tabla externa y, para cada fila, busca coincidencias en la tabla interna — esencialmente dos bucles for anidados.

Pseudo-código conceptual:

for each row R1 in outer_table:
    for each row R2 in inner_table:
        if R1.key = R2.key:
            output(R1, R2)

Cuando existe un índice en la columna de join de la tabla interna, el escaneo interno se convierte en una búsqueda rápida de índice en lugar de un escaneo completo de la tabla. Esta variante se llama Index Nested Loop Join y es uno de los caminos de ejecución más eficientes posibles.

Cuándo lo Usa el Planificador

• La tabla externa (controladora) es pequeña.
• Existe un índice en la columna de join de la tabla interna.
• El join utiliza una condición de no igualdad (<, >, BETWEEN) — Hash Join y Merge Join requieren igualdad, por lo que Nested Loop es la única opción en este caso.

Ventajas y Desventajas

2. Hash Join

Cómo Funciona

Un Hash Join funciona en dos fases:

1. Fase de construcción: El base de datos lee la tabla más pequeña y construye una tabla hash en memoria clave en la columna de join.
2. Fase de sondeo: El base de datos escanea la tabla más grande y, para cada fila, busca en la tabla hash para encontrar filas coincidentes.

Pseudo-código conceptual:

-- Fase de construcción
hash_table = {}
for each row R1 in smaller_table:
    hash_table[ hash(R1.key) ].append(R1)

-- Fase de sondeo
for each row R2 in larger_table:
    for each match in hash_table[ hash(R2.key) ]:
        if R2.key = match.key:
            output(R2, match)

Esto da una complejidad general de O(N + M) — lineal en ambos tamaños de tabla — lo que lo hace mucho más escalable que un Nested Loop Join sin índice.

Cuándo lo Usa el Planificador

• Uniendo dos tablas grandes en una condición de igualdad.
• No existe un índice útil en la(s) columna(s) de join.
• Hay suficiente memoria disponible para mantener la tabla hash (work_mem en PostgreSQL).

Ventajas y Desventajas

Nota: En PostgreSQL puedes controlar el presupuesto de memoria con la configuración work_mem. Aumentarlo reduce la posibilidad de volcamientos costosos en disco en grandes Hash Joins.

3. Merge Join (Sort-Merge Join)

Cómo Funciona

Un Merge Join requiere que ambas tablas de entrada estén ordenadas en la columna de join. Luego fusiona los dos flujos ordenados simultáneamente — muy parecido al paso final del clásico algoritmo Merge Sort — avanzando un puntero a través de cada flujo para encontrar coincidencias.

Pseudo-código conceptual:

sort outer_table by key   -- se omite si se usa un índice ordenado
sort inner_table by key   -- se omite si se usa un índice ordenado

p1 = inicio de outer_table
p2 = inicio de inner_table

while not end of either stream:
    if outer[p1].key = inner[p2].key:
        output matching rows and advance both pointers
    elif outer[p1].key < inner[p2].key:
        advance p1
    else:
        advance p2

La optimización crítica: si la tabla se puede escanear a través de un índice ordenado, el paso de ordenación es gratuito y Merge Join se convierte en uno de los algoritmos más eficientes disponibles.

Cuándo lo Usa el Planificador

• Ambas tablas son grandes y la condición de join es de igualdad.
• Ambas tablas ya están ordenadas, o ambas se pueden escanear a través de un índice ordenado.
• La consulta ya requiere ORDER BY o GROUP BY en la columna de join (la ordenación ocurre de todos modos).

Ventajas y Desventajas

4. Elegir el Algoritmo Correcto

El planificador de consultas elige el algoritmo automáticamente. Tú influyes en su decisión indirectamente creando los índices correctos y ajustando la configuración de memoria.

Consejos prácticos:

• Crea índices en columnas de clave foránea que se unan con frecuencia — esto permite joins rápidos de Index Nested Loop y Merge.
• Si un Hash Join se está volcando en disco, considera aumentar work_mem o revisar si la consulta puede ser reestructurada.
• Usa EXPLAIN ANALYZE para inspeccionar qué algoritmo eligió realmente el planificador y cuánto tiempo tomó cada paso:

EXPLAIN ANALYZE
SELECT a.first_name, a.last_name, f.title
FROM actor AS a
INNER JOIN film_actor AS fa ON a.actor_id = fa.actor_id
INNER JOIN film AS f ON fa.film_id = f.film_id;

Busca palabras clave como Hash Join, Merge Join o Nested Loop en el plan de salida para identificar el algoritmo elegido y su costo.

Conclusiones Clave de Esta Lección

• Nested Loop Join itera filas en bucles anidados — rápido para tablas pequeñas con índices de soporte, muy lento para tablas grandes sin índices; el único algoritmo que admite condiciones de no igualdad.
• Hash Join construye una tabla hash en memoria a partir de la tabla más pequeña y la sondea — eficiente para tablas grandes no indexadas unidas por igualdad, pero intensivo en memoria.
• Merge Join lee dos flujos preordenados simultáneamente — ideal cuando los datos ya están en orden (por ejemplo, a través de un índice) y el join es por igualdad; produce resultados en orden ordenado como un bono.
• Los tres algoritmos admiten joins de igualdad; solo Nested Loop también admite condiciones de rango.
• Tú influyes en la elección del planificador a través de índices, configuraciones de memoria (work_mem) y estructura de consulta — no especificando el algoritmo en SQL.
• Siempre usa EXPLAIN ANALYZE para verificar qué algoritmo se está utilizando realmente y dónde se está gastando el tiempo.