Resumen Técnico: ¿Cuándo el q-error predice el arrepentimiento del plan?

Planteamiento del Problema

El campo de la estimación de cardinalidad (CE) clasifica tradicionalmente a los estimadores utilizando el q-error ($\max(\hat{c}/c, c/\hat{c})$). Si bien el q-error ofrece una garantía de caso peor que establece que acotar el error máximo sobre las subexpresiones acota la suboptimalidad del plan, la evidencia empírica sugiere que este límite es a menudo laxo e impracticable. Específicamente, las grandes mejoras en el q-error no se traducen consistentemente en mejores planes de consulta y, por el contrario, los q-errores grandes no siempre resultan en planes deficientes. El problema central abordado es determinar cuándo el q-error sirve como un proxy confiable para el arrepentimiento del plan (la relación de costo del plan elegido respecto al plan óptimo bajo cardinalidades reales) e identificar qué métrica predice el arrepentimiento cuando el q-error falla.

Metodología

Los autores modelan la selección de planes como una operación $\text{argmin}$ sobre un paisaje de costos de segmentación lineal (en el espacio de log-cardinalidad). Analizan la relación entre el error de estimación y el arrepentimiento del plan a través de tres regímenes distintos definidos por la magnitud del error ($\sigma$):

1. Régimen de Error Pequeño: El error de estimación es lo suficientemente pequeño como para que las cardinalidades estimadas permanezcan dentro de la "celda de optimalidad del plan" del plan óptimo real.

   • Métrica: Un número de condición ($\kappa$) por consulta, definido como el inverso de la distancia a la frontera de cambio de plan más cercana (donde el costo del plan óptimo es igual al de un plan alternativo).
   • Hipótesis: El arrepentimiento está gobernado por la geometría local; $\kappa$ predice el arrepentimiento solo cuando el error es lo suficientemente pequeño como para que la linealización local sea válida.

2. Régimen de Error Grande: El error de estimación es grande (típico de los estimadores aprendidos desplegados), lo que provoca que la estimación caiga en cualquier celda dentro del paisaje de costos, lejos de la celda óptima real.

   • Métrica: Suboptimalidad del Caso Promedio ($ACS_\infty$). Se define como el límite del arrepentimiento esperado a medida que la varianza del error tiende al infinito ($\sigma \to \infty$).
   • Hipótesis: En este régimen, las cantidades locales como $\kappa$ y el q-error carecen de información. En su lugar, el arrepentimiento es predicho por la "maldad típica" de un plan aleatorio para una consulta específica, independientemente del estimador utilizado.

3. Régimen de Caso Peor: El límite teórico superior de la suboptimalidad.

   • Métrica: Suboptimalidad Máxima (MSO), definida como $\max_k r_k$, donde $r_k$ es la verdadera relación de costo del plan $k$ respecto al plan óptimo.

Los autores derivan una ley de límite que muestra que $ACS_\infty$ puede expresarse como una suma ponderada del espectro de relación de costos reales ($\{r_k\}$) con pesos combinatorios independientes de la cardinalidad ($\pi_k$):
$$ACS_\infty(q) = \sum_{k} r_k \pi_k$$
Esto contrasta con MSO, que utiliza una ponderación de máximo, y con $\kappa$, que utiliza una ponderación de brecha más cercana.

Configuración Experimental

• Conjuntos de Datos: STATS-CEB (donde los estimadores son conocidos por ser inexactosos) y JOB-light (esquema IMDB).
• Estimadores: Cuatro estimadores lanzados (BayesCard, DeepDB, FLAT, NeuroCard) y el optimizador nativo de DuckDB.
• Validación:
  • Sintética: Inyección de error con variaciones de $\sigma$ para probar las transiciones de régimen.
  • Mundo Real: Inyección de cardinalidades de estimadores en PostgreSQL 13.1 para medir el arrepentimiento de tiempo de ejecución real, comparándolo contra las predicciones del modelo $C_{out}$.
• Rigor: El estudio utiliza reglas de decisión pre-registradas, incluyendo una hipótesis rechazada y un "casi acierto" mantenido en registro, para asegurar la validez estadística.

Resultados Clave

1. El Régimen de Error Pequeño

• El número de condición $\kappa$ predice fuertemente el arrepentimiento del plan (Spearman $\rho \approx 0.70$ en STATS-CEB, $0.79$ en JOB-light).
• $\kappa$ supera al q-error en este régimen.
• A medida que la magnitud del error ($\sigma$) aumenta, el poder predictivo de $\kappa$ decae a cero, confirmando su naturaleza como herramienta de linealización local.

2. El Régimen de Error Grande

• En el régimen donde operan los estimadores aprendidos desplegados (mediana de q-error de 2 a $10^5$), el q-error es casi inútil para predecir el arrepentimiento por consulta ($\rho \approx 0.05$).
• $ACS_\infty$ es el predictor superior: Logra una correlación de Spearman de $\rho \approx 0.54$ con el arrepentimiento de la consulta en STATS-CEB, superando significativamente tanto al q-error como a $\kappa$ ($\rho \approx 0.20$).
• Validación en PostgreSQL: Al probarse contra los tiempos de ejecución reales de PostgreSQL, $ACS_\infty$ (calculado puramente desde la geometría de $C_{out}$ sin ver la base de datos) predice el arrepentimiento de tiempo de ejecución con $\rho = 0.42$, mientras que el q-error muestra una correlación negativa ($\rho = -0.16$).

3. La Ley de Límite

• El artículo demuestra que, a medida que $\sigma \to \infty$, la selección del optimizador converge a una regla de rango minimax libre de cardinalidad.
• $ACS_\infty$ se factoriza en el espectro de relación de costos reales y pesos combinatorios determinados únicamente por el sistema de conjuntos de planes, lo que lo convierte en una medida de dificultad de consulta independiente del estimador.

Conclusiones y Significado

El artículo reclama modestamente proporcionar una reconciliación conceptual y empírica de la tensión "q-error vs. costo del plan", en lugar de proponer un nuevo estimador.

• Predicción Dependiente del Régimen: El artículo establece que ninguna métrica escalar única (como el q-error) puede predecir el arrepentimiento del plan en todas las magnitudes de error. El poder predictivo depende enteramente del régimen de error:
  • Error Pequeño: Predicho por el Número de Condición ($\kappa$).
  • Error Grande: Predicho por la Suboptimalidad del Caso Promedio ($ACS_\infty$).
  • Caso Peor: Acotado por la Suboptimalidad Máxima (MSO).
• Perspectiva Geométrica: Estas tres métricas se revelan como diferentes ponderaciones del mismo espectro de relación de costos de los planes ($\{r_k\}$).
• Implicación Práctica: Para los estimadores aprendidos desplegados (que operan en el régimen de error grande), el q-error es un indicador pobre de la calidad del plan. $ACS_\infty$ sirve como un compañero para la optimización de consultas robusta en el caso promedio, ofreciendo una medida de caso promedio de qué consultas son inherentemente "propensas al arrepentimiento" debido a su geometría de costo de plan, independientemente del estimador específico utilizado.

Los autores enfatizan que su contribución es la caracterización de cuándo las métricas de precisión rastrean la calidad del plan y la introducción de $ACS_\infty$ como una medida de dificultad de consulta, validada mediante pre-registro riguroso y pruebas de tiempo de ejecución en el mundo real.