🤖 machine learning

Selectivity Estimation for Linear Queries via Online Learning

Dit artikel stelt een online leerraamwerk voor om selectiviteit te schatten in dynamische databaseomgevingen, waarbij theoretische regret-bounds wordt vastgesteld voor histogramgebaseerde lineaire queries onder zowel statische als dynamische instellingen.

Oorspronkelijke auteurs: Fangzhu Shen, Debmalya Panigrahi, Sudeepa Roy

Gepubliceerd 2026-07-07

📖 6 min leestijd🧠 Diepgaand

CC BY 4.0

Oorspronkelijke auteurs: Fangzhu Shen, Debmalya Panigrahi, Sudeepa Roy

Oorspronkelijk artikel gelicentieerd onder CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Dit is een AI-gegenereerde uitleg van het onderstaande artikel. Het is niet geschreven of goedgekeurd door de auteurs. Raadpleeg het oorspronkelijke artikel voor technische nauwkeurigheid. Lees de volledige disclaimer

Stel je voor dat je een detective bent die probeert te raden hoeveel mensen in een enorme stad aan een specifieke beschrijving voldoen, zoals "een rode hoed dragen." In de wereld van databases wordt dit selectiviteitschatting genoemd: de database is de stad, de mensen zijn de data en de beschrijving is een "query". Als je gok fout is, kan de computer een verschrikkelijk plan kiezen om het antwoord te vinden, wat tijd en energie verspilt.

Lange tijd gebruikten detectives (databasesystemen) eenvoudige vuistregels, zoals aan te nemen dat de hoedkleur van iemand onafhankelijk is van hun schoenmaat. Maar het echte leven is rommelig; deze regels falen vaak. Recentelijk zijn mensen begonnen met het gebruiken van "AI-detectives" (machine learning) die leren van eerdere gokken om beter te worden. Echter, de meeste AI-detectives werden getraind in een laboratorium waar de stad nooit veranderde en de vragen altijd hetzelfde waren.

Dit artikel vraat: Wat gebeurt er wanneer de stad constant verandert en de vragen onvoorspelbaar zijn? De auteurs stellen een nieuwe manier voor om dit probleem aan te pakken met behulp van een concept genaamd Online Learning.

Het Spel: Gokken in het Donker

De auteurs hebben een spel opgezet om te testen hoe goed een AI-detective kan leren in een chaotische wereld. Zo werkt het spel, ronde voor ronde:

De Vraag: Er komt een nieuwe query aan (bijv. "Hoeveel mensen dragen een rode hoed?").
De Gok: De AI moet onmiddellijk een gok doen, gebaseerd op alleen wat hij eerder heeft gezien. Hij weet het antwoord nog niet.
De Onthulling: Het ware antwoord wordt onthuld.
De Score: De AI krijgt een "straf" (genaamd Loss) gebaseerd op hoe fout hij zat.
- Squared Loss (Kwadratisch Verlies): Denk aan een "strenge leraar." Als je er een klein beetje naast zit, is dat oké. Maar als je er enorm naast zit, explodeert de straf. Dit is belangrijk omdat één grote fout in een database een plan kan laten crashen.
- Absolute Loss (Absoluut Verlies): Denk aan een "eerlijke leraar." Deze telt gewoon hoe ver je er vandaan zat, ongeacht of het een beetje of een veel was.

De Benchmark: De "Beste Statische" Detective

Om te weten of de AI het goed doet, moeten we hem vergelijken met iemand. De auteurs vergelijken de AI met de best mogelijke vaste strategie die gekozen had kunnen worden als we de hele toekomst van tevoren hadden gekend.

De Statische Wereld: Stel je voor dat de bevolking van de stad vaststaat (niemand verhuist in of uit), maar de vragen veranderen. De "beste statische strategie" is een enkele, perfecte kaart van die stad.
De Dynamische Wereld: Stel je voor dat de stad chaotisch is. Mensen komen voortdurend aan en gaan weg, en veranderen voortdurend van hoed. De "beste statische strategie" is nog steeds slechts één vaste kaart. De taak van de AI is om te zien hoe dicht hij bij die ene vaste kaart kan komen, zelfs terwijl de stad blijft verschuiven.

