LQRS: Learned Query Re-optimization Framework for Spark SQL

Dit paper introduceert LQRS, een leerframework voor queryhervorming in Spark SQL dat gebruikmaakt van curriculumversterkend leren en runtime-observaties om bestaande plannen dynamisch te optimaliseren en de uitvoeringstijd tot 90% te verkorten.

De kern

Stel je voor dat je een enorm complex recept hebt om een gigantische maaltijd te bereiden voor duizenden gasten. Je hebt een chef-kok (de query optimizer) die het recept moet plannen voordat de kook begint.

In de traditionele wereld (zoals Spark SQL zonder LQRS) kijkt de chef naar het recept en zegt: "Oké, ik denk dat we eerst de aardappels moeten schillen, dan de ui snijden, en daarna de saus maken." Hij baseert dit op wat hij denkt dat er in de koelkast zit. Maar wat als er eigenlijk maar één aardappel is, en de ui is gigantisch groot? De chef had dit niet kunnen weten voordat hij begon. Hij blijft steken in zijn oorspronkelijke plan, wat resulteert in een chaotische keuken en een maaltijd die te laat is.

LQRS (Learned Query Re-optimization Framework) is als een slimme, lerende assistent-chef die niet alleen vooraf plannen maakt, maar ook tijdens het koken meekijkt en ingrijpt.

Hier is hoe het werkt, in simpele termen:

1. Het Probleem: De "Vaste" Chef

Traditionele systemen en zelfs moderne "leer-systemen" (zoals Lero) maken hun plan voordat ze beginnen. Ze proberen te raden wat er gaat gebeuren.

• Het probleem: Ze kunnen niet zien dat de aardappels (data) veel kleiner zijn dan gedacht, of dat de saus (een database-tabel) veel groter is. Omdat ze vastzitten aan hun oorspronkelijke plan, maken ze fouten die ze niet kunnen corrigeren.

2. De Oplossing: LQRS, de "Live" Chef

LQRS is anders. Het combineert twee dingen:

1. Een slimme planner: Die een goed startplan maakt.
2. Een slimme regisseur: Die tijdens het koken (tijdens de uitvoering van de query) echt kijkt wat er gebeurt.

De Analogie van de "Halve Maaltijd":
Stel je voor dat de chef de aardappels heeft geschild en ziet: "Oh, er zijn er maar twee! Ik hoef niet de hele pan te vullen."

• De oude chef: Zegt: "Nee, we blijven doen alsof er 100 zijn, want dat stond in het plan."
• LQRS: Zegt: "Wacht! We hebben maar twee aardappels. Laten we de volgorde van het recept direct aanpassen! Laten we eerst de saus maken en de aardappels er later bij doen, want dat gaat veel sneller."

LQRS doet precies dit. Het wacht niet tot het einde van de maaltijd om te zeggen "oh, dat was een slecht plan". Het grijpt in op het moment dat het ziet dat een stap veel sneller of langzamer gaat dan verwacht.

3. Hoe leert LQRS? (De "Curriculum" Methode)

LQRS is niet meteen een meester-chef. Het leert stap voor stap, net zoals een leerling:

• Stap 1: Eerst leert het alleen de basis: "Welke pan gebruiken we?" (De startstrategie kiezen).
• Stap 2: Dan leert het: "Als ik zie dat er weinig eten is, moet ik de volgorde van snijden aanpassen."
• Stap 3: Uiteindelijk leert het complexe trucs, zoals het wisselen van grote en kleine ingrediënten om de snelste route te vinden.

Dit noemen ze Curriculum Reinforcement Learning. Het is alsof je een kind leert fietsen: eerst op een vlakke weg, dan op een heuvel, en pas later in de drukke stad.

4. De Magische "Plug-in"

LQRS is niet gebouwd als een compleet nieuw systeem, maar als een slimme plug-in voor Spark SQL (het bestaande kookapparaat).

• Het gebruikt de bestaande "veiligheidsnetten" van Spark.
• Het kan op elk moment zeggen: "Stop even! We hebben net gezien dat dit stukje data klein is. Laten we de volgorde van de volgende stappen veranderen."
• Het doet dit zonder de hele maaltijd te moeten herstarten. Het past alleen het overgebleven deel van het recept aan.

5. Het Resultaat: Snelheid en Flexibiliteit

In de tests van het papier bleek dat LQRS tot 90% sneller kon zijn dan andere systemen.

