Algoritmos de JOIN: Nested Loop, Hash y Merge

Ya conoce INNER JOIN como sintaxis. En una entrevista para un puesto sénior, le preguntarán cómo la base de datos ejecuta físicamente un join. Hay tres algoritmos:

• Nested Loop Join
• Hash Join
• Merge Join (sort-merge)

El tipo lógico de join (INNER, LEFT) es independiente del algoritmo. El planificador elige el algoritmo según el tamaño de las tablas, los índices y el ordenamiento. Saber cuándo conviene cada uno es el objetivo central de esta lección.

Nested Loop es el algoritmo más sencillo: para cada fila de la tabla externa, busca coincidencias en la tabla interna. En pseudocódigo, son dos bucles, uno dentro del otro.

De forma ingenua, su complejidad es O(outer * inner), lo que resulta terrible con tablas grandes. Sin embargo, se vuelve excelente cuando el lado interno tiene un índice sobre la clave del join: cada fila externa activa una búsqueda rápida en el índice en lugar de un escaneo completo de la tabla interna.

Es el algoritmo favorito del planificador cuando la tabla externa es pequeña y la columna de join interna está indexada.

La señal inequívoca de un bucle anidado es el valor de loops en el nodo interno. El ejemplo muestra loops=3 porque el lado externo produjo 3 filas, por lo que el escaneo del índice interno se ejecutó 3 veces.

El problema aparece cuando el lado externo es grande. Si produce 2 millones de filas, el lado interno se ejecuta 2 millones de veces. Incluso una búsqueda rápida de 0.01ms se convierte en 20 segundos.

En una entrevista, señale cualquier nested loop cuyo valor de loops sea alto sobre una tabla interna sin un buen índice: esa es la consulta lenta.

Hash Join funciona bien con tablas grandes sin ordenar. Se ejecuta en dos fases:

• Build: lee la tabla más pequeña y la carga en una tabla hash en memoria, usando la columna de join como clave.
• Probe: recorre la tabla más grande; para cada fila, calcula el hash de la clave de join y la busca en la tabla hash.

Cada tabla se lee una sola vez, lo que da aproximadamente O(outer + inner). No necesita índices ni entradas ordenadas, por eso suele imponerse en joins analíticos grandes con condiciones de igualdad.

Hay dos aspectos que debe mencionar sobre los hash joins:

• Solo funcionan con condiciones de join de igualdad (a.id = b.id). Una condición de rango como a.x < b.y no puede usar un hash join.
• El lado de build debe caber en work_mem. Si no cabe, Postgres vuelca lotes al disco (verá Batches: > 1 y uso de disco), lo que ralentiza mucho el join.

Por tanto, un hash join con un lado de build enorme y un valor diminuto de work_mem es un problema de rendimiento real que debe señalar.

Merge Join (sort-merge) requiere que ambas entradas estén ordenadas según la clave de join. Después recorre ambas al mismo tiempo, como al combinar dos listas ordenadas, avanzando el puntero que va más atrasado.

Es eficiente cuando las entradas ya están ordenadas, por ejemplo, cuando provienen directamente de un índice en el orden de la clave, porque así no hace falta un paso de ordenamiento. También admite joins por rango y por desigualdad, a diferencia de hash join.

Si las entradas no están ordenadas de antemano, el planificador añade nodos Sort explícitos, y el coste de ordenar puede hacer que hash join sea más barato.

Memorice en qué casos conviene cada algoritmo:

• Nested Loop, cuando la tabla externa es pequeña y la clave de join interna está indexada; también es la única opción para joins que no son de igualdad y no tienen entradas ordenadas.
• Hash Join, cuando se unen tablas grandes sin ordenar mediante una condición de igualdad; no necesita índices.
• Merge Join, cuando ambas entradas ya están ordenadas según la clave (a menudo mediante índices), o para joins por rango; es excelente con conjuntos muy grandes y previamente ordenados.

El planificador estima el coste de cada opción y elige la más barata según sus estimaciones de filas.

El uso de recursos varía mucho, y es un aspecto que los entrevistadores suelen explorar:

• Nested Loop, usa muy poca memoria; su coste está dominado por las búsquedas internas repetidas.
• Hash Join, necesita memoria para la tabla hash; si es demasiado grande, vuelca datos al disco.
• Merge Join, es barato al combinar las entradas, pero costoso si primero debe ordenarlas; los ordenamientos también usan work_mem y pueden desbordarse al disco.

Por eso, aumentar work_mem puede convertir un hash o un ordenamiento lento que usa el disco en uno que se ejecuta en memoria: es una respuesta de optimización concreta.

Escenario clásico: una consulta era rápida en desarrollo y lenta en producción. El plan muestra un Nested Loop con loops=3000000.

El planificador subestimó el número de filas externas (las estadísticas desactualizadas indicaban 3 filas, pero en realidad eran 3 millones), así que eligió un nested loop. Con estadísticas precisas habría elegido un hash join.

Su respuesta en la entrevista: ejecute ANALYZE para corregir la estimación; entonces el planificador cambiará a un hash join y la consulta se acelerará considerablemente.

Por lo general, no debería forzar los algoritmos, pero puede hacerlo durante las pruebas para compararlos. Postgres ofrece interruptores para cada método:

SET enable_nestloop = off; y equivalentes para enable_hashjoin y enable_mergejoin. Desactive uno, vuelva a ejecutar EXPLAIN ANALYZE y observe si la alternativa es realmente más rápida.

Las soluciones adecuadas siguen siendo: estadísticas actualizadas, los índices correctos, suficiente work_mem y predicados selectivos. Forzar un algoritmo solo sirve para diagnosticar.

Aplíquelo a una carga de trabajo analítica que une dos tablas grandes de hechos y dimensiones mediante un id:

• Si la dimensión cabe en memoria, espere un Hash Join, que suele ser la mejor opción.
• Si ambas tablas llegan ordenadas desde índices, un Merge Join puede evitar la construcción de la tabla hash.
• Un Nested Loop en este caso sería una señal de alarma y normalmente se debería a una estimación incorrecta.

Leer qué algoritmo eligió el planificador y juzgar si debió elegirlo es exactamente lo que estas preguntas evalúan en un perfil sénior.

Une dos tablas grandes sin ordenar mediante una condición de igualdad a.id = b.id; ninguna tiene un índice útil y las estadísticas son precisas. ¿Qué algoritmo de join elegirá probablemente el planificador?

Los tres algoritmos de join:

• Nested Loop, multiplica las filas externas por las búsquedas internas; es excelente con una tabla externa pequeña y una clave interna indexada, pero peligroso cuando loops es enorme.
• Hash Join, construye y consulta una tabla hash; es la mejor opción para joins grandes sin ordenar y con condiciones de igualdad, pero se limita a la igualdad y está condicionado por work_mem.
• Merge Join, recorre entradas ordenadas al mismo tiempo; es ideal cuando los datos ya están ordenados o para joins por rango.

El planificador elige según el coste y las estadísticas. Un nested loop sorprendente con un número enorme de bucles casi siempre indica una estimación incorrecta de filas: corrija las estadísticas.