El Viaje de la Consulta SQL: El Query Planner

Por Jesús Espino • • 21 min de lectura
#PostgreSQL #Database #SQL
📚 El Viaje de la Consulta SQL (5 of 5) ▼
  1. 1. Visión General
  2. 2. Conexiones y Comunicación
  3. 3. Parsing y Análisis
  4. 4. Reescritura de Queries
  5. 5. El Query Planner Estás aquí
El Query Planner

En el artículo anterior , exploramos cómo el rewriter de PostgreSQL transforma las consultas—expandiendo vistas, aplicando políticas de seguridad y ejecutando reglas personalizadas. Al final de esa fase, tu consulta ha sido completamente expandida y asegurada, lista para su ejecución.

Pero aquí viene la pregunta del millón: ¿Cómo debe ejecutar PostgreSQL tu consulta realmente?

Déjame mostrarte por qué esto es importante. Considera esta consulta simple:

SELECT c.first_name, c.last_name, r.rental_date
FROM customer c
JOIN rental r ON c.customer_id = r.customer_id
WHERE c.active = 1;

PostgreSQL podría ejecutar esto de docenas de formas diferentes:

  • ¿Debería escanear toda la tabla customer o usar un índice sobre active?
  • ¿Debería escanear rental secuencialmente o usar un índice sobre customer_id?
  • ¿Debería hacer el join usando bucles anidados, hash join o merge join?
  • ¿Debería empezar con customer y buscar los alquileres coincidentes, o empezar con rental y buscar los clientes coincidentes?

Cada elección puede hacer que tu consulta vaya 10 veces más rápida o 100 veces más lenta. Un escaneo secuencial ingenuo de ambas tablas podría tardar segundos, mientras que un bucle anidado inteligente basado en índices podría devolver los resultados al instante. Aquí es donde entra el query planner (también conocido como optimizador)—el cerebro estratégico de PostgreSQL que determina la estrategia de ejecución óptima.

El trabajo del planner es fascinante: debe explorar potencialmente millones de enfoques posibles, estimar sus costes y elegir la mejor estrategia—todo en milisegundos. Balancea los costes de E/S frente a los costes de CPU, considera qué datos podrían estar en caché en memoria y decide si la ejecución paralela ayudaría. Esta optimización basada en costes representa décadas de investigación en bases de datos destilada en algoritmos prácticos.

En este artículo, exploraremos cómo el planner de PostgreSQL hace su magia: cómo estima costes, usa estadísticas para entender tus datos, genera diferentes rutas de ejecución y, finalmente, selecciona el enfoque más rápido para responder tu consulta.

Empecemos entendiendo la base de todas las decisiones de planificación: la estimación de costes.

Entendiendo los Costes: Cómo PostgreSQL Mide el Trabajo

PostgreSQL no mide el tiempo de ejecución en segundos o milisegundos—lo mide en unidades de coste abstractas. Estas unidades representan el gasto relativo de diferentes operaciones, permitiendo al planner comparar enfoques radicalmente diferentes en igualdad de condiciones.

La clave está en que el tiempo de ejecución se correlaciona con el trabajo computacional. Leer una página del disco cuesta más que procesar una fila en memoria. El acceso aleatorio al disco cuesta más que el acceso secuencial. El modelo de costes del planner captura estas relaciones en un marco unificado.

Entonces, ¿de qué están hechas realmente estas unidades de coste? Veamos los parámetros específicos que impulsan cada decisión de planificación.

Los Componentes Básicos del Coste

Vamos a desglosar los principales parámetros de coste que usa PostgreSQL. Las categorías más importantes son costes de E/S y costes de CPU.

Los costes de E/S tienen que ver con la lectura de datos del disco:

seq_page_cost (por defecto: 1.0) es la línea base—el coste de leer una página secuencialmente. Todo lo demás se mide en relación a esto.

random_page_cost (por defecto: 4.0) es el coste de leer una página aleatoriamente. ¿Por qué 4 veces más alto? Porque en discos duros tradicionales, el acceso aleatorio realmente es mucho más caro—el cabezal del disco tiene que moverse físicamente. En SSDs, el acceso aleatorio es casi tan rápido como el secuencial, así que configurarías esto más cerca de 1.1.

