Fundamentos B-tree revisitados con lente avanzado

Descripción de la cápsula

La guía #8 te enseñó la versión "tutorial" de B-tree: CREATE INDEX ON books(author_id); y queries con WHERE author_id = 42 se vuelven rápidas. Funcional, suficiente para empezar. Pero deja preguntas sin respuesta:

• ¿Por qué WHERE author_id = 42 es rápido pero WHERE name LIKE '%tolkien' no, aunque ambas usen el mismo tipo de índice?
• ¿Por qué a veces creas un índice y el plan sigue mostrando Seq Scan?
• ¿Qué significa exactamente "selectividad" cuando dicen "el índice no se usa porque la columna no es selectiva"?
• ¿Por qué un B-tree sirve para =, <, BETWEEN, ORDER BY pero no para <> ni LIKE '%foo'?

Esta cápsula abre el B-tree por dentro lo suficiente para que las próximas cápsulas (composite, covering, partial, expression) tengan sentido como consecuencias lógicas, no como recetas memorizadas. Al terminar, vas a poder mirar una query y predecir si un índice B-tree va a ayudar — antes de crearlo.

Objetivo concreto: vas a poder explicarle a un colega por qué el planner decidió ignorar el índice que acabas de crear, y proponer al menos dos hipótesis de qué cambiar (la query, el índice o las estadísticas).

Un B-tree por dentro: árbol balanceado ordenado

PostgreSQL implementa B-trees como árboles balanceados de varios niveles. La idea esencial es la misma que cualquier diccionario o índice telefónico:

                          [ G | M | T ]              ← raíz
                         /     |    |     \
                  [A..F]  [G..L] [M..S] [T..Z]       ← nivel intermedio
                 /  |  \   ...                         ...
            [filas] [filas] [filas]                    ← hojas (apuntan a tuplas)

Cada nodo intermedio guarda separadores (las claves que dividen rangos). Cuando buscas author_id = 42:

1. Empiezas en la raíz. Ves separadores [100, 500, 1000]. Como 42 < 100, bajas por la rama izquierda.
2. En el nivel intermedio, ves separadores más finos [10, 50, 80]. Como 42 está entre 10 y 50, bajas por esa rama.
3. Llegas a una hoja. La hoja contiene las claves ordenadas y, junto a cada clave, un TID (Tuple Identifier: un puntero a la fila en el heap).
4. Lees la fila del heap usando el TID.

Costo de la búsqueda: O(log n). Para 1,000,000 de filas con un fanout típico de 100 entradas por nodo, el árbol tiene unos 4 niveles. Significa 4 lecturas de páginas para encontrar una clave, vs leer la tabla entera (potencialmente miles de páginas).

Por qué importa que las hojas estén ordenadas

Las hojas de un B-tree están enlazadas en orden. Esto te da gratis tres operaciones eficientes:

• Igualdad (= 42): bajas el árbol y lees una hoja.
• Rango (BETWEEN 10 AND 50, >= 100, < 2026-01-01): bajas a la primera hoja del rango y caminas las siguientes en orden.
• Ordenamiento (ORDER BY author_id): el índice ya está ordenado. Lees las hojas en orden y devuelves filas sin hacer un Sort aparte.

Por qué B-tree NO sirve para todo

Los siguientes patrones no aprovechan un B-tree estándar, aunque la columna esté indexada:

Las cápsulas siguientes resuelven varios de estos casos:

• LIKE 'tolkien%' (con prefijo): sí funciona con B-tree estándar (mismo prefijo = bajada al árbol).
• LIKE '%tolkien%': necesita pg_trgm con GIN — guía #14.
• lower(email): expression index — cápsula 06.
• created_at::date: expression index — cápsula 06.
• jsonb @> ...: GIN — guía #14.

Selectividad y cardinalidad: el lenguaje del planner

Los términos que más vas a leer cuando alguien explique por qué el planner ignora un índice:

• Cardinalidad de una columna: cuántos valores distintos tiene. gender con valores ('M', 'F', 'O') tiene cardinalidad 3. email en una tabla de usuarios tiene cardinalidad casi igual al número de filas.
• Selectividad de un predicado: qué fracción de la tabla devuelve. WHERE id = 42 devuelve 1 fila de 1M = selectividad 0.000001 (muy selectivo). WHERE active = true en una tabla donde 95% son activos devuelve 950k de 1M = selectividad 0.95 (poco selectivo).

Regla intuitiva:

• Selectividad muy baja (devuelves <5% de la tabla): el índice probablemente gana.
• Selectividad media (5-30%): depende — Bitmap Heap Scan puede aparecer.
• Selectividad alta (>30%): el Seq Scan suele ganar. Leer toda la tabla secuencialmente con cache prefetching es más rápido que dar saltos aleatorios al heap a través del índice.

Por eso una columna con baja cardinalidad (active true/false, status pending/done/cancelled) muchas veces no se beneficia de un índice B-tree estándar: cualquier valor cubre demasiada tabla. Las soluciones para esos casos son partial indexes (cápsula 05) y composite indexes poniendo otra columna primero (cápsula 03).

Cómo el planner conoce la selectividad

PostgreSQL mantiene estadísticas en pg_stats (poblada por ANALYZE y autovacuum). Para cada columna guarda:

• null_frac: fracción de valores nulos.
• n_distinct: estimación de valores distintos.
• most_common_vals y most_common_freqs: los valores más frecuentes y su frecuencia.
• histogram_bounds: un histograma para distribución general.

Cuando el planner ve WHERE status = 'pending', busca 'pending' en most_common_vals. Si lo encuentra, usa la frecuencia exacta. Si no, asume distribución uniforme sobre los valores no comunes.

Ejemplo práctico (verlo tú mismo):

-- Reemplaza 'orders' por una tabla tuya con datos
SELECT
  attname,
  n_distinct,
  most_common_vals,
  most_common_freqs
FROM pg_stats
WHERE tablename = 'orders'
  AND attname = 'status';

Si most_common_freqs te dice que 'pending' cubre el 0.05 de la tabla, el planner estima 50,000 filas en una tabla de 1M — bajo, índice probablemente se usa.

Si te dice que 'pending' cubre el 0.6, el planner estima 600,000 filas — alto, Seq Scan probablemente gana.

(Estadísticas y ANALYZE se profundizan en el módulo 7. Acá solo necesitas saber que existen y que el planner se basa en ellas.)

Ejemplo trabajado: misma columna, dos índices, comportamientos opuestos

Vas a montar una tabla de prueba, cargar datos, crear un índice, y ver dos casos donde el planner toma decisiones distintas.

Setup

Conéctate a tu PostgreSQL local (en psql o el cliente que uses):

-- Crear tabla de prueba
DROP TABLE IF EXISTS demo_orders;
CREATE TABLE demo_orders (
    id          BIGSERIAL PRIMARY KEY,
    customer_id INTEGER NOT NULL,
    status      TEXT NOT NULL,
    total       NUMERIC(10, 2) NOT NULL,
    created_at  TIMESTAMPTZ NOT NULL DEFAULT NOW()
);

-- Cargar 500,000 filas con status sesgado:
-- 95% 'completed', 4% 'pending', 1% 'cancelled'
INSERT INTO demo_orders (customer_id, status, total, created_at)
SELECT
    (random() * 50000)::INTEGER + 1,
    CASE
        WHEN random() < 0.95 THEN 'completed'
        WHEN random() < 0.99 THEN 'pending'
        ELSE 'cancelled'
    END,
    (random() * 1000)::NUMERIC(10, 2),
    NOW() - (random() * INTERVAL '365 days')
FROM generate_series(1, 500000);

-- Refrescar estadísticas
ANALYZE demo_orders;

Caso 1: índice sobre customer_id (alta cardinalidad)

customer_id tiene 50,000 valores distintos sobre 500,000 filas. Cada valor cubre ~10 filas en promedio: muy selectivo.

CREATE INDEX idx_demo_customer ON demo_orders(customer_id);

