Cómo funcionan los query engines 1. El pequeño compilador detrás de cada query SQL

La mayoría usamos SQL todo el tiempo y, aun así, tratamos al motor del otro lado como una caja negra. Escribimos una query, presionamos enter y esperamos. Si corre rápido, perfecto. Si corre lento, reescribimos el SQL, agregamos un índice o miramos EXPLAIN ANALYZE esperando que el plan se explique solo.

Lo interesante es que las tripas del sistema no son tan ajenas. Un query engine se parece mucho a un compilador: parsea texto, construye una representación intermedia, la reescribe para mejorarla y después ejecuta el resultado. La diferencia es que, en vez de producir un binario para mañana, produce un plan de ejecución para ahora mismo, contra tus datos. Cuando lo miras así, muchas cosas que parecían magia empiezan a verse bastante razonables.

Este post recorre ese pipeline de punta a punta. No como una explicación abstracta, sino en Rust, con código real, contra un CSV pequeño, viendo qué produce cada etapa.

La versión de cinco segundos

#

Escribes esto:

SELECT department, AVG(salary) as avg_salary
FROM employees
WHERE hire_date > '2020-01-01'
GROUP BY department
ORDER BY avg_salary DESC

Entre tú y los resultados, pasan cuatro cosas:

1. Parsing. El texto SQL se convierte en un árbol sintáctico. Pura gramática, sin significado.
2. Planificación lógica. El árbol sintáctico se convierte en un árbol de operaciones relacionales. El motor verifica que employees existe, que salary es un número y que AVG es un agregado válido. Esto es type checking para datos.
3. Optimización. El plan se reescribe. Los filtros se mueven más cerca de la fuente de datos. Las columnas que nadie pidió se descartan antes de salir del disco. La query computa lo mismo, pero más rápido.
4. Ejecución física. El plan abstracto se convierte en operadores concretos: un scanner de CSV, una agregación hash, un sort. Los datos fluyen a través de estos operadores en lotes de registros columnares, y los resultados salen por el otro extremo.

Ese es todo el truco. Cada query engine que hayas usado, desde SQLite hasta Spark o BigQuery, implementa alguna variación de este pipeline. Los detalles cambian. La forma no.

Por qué importa si escribes SQL en tu día a día

#

La mayoría de los desarrolladores interactúan con query engines como la mayoría de los conductores interactúan con motores: pisan el acelerador y esperan que el auto se mueva. Eso funciona hasta que algo sale mal. Una query que tardaba 200 milisegundos ayer hoy tarda 40 segundos. El dashboard hace timeout. Alguien te escribe. Ahí necesitas un modelo mental, no suerte.

Si entiendes el pipeline, puedes leer la salida de EXPLAIN ANALYZE y ver exactamente dónde está el problema. Un sequential scan donde debería haber un index lookup. Un nested loop join donde un hash join sería tres órdenes de magnitud más rápido. Cincuenta columnas leyéndose de un archivo Parquet cuando solo se necesitan tres.

Si no entiendes el pipeline, reescribes el SQL, cruzas los dedos y lo ejecutas de nuevo. A veces funciona. A veces se te va la tarde.

Entender las internas no te convierte en ingeniero de bases de datos. Simplemente te da una mejor forma de pensar cuando una query se pone rara.

El dataset mínimo que vamos a usar

#

Cada ejemplo en este post corre contra el mismo archivo CSV. Ocho empleados, cinco columnas, nada sofisticado:

id,name,department,salary,hire_date
1,Alice,Engineering,95000,2021-03-15
2,Bob,Sales,87000,2019-06-01
3,Carol,Engineering,102000,2022-01-10
4,Dave,Marketing,78000,2018-11-20
5,Eve,Engineering,110000,2023-05-01
6,Frank,Sales,92000,2020-09-15
7,Grace,Marketing,85000,2021-07-22
8,Hank,Engineering,98000,2017-03-01

Guárdalo como employees.csv. Vamos a empujar este archivo diminuto por la misma maquinaria que otros motores usan con tablas de millones o miles de millones de filas.

Etapa 1: Parsing

#

Un string SQL es solo texto. Antes de que el motor pueda hacer algo significativo, necesita estructura. El parser convierte caracteres crudos en un arbol de nodos que representan la gramatica de la query, no su significado. No sabe si employees es una tabla real. No sabe si salary es un numero. Verifica la sintaxis, nada mas.

DataFusion delega este trabajo a sqlparser-rs, uno de los parsers SQL mas usados en el ecosistema Rust. Podemos llamarlo directamente:

use sqlparser::dialect::GenericDialect;
use sqlparser::parser::Parser;

fn main() {
    let sql = "SELECT department, AVG(salary) \
               FROM employees \
               WHERE hire_date > '2020-01-01' \
               GROUP BY department \
               ORDER BY AVG(salary) DESC";

    let dialect = GenericDialect {};
    let ast = Parser::parse_sql(&dialect, sql).unwrap();

    println!("{:#?}", ast);
}