Este ratio es crucial para las decisiones de planificación. ¿Ratio alto? PostgreSQL prefiere escaneos secuenciales. ¿Ratio bajo? Los escaneos por índice se vuelven mucho más atractivos.

Los costes de CPU son mucho más simples porque la CPU es rápida:

cpu_tuple_cost (por defecto: 0.01) es el coste de procesar una fila.

cpu_index_tuple_cost (por defecto: 0.005) es el coste de procesar una entrada de índice. Es más barato porque las entradas de índice son más pequeñas.

cpu_operator_cost (por defecto: 0.0025) es el coste de ejecutar un operador o llamada a función.

Aquí vemos que los costes de CPU son significativamente más bajos que los de E/S. Pero cuidado—estos costes son por fila. Cuando estás procesando millones de filas, los costes de CPU crecen rápidamente y pueden tener un impacto significativo en el coste total.

Coste de Inicio vs. Coste Total

PostgreSQL calcula dos costes para cada operación:

Coste de Inicio: El trabajo requerido antes de producir la primera fila de resultado. Para un escaneo secuencial, el inicio está cerca de cero—PostgreSQL puede empezar a devolver filas inmediatamente. Para una operación de ordenación, el inicio incluye ordenar todos los datos antes de devolver nada.

Coste Total: El inicio más el trabajo para producir todas las filas restantes.

Veamos un ejemplo concreto usando la base de datos pagila :

EXPLAIN (ANALYZE, BUFFERS) SELECT * FROM film WHERE rental_duration = 5;

-- QUERY PLAN
-- Seq Scan on film  (cost=0.00..76.50 rows=191 width=390) (actual time=0.013..0.252 rows=191 loops=1)
--   Filter: (rental_duration = 5)
--   Rows Removed by Filter: 809
--   Buffers: shared hit=64
-- Planning Time: 0.063 ms
-- Execution Time: 0.274 ms

Este plan muestra cost=0.00..76.50:

  • Coste de inicio: 0.00 (puede empezar a devolver filas inmediatamente)
  • Coste total: 76.50 (leer todas las páginas + procesar todas las filas + aplicar el filtro)

¿Ves la línea Buffers: shared hit=64 en la salida? PostgreSQL nos está diciendo que accedió a 64 páginas de la caché de buffer compartida para completar esta consulta. Ahora podemos ver exactamente cómo el planner estimó ese coste de 76.50:

  • Coste de lectura de páginas: 1.0 × 64 páginas = 64.0
  • Coste de procesamiento: 0.01 × 1000 filas = 10.0
  • Coste de evaluación del filtro: 0.0025 × 1000 filas = 2.5
  • Total: 76.5

Esas 64 páginas fueron la mayor parte del coste de nuestra consulta—la E/S de páginas es cara comparada con las operaciones de CPU.

Por esto entender los parámetros de coste importa—son los bloques de construcción de cada decisión de planificación.

¿Quieres ver el código? Los cálculos de coste están en src/backend/optimizer/path/costsize.c .

Con los fundamentos de coste establecidos, exploremos cómo PostgreSQL recopila el conocimiento de datos necesario para hacer estos cálculos de coste significativos.

Estadísticas: Entendiendo Tus Datos

Las fórmulas de coste son inútiles sin conocimiento preciso de los datos. ¿Cuántas filas coincidirán con esa cláusula WHERE? ¿Cuántos valores distintos existen en esa columna? ¿Cuál es el valor más común? Estas preguntas requieren estadísticas.

El comando ANALYZE de PostgreSQL muestrea tus tablas para construir resúmenes estadísticos. Estas estadísticas guían cada decisión de planificación, marcando la diferencia entre un query plan brillante y un desastre.

Lo Que PostgreSQL Rastrea

Para cada columna, PostgreSQL mantiene varias medidas estadísticas:

Conteos de Filas: El número total de filas vivas en cada tabla. Esta es la base—sin conocer los tamaños de las tablas, el planner no puede estimar nada.

Fracción Nula: El porcentaje de valores NULL. Cuando filtras WHERE column IS NOT NULL, esta estadística le dice al planner qué tan selectivo es ese filtro.

Valores Más Comunes (MCVs): Los valores que ocurren con más frecuencia y sus frecuencias. PostgreSQL almacena hasta 100 de estos por columna.