Waarom vergelijken met een vaste kaart? Als we de AI zouden vergelijken met een "magische kaart" die elke seconde perfect verandert om de stad te matchen, zou geen enkele AI kunnen winnen. Het doel is om te zien of de AI het onderliggende patroon kan vinden dat standhoudt, zelfs in een veranderende wereld.

De Resultaten: Hoe goed kunnen ze worden?

De auteurs hebben dit spel gespeeld met verschillende soorten vragen en verschillende niveaus van chaos. Ze maten de "Regret" (het berouw), wat simpelweg het verschil is tussen de totale straf van de AI en de straf van de best mogelijke vaste strategie.

1. De Statische Stad (Data verandert niet)

Het Goede Nieuws: Als de data stabiel is, leert de AI zeer snel.
De Analogie: Stel je voor dat je probeert het gewicht van een enkele, onveranderlijke rots te raden. Je stelt vragen zoals "Is het zwaarder dan 10 kg?" en "Is het lichter dan 20 kg?".
Het Resultaat: De auteurs ontdekten dat voor complexe vragen de fouten van de AI zeer langzaam groeien—slechts volgens de logaritme van het aantal mogelijke categorieën. In gewone mensentaal: zelfs als de stad een miljoen verschillende wijken heeft, maakt de AI slechts een paar extra fouten om de hele kaart te leren kennen. Het is ongelooflijk efficiënt.

2. De Dynamische Stad (Data verandert constant)

De Uitdaging: Nu verandert de stad elke seconde. De "beste vaste kaart" is al licht verouderd op het moment dat de AI ernaar kijkt.
Het Resultaat: De fouten groeien naarmate het spel vordert, maar de auteurs vonden specifieke limieten:
- Voor eenvoudige vragen (Point Queries): De fouten groeien met de wortel van het aantal rondes.
- Voor complexe vragen (Range/Subset Queries): De fouten groeien met de wortel van de rondes vermenigvuldigd met de logaritme van de stadsgrootte.
- Voor de "Strenge Leraar" (Squared Loss): De fouten groeien zeer langzaam, alleen met de logaritme van de rondes. Dit is verrassend goed voor een chaotische omgeving!

De Geheime Wapens (Algoritmen)

Hoe hebben ze deze resultaten bereikt? Ze gebruikten slimme wiskundige trucs:

De "Meest Gebalanceerde" Gok (Sequential Maximum Entropy):
- De Analogie: Stel je voor dat je een zak knikkers hebt, en je weet enkele regels over hen (bijv. "Er zijn 50% rode knikkers"). Je weet de rest niet. De slimste gok is om aan te nemen dat de overige knikkers zo gelijkmatig mogelijk verdeeld zijn. Dit wordt "Maximum Entropy" genoemd.
- Hoe het helpt: De AI houdt een lijst bij van alle mogelijke stadskaarten die passen bij de aanwijzingen tot nu toe. In plaats van een willekeurige kaart uit die lijst te kiezen, kiest hij de "meest gebalanceerde" kaart. Als hij een vraag fout heeft, leert hij dat de ware stad ver verwijderd is van deze gebalanceerde gok, waardoor hij de mogelijkheden snel kan verfijnen.
Het "Hadamard" Puzzel (Voor het bewijzen van limieten):
- Om te bewijzen dat geen enkele AI beter kan presteren dan een bepaalde limiet, creëerden de auteurs een lastige puzzel met behulp van een speciale matrix van getallen (een Hadamard-matrix). Ze verborgen willekeurige veranderingen in de stad op een manier die leek op ruis. Dit bewees dat zelfs de slimste AI vast zou lopen in het gokken, wat een "bodem" vaststelde voor hoe goed iemand ook zou kunnen presteren.

De Conclusie

Dit artikel biedt een theoretisch vangnet voor het gebruik van AI in databases. Het bewijst dat zelfs als de data rommelig is en de vragen onvoorspelbaar zijn, we algoritmen kunnen bouwen die efficiënt leren.

Als de data stabiel is: Leert de AI bijna perfect snel.
Als de data chaotisch is: Leert de AI nog steeds, en we weten precies hoe snel het zal convergeren naar een goede oplossing.

De auteurs concluderen dat hoewel hun wiskunde complex is, de boodschap simpel is: Leren-gebaseerde selectiviteitschatting is niet alleen een gelukkige gok; het is een wiskundig onderbouwde strategie die werkt, zelfs in de wildste, meest veranderende omgevingen. Ze laten de deur open voor toekomstig werk om deze ideeën te testen op echte databases en om zelfs complexere soorten vragen aan te pakken, zoals het samenvoegen (joining) van meerdere tabellen.

