The Case for Cardinality Lower Bounds

Dit paper introduceert xBound, het eerste theoretische kader voor het berekenen van bewezen ondergrenzen voor join-groottes, dat het kritieke probleem van onderestimatie in database-optimizers aanpakt en in Microsoft Fabric Data Warehouse aanzienlijke prestatieverbeteringen oplevert.

De kern

Stel je voor dat een database een gigantische, super-snelle bibliotheek is. De "optimiseur" is de super-intelligente bibliothecaris die beslist hoe je een vraag (een query) het snelst beantwoordt. Maar er is een groot probleem: deze bibliothecaris is vaak erg optimistisch, maar dan op de verkeerde manier. Hij denkt: "Oh, dit is maar een klein boekje, ik kan het met één hand oplossen."

In werkelijkheid is het echter een hele zware encyclopedie. Omdat hij de omvang onderschat, geeft hij niet genoeg personeel (CPU-kracht) of ruimte (geheugen) om de taak te doen. Het resultaat? De bibliotheek raakt in paniek, de taken blijven steken en alles wordt langzaam. Dit noemen ze in de paper "cardinality underestimation" (het onderschatten van het aantal resultaten).

De auteurs van dit paper, Mihail Stoian en zijn team, zeggen: "Stop met alleen proberen te voorkomen dat de bibliothecaris denkt dat iets te groot is. We moeten voorkomen dat hij denkt dat iets te klein is."

Hier is de oplossing, vertaald in begrijpelijke taal:

1. Het Probleem: De "Te Klein" Valstrik

In de echte wereld (zoals bij Microsoft Fabric, een enorme cloud-database) gebeurt dit vaak. Soms denkt de computer dat een zoekopdracht 100 regels teruggeeft, terwijl het er eigenlijk 10 miljoen zijn.

• Het gevolg: De computer bereidt zich voor op 100 regels, maar krijgt er 10 miljoen. Het geheugen springt op, de schijven worden overbelast en de vraag duurt plotseling 20 keer langer dan normaal.
• De huidige oplossing: Er bestonden al methoden om te zeggen: "Hé, dit kan maximaal zo groot zijn" (een bovengrens). Maar dat helpt niet als de computer denkt dat het klein is. Je hebt een ondergrens nodig.

2. De Oplossing: xBound (De "Veiligheidsnet"-Rekenmachine)

De auteurs hebben xBound bedacht. Dit is een wiskundig frame dat zegt: "Zelfs als we niets anders weten, kan dit resultaat nooit kleiner zijn dan X."

Hoe doen ze dit zonder de hele database te doorzoeken? Ze gebruiken slimme statistieken, alsof je een schatting maakt op basis van een paar steekproeven:

• De Analogie van de Lijstjes: Stel je hebt twee lijsten met namen.
  • Lijst A heeft 1000 namen.
  • Lijst B heeft 500 namen.
  • De bibliothecaris denkt: "Ze hebben misschien maar 10 namen gemeen."
  • xBound kijkt naar de uitersten: "Oké, wat is het kleinste aantal namen dat ze zeker gemeen hebben? Zelfs als we alleen kijken naar de meest voorkomende namen (de 'heavy hitters') en de minimale en maximale waarden, moeten ze op zijn minst 50 namen gemeen hebben."
• De Wiskunde (Simpele versie): Ze gebruiken een trucje met "normen" (een soort maatstaf voor de spreiding van de data). Ze weten dat als je twee lijsten kruist, het resultaat nooit kleiner kan zijn dan een bepaalde berekening gebaseerd op de kleinste en grootste waarden in die lijsten.

3. De "Kleef-Techniek" (Norm Stitching)

Soms weten we niet precies hoeveel namen er op een specifiek punt staan, maar wel op grotere blokken.