Aquí es donde los MCVs importan. Considera esta tabla:

-- La mayoría de películas tienen rental_duration = 6 (21.2%), otras distribuidas más uniformemente
SELECT * FROM film WHERE rental_duration = 6;
-- MCV muestra frecuencia del 21.2% → probablemente escaneo secuencial

SELECT * FROM film WHERE rental_duration = 7;
-- MCV muestra frecuencia del 19.1% → todavía moderadamente selectivo

El mismo índice, diferentes valores, diferente selectividad—los MCVs le dicen al planner exactamente qué porcentaje de filas esperar.

Histogramas: Para valores no capturados por los MCVs, PostgreSQL crea histogramas dividiendo los valores restantes en grupos, donde cada grupo contiene aproximadamente la misma cantidad de filas. Esto ayuda al planner a estimar cuántas filas caen dentro de un rango:

SELECT * FROM payment WHERE amount BETWEEN 5.00 AND 10.00;

El planner usa el histograma para estimar qué fracción de filas cae en ese rango de importes, lo que determina si vale la pena un escaneo por índice.

Correlación: Esto mide si los valores de una columna se correlacionan con el orden de almacenamiento físico. Alta correlación significa que páginas consecutivas contienen valores similares. Baja correlación significa que los valores están dispersos aleatoriamente.

La correlación afecta dramáticamente los costes de escaneo por índice. En la base de datos pagila, rental_date tiene una correlación de 0.95 (muy alta)—los alquileres se insertan cronológicamente, así que páginas consecutivas contienen fechas similares. Un escaneo por índice en un rango de fechas lee páginas consecutivas—¡rápido! Pero customer_id tiene una correlación de solo 0.0025 (esencialmente aleatorio)—el mismo escaneo por índice requiere acceso aleatorio a páginas por toda la tabla—caro.

Ahora que entendemos qué estadísticas rastrea PostgreSQL, veamos cómo verlas.

Viendo Tus Estadísticas

PostgreSQL almacena todos estos datos en catálogos del sistema que puedes consultar directamente:

-- Estadísticas básicas de tabla
SELECT schemaname, relname, n_live_tup, n_dead_tup
FROM pg_stat_user_tables
WHERE relname = 'film';

-- Resultado:
-- schemaname | relname | n_live_tup | n_dead_tup
-- -----------+---------+------------+------------
-- public     | film    |       1000 |          0

-- Estadísticas de columna
SELECT tablename, attname, n_distinct, null_frac,
       most_common_vals, most_common_freqs,
       correlation
FROM pg_stats
WHERE tablename = 'film' AND attname = 'rental_duration';

-- Resultado:
-- tablename | attname         | n_distinct | null_frac | most_common_vals  | most_common_freqs                      | correlation
-- ----------+-----------------+------------+-----------+-------------------+----------------------------------------+-------------
-- film      | rental_duration |          5 |         0 | {6,3,4,5,7}       | {0.212,0.203,0.203,0.191,0.191}        |      0.163

Esto le dice al planner que el 21.2% de las películas tienen rental_duration = 6, el 20.3% tienen 3, el 20.3% tienen 4, el 19.1% tienen 5, y el 19.1% tienen 7. La correlación de 0.163 (baja) significa que estos valores están dispersos aleatoriamente por las páginas de la tabla—sin agrupación por duración de alquiler.

La calidad de las estadísticas afecta directamente la calidad del query plan. Estadísticas obsoletas llevan a malas estimaciones, que llevan a malos query plans. Por esto ANALYZE importa—ejecútalo regularmente, especialmente después de cambios significativos de datos, o habilita autovacuum para que lo maneje automáticamente.

Con estos bloques de construcción establecidos—parámetros de coste para estimar trabajo y estadísticas para entender datos—el planner está listo para evaluar diferentes estrategias de ejecución.

Cómo el Planner Evalúa los Query Plans

Ahora que entendemos costes y estadísticas, veamos cómo PostgreSQL realmente construye y elige query plans.

El planner funciona descomponiendo tu consulta en piezas y calculando el coste de cada pieza por separado:

Para cada tabla en tu consulta, PostgreSQL evalúa diferentes formas de acceder a ella. ¿Debería escanear toda la tabla secuencialmente? ¿Usar un índice? ¿Usar múltiples índices combinados? Cada opción obtiene una estimación de coste basada en los parámetros de coste y las estadísticas que acabamos de aprender.

