Efficient Query Rewrite Rule Discovery via Standardized Enumeration and Learning-to-Rank(extend)

O artigo apresenta o SLER, um sistema escalável que combina enumeração de templates padronizados com uma abordagem de aprendizado para ranqueamento para descobrir regras de reescrita de consultas de forma eficiente, superando limitações de redundância e escalabilidade e gerando um repositório de mais de um milhão de regras validadas em cenários reais.

O essencial

Imagine que você tem uma cozinha gigante (o banco de dados) onde milhões de pratos (consultas SQL) são preparados todos os dias. O objetivo é fazer esses pratos o mais rápido e saboroso possível.

Por anos, os cozinheiros (os otimizadores de banco de dados) usavam um livro de receitas antigo e manual. Eles tinham que escrever cada regra de como cortar legumes ou misturar ingredientes à mão. O problema? O mundo mudou, os pedidos ficaram mais complexos, e o livro de receitas ficou pequeno demais. Muitos pratos chegavam à mesa com ingredientes desnecessários, demorando horas para serem feitos.

Recentemente, surgiu uma IA chamada WeTune que tentou automatizar a criação de novas regras. Ela funcionava como um robô que lia todas as combinações possíveis de receitas. O problema? O robô era lento e criava muitas regras inúteis. Se você pedisse um prato com 5 ingredientes, o robô levava anos para pensar em uma solução. Se o prato tivesse 6 ingredientes, ele desistia e dizia: "Isso é impossível".

É aqui que entra o SLER (o protagonista deste artigo), uma nova abordagem inteligente que resolve esse caos. Vamos entender como o SLER funciona usando analogias do dia a dia:

1. O Problema: A Montanha de Papel

Imagine que você precisa encontrar a melhor forma de organizar uma sala de estar.

• O jeito antigo (WeTune): Tentar mover cada móvel para cada canto possível, testar, medir, anotar, e depois tentar de novo. Para uma sala pequena, é ok. Para uma sala gigante com muitos móveis (consultas complexas), você passaria a vida toda movendo móveis e ainda assim não acharia a melhor disposição. Além disso, você criaria milhares de anotações repetidas (ex: "mover a cadeira 1cm para a esquerda" vs "mover a cadeira 1cm para a direita" — a diferença é irrelevante).

2. A Solução SLER: O "Template" e o "Filtro Inteligente"

O SLER usa três truques principais para ser rápido e eficiente:

A. O "Template" Padronizado (A Receita Base)

Em vez de olhar para cada prato individualmente, o SLER olha para a estrutura do prato.

• Analogia: Imagine que, em vez de escrever "Corte a cebola em rodelas finas", o SLER diz: "Toda vez que você vir uma cebola, corte-a em rodelas".
• O SLER cria modelos padronizados. Ele ignora detalhes específicos (como o nome do cliente ou o preço exato) e foca na forma como os ingredientes são combinados (o "esqueleto" da consulta).
• O Ganho: Isso elimina a redundância. Se duas receitas são quase idênticas, o SLER as trata como a mesma coisa, economizando tempo e evitando criar regras duplicadas.

B. O "Filtro de Prioridade" (O Chefe de Cozinha Experiente)

Aqui entra a parte mais genial: o Learning-to-Rank (Aprendizado para Classificação).

• Analogia: Imagine que você tem uma pilha de 1 milhão de ideias de como melhorar a cozinha. Você não tem tempo de testar todas. Então, você contrata um Chefe de Cozinha Experiente (um modelo de Inteligência Artificial treinado).
• Esse Chef olha para as ideias e diz: "Essa ideia aqui é brilhante, vamos testar primeiro. Aquela outra é chata, vamos ignorar".
• O SLER treina esse "Chef" com milhares de receitas reais. Quando surge uma nova consulta complexa, o SLER não tenta todas as possibilidades. Ele pede ao Chef para filtrar e mostrar apenas as 10 melhores ideias para testar.
• Resultado: Em vez de gastar 10 anos testando tudo, o SLER foca no que realmente importa, permitindo descobrir regras para pratos com 10, 12 ou até mais ingredientes (algo que o método antigo nem conseguia tentar).

C. O "Deduplicador" (O Organizador de Gavetas)

Mesmo com o filtro, às vezes surgem regras que são basicamente a mesma coisa com nomes diferentes.

• Analogia: É como ter 50 etiquetas de "Arroz" na sua despensa. O SLER tem um robô que entra, olha todas as etiquetas, joga fora as repetidas e deixa apenas uma etiqueta perfeita.
• Isso garante que o banco de dados não fique "pesado" com regras inúteis.

