Análisis de la estructura del motor SQL

• El motor SQL es la capa lógica de la base de datos, y opera entre el cliente y el almacenamiento
• Explicación detallada de los procesos principales del motor SQL: parsing, binding, simplificación del plan, exploración de joins y evaluación de costos, ejecución y spooling de resultados
  • El parsing convierte una consulta SQL en un árbol de sintaxis abstracta (AST) estructurado
  • El binding hace coincidir los campos del AST con los símbolos del catálogo actual de la base de datos
  • La simplificación del plan normaliza la sintaxis compleja de SQL a un formato simplificado para acelerar la ejecución
  • La exploración del plan recorre distintas variantes de joins, agregaciones y funciones de ventana para encontrar el mejor plan de ejecución
  • La ejecución y el spooling de resultados convierten el plan final a un formato ejecutable y devuelven los resultados al cliente

---

Resumen del motor SQL

• El motor SQL es una capa intermediaria lógica entre las solicitudes del cliente y el almacenamiento de datos
• Etapas principales
  • Parsing: convierte la consulta en un AST (árbol de sintaxis abstracta)
  • Binding: conecta los identificadores del AST con los símbolos del catálogo de la base de datos
  • Plan Simplification: simplifica diversas sintaxis SQL a una forma de plan estandarizada
  • Join Exploration & Costing: explora distintos órdenes de joins y evalúa sus costos
  • Execution: ejecuta la consulta usando el plan de ejecución óptimo
  • Spooling Results: devuelve los resultados al cliente

Parsing

• El parsing es el proceso de tokenizar la consulta de entrada y convertirla a un AST
• Un parser recursivo por la derecha es fácil de entender y depurar, pero usa mucha memoria de stack
• Un parser recursivo por la izquierda (basado en Yacc) es más eficiente en memoria, pero requiere lógica más compleja
• Dolt usa un parser recursivo por la izquierda para ofrecer parsing rápido
• Si el parsing tiene éxito, la estructura del AST coincide con las reglas de Yacc

Binding

• El binding es el proceso de conectar los campos del AST con las tablas y columnas reales de la base de datos
• Conceptos principales
  • Definición de tabla: actúa como fuente de los datos
  • Definición de columna: referencia una columna específica desde la fuente de tabla
  • Alias: usa un valor escalar tanto como fuente como destino
  • Subconsulta escalar: comparte el scope padre y realiza el binding de nombres
• Como resultado del binding, se generan nodos del plan de ejecución en formato sql.Node

Simplificación del plan

• Es el proceso de convertir varias expresiones SQL a una forma normalizada para ayudar a optimizar la ejecución
• Optimizaciones representativas
  • Filter Pushdown: elimina filas innecesarias
  • Column Pruning: elimina columnas no necesarias
• También realiza optimización de planes de join mediante transformaciones como subquery decorrelation

Coerción de tipos

• La coerción de tipos es el proceso de convertir automáticamente el tipo de una expresión según el contexto
• El tipo puede variar según el contexto, como en WHERE o INSERT
• Dolt está manejando la conversión de tipos gradualmente en la etapa de binding

Exploración del plan

• La exploración de joins es el proceso de generar y revisar distintos órdenes de joins
• Dos estrategias de exploración
  • Backtracking top-down: explora solo órdenes de join válidos
  • Programación dinámica bottom-up (DP): prueba todas las combinaciones para encontrar el orden de join óptimo
• Usa una estructura Memo para administrar de forma eficiente los estados intermedios

Dependencias funcionales

• Al hacer joins de 5 o más tablas, el costo puede aumentar drásticamente
• Aprovechar relaciones 1:1, como joins basados en claves primarias (PK), permite reducir el costo de exploración
• Se optimiza dando prioridad a LOOKUP_JOIN

Intermedio sobre la representación intermedia (IR)

• Resumen de las 3 etapas de IR vistas hasta ahora
  • AST: organización de tokens
  • Binding de scope: validación de referencias de columnas
  • Memo: representación para exploración de joins y evaluación de costos

Evaluación de costos de joins

• La evaluación de costos de joins es el proceso de estimar el costo de ejecución para todos los planes posibles
• Factores de costo
  • Tamaño de las tablas de entrada
  • Tamaño de la tabla de resultados
  • Tipo de operador de join (LOOKUP_JOIN, HASH_JOIN, etc.)
• Dolt evalúa los costos con base en estadísticas precisas de tablas (histogramas)

Join hints

• Intenta aplicar primero la estrategia de join según los hints proporcionados por el usuario
• Los hints contradictorios o inadecuados se ignoran

Ejecución

• Convierte el plan óptimo a una estructura de iterador (Volcano Iterator) realmente ejecutable
• Características
  • Iterador no materializante (non-materializing): devuelve filas de inmediato
  • Iterador materializante (materializing): recopila todas las filas antes de devolverlas
• Las referencias de columnas se mapean con base en offsets de índice antes de la ejecución

I/O y spooling de resultados

• Convierte los resultados de ejecución al formato del protocolo MySQL y los entrega al cliente
• En algunos casos, también optimiza leyendo los resultados directamente desde la capa de almacenamiento clave-valor (KV)
• Mejora la velocidad de procesamiento y la eficiencia de memoria mediante procesamiento por lotes (batch) y reutilización de buffers

Planes a futuro

• Dolt usa por defecto ejecución basada en filas (row-based execution) en un servidor local
• Aprovecha 3 etapas de representación intermedia (IR), como AST, binding basado en scope y exploración de joins mediante la estructura Memo, para ayudar a construir el mejor plan de ejecución
• Determina la estrategia de join óptima mediante Join Search y Join Costing
• A futuro planea mejoras de rendimiento mediante integración de IR y optimización de reutilización de memoria