Efficient Query Rewrite Rule Discovery via Standardized Enumeration and Learning-to-Rank(extend)

Dit paper introduceert SLER, een schaalbaar systeem dat standaardisatie en learning-to-rank combineert om de zoekruimte voor query-herformuleringsefficiënt te verkleinen en zo een ongekend groot, empirisch gevalideerd repository met meer dan een miljoen herschrijvingsregels voor complexe queryplannen te genereren.

De kern

Stel je voor dat een database een gigantische, super-snelle bibliotheek is. Als je een vraag stelt (een "query"), moet de bibliothecaris (de database-optimizer) de snelste route vinden om het juiste boek te vinden. Soms schrijven mensen of computers echter vragen die onnodig ingewikkeld zijn, alsof je zegt: "Ga naar de eerste verdieping, loop naar de linkerkant, draai rechtsom, loop drie keer rond de tafel en zoek dan het boek," terwijl je ook gewoon had kunnen zeggen: "Ga direct naar het boek."

Het vinden van deze kortere routes heet query rewriting.

Deze paper introduceert SLER, een slim systeem dat automatisch duizenden nieuwe, slimme regels bedenkt om deze ingewikkelde vragen te versimpelen. Hier is hoe het werkt, vertaald naar alledaagse taal:

1. Het Probleem: De "Brute Force" Fout

Vroeger probeerden systemen (zoals de huidige leider, WeTune) om alle mogelijke manieren te vinden om een vraag te herschrijven. Ze deden dit als een brute force-methode: ze probeerden alles.

• Het probleem: Dit is als proberen elke mogelijke combinatie van een slot te raden. Voor simpele vragen werkt het, maar zodra de vraag complex wordt (meer dan 4 stappen), wordt het aantal combinaties zo enorm dat het systeem jarenlang zou rekenen.
• De uitkomst: Ze vonden veel regels, maar 90% was nutteloos (redundant) en ze konden geen complexe vragen oplossen. Het was alsof je een hele berg schroot verzamelt in de hoop dat er één nuttig stukje metaal tussen zit.

2. De Oplossing: SLER (De Slimme Architect)

SLER lost dit op met drie slimme trucs, die we kunnen vergelijken met het bouwen van een super-efficiënte fabriek:

A. Standaardisatie (De "Blaadje-van-de-Boom" Regel)

Stel je voor dat je een boom wilt tekenen. Sommige mensen tekenen de takken eerst, dan de bladeren. Anderen doen het andersom. Het resultaat is hetzelfde, maar de tekening ziet er anders uit.

• SLER's truc: SLER zegt: "Laten we afspreken dat we altijd eerst de takken tekenen en dan de bladeren." Dit noemen ze standaardisatie.
• Het effect: Door alles op één manier te tekenen, ziet SLER direct dat twee vragen eigenlijk hetzelfde zijn. In plaats van 100 verschillende manieren te testen om hetzelfde te doen, test hij er maar één. Dit haalt de "ruis" uit het systeem en maakt het zoeken veel sneller.

B. De "RTP" Scherper (De Afvalbak)

Zelfs met standaardisatie blijven er nog veel dubbele regels over.

• SLER's truc: SLER gebruikt een algoritme genaamd RTP (Reduce by Template Pair). Dit werkt als een slimme afvalbak. Zodra het systeem ziet dat een nieuwe regel precies hetzelfde doet als een regel die het al heeft, gooit hij de nieuwe regel direct weg.
• Het effect: In plaats van een berg papier te stapelen en later te sorteren, gooit SLER het afval direct weg terwijl hij schrijft. Dit bespaart enorm veel tijd.

C. Learning-to-Rank (De Slimme Voorspeller)

Dit is misschien wel het coolste deel. Stel je voor dat je een enorme lijst met 1 miljoen mogelijke routes hebt. Je kunt ze niet allemaal uitproberen.

• SLER's truc: SLER heeft een AI-leraar (een model genaamd LambdaMART) getraind op echte database-vragen. Deze AI leert: "Als ik deze structuur zie, is de kans groot dat deze regel de vraag versnelt."
• Het effect: In plaats van alle 1 miljoen regels te testen, kijkt de AI eerst naar de lijst, selecteert de top 100 die het meest veelbelovend lijken, en test alleen die. Het is alsof je een ervaren gids vraagt om je de beste route te wijzen, in plaats van zelf elke pad te verkennen. Hierdoor kan SLER zelfs vragen oplossen met 10 of meer stappen, wat voor oude systemen onmogelijk was.

3. Het Resultaat: Een Gouden Schat

Door deze drie methoden te combineren, heeft SLER iets ongelooflijks bereikt:

• Het heeft meer dan 1 miljoen nieuwe regels gevonden.
• Het kan complexe vragen oplossen die voorheen vastliepen (zoals die met 5, 6 of zelfs 10 stappen).
• Het werkt veel sneller dan de beste systemen van nu.

Samenvattend

Vroeger probeerden databases elke mogelijke weg te lopen om een vraag te beantwoorden, wat leidde tot een enorme verspilling van tijd en energie. SLER is als een slimme navigatie-app die:

1. Alle wegen standaardiseert (zodat je niet in de war raakt).
2. Direct de doodlopende wegen weglaat.
3. Gebruikt maakt van ervaring (AI) om alleen de snelste routes te testen.

Hierdoor kunnen databases veel sneller en slimmer werken, zelfs met de meest ingewikkelde vragen die moderne software genereert. Het is een enorme stap voorwaarts in het maken van databases die niet alleen snel zijn, maar ook slim genoeg om zichzelf te verbeteren.

Technische samenvatting

Hier is een gedetailleerde technische samenvatting van het paper "Efficient Query Rewrite Rule Discovery via Standardized Enumeration and Learning-to-Rank" (SLER), vertaald en samengevat in het Nederlands.

Probleemstelling

Query-rewriting is cruciaal voor het optimaliseren van databaseprestaties, maar bestaande methoden voor het automatisch ontdekken van herschrijvingsregels kampen met ernstige beperkingen:

1. Exponentiële zoekruimte: Bestaande state-of-the-art (SOTA) systemen, zoals WeTune, gebruiken een brute-force benadering om paren van query-plan-sjablonen te enumereren. Dit leidt tot een onbeheersbare rekencomplexiteit, vooral bij complexe query's met vijf of meer knopen (operatoren).
2. Schalingsproblemen: WeTune is beperkt tot regels met maximaal 4 knopen. Het enumereren van regels voor 5-knooppunten zou maanden duren, en voor 6 knopen zou het decennia kosten. Echter, real-world productie-databases (zoals PostgreSQL) verwerken vaak query's met 5 tot 8 knopen, en complexe werklasten kunnen er meer dan 10 hebben.
3. Redundantie en inefficiëntie: Meer dan 90% van de gegenereerde regels is redundant, en meer dan 50% van de niet-redundante regels is triviaal (geen waardevolle optimalisatie).
4. Beperkte effectiviteit: Bestaande methoden falen vaak bij het vereenvoudigen van ingewikkelde, door ORM-tools gegenereerde SQL-query's met diepe geneste subqueries en onnodige joins.

Methodologie: Het SLER-systeem

Het paper introduceert SLER (Scalable Learning-to-Rank based Enumeration for Rewrite rules), een systeem dat drie kerncomponenten combineert om efficiënt en effectief regels te ontdekken:

1. Gestandaardiseerde Enumeratie (Rule Enumerator)

In plaats van alle mogelijke sjablonen te enumereren, gebruikt SLER een gestandaardiseerde template-benadering:

• Concept: Query-plannen worden omgezet naar een canonieke structuur door operatoren (zoals Projectie en Filter) op een specifieke volgorde te plaatsen (bijv. Projectie boven Filter) of redundante operatoren te verwijderen.
• Voordeel: Dit elimineert structurele redundanties vroeg in het proces. Regels die alleen verschillen door de volgorde van operatoren worden niet als nieuwe regels behandeld, maar als redundant.
• Complexiteitsreductie: Hierdoor daalt de verificatiecomplexiteit van exponentieel naar polynomiëel voor bepaalde categorieën van redundante sjablonen.

2. Redundantieverwijdering (RTP-algoritme)

Om de enorme hoeveelheid gegenereerde regels te filteren, introduceert SLER het Reduce by Template Pair (RTP) algoritme:

• Dit algoritme werkt tijdens de enumeratiefase zelf. Voor elk paar sjablonen (bron en doel) wordt een lokale regelbasis opgezet.
• Nieuwe regels worden direct getest op redundantie tegenover reeds gevonden regels binnen dat specifieke paar. Als een regel geen extra optimalisatie biedt ten opzichte van bestaande regels, wordt deze direct verworpen.
• Dit voorkomt dat onnodige regels de verificatiestap (via SMT-oplossers zoals Z3) bereiken, wat de totale doorlooptijd drastisch verkort.

3. Learning-to-Rank (LambdaMART Ranker)

Omdat volledige enumeratie voor zeer grote sjablonen (≥7 knopen) zelfs met SLER te duur blijft, wordt een Learning-to-Rank (LTR) model ingezet:

• Model: Een LambdaMART-model (Gradient Boosted Decision Trees) wordt getraind om de effectiviteit van een regel te voorspellen.
• Features: Het model gebruikt kenmerken zoals de L2-afstand tussen sjablonen, cosine-similariteit, en expressie-complexiteit (aantal operatoren, haakjes, variabelen).
• Training: Het model is getraind op meer dan 11.000 real-world SQL-query's. Regels die de uitvoeringstijd verkorten, krijgen een hoge score.
• Toepassing: Tijdens de enumeratie fungeert de ranker als een pre-filter. Alleen de top-k meest veelbelovende sjabloonparen worden volledig geënumereerd en geverifieerd. Dit maakt het mogelijk om schaalbaar regels te vinden voor complexe query's zonder de volledige zoekruimte te doorlopen.

Belangrijkste Bijdragen

1. Formalisatie en weerlegging van de "Small-to-Large" hypothese: Het paper toont aan dat complexe regels (bijv. 4→2 knopen) niet efficiënt kunnen worden afgeleid door het combineren van eenvoudigere regels (4→3 en 3→2). Slechts 9% van de complexe regels kan zo worden samengesteld, wat directe enumeratie noodzakelijk maakt.
2. Gestandaardiseerde Enumeratie: Een nieuw algoritme dat structurele redundanties elimineert door sjablonen te normaliseren, waardoor de zoekruimte drastisch wordt verkleind.
3. RTP-algoritme: Een efficiënte methode voor het verwijderen van redundante regels tijdens de generatie, wat de verificatiekosten minimaliseert.
4. Learning-to-Rank voor Schaalbaarheid: De introductie van een ML-model om de enumeratie te sturen, waardoor het systeem schaalbaar wordt voor query's met meer dan 6 knopen, wat voorheen onmogelijk was.
5. Grootste Regelbibliotheek: SLER heeft automatisch een repository van meer dan 1 miljoen herschrijvingsregels gegenereerd, wat de grootste empirisch gevalideerde bibliotheek tot nu toe is.

Resultaten

De evaluatie is uitgevoerd op een dataset van 11.518 query's (open-source en commercieel, o.a. Yashan DB).

• Efficiëntie:
  • Voor 4-knooppunten is SLER 3x sneller in enumeratie en >100x sneller in het verwijderen van redundantie vergeleken met WeTune.
  • WeTune faalt (timeout) bij 5 knopen. SLER kan 5-knooppunten in ~30 dagen en 6-knooppunten in ~395 dagen verwerken (zonder ranker).
  • Met de ranker (top-k filtering) kan SLER schaalbaar werken met 10-knooppunten sjablonen, waarbij in 523 minuten meer dan 5.100 effectieve regels worden gevonden.
• Effectiviteit:
  • SLER genereert 679.316 nieuwe, niet-redundante regels voor 5- en 6-knooppunten, wat een uitbreiding is van 98x ten opzichte van de 4-knooppunten regels van WeTune.
  • Query's die door WeTune niet konden worden geoptimaliseerd (bijv. complexe geneste subqueries), worden door SLER succesvol herschreven.
  • De ranker zorgt ervoor dat de meest effectieve regels bovenaan staan: de top 500 regels zorgen voor een gemiddelde verbetering van 98,6% in uitvoeringstijd, terwijl de onderste 50% slechts 11,9% verbetering biedt.
• End-to-End Prestaties:
  • SLER convergeert sneller naar de optimale uitvoeringsplannen (minder stappen nodig).
  • SLER bereikt een hogere optimalisatiegraad voor complexe query's waar WeTune vastloopt in lokale optima.
  • Voor unieke, complexe patronen (Scenario C in de evaluatie) biedt SLER significante optimalisaties waar WeTune 0% verbetering levert.

Betekenis en Conclusie

SLER vertegenwoordigt een doorbraak in database-optimisatie door de schaalbaarheid van regelontdekking te doorbreken. Door de combinatie van gestandaardiseerde templates (voor efficiëntie) en Learning-to-Rank (voor effectiviteit en schaalbaarheid), maakt het systeem het mogelijk om complexe, real-world query-patronen te optimaliseren die voorheen buiten bereik lagen.

De ontdekking van een miljoen regels en de mogelijkheid om regels voor sjablonen met 10+ knopen te vinden, opent de deur voor een volgende generatie database-optimizers die adaptief en uitgebreid kunnen werken met diverse query-patronen, inclusief die gegenereerd door AI-tools en ORM-frameworks. Het systeem is ontworpen om uitbreidbaar te zijn naar andere operatoren (zoals aggregatie en window-functies) in de toekomst.