EXPLAIN (ANALYZE, BUFFERS)
SELECT * FROM demo_orders WHERE customer_id = 42;

Output esperado:

Index Scan using idx_demo_customer on demo_orders
  Index Cond: (customer_id = 42)
  Buffers: shared hit=12
Planning Time: 0.234 ms
Execution Time: 0.187 ms

El planner eligió Index Scan. Selectividad muy alta favorece el índice.

Caso 2: mismo índice, distinta query — status = 'completed'

Ahora intentas:

CREATE INDEX idx_demo_status ON demo_orders(status);

EXPLAIN (ANALYZE, BUFFERS)
SELECT * FROM demo_orders WHERE status = 'completed';

Output esperado:

Seq Scan on demo_orders
  Filter: (status = 'completed'::text)
  Rows Removed by Filter: 25000
  Buffers: shared hit=4500
Planning Time: 0.245 ms
Execution Time: 92.345 ms

El planner ignoró el índice. Razón: status='completed' cubre el 95% de la tabla. Leer 475,000 filas a través de un índice (con saltos aleatorios al heap) es más caro que leer las 500,000 secuencialmente. Es la decisión correcta.

Caso 3: misma columna, valor distinto — status = 'cancelled'

EXPLAIN (ANALYZE, BUFFERS)
SELECT * FROM demo_orders WHERE status = 'cancelled';

Output esperado:

Bitmap Heap Scan on demo_orders
  Recheck Cond: (status = 'cancelled'::text)
  Heap Blocks: exact=...
  Buffers: shared hit=...
  ->  Bitmap Index Scan on idx_demo_status
        Index Cond: (status = 'cancelled'::text)
Planning Time: 0.234 ms
Execution Time: 8.412 ms

Ahora sí usa el índice (vía Bitmap Index Scan). Razón: cancelled es el 1% de la tabla — selectivo. El planner consultó most_common_freqs, vio que cancelled es raro, y eligió usar el índice.

Punto clave: el mismo índice sobre la misma columna se usa o no se usa según el valor exacto del predicado. El planner es valor-aware.

Cuándo el planner ignora un índice "perfectamente válido"

Lista de causas comunes — vale la pena memorizarlas:

1. Selectividad alta del predicado

Ya cubierto arriba. Si WHERE x = $val devuelve >30% de la tabla, Seq Scan suele ganar.

Cómo verificar:

EXPLAIN (ANALYZE)
SELECT * FROM tabla WHERE columna = 'valor';

Mira actual rows del nodo. Si es una fracción grande de la tabla, el planner está siendo razonable.

2. Estadísticas desactualizadas

Si insertaste muchos datos recientemente y no corriste ANALYZE, el planner cree que la tabla tiene la distribución vieja. Decisión basada en información desfasada.

Cómo verificar:

SELECT
  schemaname, relname,
  last_analyze, last_autoanalyze,
  n_live_tup, n_dead_tup
FROM pg_stat_user_tables
WHERE relname = 'tu_tabla';

Si last_analyze y last_autoanalyze son viejos, corre ANALYZE tu_tabla;.

3. Tabla pequeña

Para tablas con menos de ~1000 filas, el planner casi siempre prefiere Seq Scan. Cargar el índice y dar saltos al heap cuesta más que leer la tabla entera.

Síntoma: trabajas en local con 100 filas, todo es Seq Scan. Insertas 100k filas con un script de seed y de pronto el planner empieza a usar el índice. Normal.

4. Función o cast en la columna del WHERE

WHERE lower(email) = 'foo@bar.com'   -- índice sobre email NO sirve
WHERE created_at::date = '2026-05-01'  -- índice sobre created_at NO sirve
WHERE id::TEXT = '42'                  -- índice sobre id NO sirve

La función envuelve la columna y rompe la coincidencia. Solución: expression index (cápsula 06) o reescribir la query (WHERE created_at >= '2026-05-01' AND created_at < '2026-05-02' en vez de cast).

5. Tipo no coincidente

-- Columna user_id es BIGINT
WHERE user_id = '42'  -- string, no integer