3. Os Resultados: O Que Isso Significa na Vida Real?

O SLER conseguiu fazer coisas que pareciam impossíveis:

1. Velocidade: Onde o método antigo levava dias ou anos para pensar em regras para pratos complexos, o SLER faz em horas ou minutos.
2. Escala: O SLER descobriu mais de 1 milhão de novas regras de otimização. O método anterior só conseguia lidar com pratos simples (até 4 ingredientes). O SLER lida com pratos gigantes (5, 6, 7+ ingredientes).
3. Qualidade: Ele não só achou mais regras, mas achou regras que realmente aceleram o sistema. Em testes, ele conseguiu simplificar consultas que o método antigo nem conseguia tocar.

Resumo em uma Frase

O SLER é como um sistema de navegação GPS inteligente para bancos de dados. Em vez de tentar todas as ruas possíveis (o que levaria uma eternidade), ele usa um mapa padronizado e um GPS experiente (IA) para te dizer exatamente qual é o caminho mais rápido, ignorando os atalhos que não levam a lugar nenhum.

Isso significa que, no futuro, quando você pedir algo na internet (como um relatório financeiro ou uma busca em uma rede social), o sistema conseguirá entregar o resultado muito mais rápido, porque "aprendeu" novas e melhores formas de fazer isso automaticamente.

Resumo técnico

1. O Problema

A reescrita de consultas (query rewriting) é fundamental para otimizar o desempenho de bancos de dados, transformando consultas mal estruturadas em formas mais eficientes antes da execução pelo otimizador. No entanto, os métodos existentes enfrentam desafios críticos:

• Espaço de Busca Exponencial e Redundância: Sistemas atuais, como o WeTune (estado da arte), utilizam uma abordagem de força bruta para enumerar pares de templates de planos de consulta. Isso resulta em um espaço de busca exponencial, gerando uma quantidade massiva de regras redundantes (mais de 90%) e triviais.
• Escalabilidade Limitada: Devido à complexidade computacional, métodos existentes conseguem enumerar regras apenas para consultas com até 4 nós (operadores). Consultas do mundo real, especialmente aquelas geradas por ferramentas ORM ou em cargas de trabalho complexas, frequentemente possuem 5 a 10+ nós, tornando os métodos atuais inadequados.
• Ineficiência de Verificação: A verificação de equivalência semântica (usando solvers SMT como Z3) consome a maior parte do tempo. Para templates com mais de 6 nós, o tempo de verificação torna-se impraticável (estimado em anos para 6 nós em máquinas de 64 CPUs).
• Falta de Regras para Padrões Complexos: A dependência de regras manuais ou a incapacidade de descobrir novas regras para padrões complexos deixa muitas oportunidades de otimização desperdiçadas.

2. Metodologia: O Sistema SLER

O artigo propõe o SLER (Scalable Learning-to-Rank for Efficient Rewrite), um sistema que combina enumeração padronizada com aprendizado de máquina para descobrir regras de reescrita de forma eficiente e eficaz. O fluxo de trabalho divide-se em três componentes principais:

A. Enumerador de Regras Padronizadas (Standardized Rule Enumerator)

• Templates Padronizados: Em vez de enumerar todas as variações estruturais, o SLER utiliza "templates padronizados". Esses são planos de consulta abstratos onde a estrutura dos operadores é preservada, mas detalhes específicos de dados são removidos.
• Regras de Normalização: O sistema define regras para reordenar ou remover operadores redundantes (ex: mover filtros para cima de projeções, remover duplicatas desnecessárias). Isso transforma planos estruturalmente diferentes, mas semanticamente equivalentes, em uma forma canônica.
• Redução de Complexidade: Ao forçar a padronização, o sistema reduz a complexidade de verificação de exponencial para polinomial para certos casos redundantes, eliminando a necessidade de verificar pares de templates que diferem apenas por permutações triviais de operadores.

B. Deduplicador Baseado em RTP (Reduce by Template Pair)

• Algoritmo RTP: Para lidar com a redundância restante, o SLER emprega o algoritmo Reduce by Template Pair. Diferente de métodos anteriores que deduplicam após a geração completa, o RTP verifica a redundância durante a enumeração.
• Mecanismo: Para cada par de templates (origem e destino), o sistema mantém uma base de regras local. Se uma nova regra gerada for semanticamente redundante em relação às regras já validadas para aquele par, ela é descartada imediatamente, evitando chamadas caras ao verificador SMT.

C. Classificador de Aprendizado para Classificação (Learning-to-Rank Ranker)

