🤖 machine learning

A Practical Theory of Generalization in Selectivity Learning

Ursprüngliche Autoren: Peizhi Wu, Haoshu Xu, Ryan Marcus, Zachary G. Ives

Veröffentlicht 2026-05-19

📖 5 Min. Lesezeit🧠 Tiefgang

Ursprüngliche Autoren: Peizhi Wu, Haoshu Xu, Ryan Marcus, Zachary G. Ives

Originalarbeit lizenziert unter CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Dies ist eine KI-generierte Erklärung des untenstehenden Papers. Sie wurde nicht von den Autoren verfasst oder gebilligt. Für technische Genauigkeit konsultieren Sie das Originalpaper. Vollständigen Haftungsausschluss lesen

Stellen Sie sich vor, Sie sind ein Koch, der vorhersagen soll, wie viele Personen zu einer Dinnerparty erscheinen werden, basierend auf den gesendeten Einladungen. In der Welt der Datenbanken nennt man dies Selektivitätsschätzung: das Raten, wie viele Datenzeilen einer spezifischen Suchanfrage entsprechen werden.

Seit Jahrzehnten verwendeten Datenbanksysteme einfache Regeln (wie „nehmen Sie an, alle sind gleichmäßig verteilt"), um diese Schätzungen vorzunehmen. Doch diese Regeln versagen oft, wenn die Daten unordentlich sind oder die Fragen knifflig. Kürzlich begannen Wissenschaftler, Maschinelles Lernen (KI) einzusetzen, um diese Muster zu erlernen. Diese KI-Modelle sind hervorragend im Raten für Fragen, die sie zuvor gesehen haben, doch sie scheitern oft katastrophal, wenn sie mit einer Frage konfrontiert werden, die sich geringfügig von dem unterscheidet, worauf sie trainiert wurden. Dies wird als Out-of-Distribution (OOD)-Problem bezeichnet.

Dieser Artikel, „A Practical Theory of Generalization in Selectivity Learning" (Eine praktische Theorie der Generalisierung im Selektivitätslernen), versucht, die Lücke zwischen der Mathematik zu schließen, die besagt, dass KI funktionieren sollte, und der Realität, dass sie oft nicht gut funktioniert, wenn es um neue, seltsame Fragen geht.

Hier ist die Aufschlüsselung in einfachen Worten:

1. Das Problem: Die „Wahrscheinlichkeits"-Falle

Die besten mathematischen Theorien, die wir bisher hatten (sogenanntes PAC-Lernen), beruhten auf einer strengen Regel: Die Vorhersagen der KI mussten sich wie eine perfekte Wahrscheinlichkeitskarte verhalten.

Die Metapher: Stellen Sie sich eine Karte vor, bei der die Tinte die Wahrscheinlichkeit darstellt, Daten zu finden. Die alte Theorie sagte: „Die Tinte muss immer positiv sein, und die Gesamtmenge der Tinte auf der gesamten Karte muss genau 1 betragen."
Die Realität: Die leistungsfähigsten KI-Modelle (wie Deep Learning) halten sich nicht an diese strengen Regeln. Sie könnten „negative Tinte" oder „mehr als 100 % Tinte" an bestimmten Stellen vorhersagen, weil sie lediglich versuchen, Fehler zu minimieren. Da sie die Regel der „perfekten Karte" brachen, sagte die alte Mathematik: „Wir können nicht beweisen, dass diese Modelle bei neuen Daten funktionieren."
Das Ergebnis: Wir hatten leistungsfähige Werkzeuge, aber keine mathematische Garantie dafür, dass sie nicht versagen würden, wenn sich die Daten änderten.

2. Der Durchbruch: Die Theorie der „Vorzeichen-Karte"

Die Autoren erkannten, dass wir keine „perfekte Wahrscheinlichkeitskarte" benötigen. Wir brauchen lediglich eine „Vorzeichen-Karte".

Die Metapher: Stellen Sie sich eine Karte vor, bei der die Tinte positiv (blau) oder negativ (rot) sein kann. Solange die Mathematik ausgeglichen ist, funktioniert die Karte noch.
Die Entdeckung: Sie bewiesen, dass selbst wenn ein KI-Modell diese „vorzeichenbehafteten" (positiven und negativen) Vorhersagen verwendet, es dennoch lernbar ist.
Der große Gewinn: Sie bewiesen, dass, wenn ein KI-Modell auf Trainingsdaten gut lernt, es auch bei neuen, ungesehenen Daten (OOD) eine anständige Leistung erbringen wird, vorausgesetzt, die neuen Daten sind nicht völlig fremd (z. B. befinden sie sich noch im allgemeinen Bereich, den das Modell kennt). Dies ist ein großer Sprung, da er die leistungsfähigen Deep-Learning-Modelle abdeckt, die die alten Theorien nicht erklären konnten.

3. Die Lösung: Zwei neue Strategien

Unter Verwendung dieser neuen „Vorzeichen-Karte"-Theorie entwickelten die Autoren zwei praktische Werkzeuge, um bestehenden KI-Modellen zu helfen, bei neuen Daten besser zu raten.

Strategie A: NeuroCDF (Der „CDF"-Ansatz)

Anstatt die KI zu bitten, die Antwort direkt zu erraten (z. B. „Wie viele Zeilen?"), baten sie die KI, die Kumulative Verteilungsfunktion (CDF) zu erraten.

Die Metapher: Anstatt zu fragen: „Wie viele Personen sind gerade im Raum?" (was schwierig ist, wenn sich der Raum ändert), fragten sie die KI: „Wie viele Personen sind im Raum bis zu diesem spezifischen Punkt?"
Funktionsweise: Die KI lernt die Form der Datenverteilung (die CDF). Um die Antwort für eine spezifische Anfrage zu erhalten, addiert und subtrahiert das System einfach diese CDF-Punkte (wie die Berechnung der Fläche eines Rechtecks durch Kenntnis der Ecken).
Der Vorteil: Da diese Methode die KI mathematisch zwingt, sich wie eine „Vorzeichen-Karte" zu verhalten, ist garantiert, dass sie bei neuen Daten robust ist.
Der Haken: Das Training ist etwas knifflig, da es manchmal zu einer negativen Zahl führen kann, was für eine Zeilenzählung keinen Sinn ergibt.

Strategie B: SeConCDF (Der „Selbstkonsistenz"-Trainer)

Dies ist die praktischere „Plug-and-Play"-Lösung. Sie nimmt jedes bestehende KI-Modell und gibt ihm eine spezielle Trainingsroutine.

Die Metapher: Stellen Sie sich einen Schüler vor, der eine Prüfung ablegt. Normalerweise merkt er sich nur die Antworten. Mit SeConCDF bittet der Lehrer den Schüler zusätzlich zu erklären, warum die Antwort so ist, basierend auf den zugrunde liegenden Regeln (den CDFs).
Funktionsweise: Die KI wird trainiert, zwei Dinge gleichzeitig zu tun:
1. Die Antwort direkt vorherzusagen (die übliche Art).
2. Die zugrunde liegenden CDFs vorherzusagen und zu prüfen, ob diese CDFs mit der Antwort konsistent sind.
Der Vorteil: Diese „Selbstprüfung" zwingt die KI, die zugrunde liegende Struktur der Daten zu lernen, nicht nur Antworten auswendig zu lernen. Sie macht das Modell viel robuster gegenüber neuen Fragen, ohne die Architektur des Modells zu ändern oder es zu verlangsamen.

4. Die Ergebnisse: Funktioniert es?

Die Autoren testeten diese Ideen an realen Datensätzen aus Datenbanken (wie Film-Datenbanken und Volkszählungsdaten).

Genauigkeit: Als sie den Modellen Fragen stellten, die sich geringfügig von den Trainingsdaten unterschieden (z. B. Fragen zu einem anderen Jahr oder einem anderen Wertebereich), machten die mit SeConCDF trainierten Modelle weit weniger Fehler als die Standardmodelle.
Geschwindigkeit: Da die Schätzungen genauer waren, verschwendete das Datenbanksystem keine Zeit damit, versucht, die falsche Datenmenge zu verarbeiten. Die Abfragen liefen schneller.
Vergleich: Die neuen Methoden schlugen die alten „perfekten Wahrscheinlichkeits"-Modelle (die theoretisch sicher, aber praktisch schwach waren) und verbesserten die leistungsfähigen Deep-Learning-Modelle (die praktisch stark, aber theoretisch riskant waren) erheblich.

Zusammenfassung

Der Artikel sagt: „Wir haben eine neue mathematische Regel gefunden, die beweist, dass leistungsfähige KI-Modelle bei neuen Daten vertrauenswürdig sein können, selbst wenn sie nicht den alten strengen Regeln folgen. Anschließend entwickelten wir eine Trainingsmethode (SeConCDF), die diese Regel nutzt, um Datenbank-KI-Modelle bei der Bewältigung unerwarteter Fragen viel schlauer und zuverlässiger zu machen."

Technische Zusammenfassung: Eine praktische Theorie der Generalisierung beim Selectivity-Learning

1. Problemstellung

Der Artikel adressiert die theoretische Lücke zwischen praktischen, abfragegesteuerten Modellen für das Selectivity-Learning und der state-of-the-art (SOTA) Lerntheorie. Während abfragegesteuerte Modelle (z. B. Deep-Learning-Regressoren wie MSCN) eine überlegene empirische Leistung gegenüber traditionellen Histogrammen gezeigt haben, können bestehende theoretische Rahmenwerke – insbesondere das Probably Approximately Correct (PAC)-Lernframework – deren Wirksamkeit nicht erklären.

Zwei Hauptbeschränkungen der vorherigen Theorie werden identifiziert:

Restriktive Hypothesenannahmen: Die SOTA-Theorie [26] geht davon aus, dass Selectivity-Prädiktoren durch Wahrscheinlichkeitsmaße induziert werden (die Positivitäts- und Summe-zu-Eins-Bedingungen erfüllen). Hochperformante praktische Modelle, wie regressionsbasiertes Deep Learning und LEO, verletzen diese Bedingungen jedoch häufig (z. B. durch die Erzeugung negativer Werte oder nicht-monotoner Ausgaben) und werden nicht durch Wahrscheinlichkeitsmaße induziert. Folglich gelten die bestehenden Ergebnisse zur Lernbarkeit nicht für diese praktischen Modelle.
Beschränkung auf In-Distribution: Das PAC-Framework charakterisiert Generalisierung nur dann, wenn Trainings- und Test-Workloads aus derselben Verteilung gezogen werden. Es kann den Out-of-Distribution (OOD)-Generalisiertungsfehler nicht quantifizieren, was in realen Datenbank-Szenarien kritisch ist, in denen Abfrage-Workloads häufig wechseln (z. B. Änderungen von Abfragezentren oder Granularität).

Der Artikel zielt darauf ab, diese Lücken zu schließen durch: (1) die Lockerung der theoretischen Abhängigkeit von Wahrscheinlichkeitsmaßen zugunsten von signierten Maßen und (2) die Etablierung von OOD-Generalisierungsgrenzen unter milden Annahmen.

2. Methodik und Theoretischer Rahmen

2.1 Theoretische Grundlagen

Die Autoren stellen ein neues theoretisches Framework basierend auf signierten Maßen vor.

Signierte Maße: Im Gegensatz zu Wahrscheinlichkeitsmaßen erfüllen signierte Maße die abzählbare Additivität, lockern jedoch die Bedingungen der Positivität (C2) und der Summe zu Eins (C3) auf. Dies ermöglicht es der Theorie, regressionsbasierte Modelle zu umfassen, die negative Werte oder Werte, die nicht zu Eins summieren, ausgeben können.
In-Distribution-Lernbarkeit (Satz 4.1): Die Autoren beweisen, dass die Klasse der Selectivity-Prädiktoren, die durch signierte Maße induziert werden (insbesondere diejenigen, die bezüglich des Lebesgue-Maßes absolut stetig sind), PAC-lernbar ist. Sie stellen fest, dass die Fat-Shattering-Dimension dieser Klasse endlich ist und durch $\tilde{O}(C \cdot (1/\gamma)^{\lambda+1})$ beschränkt wird, wobei $C$ eine Schranke für die totale Variation des Maßes und $\lambda$ die VC-Dimension des Bereichsraums ist. Dies impliziert, dass bei ausreichenden Trainingsdaten der Trainingsfehler und der wahre Fehler nahe beieinander bleiben.

2.2 Out-of-Distribution (OOD)-Generalisierung

Über das PAC-Framework hinaus stellt der Artikel Satz 4.2 auf, der eine OOD-Generalisierungsgrenze liefert.

Annahmen: Der Satz stützt sich auf drei milde Annahmen:
1. Beschränktheit: Die gelernte Selectivity-Funktion ist beschränkt.
2. Träger-Enthaltensein: Der Träger der Testverteilung ist im Träger der Trainingsverteilung enthalten (d. h., der Test-Workload fragt keine Regionen ab, die während des Trainings nicht gesehen wurden).
3. Vielfalt: Die Trainingsbereiche decken eine vielfältige Menge von Regionen ab, wodurch sichergestellt wird, dass der Fehler nicht nur auf spezifischen „einfachen" Bereichen minimiert wird.
Ergebnis: Unter diesen Annahmen ist, wenn ein Prädiktor $\hat{S}$ einen In-Distribution-Fehler hat, der durch $\epsilon$ beschränkt ist, sein OOD-Fehler auf einer anderen Verteilung $P$ durch $O(\sqrt{\epsilon})$ beschränkt. Dieses Ergebnis gilt für jeden durch ein signiertes Maß induzierten Prädiktor.

2.3 Vorgeschlagene Strategien

Unter Ausnutzung dieser theoretischen Erkenntnisse schlagen die Autoren zwei Strategien zur Verbesserung bestehender Modelle vor:

Strategie 1: NeuroCDF (Modellierung von CDFs)

Konzept: Anstatt die Selectivity einer Abfrage direkt zu modellieren, verwendet NeuroCDF ein neuronales Netz, um die zugrunde liegende kumulative Verteilungsfunktion (CDF) zu modellieren. Die Selectivity einer Bereichsabfrage wird dann als lineare Kombination von CDF-Werten an den Eckpunkten der Abfrage berechnet (mittels des Inklusions-Exklusions-Prinzips).
Theoretische Garantie: Da NeuroCDF CDFs explizit modelliert, sind seine Vorhersagen nachweislich durch signierte Maße induziert. Somit erbt es die OOD-Generalisierungsgarantien von Satz 4.2.
Einschränkung: NeuroCDF hat Schwierigkeiten mit relativen Fehlermetriken wie Qerror, da die lineare Kombination von CDFs negative Schätzungen liefern kann, die für Qerror ungültig sind.

Strategie 2: SeConCDF (CDF-Selbstkonsistenz-Regularisierung)

Konzept: Um die Flexibilität der direkten Selectivity-Modellierung (die Qerror unterstützt) mit der OOD-Robustheit der CDF-Modellierung zu kombinieren, schlagen die Autoren SeConCDF vor.
Mechanismus: SeConCDF trainiert ein Standard-abfragegesteuertes Modell (z. B. MSCN oder LW-NN) unter Verwendung einer zusammengesetzten Verlustfunktion:
1. Originaler Vorhersageverlust: Standardverlust (z. B. Qerror oder RMSE) für direkte Selectivity-Vorhersagen.
2. CDF-Vorhersageverlust: Ein zusätzlicher Verlust, der das Modell zwingt, CDF-Werte vorherzusagen, die mit den beobachteten Daten konsistent sind.
3. Konsistenzverlust: Ein Regularisierungsterm, der die Konsistenz zwischen der direkten Selectivity-Vorhersage und der aus den gelernten CDFs des Modells abgeleiteten Selectivity erzwingt.
Ziel: Diese „weiche Einschränkung" ermutigt das Modell, sich so zu verhalten, als wäre es durch ein signiertes Maß induziert, wodurch die OOD-Generalisierung verbessert wird, ohne die Fähigkeit zu beeinträchtigen, Qerror zu optimieren oder die Modellarchitektur zu ändern.

3. Experimentelle Ergebnisse

Die Autoren evaluieren SeConCDF durch die Integration in zwei state-of-the-art Deep-Learning-Modelle: LW-NN und MSCN. Die Experimente werden auf Single-Table-Datensätzen (Census) und Multi-Table-Datensätzen (IMDb-small, DSB, CEB) mit synthetischen OOD-Workloads durchgeführt, die Verschiebungen des Abfragezentrums und Verschiebungen der Abfragegranularität beinhalten.

OOD-Generalisierungsgenauigkeit:
- Standard-Deep-Modelle (MSCN, LW-NN) zeigen eine signifikante Leistungsverschlechterung bei OOD-Abfragen (z. B. springt der mediane Qerror von einstelligen auf vierstellige Werte).
- SeConCDF mildert diesen Abfall erheblich. Beispielsweise reduziert SeConCDF auf dem IMDb-small-Datensatz bei einer Granularitätsverschiebung den medianen Qerror von MSCN von ~103 auf ~2,1, während gleichzeitig eine starke In-Distribution-Leistung beibehalten wird.
- NeuroCDF zeigt ebenfalls eine verbesserte OOD-Robustheit, ist jedoch durch seine Inkompatibilität mit Qerror eingeschränkt.
Abfrage-Latenz:
- Eine verbesserte Genauigkeit der Selectivity-Schätzung führt direkt zu besseren Abfrageausführungsplänen.
- In OOD-Szenarien erreichen mit SeConCDF trainierte Modelle eine Abfrage-Latenz, die mit PostgreSQL vergleichbar ist und deutlich besser ist als bei normalem MSCN, das häufig unter schlechten Kardinalitätsschätzungen leidet, die zu suboptimalen Plänen führen.
Vergleich mit SOTA-Theoriemodellen: Modelle, die auf der vorherigen SOTA-Theorie basieren (durch Wahrscheinlichkeitsmaße induziert, z. B. PtsHist, QuadHist), zeigen eine bessere OOD-Stabilität als reine Deep-Learning-Modelle, schneiden jedoch im Allgemeinen bei der In-Distribution-Genauigkeit und der gesamten OOD-Leistung im Vergleich zu SeConCDF-verbesserten Deep-Modellen schlechter ab.

4. Hauptbeiträge

Theoretische Erweiterung: Der Artikel beweist, dass durch signierte Maße induzierte Selectivity-Prädiktoren lernbar sind, und erweitert den Geltungsbereich des PAC-Lernens über Wahrscheinlichkeitsmaße hinaus, um praktische regressionsbasierte Modelle einzuschließen.
OOD-Generalisierungsgrenzen: Es werden die ersten nicht-trivialen OOD-Generalisierungsgrenzen für Selectivity-Learning unter milden Annahmen etabliert, die zeigen, dass der Fehler mit der Quadratwurzel des In-Distribution-Fehlers skaliert ( $O(\sqrt{\epsilon})$ ).
Praktische Frameworks:
- NeuroCDF: Ein neues Paradigma zur Modellierung von CDFs, um die Induktion durch signierte Maße zu garantieren.
- SeConCDF: Eine allgemeine Trainingsmethode, die die OOD-Generalisierung bestehender Modelle durch CDF-Selbstkonsistenz-Regularisierung verbessert und mit Standardverlustfunktionen wie Qerror kompatibel ist.
Empirische Validierung: Es wird demonstriert, dass diese theoretischen Erkenntnisse zu greifbaren Verbesserungen sowohl der Vorhersagegenauigkeit als auch der Abfrage-Latenz für OOD-Workloads in realen Datenbank-Szenarien führen.

5. Bedeutung und Behauptungen

Der Artikel behauptet, dass sein Hauptbeitrag die Überbrückung der Lücke zwischen Theorie und Praxis im Selectivity-Learning ist. Durch die Lockerung der restriktiven Annahme von Wahrscheinlichkeitsmaßen stellen die Autoren eine theoretische Grundlage bereit, die erklärt, warum und wann praktische Deep-Learning-Modelle generalisieren.

Die Bedeutung liegt in der Fähigkeit, die Robustheit gelernter Kardinalitätsschätzer gegenüber Workload-Verschiebungen formell zu garantieren und praktisch zu verbessern. Die Autoren betonen, dass ihr Ziel nicht lediglich darin besteht, in einem spezifischen Benchmark bestehende SOTA-Modelle zu übertreffen, sondern zu validieren, dass ihr theoretisches Framework operationalisiert werden kann, um bestehende Modelle in dynamischen, realen Umgebungen zuverlässiger zu machen, in denen Abfrageverteilungen unvermeidlich wechseln. Sie schließen daraus, dass ihr Ansatz einen prinzipiellen Weg bietet, die Zuverlässigkeit gelernter Datenbankkomponenten zu erhöhen.