Lo que sale es un enum de Rust profundamente anidado. Un Statement::Query conteniendo un Select con items de proyeccion, un TableWithJoins, una expresion WHERE, una clausula GROUP BY, y una lista ORDER BY. La estructura refleja la gramatica de SQL, no la semantica. Es la misma relacion que tiene el crate syn de Rust con el codigo fuente: fiel al texto, ciego al significado.

Si escribes SELECT foo FROM bar WHERE baz > 42, el parser lo acepta felizmente aunque ninguno de esos nombres exista en ninguna tabla. Esa conversación incómoda ocurre en la siguiente etapa.

Etapa 2: Planificación lógica

#

El AST entra al planner. El planner tiene algo que el parser no tenia: un catalogo, un registro de tablas, sus schemas y los tipos de sus columnas. Ahora el motor puede responder preguntas. Existe employees? Si. Tiene una columna llamada salary? Si. Es salary un tipo que soporta AVG? Si. Es hire_date comparable con un literal string? Podemos coercionar eso.

La salida es un plan logico: un arbol de operadores relacionales.

Sort: AVG(salary) DESC
  Projection: department, AVG(salary)
    Aggregate: groupBy=[department], aggr=[AVG(salary)]
      Filter: hire_date > '2020-01-01'
        Scan: employees

Leelo de abajo hacia arriba, como un call stack. Los datos empiezan en Scan, fluyen hacia arriba a traves de Filter (que descarta filas contratadas antes de 2020), hacia Aggregate (que agrupa por departamento y computa promedios), a traves de Projection (que selecciona las columnas de salida), y finalmente hacia Sort.

Cada nodo en este arbol conoce su schema de salida: que columnas produce y de que tipos son. El nodo Filter pasa el mismo schema que su entrada. El nodo Aggregate produce dos columnas: department (Utf8) y AVG(salary) (Float64). Esta propagacion de schema es como el motor captura errores como referenciar una columna que fue eliminada por una proyeccion arriba.

El plan logico describe que computar. No dice nada sobre como. No hay mencion de hash tables, ni de algoritmos de sort, ni de tamanos de lote. Esa separacion es el punto completo: el optimizador puede reorganizar este arbol libremente, y el planner fisico puede elegir el mejor algoritmo para cada nodo de forma independiente.

Etapa 3: Optimización

#

El plan logico funciona, pero es ingenuo. Lee las cinco columnas del CSV aunque la query solo necesita tres (department, salary, hire_date). Un plan mas inteligente le diria al scanner que omita id y name por completo.

Esto es lo que hace el optimizador. Aplica reglas de reescritura que transforman el plan en uno equivalente pero mas eficiente. La palabra clave es equivalente: el optimizador nunca cambia lo que la query retorna, solo que tan rapido llega ahi.

Las reglas que mas importan en la practica:

Projection push-down. Recorre el arbol del plan, recolecta cada nombre de columna que algun nodo realmente referencia, y empuja esa lista hacia abajo al scan. Si el scan lee un archivo Parquet con 50 columnas y la query solo toca 3, esta unica regla reduce el I/O en un 94%. Para archivos CSV, el ahorro viene de no construir arrays de Arrow para columnas no utilizadas.

Predicate push-down. Mueve filtros lo mas cerca posible de la fuente de datos. Si un filtro solo referencia columnas de un lado de un join, lo empuja debajo del join para que se ejecute antes de la operacion costosa. Para fuentes de datos que lo soportan (como Parquet con estadisticas de row group), el predicado puede saltear chunks enteros de datos sin leerlos.

Constant folding. Reemplaza 2 + 3 con 5 en tiempo de planificacion. Reemplaza WHERE 1 = 1 con nada. Ahorros pequenos, pero se componen.

Join reordering. Cuando se hacen joins de tres o mas tablas, el orden importa enormemente. Hacer join de una tabla de lookup de 10 filas con una tabla de hechos de mil millones primero produce un resultado intermedio mucho mas pequeno que al reves.

En DataFusion, podemos ver el antes y el despues:

// Antes de la optimizacion
let naive_plan = ctx.sql(sql).await?.into_unoptimized_plan();
println!("{}", naive_plan.display_indent());

// Despues de la optimizacion
let optimized = ctx.state().optimize(&naive_plan)?;
println!("{}", optimized.display_indent());

El plan optimizado se ve parecido, pero con una diferencia crítica en la base: el scan ahora lista solo las columnas que necesita. Para nuestro CSV pequeño, la diferencia es mínima. Para una tabla Parquet de producción con cientos de columnas, puede significar leer 50 MB en vez de 2 GB.

El libro de Andy Grove reporta un speedup de 5x solo con projection push-down en un CSV de 17 columnas. En Parquet, las ganancias son tipicamente mayores porque el formato de archivo soporta lecturas realmente a nivel de columna: chunks de columna enteros nunca se descomprimen.