Technische Samenvatting: Selectiviteitschatting voor Lineaire Queries via Online Learning

Probleemstelling

Selectiviteitschatting is een fundamenteel onderdeel van query-optimalisatie, wat query-optimizers in staat stelt om efficiënte executieplannen te kiezen. Hoewel traditionele methoden vertrouwen op sterke aannames (bijv. attributie-onafhankelijkheid) en vooraf berekende statistieken (histogrammen, sketches), hebben recente op machine learning gebaseerde benaderingen empirisch veelbelovende resultaten laten zien door machine learning te gebruiken om complexe datadistributies te vangen. Bestaande theoretische studies van deze op learning gebaseerde benaderingen zijn echter grotendeels beperkt tot statische databases met vaste query-distributies.

In de praktijk zijn real-world databaseomgevingen dynamisch: data wordt continu ingevoegd, bijgewerkt en verwijderd, en query-workloads kunnen onvoorspelbaar verschuiven zonder een stationaire distributie te volgen. Statische modellen die getraind zijn op historische data kunnen verouderd raken, wat leidt tot een verminderde nauwkeurigheid of de noodzaak van dure hertraining. Dit paper adresseert deze kloof door een theoretisch kader voor selectiviteitschatting in een volledig dynamische, distributievrije setting voor te stellen.

Het kernprobleem wordt geformuleerd als een online learning taak waarbij:

In elke ronde $t$ een query-vector $v_t$ arriveert.
De learner de selectiviteit $\hat{\sigma}_t$ voorspelt.
De ware selectiviteit $\sigma_t = \langle v_t, w_t \rangle$ wordt onthuld, waarbij $w_t$ de onderliggende database-toestand is (een vector in de $k$ -dimensionale simplex $\Delta_k$ ).
De learner een verlies incasseert op basis van de voorspellingsfout.

Het doel is om regret (spijt) te minimaliseren, gedefinieerd als het verschil tussen het cumulatieve verlies van de learner en het cumulatieve verlies van de beste vaste database-vector (gekozen in hindsight). Het paper wijst expliciet op de vergelijking met een dynamische benchmark (waarbij de database elke ronde verandert), omdat aangetoond is dat geen enkel algoritme niet-triviale regret-garanties kan behalen tegen een dergelijke benchmark in een adversariële setting.

Methodologie en Kader

De auteurs analyseren twee verschillende database-instellingen:

Statische Databases: De onderliggende database-vector $w^*$ is vast maar onbekend, terwijl queries willekeurig kunnen zijn.
Dynamische Databases: De database-vector $w_t$ kan van ronde tot ronde willekeurig veranderen, naast de queries.

De studie richt zich op lineaire queries (inclusief punt-, range- en subset-queries) gerepresenteerd door vectoren $v \in [0, 1]^k$ . Er worden twee standaard verliesfuncties overwogen:

Squared Loss (Kwadratisch Verlies): $(\sigma_t - \hat{\sigma}_t)^2$ , waarbij grote fouten zwaar worden bestraft.
Absolute Loss (Absoluut Verlies): $|\sigma_t - \hat{\sigma}_t|$ , wat de gemiddelde fout vangt.

Belangrijke Algoritmen

Sequential Maximum Entropy (SeqMaxEnt): Voorgesteld voor de statische setting. Dit algoritme houdt een haalbaar gebied van database-vectoren bij die consistent zijn met alle geobserveerde query-selectiviteit paren. In elke ronde voorspelt het de selectiviteit van de maximum entropy distributie binnen dit haalbare gebied. De intuïtie is dat als het algoritme een groot verlies lijdt, de ware database "ver" moet zijn van de huidige maximum entropy schatting, wat zorgt voor significante progressie in het identificeren van de ware toestand.
Exponentially Weighted Online Optimization (EWOOW): Toegepast op de dynamische setting voor squared loss.
Follow-the-Regularized-Leader (FTRL): Toegepast op de dynamische setting voor absolute loss, gebruikmakend van verschillende regularisaties ( $\ell_2$ voor punt-queries en negatieve entropie voor subset/lineaire queries).

Belangrijkste Resultaten en Regret Bounds

