Optimizando Motores de Consulta: De Volcano a SIMD para Bases de Datos Analíticas

El problema fundamental que aborda este artículo es la ineficiencia de los motores de consulta de bases de datos relacionales tradicionales, como PostgreSQL, frente a las cargas de trabajo analíticas modernas. Diseñados en una era donde el I/O de disco era el principal cuello de botella, estos motores no están optimizados para el rendimiento de CPU y memoria, que son críticos en entornos donde los datasets caben en RAM o se procesan en grandes volúmenes. La tesis es que, mediante una serie de optimizaciones incrementales en el motor de consulta, es posible lograr mejoras de rendimiento de órdenes de magnitud, transformando un sistema de propósito general en uno altamente eficiente para OLAP.

La relevancia actual de este problema radica en la prevalencia de la computación in-memory y el aumento de la velocidad de los dispositivos de almacenamiento (NVMe), que han desplazado el cuello de botella del I/O de disco a la CPU y el ancho de banda de memoria. Esto ha creado una brecha de rendimiento significativa entre los sistemas heredados y las capacidades del hardware moderno, especialmente para consultas analíticas que implican escaneos masivos de datos. La optimización del motor de consulta se convierte así en un factor clave para explotar plenamente el potencial del hardware contemporáneo.

Arquitectura del Sistema

El motor de consulta de pgrust se basa inicialmente en una variación del "Volcano model", un patrón de diseño común en motores de bases de datos donde cada nodo del plan de consulta implementa una interfaz next() que devuelve una única fila. Este modelo, aunque simple y extensible, introduce una sobrecarga significativa debido a las llamadas a funciones virtuales y la falta de batching, lo que limita la eficiencia de la caché de CPU y el pipelining.

La primera optimización clave es la introducción del procesamiento por lotes (batching). En lugar de procesar una fila a la vez, el motor opera con bloques de datos (BATCH = 1024 filas). Esto reduce drásticamente la sobrecarga de llamadas a funciones y mejora la localidad de los datos, permitiendo un uso más eficiente de la caché. La implementación utiliza buffers en la pila para evitar asignaciones de memoria dinámicas, que son costosas. La siguiente mejora es la "fusión de operadores" (operator fusion), donde nodos de plan de consulta adyacentes y comúnmente ejecutados juntos (como un SeqScan y un SumAggregate) se combinan en un único nodo. Esto elimina la necesidad de copiar datos entre buffers intermedios y permite al compilador generar código más eficiente, similar a un bucle for directo. Finalmente, se integra el uso de instrucciones SIMD (Single Instruction, Multiple Data) para realizar operaciones en múltiples elementos de datos simultáneamente. Esto explota las capacidades de paralelismo a nivel de instrucción de las CPUs modernas, como ARM AArch64, para acelerar aún más las agregaciones y transformaciones de datos. La combinación de estas técnicas permite que el motor de consulta de pgrust supere significativamente el rendimiento de motores tradicionales.

use std::hint::black_box;
trait Node {
    fn next(&mut self) -> Option<f64>;
}
struct SeqScan<'a> {
    table: &'a [f64],
    pos: usize,
}
impl Node for SeqScan<'_> {
    fn next(&mut self) -> Option<f64> {
        if self.pos >= self.table.len() {
            return None; // end of table
        }
        let value = self.table[self.pos];
        self.pos += 1;
        Some(value)
    }
}
struct SumAggregate<'a> {
    child: Box<dyn Node + 'a>,
    total: f64,
    done: bool,
}
impl Node for SumAggregate<'_> {
    fn next(&mut self) -> Option<f64> {
        if self.done {
            return None;
        }
        while let Some(value) = self.child.next() {
            self.total += value;
        }
        self.done = true;
        Some(self.total)
    }
}
let table: Vec<f64> = (1..=500_000_000usize).map(|i| i as f64).collect();
let mut plan = SumAggregate {
    child: black_box(Box::new(SeqScan { table: &table, pos: 0 })),
    total: 0.0,
    done: false,
};
let sum = plan.next().unwrap();