• Voorbeeld: Soms duurt een query 33 seconden. Met LQRS duurt het maar 15 seconden.
• Waarom? Omdat LQRS ziet dat een bepaalde tabel (een "ingrediënt") slechts uit één regel bestaat. In plaats van die tabel als laatste te verwerken (zoals een traditionele chef zou doen), schuift LQRS deze naar voren. Hierdoor wordt de hele berekening veel lichter en sneller.

Samenvattend

LQRS is als een slimme navigatie-app voor een vrachtwagenchauffeur.

• De oude systemen plannen de route op de kaart (voordat je vertrekt). Als er een file staat, weten ze het niet en blijven ze doorrijden.
• LQRS kijkt live naar het verkeer. Zodra het ziet dat er een file is (of juist dat de weg vrij is), herpland het de route direct terwijl je rijdt. Het gebruikt de echte ervaring van de rit om de volgende beslissingen te nemen.

Dit maakt het systeem niet alleen slimmer, maar ook veel sneller en flexibeler dan alles wat we tot nu toe hadden.

Technische samenvatting

Hier is een gedetailleerde technische samenvatting van het paper "LQRS: Learned Query Re-optimization Framework for Spark SQL" in het Nederlands.

Probleemstelling

De query-optimizer is een fundamenteel onderdeel van databasebeheersystemen. Traditionele, op kosten gebaseerde optimizers (CBO) gebruiken handgemaakte formules om uitvoeringskosten te schatten, wat vaak leidt tot onnauwkeurige schattingen en suboptimale uitvoeringsplannen.

Recente studies hebben "Learned Query Optimizers" (LQO) zoals Lero geïntroduceerd, die machinelearningmodellen gebruiken om plannen te selecteren op basis van historische feedback. Hoewel deze beter presteren dan traditionele methoden, hebben ze een cruciaal nadeel: ze opereren binnen het paradigma "optimaliseer eerst, voer dan uit". Dit betekent dat ze beslissingen nemen op basis van geschatte statistieken voordat de query begint, en het plan statisch houden tijdens de uitvoering. Ze kunnen geen gebruik maken van waardevolle runtime-observaties (zoals de werkelijke grootte van tussentijdse resultaten) om het plan dynamisch aan te passen. Hierdoor blijven potentiële prestatiewinsten onbenut, vooral bij complexe queries waar de werkelijke data-selectiviteit pas tijdens de uitvoering duidelijk wordt.

Methodologie: LQRS

Om dit probleem op te lossen, stellen de auteurs LQRS (Learned Query Re-optimization Framework) voor. LQRS is het eerste framework dat leren en adaptieve queryverwerking (AQP) verenigt binnen Spark SQL. Het stelt de optimalisatiebeslissingen uit tot het uitvoeringstijd en gebruikt echte runtime-observaties om het plan dynamisch te verfijnen.

De kerncomponenten van LQRS zijn:

1. Integratie met Spark AQE:
   LQRS bouwt voort op de Adaptive Query Execution (AQE) van Spark SQL. Spark AQE verdeelt een query in "query stages" (stages gescheiden door shuffle-operaties). LQRS gebruikt de voltooiing van een stage als een natuurlijk beslispunt. Op dat moment zijn de werkelijke statistieken (cardinaliteit, data-grootte) van de reeds uitgevoerde delen van de query bekend.

2. Beslismodel (Actor-Critic Reinforcement Learning):
   LQRS gebruikt een Reinforcement Learning (RL) framework met een Actor-Critic architectuur:

   • State (Toestand): Bestaat uit het deels uitgevoerde plan en de werkelijke statistieken van de voltooide stages.
   • Acties: Het model kan verschillende optimalisatieacties uitvoeren, zoals:
     • init: Kies een strategie voor de initiële planopbouw.
     • swap: Verwissel twee leaf-nodes (tabellen) in het join-plan.
     • lead: Breng een specifieke tabel (of subset) naar voren in de join-volgorde.
     • broadcast: Forceer een broadcast join voor een specifieke tabel.
     • no-op: Voer geen actie uit (wacht op meer informatie).
   • Reward: De beloning is gebaseerd op de totale uitvoeringstijd, maar bevat ook een tussentijdse straf voor extra shuffle-operaties die nodig zijn door planwijzigingen. Dit moedigt het model aan om kostbare herordeningen te vermijden tenzij de winst groot is.
   • Modelarchitectuur: Het model gebruikt een TreeCNN (Tree Convolutional Neural Network) om de query-structuur te encoderen.

