Análise da estrutura do mecanismo SQL

• O mecanismo SQL é a camada lógica do banco de dados, operando entre o cliente e o armazenamento
• Explicação detalhada dos principais processos do mecanismo SQL: parsing, binding, simplificação de plano, exploração de joins e avaliação de custo, execução e spooling de resultados
  • Parsing converte a consulta SQL em uma árvore sintática abstrata estruturada (AST)
  • Binding faz a correspondência entre os campos da AST e os símbolos do catálogo atual do banco de dados
  • Simplificação de plano normaliza sintaxes SQL complexas em um formato simplificado para acelerar a execução
  • Exploração de plano busca diferentes variações de joins, agregações e funções de janela para encontrar o melhor plano de execução
  • Execução e spooling de resultados convertem o plano final em um formato executável e retornam os resultados ao cliente

---

Visão geral do mecanismo SQL

• O mecanismo SQL é uma camada intermediária lógica entre as requisições do cliente e o armazenamento de dados
• Etapas principais
  • Parsing: converte a consulta em uma AST (árvore sintática abstrata)
  • Binding: conecta os identificadores da AST aos símbolos do catálogo do banco de dados
  • Plan Simplification: simplifica várias sintaxes SQL em uma forma de plano padronizada
  • Join Exploration & Costing: explora diferentes ordens de join e avalia seus custos
  • Execution: executa a consulta usando o plano de execução ideal
  • Spooling Results: retorna os resultados ao cliente

Parsing

• Parsing é o processo de tokenizar a consulta de entrada e convertê-la em uma AST
• Um parser recursivo à direita é mais fácil de entender e depurar, mas consome mais memória de pilha
• Um parser recursivo à esquerda (baseado em Yacc) é mais eficiente em memória, mas exige lógica mais complexa
• O Dolt usa um parser recursivo à esquerda para oferecer parsing rápido
• Quando o parsing é bem-sucedido, a estrutura da AST corresponde às regras do Yacc

Binding

• Binding é o processo de ligar os campos da AST aos símbolos reais de tabelas e colunas do banco de dados
• Conceitos principais
  • Definição de tabela: atua como a fonte dos dados
  • Definição de coluna: referencia uma coluna específica da fonte da tabela
  • Alias: usa um valor escalar tanto como origem quanto como destino
  • Subconsulta escalar: compartilha o escopo pai e realiza a vinculação de nomes
• Como resultado do binding, são gerados nós do plano de execução no formato sql.Node

Simplificação de plano

• É o processo de converter várias expressões SQL em uma forma normalizada para ajudar na otimização da execução
• Otimizações representativas
  • Filter Pushdown: remove linhas desnecessárias
  • Column Pruning: remove colunas desnecessárias
• Também realiza otimização de planos de join por meio de transformações como subquery decorrelation

Coerção de tipos

• Coerção de tipos é o processo de converter automaticamente o tipo de uma expressão conforme o contexto
• O tipo pode variar conforme o contexto, como em WHERE e INSERT
• O Dolt está tratando a conversão de tipos de forma gradual na etapa de binding

Exploração de joins

• Exploração de joins é o processo de gerar e revisar várias ordens possíveis de join
• Duas estratégias de exploração
  • Backtracking top-down: explora apenas ordens de join válidas
  • Programação dinâmica bottom-up (DP): tenta todas as combinações para encontrar a melhor ordem de join
• Usa uma estrutura Memo para gerenciar estados intermediários com eficiência

Dependências funcionais

• O custo pode aumentar drasticamente em joins com 5 ou mais tabelas
• Aproveitar relações 1:1, como joins baseados em chave primária (PK), pode reduzir o custo da exploração
• A otimização prioriza LOOKUP_JOIN

Resumo da representação intermediária (IR Intermission)

• Resumo das 3 etapas de IR vistas até aqui
  • AST: organização dos tokens
  • Binding de escopo: validação de referências de colunas
  • Memo: representação para exploração de joins e avaliação de custo

Avaliação de custo de joins

• Avaliação de custo de joins é o processo de estimar o custo de execução para todos os planos possíveis
• Fatores de custo
  • Tamanho da tabela de entrada
  • Tamanho da tabela de saída
  • Tipo de operador de join (LOOKUP_JOIN, HASH_JOIN etc.)
• O Dolt avalia os custos com base em estatísticas precisas de tabelas (histogramas)

Join hints

• O sistema tenta aplicar primeiro a estratégia de join indicada pelo usuário
• Hints contraditórios ou inadequados são ignorados

Execução

• Converte o plano ideal em uma estrutura de iteradores (Volcano Iterator) realmente executável
• Características
  • Iteradores não materializantes (non-materializing): retornam linhas imediatamente
  • Iteradores materializantes (materializing): coletam todas as linhas antes de retornar
• As referências de coluna são mapeadas com base em offsets de índice antes da execução

I/O e spooling de resultados

• Converte os resultados da execução para o formato do protocolo MySQL e os entrega ao cliente
• Em alguns casos, a leitura dos resultados é otimizada diretamente na camada de armazenamento chave-valor (KV)
• Processamento em lote (batch) e reutilização de buffers melhoram a velocidade e a eficiência de memória

Próximos passos

• O Dolt usa, por padrão, execução baseada em linhas (row-based execution) em um servidor local
• Ele dá suporte à definição do melhor plano de execução usando 3 etapas de representação intermediária (IR), como AST, binding baseado em escopo e exploração de joins por meio da estrutura Memo
• Define a melhor estratégia de join por meio de busca da ordem de joins (Join Search) e avaliação de custo de joins (Join Costing)
• No futuro, planeja melhorias de desempenho por meio de integração de IR e otimização da reutilização de memória