Technische Samenvatting: Een Praktische Theorie van Generalisatie in Selectiviteitsleren

1. Probleemstelling

Het artikel adresseert de theoretische kloof tussen praktische, query-gedreven modellen voor selectiviteitsleren en de state-of-the-art (SOTA) leerttheorie. Hoewel query-gedreven modellen (bijvoorbeeld regressiemodellen op basis van diepe learning zoals MSCN) superieure empirische prestaties hebben aangetoond ten opzichte van traditionele histogrammen, falen bestaande theoretische kaders – specifiek het Probably Approximately Correct (PAC) leerkader – om hun effectiviteit te verklaren.

Twee primaire beperkingen van eerdere theorie worden geïdentificeerd:

1. Beperkende Hypothese-aannames: SOTA-theorie [26] neemt aan dat selectiviteitspredictoren worden geïnduceerd door kansmaten (die voldoen aan positiviteits- en som-eenheid-beperkingen). Echter, hoogpresterende praktische modellen, zoals regressiegebaseerde diepe learning en LEO, schenden deze beperkingen vaak (bijvoorbeeld door het produceren van negatieve waarden of niet-monotoon outputs) en worden niet geïnduceerd door kansmaten. Bijgevolg zijn bestaande leerbaarheidsresultaten niet van toepassing op deze praktische modellen.
2. Beperking tot In-Distribution: Het PAC-kader karakteriseert generalisatie alleen wanneer trainings- en testwerkloads uit dezelfde verdeling worden getrokken. Het kan geen Out-of-Distribution (OOD) generalisatiefout kwantificeren, wat cruciaal is in real-world databasescenario's waar querywerkloads frequent verschuiven (bijvoorbeeld veranderingen in querycentra of granulariteit).

Het artikel beoogt deze kloven te overbruggen door: (1) de theoretische afhankelijkheid van kansmaten te versoepelen tot het omvatten van getekende maten, en (2) OOD generalisatiefoutgrenzen vast te stellen onder milde aannames.

2. Methodologie en Theoretisch Kader

2.1 Theoretische Grondslagen

De auteurs introduceren een nieuw theoretisch kader gebaseerd op getekende maten.

• Getekende Maten: In tegenstelling tot kansmaten voldoen getekende maten aan telbare additiviteit, maar versoepelen ze de beperkingen van positiviteit (C2) en som-eenheid (C3). Dit stelt de theorie in staat regressiegebaseerde modellen te omvatten die negatieve waarden of waarden kunnen outputten die niet tot eenheid sommeren.
• In-Distribution Leerbaarheid (Stelling 4.1): De auteurs bewijzen dat de klasse van selectiviteitspredictoren geïnduceerd door getekende maten (specifiek die welke absoluut continu zijn ten opzichte van het Lebesgue-maat) PAC-learnable is. Zij stellen vast dat de vet-splijtingsdimensie van deze klasse eindig is, begrensd door $\tilde{O}(C \cdot (1/\gamma)^{\lambda+1})$, waarbij $C$ een grens is voor de totale variatie van de maat en $\lambda$ de VC-dimensie van de ruimtelijke ruimte is. Dit impliceert dat met voldoende trainingsdata de trainingsfout en de ware fout dicht bij elkaar blijven.

2.2 Out-of-Distribution (OOD) Generalisatie

Boven het PAC-kader uitgaande, stelt het artikel Stelling 4.2 vast, die een OOD generalisatiefoutgrens biedt.

