Mejora del rendimiento en escenarios de ordenamiento con límite

En operaciones que combinan ORDER BY y LIMIT, el motor de base de datos normalmente aplica un nodo de calsificación completo, lo cual puede ser costoso en términos de CPU y memoria. Sin embargo, existen estrategias eficientes para reducir esta carga, especialmente cuando solo se requeiren las primeras N filas. #### Uso del algoritmo Top-N Heap Sort

Cuando una consulta incluye ORDER BY ... LIMIT N (o su equivalente FETCH FIRST N ROWS ONLY), PostgreSQL puede aplicar una optimización conocida como heurística top-N, que evita ordenar todo el conjunto de resultados. Condiciones necesarias:

• La cláusula debe contener LIMIT N sin OFFSET, o con OFFSET 0.
• El planificador debe garantizar que alcanza con obtener los primeros N elementos según el criterio de orden.

Si se cumplen estas condiciones, el plan muestra en el nodo Sort la anotación use top-N heuristic.

Implementación basada en montículo

El sistema construye internamente un montículo (heap) de tamaño fijo N: - Para ASC: utiliza un montículo mínimo. Las filas mayores o iguales al tope se descartan.

• Para DESC: emplea un montículo máximo. Solo se conservan las filas menores o iguales al tope.

El proceso sigue estos pasos: 1. Inicializa el montículo con las primeras N filas. 2. Para cada fila restante: si mejora respecto al tope, reemplaza al tope y reordena el montículo. 3. Al final, extrae y ordena las N filas almacenadas.

Este enfoque reduce drásticamente el uso de recursos. Por ejemplo, mantener 10 filas de ~48 bytes implica aproximadamente 27 KiB de memoria, frente a los megabytes necesarios para ordenar 50 mil registros completos. ##### Diferencia entre costo estimado y real

Aunque el planificador estima el costo como si se realizara una ordenación completa — usando la fórmula N × log₂(N), donde N es el número total de filas —, la complejidad real es N × log₂(n), siendo n el valor del límite. Esto provoca una sobreestimación significativa del costo, mientras que el tiempo de ejecución real puede ser tan bajo como 1.4 ms. ##### Comparación con escaneo de índice

Si existe un índice compatible con la cláusula ORDER BY, el optimizador prefiere un Index Scan seguido de LIMIT, logrando una complejidad cercana a O(n). Esta estrategia es más eficiente que cualquier variante de ordenación, ya que accede directamente a los datos en el orden deseado. ``` DROP TABLE IF EXISTS measurements; CREATE TABLE measurements ( id serial PRIMARY KEY, value integer NOT NULL, data char(48) DEFAULT 'x' );

INSERT INTO measurements(value) SELECT (random() * 100000)::int FROM generate_series(1, 50000);

-- Consulta con LIMIT: activa top-N heuristic EXPLAIN (ANALYZE) SELECT value, data FROM measurements ORDER BY value LIMIT 10;

Sin `LIMIT`, el plan cambia completamente: ```
EXPLAIN (ANALYZE)
SELECT value, data
FROM measurements
ORDER BY value; -- Ordenación completa

Este caso muestra métodos como quicksort o external sort con alto consumo de memoria o disco, demostrando el impacto negativo de no aprovechar la heurística top-N. #### Optimización mediante índices ordenados

Cuando el campo de orden está indexado, el motor puede evitar la operación Sort por completo. ``` CREATE INDEX measurements_value_idx ON measurements(value);

EXPLAIN (ANALYZE) SELECT value, data FROM measurements ORDER BY value LIMIT 10;

El plan resultante utiliza `Index Scan using measurements_value_idx`, eliminando el nodo de ordenación. Es más rápido y consume menos recursos. ##### Índices cubrientes para evitar accesos adicionales

Para maximizar el rendimiento, se puede crear un índice que incluya todos los campos seleccionados: ```
CREATE INDEX measurements_value_data_idx ON measurements(value, data);

Ventajas de este diseño: - Escaneo exclusivo de índice: No se accede a la tabla base (Index Only Scan).

• Menor presión sobre caché: Solo se cargan páginas de índice.
• Resistencia a actualizaciones HOT: Si no se modifica value, no se ganera nueva entrada de índice.

Desventajas: - Aumento del tamaño del índice: De ~16 bytes por fila a ~64 bytes. En tablas grandes (ej. 5M filas), esto implica pasar de 300 MiB a 1.2 GiB.

• Mayor sobrecarga en escritura: Cualquier cambio en data requiere actualizar el índice.
• Riesgo de mal uso por el optimizador: En consultas con condiciones WHERE, podría elegirse este índice ancho cuando uno más estrecho sería más eficiente.

Guía para decidir el tipo de índice

• Caso ideal para índice cubiente: Lecturas frecuentes, columnas no clave raramente modificadas.
• Preferir índice simple: Si hay alta concurrencia de escritura o cambios frecuentes en campos incluidos.
• No justificado: En tablas pequeñas (< 100K filas) con baja carga, el beneficio es marginal.

Limitaciones y casos no aplicables

La optimización mediante índice falla cuando:

• El orden de ORDER BY no coincide con el del índice (por ejemplo, mezcla ASC y DESC).
• La condición WHERE no involucra el prefijo del índice compuesto.

Ejemplo de incompatibilidad por dirección inversa: ``` CREATE TABLE metrics ( x int NOT NULL, y int NOT NULL );

CREATE INDEX idx_x_y_asc ON metrics(x ASC, y ASC);

-- Compatible: mismo orden EXPLAIN SELECT * FROM metrics ORDER BY x ASC, y ASC LIMIT 10;

-- Incompatible: segundo campo en DESC EXPLAIN SELECT * FROM metrics ORDER BY x ASC, y DESC LIMIT 10;

Otro caso común de fallo: filtro en columna no líder del índice. ```
CREATE TABLE transactions (
    tx_id         bigserial PRIMARY KEY,
    customer_id   int,
    timestamp     timestamptz,
    amount        numeric,
    state         smallint
);

CREATE INDEX idx_customer_time ON transactions(customer_id, timestamp);

-- No usa índice para ordenar: state no está en el índice
EXPLAIN SELECT *
FROM transactions
WHERE state = 1
ORDER BY timestamp DESC
LIMIT 10;

En este caso, aunque se necesita orden cronológico reciente, el índice no puede usarse porque la condición WHERE state = 1 no corresponde al primer campo del índice. #### Conclusión práctica

Las optimizaciones para ORDER BY ... LIMIT dependen críticamente del diseño del índice y de la estructura de la consulta. El uso adecuado de índices simples, compuestos o cubrientes permite transformar operaciones costosas en accesos directos y eficientes.