• Modelo LambdaMART: Para superar a limitação de escalabilidade em templates grandes (n ≥ 7), o SLER introduz um modelo de Learning-to-Rank (LTR) baseado em Gradient Boosted Decision Trees (GBDT/LightGBM).
• Treinamento: O modelo é treinado em mais de 11.000 consultas SQL reais (open-source e comerciais). As características (features) incluem distância estrutural entre árvores de consulta, complexidade de expressões e tipos de operadores.
• Função de Objetivo: O modelo otimiza o Normalized Discounted Cumulative Gain (NDCG), aprendendo a prever quais pares de templates têm maior probabilidade de gerar regras de reescrita eficazes (que reduzem o tempo de execução).
• Aplicação: O classificador atua como um filtro pré-enumeração. Ele ranqueia os pares de templates e seleciona apenas os top-k mais promissores para enumeração completa, permitindo a exploração de templates complexos (10+ nós) que seriam computacionalmente inviáveis com força bruta.

3. Principais Contribuições

1. Refutação da Hipótese "Pequeno para Grande": O trabalho demonstra empiricamente que regras complexas não podem ser compostas apenas pela combinação de regras simples (apenas 9% das regras 4→2 nós podem ser compostas). Portanto, a enumeração direta é necessária, mas deve ser otimizada.
2. Algoritmo de Enumeração Padronizada: Propõe um método que reduz a redundância estrutural e a complexidade de verificação, permitindo a geração de regras para templates maiores.
3. Mecanismo de Deduplicação RTP: Um algoritmo inovador que elimina redundâncias durante a geração, preservando a capacidade de otimização enquanto reduz drasticamente o overhead de verificação.
4. Ranker Baseado em ML: Introduz o uso de Learning-to-Rank para priorizar a descoberta de regras, resolvendo o problema de escalabilidade e permitindo a descoberta de regras em templates com 7 a 10+ nós.
5. Repositório de Regras em Escala: Construiu o maior repositório de regras de reescrita validado empiricamente até a data, contendo mais de 1 milhão de regras.

4. Resultados Experimentais

O SLER foi avaliado em mais de 11.000 consultas reais e comparado com o WeTune:

• Eficiência (Tempo de Enumeração):
  • Para templates de 4 nós, o SLER é 3x mais rápido que o WeTune (redução de 67h para ~23h).
  • Para templates de 5 e 6 nós, o WeTune falha (tempo limite de anos), enquanto o SLER consegue enumerar em ~30 dias (5 nós) e ~395 dias (6 nós) sem filtragem, ou em minutos com o uso do ranker (filtrando 40% dos templates, cobre >80% das regras eficazes).
• Eficácia (Qualidade das Regras):
  • O SLER descobriu 679.316 novas regras (para 5 e 6 nós), expandindo a base de regras em 98x em comparação com o conjunto de 4 nós do WeTune.
  • Em consultas complexas (ex: q1, q4, q7 na Tabela I do artigo), o SLER conseguiu reescrever consultas que o WeTune não conseguia reescrever ou que resultavam em formas não mínimas.
  • O ranker mostrou alta precisão: as 500 melhores regras identificadas pelo modelo geraram uma melhoria média de 98,6% no desempenho, enquanto as piores 50% geraram apenas 11,9%.
• Impacto de Ponta a Ponta: Em cenários de teste, o SLER alcançou a otimização ideal em menos passos (convergência mais rápida) e encontrou otimizações únicas que o WeTune não percebeu devido à sua limitação de 4 nós.

5. Significado e Conclusão

O trabalho SLER representa um avanço significativo na otimização de bancos de dados ao superar as barreiras de escalabilidade na descoberta de regras de reescrita.

• Viabilidade de Regras Complexas: Demonstra que é possível descobrir e validar regras para consultas complexas (5-10+ nós), que são comuns em aplicações modernas e geradas por ORM, mas que eram anteriormente inacessíveis.
• Mudança de Paradigma: A transição de uma enumeração cega (força bruta) para uma abordagem guiada por dados (padronização + aprendizado de máquina) permite que os otimizadores de consulta se adaptem a cargas de trabalho dinâmicas e complexas.
• Extensibilidade: A arquitetura é projetada para ser extensível, permitindo a integração futura de novos operadores (como agregações e funções de janela) e a adaptação contínua a novos padrões de consulta.

Em resumo, o SLER não apenas acelera a descoberta de regras existentes, mas abre a porta para um novo espaço de otimização, permitindo que sistemas de banco de dados explorem transformações intrincadas que antes eram computacionalmente proibitivas.