3. Curriculum Learning:
   Om de stabiliteit van het leren te vergroten, gebruikt LQRS een curriculum-strategie. Het model begint met het leren van eenvoudige beslissingen (zoals de initiële planstrategie) en schakelt geleidelijk over naar complexere runtime-aanpassingen (zoals join-reordering) zodra het meer ervaring heeft.

4. Plug-and-Play Planner Extension:
   LQRS implementeert een extensie voor de Spark-planner die als een regel in de AQE-pijplijn werkt. Deze extensie:

   • Haalt het huidige deels uitgevoerde plan en statistieken op.
   • Stuurt deze naar het beslismodel.
   • Past de teruggekregen acties toe op het lopende plan (bijv. het herschikken van joins) zonder de reeds voltooide stages te vernietigen.
   • Zorgt ervoor dat de wijzigingen semantisch correct zijn en door de engine kunnen worden uitgevoerd.

Belangrijkste Bijdragen

• Eerste Learned Re-optimizer voor Spark: LQRS is het eerste systeem dat zowel pre-execution als in-execution optimalisatie ondersteunt binnen Spark SQL, waarbij het leren en adaptieve verwerking combineert.
• Runtime-geleide beslissingen: In plaats van te vertrouwen op statische schattingen, gebruikt LQRS echte runtime-data (zoals de werkelijke rij-aantallen) om join-volgorde en strategieën dynamisch aan te passen.
• Dichte Feedback: Door te leren op basis van feedback per query-stage (in plaats van alleen aan het einde van de query), krijgt het model veel dichter feedback (minimaal 3x dichter dan traditionele end-to-end methoden), wat het leren versnelt.
• Veilige Planwijziging: De planner-extensie zorgt voor veilige transformaties (bijv. het omzetten van een lineaire join-structuur in een 'bushy' structuur) zonder de semantiek van de query te breken.

Resultaten

De auteurs hebben LQRS uitgebreid getest op vier benchmarks (JOB, ExtJOB, STACK, TPC-H) in vergelijking met Spark SQL (standaard), Lero, AutoSteer en SSA (QuerySplit).

• Prestatieverbetering: LQRS reduceert de end-to-end uitvoeringstijd met tot 90% in vergelijking met andere learned optimizers en re-optimisatiemethoden.
• Vergelijking met Baselines:
  • T.o.v. Spark SQL: LQRS verbetert de prestaties met 16,3% tot 73,3% over de verschillende benchmarks.
  • T.o.v. Lero: Lero presteert goed in pre-execution, maar faalt vaak tijdens de uitvoering omdat het plan statisch is. LQRS corrigeert deze fouten tijdens de uitvoering.
  • T.o.v. AutoSteer & SSA: LQRS toont minder regressies (verslechtering van prestaties) en is robuuster, vooral bij complexe queries.
• Overhead: LQRS heeft de laagste optimalisatie-overhead van alle geteste methoden, omdat het geen uitgebreide enumeratie van plannen vooraf hoeft uit te voeren en alleen ingrijpt wanneer nodig (via de no-op actie).
• Robuustheid: LQRS toont goede generalisatie bij veranderingen in data-distributie en workload, hoewel er enige prestatieverlies optreedt bij zeer grote veranderingen in de uitvoeringsomgeving.

Significantie

Dit paper markeert een belangrijke verschuiving in het veld van database-optimalisatie. Het bewijst dat het uitstellen van optimalisatiebeslissingen tot het uitvoeringstijd (via runtime feedback) een krachtigere strategie is dan puur leren op historische data.

De belangrijkste implicaties zijn:

1. Overbrugging van de kloof: Het overbrugt de kloof tussen "Learned Query Optimization" (LQO) en "Adaptive Query Processing" (AQP). Het combineert de voorspellende kracht van ML met de flexibiliteit van runtime-aanpassing.
2. Praktische toepasbaarheid: De implementatie als een extensie op Spark SQL toont aan dat dergelijke systemen kunnen worden geïntegreerd in bestaande, industriële query-engines zonder de kernarchitectuur volledig te vervangen.
3. Toekomstperspectief: Het suggereert dat toekomstige databasesystemen niet alleen moeten leren voordat ze uitvoeren, maar continu moeten leren tijdens het uitvoeren om zich aan te passen aan de werkelijke data-dynamiek.

Kortom, LQRS demonstreert dat door runtime-observaties te gebruiken om plannen dynamisch bij te sturen, de prestaties van SQL-queries aanzienlijk kunnen worden verbeterd, zelfs in complexe scenario's waar traditionele optimizers en eerdere learned methoden tekortschieten.