Algunos drivers/ORMs hacen casts implícitos. Si el cast es explícito o el tipo del parámetro no coincide, puede romperse el uso del índice. Verifica que tu driver pase el tipo correcto.

6. Operador no compatible con B-tree

WHERE columna <> 'valor'           -- "distinto de"
WHERE columna LIKE '%algo'         -- sufijo
WHERE columna IS NOT NULL          -- (a veces sí, a veces no)
WHERE arr_col @> ARRAY['x']        -- containment de array

B-tree no soporta estos operadores eficientemente. Para algunos, hay otros tipos de índice (GIN, GiST, BRIN). Para <>, casi nunca hay índice eficiente.

7. OR sobre columnas distintas sin índice combinado

WHERE author_id = 42 OR isbn = 'XYZ'

Con índices separados sobre author_id y isbn, el planner puede usar BitmapOr (combina bitmaps). A veces decide que es más caro y va a Seq Scan. Soluciones: composite index, o UNION en lugar de OR.

8. Versión de PostgreSQL o configuración

random_page_cost (default 4 en magnetic disks, 1.1 recomendado en SSD) afecta cuándo el planner prefiere index vs sequential. Si tu base corre en SSD pero tiene random_page_cost = 4, el planner sub-estima al índice.

SHOW random_page_cost;

Si está en 4 y corres en SSD, considera bajarlo a 1.1 globalmente.

¿Por qué importa esto en el trabajo real?

1. Evitas el ciclo "creo índice, no funciona, creo otro".

Sin entender los fundamentos, vas adivinando. Con los fundamentos, miras la query, miras pg_stats, miras el plan, y propones un índice con confianza razonable de que se va a usar.

2. Defiendes tus decisiones técnicas.

En un PR review serio, alguien va a preguntar "¿por qué este índice?". "Porque la query lo necesitaba" es respuesta junior. "Porque la cardinalidad de status es 4 y la selectividad real de 'pending' es 5%, así que un partial sobre ese valor gana sobre uno completo, y validé con EXPLAIN que se usa" es respuesta senior.

3. Negocias con el planner sin pelearte con él.

A veces el planner ignora tu índice y la solución no es forzarlo (con enable_seqscan = off, anti-pattern), es entender por qué lo ignora y arreglar la causa real (estadísticas, query reescrita, partial index).

Trampas y errores comunes

Error 1 (conceptual): asumir que existe el índice = se usa el índice

Síntoma: "Le puse un índice y sigue lento."

Por qué pasa: el planner decide. Crear el índice habilita su uso, no lo garantiza.

Cómo detectar: captura el plan con EXPLAIN (ANALYZE). Si ves Seq Scan, el índice no se está usando.

Cómo corregir: repasa la lista de causas arriba. Si no es ninguna obvia, mira las estadísticas con pg_stats y revisa la selectividad real del predicado.

Error 2 (conceptual): forzar al planner con SET enable_seqscan = off

Síntoma: alguien en Stack Overflow recomienda SET enable_seqscan = off para "obligar" a usar índice.

Por qué es erróneo: es un parche. Si el planner prefiere Seq Scan, generalmente tiene razón. Forzar Index Scan puede ser peor en performance real. Y si funciona, es señal de un problema más profundo (estadísticas, configuración, índice mal diseñado) que estás tapando.

Cómo corregir: úsalo solo para diagnóstico ("¿cuánto cuesta el plan alternativo?"), nunca como solución permanente. Para ajustar el costing, usa random_page_cost o effective_cache_size.

Error 3 (práctico): indexar columnas con cardinalidad muy baja sin pensar

Síntoma: creas CREATE INDEX ON users(active); y nunca se usa.

Por qué pasa: active tiene cardinalidad 2 (true/false). Cualquier valor cubre un porcentaje grande de la tabla. El planner casi siempre prefiere Seq Scan.

Cómo corregir: o no indexes columnas booleanas (no aportan), o usa partial index sobre el valor minoritario (cápsula 05): CREATE INDEX ON users(id) WHERE active = false; si los inactivos son el 5%.

