LQRS: Learned Query Re-optimization Framework for Spark SQL

L'article présente LQRS, un cadre d'optimisation réactive des requêtes pour Spark SQL qui utilise l'apprentissage par renforcement et des observations d'exécution en temps réel pour affiner dynamiquement les plans d'exécution, réduisant ainsi le temps d'exécution global jusqu'à 90 % par rapport aux méthodes existantes.

L'essentiel

Imaginez que vous êtes le chef d'orchestre d'un grand restaurant (votre base de données) et que vous devez préparer des plats complexes (des requêtes SQL) pour des milliers de clients.

Traditionnellement, le chef utilise un livre de recettes (l'optimiseur classique). Ce livre lui dit : "Pour faire ce plat, mélangez d'abord les tomates, puis les oignons, puis la viande." Le problème ? Le livre de recettes est basé sur des estimations. Il suppose que vous avez 100 tomates, alors qu'en réalité, vous n'en avez que 2. Résultat : le chef prépare une énorme sauce tomate inutile, gaspille du temps et de l'énergie, et le plat arrive froid.

Les chercheurs de l'Université Renmin en Chine ont créé LQRS, une nouvelle approche qui change radicalement la donne. Voici comment cela fonctionne, expliqué simplement :

1. Le Problème : Le Chef qui ne regarde pas dans la casserole

Les "optimiseurs appris" (les intelligences artificielles précédentes) sont comme des chefs qui ont lu des millions de livres de recettes. Ils sont très forts pour deviner la meilleure méthode avant de commencer à cuisiner.
Mais une fois le feu allumé, ils sont aveugles. S'ils se rendent compte qu'ils ont trop de tomates, ils ne peuvent pas changer la recette en cours de route. Ils continuent de cuisiner selon le plan initial, même si c'est inefficace.

2. La Solution : LQRS, le Chef "Super-Héros"

LQRS est un système qui permet au chef de changer de recette en plein milieu de la cuisson, en se basant sur ce qu'il voit réellement dans la casserole.

Imaginez que LQRS est un assistant de cuisine ultra-intelligent qui :

• Regarde la réalité : Il voit exactement combien de tomates sont sorties de la première étape (par exemple, "Ah ! Il n'y a qu'une seule tomate !").
• Réagit immédiatement : Au lieu de continuer à faire une sauce pour 100 personnes, il dit : "Attends, on va changer la méthode ! On va mettre cette unique tomate directement dans le plat final tout de suite."
• Apprend de ses erreurs : À chaque fois qu'il change une recette et que le plat est meilleur, il note cette leçon pour la prochaine fois.

3. Comment ça marche ? (L'analogie du Train)

Pour comprendre la technique, imaginez un train (votre requête) qui doit traverser plusieurs gares (les étapes de calcul).

• Avant LQRS (Spark AQE classique) : Le train part avec un itinéraire fixe. Si à la première gare, on se rend compte qu'il y a un embouteillage, le train peut changer de locomotive (changer de méthode de transport), mais il ne peut pas changer l'ordre des gares qu'il doit visiter. Il est bloqué dans sa séquence.
• Avec LQRS : L'assistant LQRS a le pouvoir de réorganiser les wagons en marche.
  • Si le wagon "Tomates" est vide, il le fait passer en premier pour alléger le train.
  • Si le wagon "Viande" est trop lourd, il le place plus tard.
  • Il peut même décider de faire un détour (changer la structure du plan) pour éviter les bouchons, tout en gardant le train en mouvement.

4. La Magie de l'Apprentissage (Le "Curriculum")

LQRS n'apprend pas tout d'un coup, ce qui serait trop difficile. Il utilise une méthode appelée "l'apprentissage par curriculum" (comme un élève qui apprend à lire).

1. Niveau Débutant : Il commence par des décisions simples (ex: "Choisis la bonne locomotive").
2. Niveau Intermédiaire : Il apprend à déplacer quelques wagons (changer l'ordre de deux tables).
3. Niveau Expert : Il apprend à réorganiser tout le train en temps réel, en tenant compte de la vitesse, du poids et des obstacles.

5. Les Résultats : Une course de vitesse

Dans leurs tests, LQRS a été comparé à d'autres chefs (optimiseurs) sur des tâches complexes.

• Résultat : LQRS a réduit le temps de cuisson (l'exécution de la requête) jusqu'à 90 % par rapport aux autres méthodes.
• Pourquoi ? Parce qu'il ne gaspille pas de temps à préparer des choses inutiles. Il s'adapte à la réalité du moment, comme un coureur qui ajuste sa foulée selon le terrain, au lieu de courir aveuglément sur un tapis roulant.

En résumé

LQRS est un système qui transforme l'optimisation de requêtes d'un "plan rigide écrit sur papier" en une conversation dynamique avec la réalité. Il permet à la base de données de dire : "Tiens, je vois que j'ai beaucoup moins de données que prévu, je vais donc changer ma stratégie maintenant pour aller plus vite !"

C'est comme passer d'un GPS qui vous donne un itinéraire fixe (et vous fait rater un embouteillage) à un GPS connecté en temps réel qui vous redirige instantanément vers la route la plus rapide, tout en apprenant de chaque trajet pour être encore plus malin la prochaine fois.

Résumé technique

Voici un résumé technique détaillé de l'article "LQRS: Learned Query Re-optimization Framework for Spark SQL", structuré selon les points demandés.

1. Problématique

Les optimiseurs de requêtes traditionnels, basés sur des modèles de coût, souffrent souvent d'imprécisions dues à l'utilisation de formules heuristiques pour estimer les coûts d'exécution. Bien que les optimiseurs de requêtes appris (LQO - Learned Query Optimizers) aient démontré de meilleures performances en utilisant des modèles d'apprentissage automatique, ils restent limités par le paradigme "optimiser puis exécuter".

Le problème central identifié par les auteurs est l'incapacité de ces LQO à exploiter les observations d'exécution en temps réel (runtime observations) pour réajuster dynamiquement le plan d'exécution. Une fois le plan initial généré, il reste statique, même si les statistiques réelles (comme la cardinalité exacte d'une table) diffèrent des estimations initiales. Cela empêche des améliorations de performance significatives, notamment pour les jointures où l'ordre d'exécution est critique.

2. Méthodologie : Le Framework LQRS

Les auteurs proposent LQRS, un cadre de ré-optimisation de requêtes appris qui s'intègre directement dans Spark SQL en s'appuyant sur son mécanisme d'Exécution de Requête Adaptative (AQE - Adaptive Query Execution).

Architecture et Composants

LQRS fonctionne via deux composants principaux :

1. Extension du Planificateur (Planner Extension) :

   • C'est un module "plug-and-play" construit sur les interfaces d'extensibilité de Spark SQL.
   • Il intercepte l'exécution aux points de synchronisation naturels (la fin d'une query stage ou étape de requête).
   • Il extrait le plan partiellement exécuté et les statistiques réelles (cardinalités, taille en octets) et les envoie au modèle de décision.
   • Il applique les actions d'optimisation renvoyées par le modèle et injecte le plan modifié dans le moteur AQE pour la suite de l'exécution, sans redémarrer la requête.

2. Modèle de Décision (Decision Model) :

   • Basé sur un cadre Acteur-Critique (Actor-Critic) de l'apprentissage par renforcement (RL).
   • État (State) : Représente le plan partiellement exécuté et les statistiques réelles des étapes terminées. Les plans sont encodés sous forme d'arbres vectoriels via une architecture TreeCNN.
   • Actions : Le modèle peut choisir parmi plusieurs actions :
     • init : Choisir la stratégie d'initialisation du plan.
     • swap : Échanger deux nœuds feuilles (tables) dans l'arbre de jointure.
     • lead : Promouvoir une table spécifique pour qu'elle soit jointe en premier.
     • broadcast : Forcer une jointure par diffusion (broadcast) sur un nœud spécifique.
     • no-op : Ne rien faire (attendre plus d'informations).
   • Récompense (Reward) : Conçue pour pénaliser les opérations coûteuses (comme les rediffusions de données ou reshuffles inutiles) et récompenser la réduction du temps d'exécution total.

Stratégies d'Apprentissage

• Apprentissage par Curriculum (Curriculum Learning) : Pour stabiliser l'apprentissage, le modèle commence par des tâches simples (choix de l'initialisation) avant de progresser vers des ajustements dynamiques complexes en cours d'exécution.
• Optimisation Pré-exécution et En-exécution : LQRS unifie ces deux phases. Les connaissances acquises lors de l'exécution (in-execution) sont rétroactivement utilisées pour améliorer la planification pré-exécution (pre-execution).
• Feedback Dense : Contrairement aux approches qui ne donnent une récompense qu'à la fin de la requête, LQRS fournit un feedback dense à chaque étape de décision, accélérant la convergence.

3. Contributions Clés

• Premier LQO sur Spark SQL combinant pré et post-exécution : LQRS est le premier optimiseur appris capable de réviser dynamiquement un plan pendant son exécution tout en utilisant ces apprentissages pour les requêtes futures.
• Architecture TreeCNN et Encodage Dynamique : Utilisation d'un encodeur capable de gérer les mises à jour de schéma et les statistiques en temps réel (cardinalités réelles) plutôt que des estimations statiques.
• Extension de Planificateur Plug-and-Play : Une implémentation non intrusive qui exploite les hooks AQE de Spark pour modifier les plans (y compris la transformation de plans en "arbres touffus" ou bushy plans) sans nécessiter de réécriture complète du moteur.
• Réduction drastique du temps d'exécution : Démonstration expérimentale montrant que l'ajustement dynamique basé sur le RL surpasse les méthodes statiques et les autres approches de ré-optimisation.

4. Résultats Expérimentaux

Les expériences ont été menées sur quatre benchmarks publics (JOB, ExtJOB, STACK, TPC-H) avec Spark SQL 3.5.4.

• Performance Globale : LQRS réduit le temps d'exécution de bout en bout de 16,3 % à 73,3 % par rapport à Spark SQL standard, et jusqu'à 90 % par rapport à d'autres optimiseurs appris (comme Lero) ou méthodes de ré-optimisation (SSA, AutoSteer).
• Comparaison avec les Bases :
  • Contre Spark SQL (AQE natif) : LQRS surpasse l'AQE standard car il peut réorganiser l'ordre des jointures (ce que l'AQE natif ne fait pas), permettant ainsi à l'AQE de choisir des stratégies de jointure plus efficaces (ex: passer d'une Sort-Merge Join à une Broadcast Hash Join).
  • Contre Lero : Lero est souvent plus lent car il énumère et évalue de nombreux plans avant l'exécution. LQRS est plus rapide et évite les régressions de performance grâce à l'utilisation des observations en temps réel.
  • Contre SSA (QuerySplit) : LQRS offre des gains plus stables et évite les régressions massives grâce à sa politique de décision à long terme (critique) plutôt qu'une approche gourmande (greedy).
• Robustesse : LQRS montre une bonne robustesse face aux changements de distribution de données, bien que des baisses de performance puissent survenir si les actions nécessaires n'ont pas été explorées suffisamment lors de l'entraînement.
• Surcoût (Overhead) : LQRS présente le surcoût d'optimisation le plus faible parmi les méthodes apprises, grâce à l'action no-op qui évite les modifications inutiles du plan.

5. Signification et Impact

L'article LQRS marque une avancée significative dans le domaine de l'optimisation de requêtes pour les moteurs de données massives (Big Data) :

1. Bridging the Gap : Il comble le fossé entre l'optimisation basée sur l'apprentissage (LQO) et le traitement adaptatif (AQP), prouvant que les deux peuvent être unifiés dans un seul processus d'apprentissage.
2. Exploitation du Temps d'Exécution : Il démontre que les décisions d'optimisation ne doivent pas être figées avant l'exécution. L'utilisation des observations réelles (comme le fait qu'une table ne contient qu'un seul tuple) permet des corrections de trajectoire impossibles pour les optimiseurs statiques.
3. Intégration Pratique : En s'appuyant sur l'infrastructure AQE existante de Spark, LQRS offre une voie réaliste pour déployer des optimiseurs appris dans des environnements de production sans réécrire le moteur de base.
4. Flexibilité Structurelle : La capacité à transformer dynamiquement des plans en jointures linéaires (left-deep) en plans en arbre touffu (bushy) ouvre de nouvelles possibilités d'exploration de l'espace des plans que les optimiseurs traditionnels négligent souvent.

En résumé, LQRS représente un changement de paradigme vers des systèmes de gestion de bases de données capables d'apprendre et de s'adapter en continu pendant l'exécution, offrant des gains de performance substantiels là où les méthodes traditionnelles atteignent leurs limites.