Para joins entre tablas, PostgreSQL evalúa diferentes algoritmos de join. ¿Debería usar bucles anidados? ¿Hash join? ¿Merge join? De nuevo, se calcula el coste de cada opción.

El coste total de un query plan es la suma de todos estos costes individuales—cada escaneo de tabla, cada operación de join, cada ordenación o filtro. PostgreSQL genera múltiples query plans completos de esta manera, calculando el coste total para cada uno.

El ganador es simplemente el query plan con el menor coste total estimado. Ese es el que PostgreSQL ejecutará.

Este enfoque de abajo arriba—calcular el coste de operaciones individuales, combinarlas en query plans completos, elegir el más barato—es cómo PostgreSQL navega ese enorme espacio de posibilidades. Empecemos viendo cómo evalúa las opciones de acceso a tablas.

Rutas de Acceso: Eligiendo Cómo Leer Tablas

Antes de que el planner pueda determinar cómo hacer join de múltiples tablas, debe determinar la mejor manera de leer cada tabla individual. Para cada tabla en tu consulta, PostgreSQL considera varios métodos de acceso y estima sus costes.

Escaneo Secuencial: El Punto de Partida

El enfoque más simple es leer la tabla de principio a fin, página por página:

digraph sequential_scan {
    rankdir=LR;
    node [shape=box, style=filled, fillcolor=lightblue];

    subgraph cluster_table {
        label="Páginas de Tabla en Disco";
        style=filled;
        fillcolor=lightgray;

        page1 [label="Página 1\nFilas 1-100"];
        page2 [label="Página 2\nFilas 101-200"];
        page3 [label="Página 3\nFilas 201-300"];
        page4 [label="Página 4\nFilas 301-400"];

        page1 -> page2 -> page3 -> page4 [style=bold, color=red, label="Lectura Secuencial"];
    }

    scanner [shape=ellipse, fillcolor=yellow, label="Scanner"];
    scanner -> page1 [label="Inicio"];
}

PostgreSQL siempre considera el escaneo secuencial como una opción. Es predecible, y el coste es directo:

Coste = (seq_page_cost × páginas) + (cpu_tuple_cost × filas) + costes_filtro

El escaneo secuencial es a menudo óptimo para:

  • Tablas pequeñas (leer todo es rápido de todas formas)
  • Consultas que necesitan la mayoría de las filas (¿para qué usar un índice si vas a leer el 80% de la tabla?)
  • Tablas sin índices útiles
EXPLAIN SELECT * FROM film WHERE length > 100;

-- QUERY PLAN
-- Seq Scan on film  (cost=0.00..76.50 rows=609 width=390)
--   Filter: (length > 100)

El planner eligió escaneo secuencial porque este filtro coincide con 609 de 1000 filas (61%). Leer toda la tabla secuencialmente es más rápido que el acceso aleatorio por índice para todas esas coincidencias.

Implementación: nodeSeqscan.c

Escaneo por Índice: Preciso y Dirigido

Cuando necesitas solo unas pocas filas, los índices proporcionan precisión quirúrgica. Un Index Scan usa un índice (normalmente un B-tree) para encontrar ubicaciones exactas de filas, luego obtiene esas filas de las páginas en el heap:

digraph index_scan {
    rankdir=TB;
    node [shape=box, style=filled, fillcolor=lightblue];

    subgraph cluster_index {
        label="Índice B-Tree";
        style=filled;
        fillcolor=lightgreen;

        root [label="Raíz\n10|20|30"];
        leaf1 [label="Hoja\n5|7|9\nTID1|TID2|TID3"];
        leaf2 [label="Hoja\n12|15|18\nTID4|TID5|TID6"];
        leaf3 [label="Hoja\n25|27|29\nTID7|TID8|TID9"];

        root -> leaf1;
        root -> leaf2;
        root -> leaf3;
    }

    subgraph cluster_heap {
        label="Heap de Tabla";
        style=filled;
        fillcolor=lightgray;

        page1 [label="Página 1\nFilas Completas"];
        page2 [label="Página 2\nFilas Completas"];
        page3 [label="Página 3\nFilas Completas"];
    }

    query [shape=ellipse, fillcolor=yellow, label="Consulta: id = 7"];

    query -> root [label="1. Búsqueda en Índice"];
    root -> leaf1 [label="2. Recorrer"];
    leaf1 -> page1 [label="3. Lectura del Heap\n(TID2)", style=dashed, color=red];
}