• Analogie: Stel je hebt een ladder. Je weet hoe hoog de 4e sport is en hoe hoog de 8e sport is. Je wilt weten hoe hoog de 6e sport is.
• De truc: xBound "naait" (stitching) de informatie aan elkaar. Ze zeggen: "Als de 4e sport op 1 meter staat, en de 8e op 2 meter, dan is de 6e sport zeker niet lager dan 1,5 meter." Ze vullen de gaten op een veilige manier op, zodat ze altijd een ondergrens hebben die klopt.

4. Wat levert dit op?

Toen ze dit testten in Microsoft Fabric:

• Ze corrigeerden 23,6% van de fouten waarbij de database dacht dat iets te klein was.
• Voor de slechtste gevallen (waar de database totaal de mist in ging) werd de snelheid 20 keer sneller.
• Het voorkomt dat de computer "honger" krijgt (geheugen tekort) omdat hij te weinig resources heeft toegewezen.

Samenvatting in één zin

xBound is als een veiligheidsnet voor de database: het zorgt ervoor dat de computer nooit denkt dat een taak "makkelijk en klein" is als er een kans is dat het "groot en zwaar" is, waardoor hij altijd genoeg personeel en ruimte reserveert om de taak snel af te ronden.

Het is een stap in de richting van databases die niet alleen slim zijn, maar ook veilig en betrouwbaar, zelfs als de data heel complex is.

Technische samenvatting

Hier is een gedetailleerde technische samenvatting van het paper "The Case for Cardinality Lower Bounds" in het Nederlands.

Probleemstelling: Systematische Onderschatting

Hoewel er decennialang onderzoek is gedaan naar query-optimatie, blijft cardinaliteitsschatting (het voorspellen van de grootte van tussentijdse resultaten) de zwakke schakel ("Achilleshiel") van database-systemen.

• Het kernprobleem: Industriële systemen tonen een systematische neiging tot onderschatting van de resultaatgrootte.
• Productie-impact: In Microsoft Fabric Data Warehouse (DW) zorgt een klein percentage extreme onderschattingen (0,05%) voor 95% van alle CPU-onderallocatie. Dit leidt dagelijks tot duizenden queries met ernstige, voorkombare vertragingen en resource-uitputting (bijv. out-of-memory fouten).
• Huidige tekortkomingen: Bestaande theoretische werken (zoals LpBound) bieden alleen provable upper bounds (bovengrenzen). Deze corrigeren overschattingen, maar lossen het gevaarlijkere probleem van onderschatting niet op. Een onderschatting leidt vaak tot het kiezen van fragiele uitvoeringsplannen (zoals geneste lussen in plaats van hash-joins) en resource-starre, wat catastrofaal kan zijn.

Methodologie: xBound

De auteurs introduceren xBound, het eerste theoretische kader voor het berekenen van provable lower bounds (ondergrenzen) voor join-groottes. Het doel is om de schattingen van de optimizer "van onderen af te knippen" (clipping) om een wiskundige veiligheidsnet te bieden.

Kernprincipes:

1. Reverse Inequalities: In plaats van de gebruikelijke ongelijkheden die een bovengrens geven, gebruikt xBound "reverse inequalities" om een ondergrens te vinden voor het inwendig product (inner product) van degree-vectoren (de frequentie van join-sleutels).
2. Benodigde Statistieken: xBound vereist slechts een handvol lichte statistieken van de basistabellen:
   • $\ell_\infty$: De maximale frequentie van een sleutel.
   • $\ell_2$: De Euclidische norm van de degree-vector.
   • $\ell_{-\infty}$: De minimale frequentie van een sleutel.
   • $\ell_0$: Het aantal unieke join-sleutels (ondergrens).
3. Aanpak voor Join-grootte:
   • Stap 1: Bepalen van join-sleutels: De auteurs leiden eerst een harde ondergrens af voor het aantal unieke join-sleutels dat in beide tabellen voorkomt. Dit wordt gedaan via zonemaps (min/max waarden) of probabilistische schetsen (ThetaSketches/HyperLogLog).
   • Stap 2: Toepassing van Reverse Inequaliteiten: Met deze ondergrens voor het aantal sleutels ($m$) kunnen ze de degree-vectoren beperken tot de eerste $m$ elementen (die gegarandeerd niet-nul zijn). Hierop passen ze reverse ongelijkheden toe, zoals de Pólya–Szegő-ongelijkheid en de Generalized Reverse Hölder's inequality.
   • Stap 3: Min-Degree Bound: Een specifieke, eenvoudige ondergrens die alleen $\ell_1$ en $\ell_{-\infty}$ vereist, gebaseerd op het idee dat alle andere tabellen joinen met de minimale frequentie.