Het paper stelt bijna nauwe (nearly tight) upper en lower bounds op de regret vast, samengevat hieronder. De bounds zijn afhankelijk van de support-grootte $k$ (aantal bins) en de tijdshorizon $T$ .

1. Statische Databases

In deze setting hangt de regret primair af van $k$ en is deze onafhankelijk van $T$ .

Squared Loss:
- Upper Bound: $O(\log k)$ bereikt door SeqMaxEnt voor range-, subset- en lineaire queries.
- Lower Bound: $\Omega(\log k)$ voor range-queries.
- Resultaat: $\Theta(\log k)$ regret.
Absolute Loss:
- Upper Bound: $O(\sqrt{k \log k})$ bereikt door SeqMaxEnt voor algemene lineaire queries.
- Lower Bound: $\Omega(\sqrt{k / \log k})$ voor subset-queries.
- Resultaat: $\tilde{\Theta}(\sqrt{k})$ regret.
Punt-queries: De regret is constant ( $O(1)$ ) onder beide verliesfuncties, aangezien de database snel geïdentificeerd kan worden.

2. Dynamische Databases

In deze setting hangt de regret primair af van $T$ .

Squared Loss:
- Lower Bound: $\Omega(\log T)$ voor punt-queries.
- Upper Bound: $O(k \log T)$ met gebruik van EWOO.
- Resultaat: Er bestaat een gat tussen $\Omega(\log T)$ en $O(k \log T)$ .
Absolute Loss:
- Punt-queries: Strakke (tight) bound van $\Theta(\sqrt{T})$ .
- Subset/Lineaire Queries: Strakke bound van $\Theta(\sqrt{T \log k})$ .
- Resultaat: Er is een polynomiale separatie in de dominante parameter ( $T$ ) tussen squared loss ( $\log T$ ) en absolute loss ( $\sqrt{T}$ ).

Lower Bound Technieken

Statische Absolute Loss: De auteurs construeren een lower bound met behulp van een genormaliseerde Hadamard-matrix. Ze coderen onafhankelijke random variabelen in een enkele vaste database-vector. De query-sequentie onthult deze variabelen stapsgewijs, waardoor de learner in elke ronde een verwachte loss incasseert. Een trade-off wordt beheerd tussen de magnitude van de perturbatie (om te garanderen dat de vector in de simplex blijft) en de resulterende loss.
Dynamische Squared Loss: De lower bound wordt afgeleid door het probleem te reduceren tot het schatten van een parameter $\mu$ getrokken uit een Uniform distributie, waarbij de database-toestand een Bernoulli( $\mu$ ) sample is. De regret komt overeen met de posterior variantie van $\mu$ , die een harmonische reeks vormt, wat resulteert in $\Omega(\log T)$ .

Betekenis en Bijdragen

Het paper claimt de volgende bijdragen:

Distributievrije Formulering: Het biedt een online learning-formulering voor selectiviteitschatting die geen distributieve aannames oplegt aan data of queries, waarmee de beperkingen van eerdere op PAC-learning gebaseerde studies wordt geadresseerd die vaste distributies veronderstellen.
Theoretische Garanties: Het stelt (bijna) nauwe regret bounds vast voor veelvoorkomende query-klassen (punt, range, subset, lineair) in zowel statische als dynamische database-settings onder zowel squared als absolute loss functies.
Algoritmisch Kader: Het introduceert het SeqMaxEnt algoritme, dat gebruikmaakt van maximum entropy principes om logaritmische regret te bereiken in de statische setting, en past standaard online optimalisatietechnieken (EWOO, FTRL) toe in de dynamische setting.
Inzicht in Verliesfuncties: Het werk benadrukt een fundamenteel verschil tussen squared en absolute loss functies, door een polynomiale separatie te tonen in hun regret-schaling onder dynamische condities.

De auteurs merken op dat hoewel praktische systemen vaak periodieke hertraining gebruiken, dit werk een rigoureus theoretisch fundament biedt voor het begrijpen van de grenzen van leren in dynamische omgevingen zonder distributieve aannames. Toekomstige onderzoeksrichtingen die worden geïdentificeerd, omvatten het dichten van de kloof tussen de upper en lower bounds voor dynamische squared loss, het bepalen van optimale bounds voor range-queries onder absolute loss, en het uitbreiden van het kader naar rijkere query-klassen zoals joins.