El proceso de dos pasos—recorrido del índice más lectura del heap—es eficiente cuando se obtienen pocas filas:

EXPLAIN SELECT * FROM customer WHERE customer_id = 42;

-- QUERY PLAN
-- Index Scan using customer_pkey on customer  (cost=0.28..8.29 rows=1 width=74)
--   Index Cond: (customer_id = 42)

Fíjate en el bajo coste (8.29) comparado con el escaneo secuencial. El planner sabe que esta consulta devuelve exactamente una fila de 599 clientes totales, haciendo el escaneo por índice dramáticamente más rápido.

El problema: si un escaneo por índice devuelve muchas filas dispersas por la tabla, esas lecturas del heap se convierten en E/S aleatoria cara. Ahí es cuando el escaneo secuencial gana a pesar de tener un índice disponible.

Pero existe una forma de evitar por completo esas costosas lecturas del heap. Los index-only scans son una optimización especial: si el índice contiene todas las columnas que necesitas y las filas no han sido modificadas recientemente, PostgreSQL puede saltarse el heap completamente. Por ejemplo, SELECT customer_id FROM rental WHERE customer_id = 123 puede satisfacerse enteramente desde el índice—verás Heap Fetches: 0 en el query plan. Esto es dramáticamente más rápido ya que el índice es mucho más pequeño que la tabla completa.

Implementación: nodeIndexscan.c , nodeIndexonlyscan.c

Bitmap Scan: Eficiente para Selectividad Moderada

A veces necesitas obtener un número moderado de filas—demasiadas para que un escaneo por índice simple sea eficiente (todas esas lecturas aleatorias del heap), pero demasiado pocas para justificar un escaneo secuencial completo. O tienes múltiples condiciones, cada una con su propio índice. Aquí es donde el Bitmap Scan brilla.

Los bitmap scans funcionan con un solo índice o múltiples índices combinados. La ventaja clave: eliminan la E/S aleatoria convirtiendo búsquedas dispersas en índices en un escaneo del heap organizado y secuencial.

digraph bitmap_scan {
    rankdir=TB;
    node [shape=box, style=filled, fillcolor=lightblue];

    subgraph cluster_indexes {
        label="Índices";
        style=filled;
        fillcolor=lightgreen;

        idx1 [label="Índice rental_duration\n'5'\n→ 191 filas"];
        idx2 [label="Índice rating\n'PG'\n→ 194 filas"];
    }

    subgraph cluster_bitmap {
        label="Operaciones Bitmap";
        style=filled;
        fillcolor=lightyellow;

        bitmap1 [label="Bitmap 1\n[1,0,1,0,0,0,1,0,1]"];
        bitmap2 [label="Bitmap 2\n[1,1,0,0,1,0,0,0,1]"];
        combined [label="Bitmap Combinado\n[1,0,0,0,0,0,0,0,1]\n(operación AND)"];
    }

    subgraph cluster_heap {
        label="Heap de Tabla";
        style=filled;
        fillcolor=lightgray;

        page1 [label="Página 1\n✓ Leer", fillcolor=lightcoral];
        page2 [label="Página 2\nSaltar"];
        page3 [label="Página 3\nSaltar"];
        page4 [label="Página 4\nSaltar"];
        page5 [label="Página 5\nSaltar"];
        page6 [label="Página 6\nSaltar"];
        page7 [label="Página 7\nSaltar"];
        page8 [label="Página 8\nSaltar"];
        page9 [label="Página 9\n✓ Leer", fillcolor=lightcoral];
    }

    idx1 -> bitmap1;
    idx2 -> bitmap2;
    bitmap1 -> combined;
    bitmap2 -> combined;
    combined -> page1 [label="Escaneo Guiado"];
    combined -> page9;
}

El bitmap scan funciona en dos fases:

  1. Fase de Construcción: Escanear índices y construir un bitmap en memoria marcando qué páginas de tabla contienen coincidencias
  2. Escaneo del Heap: Leer solo las páginas marcadas secuencialmente