Error 4 (conceptual): confundir un B-tree usable con eficiente

Síntoma: el plan muestra Index Scan, asumes que está optimizado.

Por qué a veces es erróneo: un Index Scan puede traer 100,000 candidatas y luego descartar el 95% por Filter. Eso es ineficiente — el índice solo cubre parcialmente la query.

Cómo detectar: mira Rows Removed by Filter. Si es alto vs actual rows, el índice está cubriendo solo parte del predicado. Necesitas composite (cápsula 03) o partial (cápsula 05).

Error 5 (conceptual): asumir que un índice "viejo" no necesita revisión

Síntoma: "Ese índice está desde 2024, debe estar bien."

Por qué pasa: las queries de la app cambian. Refactors, features nuevas, columnas agregadas. Un índice que era óptimo hace seis meses puede estar siendo ignorado hoy.

Cómo corregir: revisa periódicamente pg_stat_user_indexes (cápsula 07). Si idx_scan = 0 después de meses, el índice solo está ralentizando writes y consumiendo disco.

Ejercicios

Ejercicio 1: predecir uso de índice según selectividad

Tienes una tabla users con 1,000,000 de filas. Para cada uno de estos predicados, predice si el planner probablemente usará un índice B-tree sobre la columna correspondiente. Justifica.

1. WHERE id = 12345 (sobre PK)
2. WHERE active = true (95% son activos)
3. WHERE country = 'AR' (15% son argentinos sobre 200 países)
4. WHERE email = 'user@example.com'
5. WHERE registered_at >= '2026-01-01' (5% se registraron en ese rango)
6. WHERE registered_at >= '2020-01-01' (95% se registraron desde ese año)

Ejercicio 2: diagnosticar índice ignorado

Creaste un índice y el plan sigue mostrando Seq Scan. Lista al menos 5 causas posibles a investigar, en orden de probabilidad.

Ejercicio 3: investigar selectividad real con pg_stats

Toma una tabla tuya (o usa la demo_orders del ejemplo trabajado). Ejecuta:

SELECT
  attname,
  null_frac,
  n_distinct,
  most_common_vals,
  most_common_freqs
FROM pg_stats
WHERE tablename = 'demo_orders';

Para tres columnas distintas, escribe una frase de cada una: "esta columna tiene cardinalidad X y su valor más frecuente cubre Y% de la tabla, así que un índice B-tree estándar [se usaría / no se usaría / depende del valor]."

SELECT attname, n_distinct, most_common_vals, most_common_freqs
FROM pg_stats
WHERE tablename = 'demo_orders';

Ejercicio 4: distinguir queries B-tree-friendly de las que no

Marca cada query como B-tree usa o B-tree NO usa (asumiendo índice sobre la columna del predicado y selectividad razonable).

1. SELECT * FROM books WHERE title = 'El Señor de los Anillos'
2. SELECT * FROM books WHERE title LIKE 'El Señor%'
3. SELECT * FROM books WHERE title LIKE '%Anillos'
4. SELECT * FROM books WHERE published_year BETWEEN 1950 AND 1960
5. SELECT * FROM books WHERE published_year <> 2000
6. SELECT * FROM books WHERE lower(title) = 'el hobbit'
7. SELECT * FROM books WHERE id IN (1, 2, 3, 4, 5)
8. SELECT * FROM books WHERE author_id IS NULL
9. SELECT * FROM books ORDER BY published_year DESC LIMIT 10 (asumiendo índice sobre published_year)
10. SELECT * FROM books WHERE jsonb_metadata @> '{"genre": "fantasy"}'

Ejercicio 5: experimentar con tablas pequeñas vs grandes

En tu PostgreSQL local:

1. Crea una tabla tiny con 100 filas.
2. Crea un índice sobre cualquier columna.
3. Captura el plan de un SELECT que filtre por esa columna.
4. Inserta 100,000 filas más a la misma tabla.
5. Corre ANALYZE.
6. Captura el plan de la misma query.
7. Compara y comenta.

