Resumo Técnico: Quando o q-error Prediz o Arrependimento do Plano?

Declaração do Problema

O campo da estimativa de cardinalidade (CE) tradicionalmente classifica estimadores usando o q-error ($\max(\hat{c}/c, c/\hat{c})$). Embora o q-error ofereça uma garantia de pior caso — onde limitar o erro máximo sobre subexpressões limita a subotimalidade do plano — evidências empíricas sugerem que esse limite é frequentemente frouxo e impraticável. Especificamente, grandes melhorias no q-error não se traduzem consistentemente em melhores planos de consulta e, inversamente, grandes q-errors não resultam sempre em planos ruins. O problema central abordado é determinar quando o q-error serve como um proxy confiável para o arrependimento do plano (a razão de custo do plano escolhido em relação ao plano ótimo sob as cardinalidades reais) e identificar qual métrica prediz o arrependimento quando o q-error falha.

Metodologia

Os autores modelam a seleção de planos como uma operação $\text{argmin}$ sobre um cenário de custo linear por partes (no espaço de log-cardinalidade). Eles analisam a relação entre o erro de estimativa e o arrependimento do plano através de três regimes distintos definidos pela magnitude do erro ($\sigma$):

1. Regime de Pequeno Erro: O erro de estimativa é pequeno o suficiente para que as cardinalidades estimadas permaneçam dentro da "célula de otimalidade do plano" do plano verdadeiramente ótimo.

   • Métrica: Um número de condição ($\kappa$) por consulta, definido como o inverso da distância até a fronteira de troca de plano mais próxima (onde o custo do plano ótimo é igual ao de um plano alternativo).
   • Hipótese: O arrependimento é governado pela geometria local; $\kappa$ prediz o arrependimento apenas quando o erro é pequeno o suficiente para que a linearização local seja válida.

2. Regime de Grande Erro: O erro de estimativa é grande (típico de estimadores aprendidos implantados), fazendo com que a estimativa caia em qualquer célula dentro do cenário de custo, longe da célula ótima real.

   • Métrica: Subotimalidade de Caso Médio ($ACS_\infty$). Esta é definida como o limite do arrependimento esperado conforme a variância do erro tende ao infinito ($\sigma \to \infty$).
   • Hipótese: Neste regime, quantidades locais como $\kappa$ e q-error tornam-se informativas. Em vez disso, o arrependimento é predito pela "má qualidade típica" de um plano aleatório para uma consulta específica, independentemente do estimador utilizado.

3. Regime de Pior Caso: O limite teórico superior de subotimalidade.

   • Métrica: Subotimalidade Máxima (MSO), definida como $\max_k r_k$, onde $r_k$ é a verdadeira razão de custo do plano $k$ em relação ao plano ótimo.

Os autores derivam uma lei de limite mostrando que $ACS_\infty$ pode ser expressa como uma soma ponderada do espectro de razão de custo verdadeiro ($\{r_k\}$) com pesos combinatórios independentes de cardinalidade ($\pi_k$):
$$ACS_\infty(q) = \sum_{k} r_k \pi_k$$
Isso contrasta com o MSO, que utiliza uma ponderação de máximo, e com $\kappa$, que utiliza uma ponderação de lacuna mais próxima.

Configuração Experimental

• Datasets: STATS-CEB (onde os estimadores são conhecidos por serem imprecisos) e JOB-light (esquema IMDB).
• Estimadores: Quatro estimadores lançados (BayesCard, DeepDB, FLAT, NeuroCard) e o otimizador nativo do DuckDB.
• Validação:
  • Sintética: Injeção de erro com variações de $\sigma$ para testar transições de regime.
  • Mundo Real: Injeção de cardinalidades de estimadores no PostgreSQL 13.1 para medir o arrependimento de tempo de execução real, comparando contra as previsões do modelo $C_{out}$.
• Rigor: O estudo utiliza regras de decisão pré-registradas, incluindo uma hipótese rejeitada e um "quase erro" mantido em registro, para garantir validade estatística.

Resultados Principais

1. O Regime de Pequeno Erro

• O número de condição $\kappa$ prediz fortemente o arrependimento do plano (Spearman $\rho \approx 0.70$ no STATS-CEB, $0.79$ no JOB-light).
• $\kappa$ supera o q-error neste regime.
• À medida que a magnitude do erro ($\sigma$) aumenta, o poder preditivo de $\kappa$ decai para zero, confirmando sua natureza de ferramenta de linearização local.

2. O Regime de Grande Erro

• No regime onde operam os estimadores aprendidos implantados (mediana de q-error de $2$a$10^5$), o q-error é quase inútil para predizer o arrependimento por consulta ($\rho \approx 0.05$).
• $ACS_\infty$ é o preditor superior: Ele alcança uma correlação de Spearman de $\rho \approx 0.54$ com o arrependimento da consulta no STATS-CEB, superando significativamente tanto o q-error quanto o $\kappa$ ($\rho \approx 0.20$).
• Validação PostgreSQL: Quando testado contra tempos de execução reais do PostgreSQL, o $ACS_\infty$ (computado puramente da geometria $C_{out}$ sem ver o banco de dados) prediz o arrependimento de tempo de execução com $\rho = 0.42$, enquanto o q-error mostra uma correlação negativa ($\rho = -0.16$).

3. A Lei de Limite

• O artigo prova que, conforme $\sigma \to \infty$, a seleção do otimizador converge para uma regra de rank-minimax livre de cardinalidade.
• $ACS_\infty$ fatora-se no espectro de razão de custo verdadeiro e nos pesos combinatórios determinados unicamente pelo sistema de conjuntos de planos, tornando-o uma medida de dificuldade independente do estimador.

Alegações e Significância

O artigo reivindica modestamente fornecer uma reconciliação conceitual e empírica da tensão "q-error vs. custo do plano", em vez de propor um novo estimador.

• Predição Dependente de Regime: O artigo estabelece que nenhuma métrica escalar única (como o q-error) pode predizer o arrependimento do plano através de todas as magnitudes de erro. O poder preditivo depende inteiramente do regime de erro:
  • Erro Pequeno: Predito pelo Número de Condição ($\kappa$).
  • Erro Grande: Predito pela Subotimalidade de Caso Médio ($ACS_\infty$).
  • Pior Caso: Limitado pela Subotimalidade Máxima (MSO).
• Insight Geométrico: Estas três métricas são reveladas como diferentes ponderações do mesmo espectro de razão de custo de plano ($\{r_k\}$).
• Implicação Prática: Para estimadores aprendidos implantados (que operam no regime de grande erro), o q-error é um indicador pobre da qualidade do plano. O $ACS_\infty$ serve como um companheiro para a otimização de consultas robusta de caso médio, ofere uma medida de caso médio de quais consultas são inerentemente "propensas ao arrependimento" devido à sua geometria de custo de plano, independentemente do estimador específico utilizado.

Os autores enfatizam que sua contribuição é a caracterização de quando as métricas de precisão acompanham a qualidade do plano e a introdução do $ACS_\infty$ como uma medida de dificuldade ao nível da consulta, validada através de pré-registro rigoroso e testes de tempo de execução no mundo real.