Algoritmos de unión y orden de unión

El dataset de este artículo — perf_sales y employee

Cuando unes dos tablas, la base de datos elige un algoritmo de unión internamente — el procedimiento que usa para emparejar filas de las dos tablas.

Los distintos métodos de unión tienen costes distintos.

El dataset es la tabla de ventas perf_sales (50 000 filas; emp_id apunta a un comercial) y la tabla de empleados employee (30 filas; emp_id es efectivamente la clave primaria).

Cuando unes las dos por emp_id, observarás cuál aparece como bucle externo en el plan y cómo cambia el orden de unión según exista o no un índice.

Antes de meterte en los ejercicios, revisa las definiciones de columna y una muestra de los datos de las dos tablas que usa este artículo — perf_sales y employee. Generar perf_sales lleva un momento, así que la primera ejecución puede pausarse unos segundos.

① Usa PRAGMA table_info(perf_sales); y PRAGMA table_info(employee); para ver las definiciones de columna de ambas tablas.

② Usa SELECT * FROM perf_sales LIMIT 5; y SELECT * FROM employee LIMIT 5; para previsualizar las 5 primeras filas de cada una.

③ Usa SELECT COUNT(*) FROM perf_sales; y SELECT COUNT(*) FROM employee; para confirmar la diferencia de filas entre ellas (50 000 frente a 30).

Unión por bucles anidados y orden de unión

Una unión por bucles anidados (nested loop join) recorre la tabla externa fila a fila y, por cada fila, busca filas en la tabla interna que cumplan la condición de unión — un bucle doblemente anidado.

-- Compara la misma consulta de unión con tres métodos de unión
SELECT e.name, s.amount
FROM employee e
JOIN perf_sales s ON s.emp_id = e.emp_id;

-- Flujo interno de la unión por bucles anidados
-- for each e in employee:        -- bucle externo (30 filas)
--   for each s in perf_sales:    -- interno (sin índice, barre las 50 000 filas)
--     if s.emp_id = e.emp_id then añade al resultado de la unión

• El bucle externo se ejecuta tantas veces como filas tiene la tabla, así que pon la tabla más pequeña en el exterior
• El lado interno se busca repetidamente desde cada fila externa, así que indexa la clave de unión para que sea una búsqueda directa
• En el plan, la tabla que aparece primero es la externa, y la que aparece después es la interna
• El optimizador elige externo / interno automáticamente a partir de las estadísticas, así que el orden que escribes en FROM no necesariamente se respeta

-- Une perf_sales y employee por emp_id (ventas totales por empleado en dept 1)
-- Sin índice sobre perf_sales.emp_id, el plan tiende a barrer la perf_sales interna por completo
EXPLAIN QUERY PLAN
SELECT e.name, SUM(s.amount) AS total
FROM employee e
JOIN perf_sales s ON s.emp_id = e.emp_id
WHERE e.dept_id = 1
GROUP BY e.name;
--> SCAN employee AS e
--> SCAN perf_sales AS s   (sin índice, así que la interna también se barre completa)

-- Añade un índice sobre perf_sales.emp_id y la interna se puede buscar vía el índice
DROP INDEX IF EXISTS ix_sales_emp;
CREATE INDEX ix_sales_emp ON perf_sales(emp_id);
EXPLAIN QUERY PLAN
SELECT e.name, SUM(s.amount) AS total
FROM employee e
JOIN perf_sales s ON s.emp_id = e.emp_id
WHERE e.dept_id = 1
GROUP BY e.name;
--> SCAN employee AS e
--> SEARCH perf_sales AS s USING INDEX ix_sales_emp (emp_id=?)

Mira el plan para una consulta de unión que cuenta ventas por comercial, y lee qué tabla está en el bucle externo. (Ejecútalo correctamente y aparecerá la explicación.)

① Antepón EXPLAIN QUERY PLAN a una consulta que una employee y perf_sales por emp_id y cuente filas por nombre de empleado con GROUP BY, y revisa su plan.

② La tabla que aparece primero en la salida es el bucle externo, y la que aparece después es la interna. Sin un índice sobre perf_sales.emp_id todavía, lee cuál acaba fuera y cómo se está leyendo la interna.

Haz que la tabla interna de la unión se pueda buscar vía un índice y confirma que el plan cambia de SCAN a SEARCH ... USING INDEX. Empaqueta la creación del índice y la revisión del plan en una sola ejecución.