• Aannames: De stelling rust op drie milde aannames:
  1. Begrensdheid: De geleerde selectiviteitsfunctie is begrensd.
  2. Ondersteuningsbevatting: De ondersteuning van de testverdeling is bevat in de ondersteuning van de trainingsverdeling (d.w.z. de testwerkload vraagt geen regio's op die onzichtbaar waren tijdens het trainen).
  3. Diversiteit: De trainingsbereiken dekken een diverse set regio's, waardoor wordt gegarandeerd dat de fout niet alleen op specifieke "makkelijke" bereiken wordt geminimaliseerd.
• Resultaat: Onder deze aannames, als een predictor $\hat{S}$ een in-distribution fout heeft die begrensd is door $\epsilon$, is zijn OOD-fout op een andere verdeling $P$ begrensd door $O(\sqrt{\epsilon})$. Dit resultaat geldt voor elke predictor die wordt geïnduceerd door een getekende maat.

2.3 Voorgestelde Strategieën

Gebruikmakend van deze theoretische inzichten, stellen de auteurs twee strategieën voor om bestaande modellen te verbeteren:

Strategie 1: NeuroCDF (Modelleren van CDF's)

• Concept: In plaats van direct de selectiviteit van een query te modelleren, gebruikt NeuroCDF een neurale netwerk om de onderliggende Cumulatieve Verdelingsfunctie (CDF) te modelleren. De selectiviteit van een bereikquery wordt vervolgens berekend als een lineaire combinatie van CDF-waarden bij de hoekpunten van de query (via het principe van inclusie-exclusie).
• Theoretische Garantie: Omdat NeuroCDF expliciet CDF's modelleert, zijn zijn voorspellingen bewijsbaar geïnduceerd door getekende maten. Derhalve erft het de OOD generalisatiegaranties van Stelling 4.2.
• Beperking: NeuroCDF worstelt met relatieve foutmetrieken zoals Qerror, omdat de lineaire combinatie van CDF's negatieve schattingen kan opleveren, die ongeldig zijn voor Qerror.

Strategie 2: SeConCDF (CDF Zelfconsistentie Regularisatie)

• Concept: Om de flexibiliteit van directe selectiviteitsmodelleren (die Qerror ondersteunt) te combineren met de OOD-robustheid van CDF-modelleren, stellen de auteurs SeConCDF voor.
• Mechanisme: SeConCDF traint een standaard query-gedreven model (bijvoorbeeld MSCN of LW-NN) met behulp van een samengestelde verliesfunctie:
  1. Originele Voorspellingsverlies: Standaard verlies (bijvoorbeeld Qerror of RMSE) op directe selectiviteitsvoorspellingen.
  2. CDF Voorspellingsverlies: Een auxiliary loss die het model dwingt CDF-waarden te voorspellen die consistent zijn met de waargenomen data.
  3. Consistentieverlies: Een regularisatieterm die consistentie afdwingt tussen de directe selectiviteitsvoorspelling en de selectiviteit die is afgeleid uit de geleerde CDF's van het model.
• Doel: Deze "zachte beperking" moedigt het model aan zich te gedragen alsof het wordt geïnduceerd door een getekende maat, waardoor de OOD generalisatie wordt verbeterd zonder het vermogen om te optimaliseren voor Qerror te offeren of de modelarchitectuur te veranderen.

3. Experimentele Resultaten

De auteurs evalueren SeConCDF door het te integreren in twee state-of-the-art deep learning-modellen: LW-NN en MSCN. Experimenten worden uitgevoerd op single-table (Census) en multi-table datasets (IMDb-small, DSB, CEB) met synthetische OOD werkloads die Query Center Moves en Query Granularity Shifts omvatten.

• OOD Generalisatie Nauwkeurigheid:
  • Standaard deep-modellen (MSCN, LW-NN) vertonen significante prestatiedegradatie op OOD queries (bijvoorbeeld springt de mediane Qerror van enkele cijfers naar vier cijfers).
  • SeConCDF mitigeert deze daling aanzienlijk. Bijvoorbeeld, op de IMDb-small dataset met een granulariteitsverschuiving, reduceert SeConCDF de mediane Qerror van MSCN van ~103 naar ~2,1, terwijl het sterke in-distribution prestaties behoudt.
  • NeuroCDF toont ook verbeterde OOD-robustheid, maar wordt beperkt door zijn incompatibiliteit met Qerror.
• Query Latentie:
  • Verbeterde nauwkeurigheid in selectiviteitsschatting vertaalt zich direct in betere query-uitvoeringsplannen.
  • In OOD-scenario's bereiken modellen getraind met SeConCDF querylatenties die vergelijkbaar zijn met PostgreSQL en significant beter zijn dan standaard MSCN, dat vaak lijdt aan slechte cardinaliteitsschattingen die leiden tot suboptimale plannen.
• Vergelijking met SOTA Theorie Modellen: Modellen gebaseerd op de vorige SOTA-theorie (geïnduceerd door kansmaten, bijvoorbeeld PtsHist, QuadHist) tonen betere OOD-stabiliteit dan ruwe deep learning-modellen, maar presteren over het algemeen slechter dan deep-modellen in in-distribution nauwkeurigheid en algehele OOD-prestaties in vergelijking met SeConCDF-verbeterde deep-modellen.

4. Belangrijkste Bijdragen

1. Theoretische Uitbreiding: Het artikel bewijst dat selectiviteitspredictoren geïnduceerd door getekende maten leerbaar zijn, waardoor het toepassingsgebied van PAC-leren wordt uitgebreid buiten kansmaten om praktische regressiegebaseerde modellen te omvatten.
2. OOD Generalisatiegrenzen: Het stelt de eerste niet-triviale OOD generalisatiefoutgrenzen vast voor selectiviteitsleren onder milde aannames, en toont aan dat de fout schaalt met de vierkantswortel van de in-distribution fout ($O(\sqrt{\epsilon})$).
3. Praktische Kaders:
   • NeuroCDF: Een nieuw paradigma dat CDF's modelleert om geïnduceerde getekende maten te garanderen.
   • SeConCDF: Een algemene trainingsmethodologie die OOD generalisatie voor bestaande modellen verbetert via CDF zelfconsistentie regularisatie, compatibel met standaard verliesfuncties zoals Qerror.
4. Empirische Validatie: Demonstreert dat deze theoretische inzichten leiden tot tastbare verbeteringen in zowel voorspellingsnauwkeurigheid als querylatentie voor OOD werkloads in real-world databasescenario's.

5. Betekenis en Claims

Het artikel claimt dat de primaire bijdrage het overbruggen van de kloof tussen theorie en praktijk in selectiviteitsleren is. Door de beperkende aanname van kansmaten te versoepelen, bieden de auteurs een theoretische basis die verklaart waarom en wanneer praktische deep learning-modellen generaliseren.

De betekenis ligt in het vermogen om de robuustheid van geleerde cardinaliteitsschatters tegen werkloadverschuivingen formeel te garanderen en praktisch te verbeteren. De auteurs benadrukken dat hun doel niet louter is om bestaande SOTA-modellen te overtreffen in een specifieke benchmark, maar om te valideren dat hun theoretische kader kan worden geoperationaliseerd om bestaande modellen betrouwbaarder te maken in dynamische, real-world omgevingen waar queryverdelingen onvermijdelijk verschuiven. Zij concluderen dat hun aanpak een principiële weg biedt om de betrouwbaarheid van geleerde databasecomponenten te versterken.