Etapa 4: Ejecucion fisica

#

El plan logico optimizado es abstracto. Dice “agregar por departamento” pero no dice como. Una hash table? Un approach basado en sort? El planner fisico toma estas decisiones y produce un arbol de operadores concretos.

let physical_plan = ctx.state()
    .create_physical_plan(&optimized)
    .await?;
println!("{}", datafusion::physical_plan::displayable(physical_plan.as_ref())
    .indent(true));

La salida nombra operadores reales: CsvExec lee el archivo, CoalesceBatchesExec fusiona lotes pequenos para eficiencia, AggregateExec construye un hash map de departamento a promedio en ejecucion, y SortExec ordena los resultados.

Estos operadores se comunican pasando Arrow RecordBatches: chunks de datos columnares, tipicamente entre 1,024 y 65,536 filas. Los datos nunca se convierten en un Vec<Row>. Se quedan en formato columnar desde el disco hasta la salida, que es por lo que los query engines modernos pueden procesar millones de filas por segundo en un solo core. Exploraremos Arrow en detalle en el proximo post.

El pipeline completo en un programa

#

Aca esta todo conectado. Agrega estas dependencias:

[dependencies]
datafusion = "46"
tokio = { version = "1", features = ["full"] }

Y el codigo:

use datafusion::prelude::*;

#[tokio::main]
async fn main() -> datafusion::error::Result<()> {
    let ctx = SessionContext::new();

    ctx.register_csv("employees", "employees.csv", CsvReadOptions::new())
        .await?;

    let sql = "SELECT department, AVG(salary) as avg_salary \
               FROM employees \
               WHERE hire_date > '2020-01-01' \
               GROUP BY department \
               ORDER BY avg_salary DESC";

    // Etapa 2: Plan logico
    let logical_plan = ctx.sql(sql).await?.into_unoptimized_plan();
    println!("=== Plan Logico ===");
    println!("{}\n", logical_plan.display_indent());

    // Etapa 3: Plan optimizado
    let optimized_plan = ctx.state().optimize(&logical_plan)?;
    println!("=== Plan Optimizado ===");
    println!("{}\n", optimized_plan.display_indent());

    // Etapa 4: Plan fisico
    let physical_plan = ctx.state()
        .create_physical_plan(&optimized_plan)
        .await?;
    println!("=== Plan Fisico ===");
    println!("{}\n", datafusion::physical_plan::displayable(physical_plan.as_ref())
        .indent(true));

    // Ejecutar
    let df = ctx.sql(sql).await?;
    println!("=== Resultados ===");
    df.show().await?;

    Ok(())
}

Ejecútalo. Vas a ver cuatro salidas, una por cada etapa. El plan lógico lee todas las columnas. El plan optimizado lee tres. El plan físico nombra operadores concretos. Después aparecen los resultados:

+-------------+------------+
| department  | avg_salary |
+-------------+------------+
| Engineering | 102333.33  |
| Sales       | 92000.00   |
| Marketing   | 85000.00   |
+-------------+------------+

Hank (contratado en 2017), Bob (2019) y Dave (2018) fueron filtrados antes de que la agregacion los tocara. El optimizador empujo el predicado debajo del aggregate. Projection push-down elimino id y name antes de que salieran del scanner. Tres numeros aparecieron en pantalla. Detras de ellos, un pequeno compilador hizo su trabajo.

El compilador escondido en tu base de datos

#

La analogia no es una metafora. Es una correspondencia estructural:

Un compilador como rustc va de codigo fuente a codigo maquina a traves de multiples representaciones intermedias, cada una mas concreta que la anterior. Un query engine va de texto SQL a operadores ejecutables a traves de la misma progresion. La diferencia es de ciclo de vida: el compilador produce un artefacto que se ejecuta muchas veces; el query engine produce un plan que se ejecuta una vez y se descarta.

Por eso las mismas tecnicas que hicieron rapidos a los compiladores en los 70, eliminacion de codigo muerto, propagacion de constantes, reordenamiento de loops, hacen rapidos a los query engines hoy. Y por eso la gente que construye query engines tiende a tener el mismo background que la gente que construye compiladores: piensan en arboles, transformaciones y sistemas de tipos.

Que sigue

#

Trazamos el pipeline desde texto SQL hasta resultados. Vimos al parsing producir un arbol sintactico, al planning producir un arbol logico, a la optimizacion reescribir ese arbol, y a la ejecucion convertirlo en lotes de datos columnares fluyendo a traves de operadores concretos.

Pero nos salteamos una pregunta que esta debajo de todo: por que columnar? Por que estos operadores pasan datos como columnas en vez de filas? La respuesta involucra cache lines, instrucciones SIMD, y un formato de memoria llamado Apache Arrow que se ha convertido en la lingua franca del procesamiento de datos moderno.

Ese es el proximo post.

Referencia:

• Apache DataFusion
• sqlparser-rs
• How Query Engines Work por Andy Grove
• Apache Arrow