① Elimina cualquier índice con el mismo nombre con DROP INDEX IF EXISTS, luego crea un índice sobre la columna emp_id de perf_sales con CREATE INDEX.

② Antepón EXPLAIN QUERY PLAN a una consulta que una employee y perf_sales por emp_id y cuente filas por nombre de empleado, y revisa su plan. Confirma que employee (30 filas) sigue en el bucle externo mientras que la perf_sales interna ahora se busca vía el índice.

El optimizador elige el orden de unión automáticamente a partir de estadísticas

El orden de unión — qué tabla va al bucle externo — es, como regla, elegido automáticamente por el optimizador basándose en estadísticas.

Si has recogido estadísticas con ANALYZE (cubierto en el artículo anterior), el optimizador puede estimar de forma más precisa "qué tabla es más pequeña" y "si la interna se puede buscar vía un índice" y optimizar la asignación externo / interno.

El orden que escribes en FROM puede muy bien ser reordenado por el optimizador.

El truco para leer el orden de unión: en la salida de EXPLAIN QUERY PLAN, la tabla más arriba está más cerca del bucle externo.

Cuando la tabla equivocada acaba en el bucle externo y las cosas se ralentizan, lo primero que hay que revisar es si la clave de unión de la tabla que quieres como interna tiene un índice.

-- Después de ANALYZE, externo / interno se deciden con más precisión a partir de estadísticas
DROP INDEX IF EXISTS ix_sales_emp;
CREATE INDEX ix_sales_emp ON perf_sales(emp_id);
ANALYZE;

-- Incluso con perf_sales primero en FROM, el optimizador puede poner la más pequeña employee en el exterior
EXPLAIN QUERY PLAN
SELECT e.name, SUM(s.amount) AS total
FROM perf_sales s
JOIN employee e ON e.emp_id = s.emp_id
WHERE e.dept_id = 1
GROUP BY e.name;
--> SCAN employee AS e
--> SEARCH perf_sales AS s USING INDEX ix_sales_emp (emp_id=?)

Confirma que el optimizador elige el mismo orden de unión incluso cuando inviertes el orden de tablas en FROM. Empaqueta la creación del índice, la recogida de estadísticas y la revisión del plan en una sola ejecución.

① Elimina cualquier índice con el mismo nombre con DROP INDEX IF EXISTS, crea un índice sobre emp_id de perf_sales, luego ejecuta ANALYZE; para recoger estadísticas.

② Antepón EXPLAIN QUERY PLAN a una consulta cuyo FROM ahora sea FROM perf_sales s JOIN employee e ON ... (la tabla más grande escrita primero en FROM) y cuente filas por nombre de empleado, y revisa su plan. Lee si el optimizador sigue eligiendo la employee de 30 filas para el bucle externo incluso con el orden de FROM invertido.

Hash join y sort-merge join — métodos de unión usados por otras bases de datos

Las bases de datos grandes (PostgreSQL / Oracle / SQL Server, etcétera) también usan hash join (construir una tabla hash desde el lado más pequeño y sondear el otro contra ella) y sort-merge join (ordenar ambos lados por la clave de unión y recorrerlos en paralelo) junto con la unión por bucles anidados.

El motor que impulsa la consola del navegador de este curso solo usa bucles anidados, así que esta sección cubre los otros dos métodos a nivel de diagrama y concepto.

Hash join — convierte el lado más pequeño en una tabla hash y haz que el otro pase a través

-- Misma consulta, ejecutándose conceptualmente como hash join
SELECT e.name, s.amount
FROM employee e
JOIN perf_sales s ON s.emp_id = e.emp_id;

-- Flujo interno del hash join
-- H := { e.emp_id => e | e in employee }    -- (1) Build (convierte employee en una tabla hash)
-- for each s in perf_sales:                  -- (2) Probe (haz pasar perf_sales)
--   if H[s.emp_id] exists: añade al resultado de la unión

• Poner la tabla más pequeña en el lado de build mantiene la tabla hash lo bastante pequeña como para caber en memoria, lo que acelera las cosas
• Solo funciona para uniones por igualdad (=); las condiciones de rango (< / BETWEEN) no se pueden unir así
• Puede unir muchas filas en ambos lados con una sola pasada por cada uno incluso sin un índice interno, así que a menudo es más rápido que un bucle anidado
• Aparece como algo así como Hash Join en los EXPLAIN de las bases de datos de producción

