Résumé Technique : Quand l'erreur q prédit-elle le regret de plan ?

Énoncé du Problème

Le domaine de l'estimation de cardinalité (CE) classe traditionnellement les estimateurs en utilisant l'erreur q ($\max(\hat{c}/c, c/\hat{c})$). Bien que l'erreur q offre une garantie de pire cas (bornant l'erreur maximale sur les sous-expressions pour borner la sous-optimalité du plan), les preuves empiriques suggèrent que cette borne est souvent lâche et peu pratique. Plus précisément, de grandes améliorations de l'erreur q ne se traduisent pas systématiquement par de meilleurs plans de requête, et inversement, de fortes erreurs q ne conduisent pas toujours à de mauvais plans. Le problème central abordé est de déterminer quand l'erreur q sert de proxy fiable pour le regret de plan (le ratio de coût du plan choisi par rapport au plan optimal sous les cardinalités réelles) et d'identifier la métrique qui prédit le regret lorsque l'erreur q échoue.

Méthodologie

Les auteurs modélisent la sélection de plan comme une opération $\text{argmin}$ sur un paysage de coûts de type linéaire par morceaux (dans l'espace du logarithme de la cardinalité). Ils analysent la relation entre l'erreur d'estimation et le regret de plan à travers trois régimes distincts définis par l'ampleur de l'erreur ($\sigma$) :

1. Régime de Faible Erreur : L'erreur d'estimation est suffisamment petite pour que les cardinalités estimées restent dans la « cellule d'optimalité du plan » du plan optimal réel.

   • Métrique : Un nombre de condition ($\kappa$) par requête, défini comme l'inverse de la distance vers la frontière de changement de plan la plus proche (où le coût du plan optimal est égal au coût d'un plan alternatif).
   • Hypothèse : Le regret est régi par la géométrie locale ; $\kappa$ ne prédit le regret que lorsque l'erreur est assez faible pour que la linéarisation locale soit valide.

2. Régime de Forte Erreur : L'erreur d'estimation est grande (typique des estimateurs appris déployés), ce qui fait que l'estimation atterrit dans n'importe quelle cellule du paysage de coûts, loin de la cellule optimale réelle.

   • Métrique : La Sous-optimalité en Moyenne ($ACS_\infty$). Elle est définie comme la limite de l'espérance du regret lorsque la variance de l'erreur tend vers l'infini ($\sigma \to \infty$).
   • Hypothèse : Dans ce régime, les quantités locales comme $\kappa$ et l'erreur q deviennent non informatives. Au lieu de cela, le regret est prédit par la « médiocrité typique » d'un plan aléatoire pour une requête spécifique, indépendamment de l'estimateur utilisé.

3. Régime du Pire Cas : La borne théorique supérieure de la sous-optimalité.

   • Métrique : La Sous-optimalité Maximale (MSO), définie comme $\max_k r_k$, où $r_k$ est le véritable ratio de coût du plan $k$ par rapport au plan optimal.

Les auteurs dérivent une loi limite montrant que $ACS_\infty$ peut être exprimée comme une somme pondérée du spectre de ratios de coûts réels ($\{r_k\}$) avec des poids combinatoires indépendants de la cardinalité ($\pi_k$) :
$$ACS_\infty(q) = \sum_{k} r_k \pi_k$$
Cela contraste avec la MSO, qui utilise une pondération par le maximum, et avec $\kappa$, qui utilise une pondération par l'écart le plus proche.

Configuration Expérimentale

• Jeux de données : STATS-CEB (où les estimateurs sont connus pour être imprécis) et JOB-light (schéma IMDB).
• Estimateurs : Quatre estimateurs publiés (BayesCard, DeepDB, FLAT, NeuroCard) et l'optimiseur natif de DuckDB.
• Validation :
  • Synthétique : Injection d'erreur avec des variations de $\sigma$ pour tester les transitions de régime.
  • Réel : Injection de cardinalités d'estimateurs dans PostgreSQL 13.1 pour mesurer le regret de temps d'exécution réel, en comparant les résultats au modèle théorique $C_{out}$.
• Rigueur : L'étude utilise des règles de décision pré-enregistrées, incluant une hypothèse rejetée et un « quasi-succès » conservé pour mémoire, afin de garantir la validité statistique.

Résultats Clés

1. Le Régime de Faible Erreur

• Le nombre de condition $\kappa$ prédit fortement le regret de plan (Spearman $\rho \approx 0,70$ sur STATS-CEB, $0,79$ sur JOB-light).
• $\kappa$ surpasse l'erreur q dans ce régime.
• À mesure que l'ampleur de l'erreur ($\sigma$) augmente, le pouvoir prédictif de $\kappa$ décroît jusqu'à zéro, confirmant sa nature d'outil de linéarisation locale.

2. Le Régime de Forte Erreur

• Dans le régime où opèrent les estimateurs appris déployés (médiane de l'erreur q entre $2$ et $10^5$), l'erreur q est presque inutile pour prédire le regret par requête ($\rho \approx 0,05$).
• $ACS_\infty$ est le prédicteur supérieur : Elle atteint une corrélation de Spearman de $\rho \approx 0,54$ avec le regret de requête sur STATS-CEB, surpassant nettement l'erreur q et $\kappa$ ($\rho \approx 0,20$).
• Validation PostgreSQL : Testée contre les temps d'exécution réels de PostgreSQL, $ACS_\infty$ (calculée uniquement à partir de la géométrie de $C_{out}$ sans voir la base de données) prédit le regret de temps d'exécution avec $\rho = 0,42$, tandis que l'erreur q montre une corrélation négative ($\rho = -0,16$).

3. La Loi Limite

• L'article prouve que lorsque $\sigma \to \infty$, la sélection de l'optimiseur converge vers une règle de rang minimax indépendante de la cardinalité.
• $ACS_\infty$ se factorise en un spectre de ratios de coûts réels et des poids combinatoires déterminés uniquement par le système de plans, ce qui en fait une mesure de la difficulté de la requête indépendante de l'estimateur.

Revendications et Signification

L'article prétend modestement fournir une réconciliation conceptuelle et empirique de la tension entre « erreur q et coût de plan », plutôt que de proposer un nouvel estimateur.

• Prédiction dépendante du régime : L'article établit qu'aucune métrique scalaire unique (comme l'erreur q) ne peut prédire le regret de plan à travers toutes les amplitudes d'erreur. Le pouvoir prédictif dépend entièrement du régime d'erreur :
  • Faible Erreur : Prédit par le Nombre de Condition ($\kappa$).
  • Forte Erreur : Prédit par la Sous-optimalité en Moyenne ($ACS_\infty$).
  • Pire Cas : Borné par la Sous-optimalité Maximale (MSO).
• Aperçu Géométrique : Ces trois métriques sont révélées comme étant différentes pondérations du même spectre de ratios de coûts de plan ($\{r_k\}$).
• Implication Pratique : Pour les estimateurs appris déployés (qui opèrent dans le régime de forte erreur), l'erreur q est un indicateur médiocre de la qualité du plan. $ACS_\infty$ sert de complément à l'optimisation de requêtes robuste en pire cas, offrant une mesure de l'ordre moyen des requêtes intrinsèquement « sujettes au regret » en raison de leur géométrie de coût de plan, quel que soit l'estimateur utilisé.

Les auteurs soulignent que leur contribution est la caractérisation de quand les métriques de précision suivent la qualité du plan et l'introduction de $ACS_\infty$ comme mesure de difficulté au niveau de la requête, validée par un enregistrement préalable rigoureux et des tests de temps d'exécution en conditions réelles.