Veámoslo con un ejemplo:

EXPLAIN SELECT * FROM film
WHERE rental_duration = 5 AND rating = 'PG';

-- QUERY PLAN
-- Bitmap Heap Scan on film  (cost=11.46..69.45 rows=37 width=390)
--   Recheck Cond: ((rental_duration = 5) AND (rating = 'PG'::mpaa_rating))
--   ->  BitmapAnd  (cost=11.46..11.46 rows=37 width=0)
--         ->  Bitmap Index Scan on idx_film_rental_duration  (cost=0.00..5.58 rows=191 width=0)
--               Index Cond: (rental_duration = 5)
--         ->  Bitmap Index Scan on idx_film_rating  (cost=0.00..5.61 rows=194 width=0)
--               Index Cond: (rating = 'PG'::mpaa_rating)

El planner combina ambos índices con BitmapAnd—un escaneo encuentra 191 películas con rental_duration = 5, otro encuentra 194 películas clasificadas PG. PostgreSQL encuentra las 37 películas que aparecen en ambos bitmaps (las que coinciden con ambas condiciones), luego escanea solo las páginas relevantes del heap. Esto es mucho más eficiente que usar un índice y filtrar, o escanear toda la tabla de 1000 películas.

Implementación: nodeBitmapHeapscan.c , nodeBitmapIndexscan.c

Ahora que entendemos los métodos de acceso a tablas, exploremos cómo PostgreSQL hace joins de múltiples tablas.

Algoritmos de Join: Uniendo Tablas

Hacer joins de tablas es donde la ejecución de consultas se vuelve cara. El planner debe elegir tanto qué algoritmo de join usar como en qué orden hacer joins de las tablas. Empecemos con los algoritmos.

Nested Loop Join: Simple y Efectivo

El Nested Loop es conceptualmente simple—para cada fila en la tabla exterior, escanear la tabla interior buscando coincidencias:

FOR cada_fila IN tabla_exterior (customer):
    FOR cada_fila IN tabla_interior (rental):
        IF filas_coinciden_condicion_join:
            RETURN fila_combinada

Esto parece caro—y lo sería si escaneáramos toda la tabla interior para cada fila exterior. Pero aquí está el truco: si la tabla interior tiene un índice en la clave de join, PostgreSQL hace una búsqueda eficiente por índice en su lugar:

EXPLAIN SELECT *
FROM customer c
JOIN rental r ON c.customer_id = r.customer_id
WHERE c.customer_id = 1;

-- QUERY PLAN
-- Nested Loop  (cost=0.28..359.16 rows=32 width=114)
--   ->  Index Scan using customer_pkey on customer c  (cost=0.28..8.29 rows=1 width=74)
--         Index Cond: (customer_id = 1)
--   ->  Seq Scan on rental r  (cost=0.00..350.55 rows=32 width=40)
--         Filter: (customer_id = 1)

El planner encuentra el cliente único (1 de 599) vía índice instantáneamente, luego escanea la tabla rental para los 32 alquileres de ese cliente de un total de 16,044. Aunque rental no usa un índice aquí, el nested loop sigue siendo eficiente porque la tabla exterior devuelve solo una fila.

Los bucles anidados destacan cuando:

  • La tabla exterior es pequeña
  • La tabla interior tiene un índice en la clave de join
  • El join es altamente selectivo (pocas coincidencias por fila exterior)

Implementación: nodeNestloop.c

Hash Join: Velocidad Mediante Hashing

Cuando se hacen joins de tablas grandes sin índices útiles, el Hash Join domina. Funciona en dos fases—construir una tabla hash, luego sondearla:

-- Fase de construcción: crear tabla hash de la tabla más pequeña
tabla_hash = {}
FOR cada_fila IN tabla_pequeña (customer):
    clave_hash = HASH(fila.customer_id)
    tabla_hash[clave_hash] = fila

-- Fase de búsqueda: recorrer la tabla más grande y buscar en la tabla hash
FOR cada_fila IN tabla_grande (rental):
    clave_hash = HASH(fila.customer_id)
    IF clave_hash EXISTS IN tabla_hash:
        RETURN fila_combinada(tabla_hash[clave_hash], fila)

El hash join es increíblemente rápido cuando la tabla hash cabe en memoria:

EXPLAIN SELECT *
FROM rental r
JOIN customer c ON r.customer_id = c.customer_id;

-- QUERY PLAN
-- Hash Join  (cost=22.48..375.33 rows=16044 width=114)
--   Hash Cond: (r.customer_id = c.customer_id)
--   ->  Seq Scan on rental r  (cost=0.00..310.44 rows=16044 width=40)
--   ->  Hash  (cost=14.99..14.99 rows=599 width=74)
--         ->  Seq Scan on customer c  (cost=0.00..14.99 rows=599 width=74)

El planner escanea la tabla customer más pequeña (599 filas) para construir una tabla hash en memoria, luego recorre todas las 16,044 filas de rental buscando coincidencias. Cada búsqueda es O(1)—búsqueda hash instantánea. Esto devuelve todos los 16,044 registros de alquiler con su información de cliente.

El problema: la tabla hash debe caber en work_mem. Si no, PostgreSQL vuelca a disco, ralentizando dramáticamente el join. Por esto el ajuste de work_mem importa para consultas analíticas.

Los hash joins brillan para:

  • Equi-joins (usando el operador =)
  • Tablas grandes sin índices útiles
  • Situaciones con memoria suficiente

Implementación: nodeHashjoin.c

Merge Join: Fusión Elegante de Datos Ordenados

Cuando ambas entradas ya están ordenadas por la clave de join, el Merge Join las fusiona elegantemente como combinar dos mazos de cartas ordenados:

-- Ambas entradas deben estar ordenadas por la clave de join
fila_izq = PRIMERA(tabla_izq)   -- tabla rental ordenada
fila_der = PRIMERA(tabla_der)   -- tabla payment ordenada

WHILE fila_izq AND fila_der:
    IF fila_izq.rental_id = fila_der.rental_id:
        RETURN fila_combinada(fila_izq, fila_der)
        AVANZAR ambos punteros
    ELSE IF fila_izq.rental_id < fila_der.rental_id:
        AVANZAR fila_izq
    ELSE:
        AVANZAR fila_der

El algoritmo avanza a través de ambas entradas ordenadas simultáneamente, comparando claves y emitiendo coincidencias:

EXPLAIN SELECT *
FROM rental r
JOIN payment p ON r.rental_id = p.rental_id;

-- QUERY PLAN
-- Merge Join  (cost=1483.07..2341.89 rows=16049 width=70)
--   Merge Cond: (r.rental_id = p.rental_id)
--   ->  Index Scan using rental_pkey on rental r  (cost=0.29..578.29 rows=16044 width=40)
--   ->  Sort  (cost=1482.77..1522.90 rows=16049 width=30)
--         Sort Key: p.rental_id
--         ->  Append  (cost=0.00..361.74 rows=16049 width=30)
--               ->  Seq Scan on payment_p2022_01 p_1  (cost=0.00..13.23 rows=723 width=30)
--               ->  Seq Scan on payment_p2022_02 p_2  (cost=0.00..42.01 rows=2401 width=30)
--               ... (particiones adicionales de payment)

La tabla rental (16,044 filas) viene pre-ordenada desde su índice de clave primaria. La tabla payment (16,049 filas a través de 7 particiones) necesita ordenarse primero, pero una vez ordenada, el merge join necesita solo un pase a través de cada una—emparejando eficientemente todos los registros de alquiler con sus pagos.

Los merge joins destacan cuando:

  • Ambas entradas ya están ordenadas (desde índices u operaciones previas)
  • Se hacen joins de tablas muy grandes donde el hash join volcaría a disco
  • Joins no equitativos (como >, <) donde el hash join no puede usarse

Implementación: nodeMergejoin.c

Orden de Join: Resolviendo la Explosión Combinatoria

Aquí es donde la planificación se pone realmente interesante. El número de órdenes de join posibles crece factorialmente con el número de tablas:

  • 3 tablas: 12 órdenes posibles
  • 4 tablas: 120 órdenes posibles
  • 5 tablas: 1,680 órdenes posibles
  • 8 tablas: 17 millones de órdenes posibles
  • 10 tablas: 17.6 mil millones de órdenes posibles
  • 12 tablas: 28 billones de órdenes posibles