Sort-merge join — ordena ambos lados, luego recórrelos juntos

-- Misma consulta, ejecutándose conceptualmente como sort-merge join
SELECT e.name, s.amount
FROM employee e
JOIN perf_sales s ON s.emp_id = e.emp_id;

-- Flujo interno del sort-merge join
-- E := sort(employee by emp_id)        -- (1) Sort (ordena ambos por emp_id)
-- S := sort(perf_sales by emp_id)
-- i, j := 0, 0
-- while i < |E| and j < |S|:            -- (2) Merge
--   if E[i].emp_id = S[j].emp_id: añade al resultado de la unión, j++
--   else if E[i].emp_id < S[j].emp_id: i++
--   else: j++

• Si ambos lados están ya ordenados (alineados por un índice, por ejemplo), el coste de ordenación es esencialmente cero y es extremadamente rápido
• También maneja uniones por rango (condiciones de unión que incluyen < o BETWEEN) — una fortaleza que el hash join no tiene
• El resultado sale ordenado por la clave de unión, lo que es conveniente para agregaciones y uniones posteriores
• Aparece como algo así como Merge Join en los EXPLAIN de las bases de datos de producción

Hash join y sort-merge join son métodos de unión de otros RDBMS

Hash join y sort-merge join son métodos de unión proporcionados por bases de datos grandes como PostgreSQL / Oracle / SQL Server.

El motor que impulsa la consola del navegador de este curso solo usa bucles anidados como algoritmo de unión (puede crear un índice interno transitorio para ayudar a la unión si es necesario), así que hash join y sort-merge join no se pueden demostrar en vivo en esta consola.

Para esos, nos conformamos con los diagramas y el código de solo lectura de arriba para captar la idea.

Mientras tanto, los lados externo / interno de la unión por bucles anidados, el orden de unión y el cambio de SCAN a SEARCH guiado por índice en el lado interno, todo cubierto antes en este artículo, son observables de verdad.

La capacidad de leer qué método de unión eligió la base de datos descansa en el mismo entendimiento de bucles anidados y orden de unión.

Las bases de datos de producción mostrarán términos como Hash Join / Merge Join en sus EXPLAIN, así que empieza por sentirte cómodo leyendo planes de bucles anidados en este curso.

-- Abajo está cómo podría verse EXPLAIN en PostgreSQL (solo lectura; no se ejecuta en la consola de este curso)
-- EXPLAIN SELECT e.name, SUM(s.amount) FROM employee e
--   JOIN perf_sales s ON s.emp_id = e.emp_id GROUP BY e.name;
-- Ejemplos de planes:
--   Hash Join  (construye una tabla hash desde employee, luego hace pasar perf_sales)
--   o Merge Join (ordena ambos por emp_id, luego los empareja)
-- PostgreSQL elige entre estos métodos automáticamente basándose en estadísticas y coste

-- Lo que sí puede demostrar la consola de este curso es esto (bucles anidados):
DROP INDEX IF EXISTS ix_sales_emp;
CREATE INDEX ix_sales_emp ON perf_sales(emp_id);
EXPLAIN QUERY PLAN
SELECT e.name, SUM(s.amount) AS total
FROM employee e
JOIN perf_sales s ON s.emp_id = e.emp_id
WHERE e.dept_id = 1
GROUP BY e.name;
--> SCAN employee / SEARCH perf_sales USING INDEX ix_sales_emp (emp_id=?)

Como cierre de este artículo, revisa el plan de unión una vez más con el índice en su sitio y lee el bucle externo, el acceso por índice interno y el significado del resultado. Empaqueta la creación del índice, la revisión del plan y la revisión del resultado en una sola ejecución.

① Elimina cualquier índice con el mismo nombre con DROP INDEX IF EXISTS, luego crea un índice sobre emp_id de perf_sales.

② Antepón EXPLAIN QUERY PLAN a una consulta que una employee y perf_sales por emp_id y cuente ventas por nombre de comercial, y revisa su plan.

③ Ejecuta la misma consulta de agregación (sin EXPLAIN QUERY PLAN) con ORDER BY cnt DESC LIMIT 5; para extraer los 5 comerciales con más conteo. Lee tanto el plan como el resultado real.