const BATCH: usize = 1024;
trait BatchNode {
    fn next_batch(&mut self, out: &mut [f64; BATCH]) -> usize;
}
struct BatchSeqScan<'a> {
    table: &'a [f64],
    pos: usize,
}
impl BatchNode for BatchSeqScan<'_> {
    fn next_batch(&mut self, out: &mut [f64; BATCH]) -> usize {
        let n = (self.table.len() - self.pos).min(BATCH);
        out[..n].copy_from_slice(&self.table[self.pos..self.pos + n]);
        self.pos += n;
        n
    }
}
struct BatchSumAggregate<'a> {
    child: Box<dyn BatchNode + 'a>,
    total: f64,
}
impl BatchSumAggregate<'_> {
    fn run(&mut self) -> f64 {
        let mut buf = [0.0f64; BATCH];
        loop {
            let n = self.child.next_batch(&mut buf);
            if n == 0 {
                break;
            }
            for &value in &buf[..n] {
                self.total += value;
            }
        }
        self.total
    }
}
let mut plan = BatchSumAggregate {
    child: black_box(Box::new(BatchSeqScan { table: &table, pos: 0 })),
    total: 0.0,
};
let sum = plan.run();

struct SumAggregateSequentialScan<'a> {
    table: &'a [f64],
    done: bool,
}
impl Node for SumAggregateSequentialScan<'_> {
    fn next(&mut self) -> Option<f64> {
        if self.done {
            return None;
        }
        self.done = true;
        let mut total = 0.0;
        for &value in self.table {
            total += value;
        }
        Some(total)
    }
}

#[cfg(target_arch = "aarch64")]
struct SumAggregateSequentialScanSimd<'a> {
    table: &'a [f64],
    done: bool,
}
#[cfg(target_arch = "aarch64")]
impl Node for SumAggregateSequentialScanSimd<'_> {
    fn next(&mut self) -> Option<f64> {
        if self.done {
            return None;
        }
        self.done = true;
        use std::arch::aarch64::*;
        let mut acc = unsafe { [vdupq_n_f64(0.0); 4] };
        let (chunks, rest) = self.table.as_chunks::<8>();
        for chunk in chunks {
            for lane in 0..4 {
                unsafe {
                    let v = vld1q_f64(chunk.as_ptr().add(2 * lane));
                    acc[lane] = vaddq_f64(acc[lane], v);
                }
            }
        }
        let mut tail = 0.0;
        for &value in rest {
            tail += value;
        }
        Some(unsafe { let s01 = vaddq_f64(acc[0], acc[1]); let s23 = vaddq_f64(acc[2], acc[3]); vaddvq_f64(vaddq_f64(s01, s23)) + tail })
    }
}

Fundamentos Teóricos

El "Volcano model" fue popularizado por Goetz Graefe en su paper "The Volcano Optimizer Generator: Extensibility and Efficient Query Optimization" (1993). Este modelo se caracteriza por su interfaz uniforme next() para todos los operadores, lo que facilita la extensibilidad y la optimización de planes de consulta. Sin embargo, su diseño de procesamiento tupla a tupla introduce una sobrecarga inherente que se ha convertido en un cuello de botella en la era de la computación in-memory.

La evolución hacia el procesamiento por lotes y la fusión de operadores se alinea con los principios de los motores de bases de datos vectorizados y compilados, como se discute en trabajos sobre sistemas como MonetDB o HyPer. Estos sistemas buscan reducir el overhead de llamadas a funciones y mejorar la localidad de caché, a menudo mediante la generación de código (JIT compilation) para fusionar operadores y explotar el paralelismo a nivel de instrucción. El uso de SIMD es una aplicación directa de la arquitectura de computadoras y se ha estudiado extensamente en el contexto de la optimización de algoritmos numéricos y de procesamiento de datos, como se ve en la literatura sobre optimización de compiladores y diseño de procesadores.