Puedes ver el problema—evaluar cada posibilidad llevaría una eternidad, incluso para consultas de tamaño moderado.

PostgreSQL maneja esto (src/backend/optimizer/path/allpaths.c ) con dos estrategias diferentes basadas en la complejidad de la consulta:

Para consultas con hasta 12 tablas (configurable vía geqo_threshold), PostgreSQL usa programación dinámica (src/backend/optimizer/path/joinrels.c ) con optimización agresiva. No explora todas las posibilidades—eso aún llevaría una eternidad. En su lugar, usa técnicas inteligentes:

  • Cacheo: Recuerda el coste de subplanes para no recalcularlos
  • Poda: Descarta ramas enteras de posibilidades que no pueden ser óptimas

Esto reduce dramáticamente el espacio de búsqueda. Pero incluso con estos trucos, el enfoque tiene límites—más allá de 12 tablas, simplemente hay demasiadas posibilidades para explorar, incluso con cacheo y poda.

Para consultas con más de 12 tablas, PostgreSQL cambia al Optimizador de Consultas Genético (GEQO) (src/backend/optimizer/geqo/ )—un enfoque completamente diferente inspirado en la selección natural. En lugar de intentar ser inteligente explorando posibilidades, GEQO “evoluciona” buenos query plans:

  1. Población: Crear órdenes de join aleatorios como “individuos”
  2. Aptitud: Evaluar coste (menor coste = mayor aptitud)
  3. Selección: Individuos más aptos más propensos a reproducirse
  4. Cruce: Combinar dos query plans padres para crear hijos
  5. Mutación: Cambios aleatorios para explorar nuevas posibilidades
  6. Evolución: Repetir durante muchas generaciones hasta que dominen query plans de alta calidad

GEQO encuentra query plans excelentes en milisegundos para consultas complejas que llevarían horas o días con búsqueda exhaustiva. Cuando tu consulta hace join de 15 tablas con cuatrillones de órdenes posibles, “bastante bueno” gana a “perfecto pero nunca termina”.

Los detalles de cómo funciona GEQO son fascinantes y merecen su propia exploración profunda—exploraremos la mecánica del algoritmo genético en un artículo futuro.

Resumiendo

Así que ese es el query planner de PostgreSQL—el motor que determina cómo ejecutar tus consultas eficientemente.

Empezamos con lo básico: parámetros de coste que miden el trabajo en unidades abstractas. Los costes de E/S como seq_page_cost y random_page_cost capturan lo caro que es el acceso a disco, mientras que los costes de CPU son diminutos en comparación. Estos parámetros permiten a PostgreSQL comparar estrategias completamente diferentes en igualdad de condiciones.

Luego miramos las estadísticas—el conocimiento de datos que hace significativas las estimaciones de coste. Valores más comunes, histogramas, estadísticas de correlación—todo recopilado por ANALYZE (o autovacuum) para decirle al planner cómo se ven realmente tus datos. Sin buenas estadísticas, incluso fórmulas de coste perfectas producen query plans terribles.

Exploramos cómo el planner evalúa query plans descomponiendo consultas en piezas—calculando el coste de cada método de acceso a tabla, calculando el coste de cada algoritmo de join, luego sumándolo todo. El query plan con el menor coste total gana.

Para acceder a tablas individuales, PostgreSQL considera escaneos secuenciales (leer todo), escaneos por índice (búsquedas dirigidas), index-only scans (sin acceso al heap), y bitmap scans (combinando índices eficientemente). Cada uno tiene su punto óptimo basado en cuántas filas necesitas.

Para hacer joins de tablas, todo se trata de las características de los datos. Bucles anidados cuando un lado es diminuto y tienes índices. Hash joins cuando se hacen joins de tablas grandes sin índices. Merge joins cuando tus datos vienen pre-ordenados. El planner elige la opción más barata basada en tamaños de tabla e índices disponibles.

Y para el orden de join, exploramos cómo el orden importa enormemente y cómo PostgreSQL usa diferentes enfoques dependiendo de cuántas tablas estás uniendo—desde optimización exhaustiva para consultas simples hasta algoritmos evolutivos para las complejas.

Con el query plan listo, PostgreSQL sabe exactamente cómo ejecutar tu consulta. Lo siguiente: el ejecutor que da vida a estos query plans y produce realmente tus resultados.