Technische Optimalisaties:

• Heavy Partition: Om de kwaliteit van de ondergrens te verhogen, worden "heavy hitters" (frequent voorkomende sleutels) apart bijgehouden en exact berekend, terwijl de rest van de data via de statistische methoden wordt benaderd.
• Norm Stitching: Omdat de ondergrens vaak op een willekeurige lengte $m$ moet worden berekend, maar de opgeslagen statistieken vaak op machten van 2 staan, wordt een techniek genaamd "norm stitching" gebruikt. Hiermee worden $\ell_2$-waarden geëxtrapoleerd door het gebruik van bekende $\ell_\infty$-waarden voor de ontbrekende elementen.
• Light Partitions: Het bereik van waarden wordt opgesplitst in bins om fijnmazigere ondergrenzen te krijgen voor selectieve queries.
• Predicatenondersteuning: Het systeem ondersteunt gelijkheids-, range-, conjunctie- en disjunctie-predicaten door de statistieken per bin of voor MCV's (Most Common Values) aan te passen.

Belangrijkste Bijdragen

1. xBound Framework: Het eerste theoretische kader voor het berekenen van proefbare ondergrenzen voor join-groottes, gebaseerd op reverse ongelijkheden en $\ell_p$-normen.
2. Uitbreiding naar Filtered Scans: Het kader is uitgebreid om ondergrenzen te bieden voor tabelscans met filters (equality, range, AND/OR), wat essentieel is voor real-world queries.
3. Empirische Validatie in Productie: De auteurs evalueren xBound in de Microsoft Fabric Data Warehouse omgeving, wat een zeldzame en waardevolle validatie in een echte productie-omgeving is.

Resultaten

De evaluatie werd uitgevoerd op de StackOverflow-CEB benchmark (220 GB dataset) binnen Microsoft Fabric DW.

• Correctie van Onderschatting: xBound corrigeerde 23,6% van de onderschattingen van de Fabric DW optimizer.
• Verbetering van Q-Error: De P90 Q-error (90e percentiel van de foutmarge) voor onderschattingen werd met een factor 35,8x verlaagd.
• Query Snelheid: Door de correcte toewijzing van CPU-resources (gebaseerd op de hogere, veiligere schattingen) werden end-to-end query-snelheidsverbeteringen bereikt tot 20,1x voor zwaar onderschatte queries.
• Generalisatie: De methode werkte ook effectief op DuckDB en PostgreSQL, hoewel Fabric DW de grootste winst liet zien vanwege de specifieke resource-allocatieproblemen.

Significantie en Toekomstperspectief

• Paradigmaverschuiving: Het paper pleit voor een verschuiving in de database-community van alleen focus op bovengrenzen (voor over-schatting) naar een evenwichtige benadering die ook ondergrenzen (voor onder-schatting) garandeert.
• Productieveiligheid: In tegenstelling tot ML-gebaseerde schatters die gemiddeld goed presteren maar geen garanties bieden, biedt xBound wiskundige zekerheid tegen catastrofale worst-case scenario's.
• Open Richtingen: De auteurs identificeren uitdagingen voor toekomstig werk, zoals het uitbreiden naar cyclische queries, het ondersteunen van complexere predicaten (zoals LIKE/REGEX), en het verfijnen van de probabilistische garanties bij het combineren van meerdere schetsen.

Kortom, xBound demonstreert dat zelfs een eerste stap richting proefbare ondergrenzen aanzienlijke prestatieverbeteringen in productie-systemen kan opleveren en een cruciale missing link is in de query-optimatie.