-- Paso 1-2
CREATE TABLE tiny (id SERIAL PRIMARY KEY, codigo TEXT);
INSERT INTO tiny (codigo) SELECT md5(random()::text) FROM generate_series(1, 100);
CREATE INDEX idx_tiny_codigo ON tiny(codigo);
ANALYZE tiny;

-- Paso 3
EXPLAIN (ANALYZE) SELECT * FROM tiny WHERE codigo = 'algun_codigo';

Seq Scan on tiny  (cost=0.00..2.25 rows=1 width=37) (actual time=0.020..0.023 rows=0 loops=1)
  Filter: (codigo = 'algun_codigo'::text)
  Rows Removed by Filter: 100

-- Paso 4-5
INSERT INTO tiny (codigo) SELECT md5(random()::text) FROM generate_series(1, 100000);
ANALYZE tiny;

-- Paso 6
EXPLAIN (ANALYZE) SELECT * FROM tiny WHERE codigo = 'algun_codigo_real';

Index Scan using idx_tiny_codigo on tiny  (cost=0.42..8.44 rows=1 width=37) (actual time=0.045..0.048 rows=0 loops=1)
  Index Cond: (codigo = 'algun_codigo_real'::text)

Resumen y siguiente paso

En esta cápsula aprendiste:

• Un B-tree es un árbol balanceado ordenado con hojas enlazadas. Permite igualdad, rango y orden eficientes en O(log n).
• B-tree NO sirve para sufijo (LIKE '%foo'), <>, funciones sobre la columna (lower(x) = ...), ni operadores no-B-tree (@>, FTS).
• Selectividad es la fracción de la tabla que devuelve un predicado. Cardinalidad es cuántos valores distintos tiene una columna.
• El planner conoce la distribución gracias a pg_stats, poblada por ANALYZE y autovacuum. Decide usar el índice o no según la selectividad estimada del predicado con el valor específico.
• El planner puede ignorar un índice "perfectamente válido" por: alta selectividad, estadísticas viejas, tabla pequeña, función envolviendo la columna, tipo no coincidente, operador incompatible, configuración (random_page_cost).
• Crear el índice no garantiza que se use. Validas siempre con EXPLAIN (ANALYZE).

Antes de avanzar, deberías poder:

• Explicar por qué WHERE name LIKE '%tolkien' no aprovecha un índice B-tree estándar.
• Predecir, dada una columna y un valor, si el planner probablemente usará un índice (basándote en selectividad).
• Listar al menos 4 causas por las que el planner ignora un índice válido.
• Consultar pg_stats para ver cardinalidad y valores más comunes de una columna.

Siguiente cápsula — Composite indexes: orden y selectividad. Ya sabes cuándo un índice simple gana o pierde. La siguiente cápsula sube la apuesta: queries con múltiples filtros (WHERE a = X AND b = Y). ¿Dos índices separados, o uno composite? ¿En qué orden las columnas? Vas a aprender la leftmost prefix rule (la regla más malentendida del indexing) y a diseñar composites que el planner sí usa.

Recursos

1. Markus Winand — Use The Index, Luke! — "Anatomy of an Index" — la mejor explicación visual de cómo se estructura un B-tree, con diagramas. Lectura obligatoria.
2. PostgreSQL Documentation — Index Types — el capítulo oficial de tipos de índices en PostgreSQL 16.
3. PostgreSQL Documentation — Statistics Used by the Planner — cómo el planner usa pg_stats para tomar decisiones.
4. Hubert "depesz" Lubaczewski — "Index Scan vs Seq Scan" — casos reales con plans antes/después.
5. Bruce Momjian — "Inside the PostgreSQL Query Optimizer" (slides) — del core team. Cubre cómo el planner decide entre planes alternativos.
6. PostgreSQL Wiki — Slow Query Questions — checklist oficial de qué información incluir cuando reportas una query lenta. Útil como recordatorio de qué mirar.
7. Tom Lane on planner cost constants — explicación canónica de random_page_cost vs seq_page_cost y cuándo ajustarlos.

Módulo 3 — Database Performance & Query Tuning Guide