Zusammenfassung

  • Der System-R-Optimierer wählte den niedrigsten geschätzten Aufwand unter den tatsächlich betrachteten Plänen. Seitenzugriffe und Aufrufe der Speicherschnittstelle wurden gewichtet; eine künftige Laufzeit wurde damit nicht gemessen.
  • Selektivität beeinflusst Kardinalität, Kardinalität wiederum Zugriffspfad, Join-Reihenfolge und physischen Operator. „Interessante Ordnungen“ hielten lokal teurere Wege im Rennen, wenn sie späteres Sortieren ersparen konnten.
  • Selinger organisierte eine Gemeinschaftsleistung mit Morton Astrahan, Donald Chamberlin, Raymond Lorie und Thomas Price. Dauerhaft war nicht Unfehlbarkeit, sondern die prüfbare Trennung von Annahme, Entscheidung und Ausführungsbeobachtung.

Wenn zwei richtige Pläne unterschiedlich teuer werden

Eine SQL-Abfrage verbindet Bestellungen, Kunden und Regionen, filtert einen Zeitraum und gruppiert Umsätze. Der relationale Ausdruck bestimmt das Ergebnis. Ob der Rechner zuerst einen Index liest, eine Tabelle durchsucht oder eine andere Join-Reihenfolge wählt, darf die korrekten Zeilen nicht verändern.

Physisch können die Wege weit auseinanderliegen. Ein selektiver Index liefert wenige Datensätze in einer nützlichen Ordnung. Ein Scan liest eine große Relation, erzeugt ein umfangreiches Zwischenergebnis und sortiert am Ende. Semantisch sind beide Wege gleichwertig; betrieblich sind sie es nicht.

Die Entscheidung fällt, bevor dieser Lauf existiert. Welche Seiten im Puffer liegen, wie viele Zeilen ein konkreter Parameter trifft, welche Konkurrenz auf I/O wirkt und ob ein Operator auf Platte ausweicht, ist nicht vollständig bekannt. Der Optimierer besitzt Beschreibungen, keine Erinnerung an die Zukunft.

„Billiger“ heißt deshalb: im Modell niedriger bewertet. Erst die Ausführung erzeugt tatsächliche Zeilen, Lesevorgänge, CPU-Arbeit, Speicherbedarf und verstrichene Zeit. Aus einer Schätzung ein Urteil zu machen, verschiebt die Evidenzgrenze.

Deklaratives SQL übergab die physische Kontrolle

SQL beschreibt das gewünschte Resultat, nicht die Folge von Speicheroperationen. Dadurch kann dieselbe Abfrage nach einem Indexaufbau, Datenwachstum oder Hardwarewechsel neu geplant werden. Die Anwendung gewinnt Abstraktion und überträgt dem Datenbanksystem Autorität.

Der Aufsatz Access Path Selection in a Relational Database Management System ordnet System R in vier Phasen. Parsing erzeugt die interne Darstellung. Optimierung wählt eine Zugriffsspezifikation. Codeerzeugung übersetzt sie. Danach beginnt die Ausführung. Diese Reihenfolge macht die Planwahl zur Ex-ante-Entscheidung.

Eine Zugriffsspezifikation enthält physischen Inhalt: erste Relation, Scan oder Index, Join-Reihenfolge und erhaltenswerte Ordnungen. Sie ist keine alternative Definition des fachlichen Ergebnisses.

Semantische Korrektheit und physische Wirtschaftlichkeit bleiben getrennt. Ein falsches Ergebnis ist ein Korrektheitsfehler. Ein richtiges, aber verspätetes Ergebnis verweist auf Schätzung, Planung oder Ausführung. Ein schneller Einzelversuch beweist ebenso wenig allgemeine Optimalität wie eine niedrige Kostenzahl reale Geschwindigkeit.

Statistik war eine bezahlbare Verdichtung

System R verwendete Katalogwerte wie NCARD für Tupel, TCARD für belegte Seiten, P für Seitenbelegung, ICARD für unterschiedliche Indexschlüssel und NINDX für Indexseiten. So ließ sich ein Weg vergleichen, ohne die gesamte Relation vorab zu lesen.

Die Werte wurden initialisiert und mit UPDATE STATISTICS periodisch erneuert. Nach jeder Datenänderung aktualisierte man sie nicht. Der Aufsatz nennt die zusätzlichen Katalogschreibvorgänge und Sperren als zu teuer.

Damit ist Unschärfe kein später hinzugekommener Betriebsfehler, sondern Bestandteil des Entwurfs. Beobachtung kostet. Eine ständig exakte Beschreibung würde selbst Ressourcen und Koordination verbrauchen. Eine grobe oder alte Beschreibung kann Kandidaten falsch sortieren.

Die heutige Frage lautet daher nicht nur, ob Statistiken vorhanden sind. Entscheidend sind Stichprobe, Granularität, Spaltenkorrelation, Partitionsunterschied und Alter. Der Katalog ist eine für die Planung gebaute Sicht auf Daten, kein vollständiges Abbild ihrer künftigen Wirkung.

Von Selektivität zu Kardinalität

Für Prädikate schätzte System R Selektivitätsfaktoren: den erwarteten Anteil passender Tupel. Bei einer indizierten Gleichheit konnte die Zahl verschiedener Schlüssel helfen. Ohne bessere Information galten praktische Vorgaben. Der Aufsatz nennt ein Zehntel für Gleichheit ohne Index, ein Drittel für einen offenen Bereich und ein Viertel für einen geschlossenen Bereich.

Die Autoren betonen, dass diese Werte keine Bedeutung jenseits einer groben Reihenfolge besitzen. Sie sind Entscheidungen bei fehlender Evidenz, keine Naturkonstanten.

Mit AND verbundene Faktoren konnten multipliziert werden. Das unterstellt Unabhängigkeit. Postleitzahl und Ort, Produktklasse und Preis, Vertragsart und Laufzeit sind häufig korreliert. Das Produkt marginaler Wahrscheinlichkeiten kann eine häufige Kombination für selten halten oder umgekehrt.

Kardinalität macht aus dem Anteil eine Zeilenzahl. Die QCARD-Logik kombiniert Relationsgrößen und Selektivitäten. Diese Zahl fließt in spätere Operatoren ein. Wird die äußere Seite eines Nested Loops unterschätzt, erscheint wiederholte Arbeit billig; in der Realität wird sie viel häufiger ausgeführt. Wird ein Filter überschätzt, verliert ein tatsächlich schmaler Indexweg.

Selektivität ist ein Verhältnis, Kardinalität eine Menge. Ein Fehler wandert von der ersten zur zweiten und verändert anschließend Join-Reihenfolge, Operator, Speicher und Sortierung.

Leis und Mitautoren zeigten 2015, dass Kardinalitätsfehler die Planqualität meist stärker beeinträchtigten als kleine Ungenauigkeiten der Kostenformel. Ihre Rückschau von 2025 behandelt Kardinalität, Robustheit und Anpassung weiterhin als offene Arbeit. Die in System R sichtbare Wirkungskette bleibt aktuell.

Die Kostenformel war keine Stoppuhr

Die veröffentlichte Gleichung lautete:

COST = PAGE FETCHES + W × (RSI CALLS)

Seitenzugriffe standen für I/O, Aufrufe der Research Storage Interface näherten CPU-Arbeit an, W setzte beides in ein Verhältnis. Prozessorarbeit zu berücksichtigen war fortschrittlich. Die Summe wurde dadurch aber nicht zu Sekunden.

Pufferzustand, sequentielles Lesen, Konkurrenz, Auslagerung, konkrete Hardware und Verbrauch des Ergebnisses waren nur teilweise oder gar nicht bekannt. Die Formel schuf eine gemeinsame Recheneinheit, um ungleiche Ressourcen zu ordnen.

Der niedrigere Wert ist innerhalb dieses Modells günstiger. Dass er schneller läuft, ist eine Hypothese. Für „optimal“ müssen zusätzlich Ziel und Suchraum genannt werden. Was der Enumerator nicht erzeugt, kann die Kostenfunktion nicht auswählen.

Die PostgreSQL-Dokumentation demonstriert dieselbe Grenze. Plankosten sind plattformabhängige Konventionen, keine Millisekunden. EXPLAIN führt die Anweisung nicht aus und zeigt Schätzungen. EXPLAIN ANALYZE führt aus und ergänzt wirkliche Zeilen und Zeiten. Prognose und Messung werden bewusst getrennt.

Zugriffspfad, Operator und Reihenfolge

Ein Zugriffspfad bestimmt, wie eine Basisrelation erreicht wird: Scan oder Index. Ein physischer Operator bestimmt, wie Join, Sortierung oder Aggregation ausgeführt werden. Die Join-Reihenfolge bestimmt, welche Relationen zuerst verbunden werden und welche Zwischengrößen entstehen.

Ein Index kann filtern und zugleich eine Ordnung liefern. Ein selektiver früher Join verkleinert alles Folgende. Ein Operator für kleine Eingaben versagt, wenn die Kardinalität unterschätzt wurde. Eine Sortierung jetzt kann eine größere Sortierung später vermeiden.

Diese Entscheidungen greifen ineinander, sind aber nicht identisch. Eine Diagnose sollte fragen, ob ein Zugriff fehlte, eine Kardinalität die Reihenfolge verzerrte, ein Operatorschwellenwert überschritten oder eine wertvolle Eigenschaft zerstört wurde.

Relationale Äquivalenz schützt die Bedeutung unter den Regeln für Nullwerte, Duplikate und Aggregation. Sie verspricht keine Gleichheit der Ressourcen. Genau dazwischen arbeitet die physische Planung.

Warum eine interessante Ordnung überleben durfte

Ein Indexweg kann für die aktuelle Relation teurer als ein Scan sein. Liefert er jedoch die Ordnung eines späteren Joins, eines GROUP BY oder des endgültigen ORDER BY, spart er womöglich eine Sortierung.

System R bewahrte deshalb nicht nur den billigsten ungeordneten Teilplan. Für jede relevante „interessante Ordnung“ blieb ebenfalls der billigste Vertreter erhalten. Gleiche Zeilen machten zwei Teilergebnisse nicht zu gleichwertigen physischen Versprechen.

Ordnung besitzt Optionswert. Ein Mehrpreis heute kann künftige Arbeit vermeiden. Wer ausschließlich den lokalen Sieger behält, verwechselt unmittelbare Kosten mit Gesamtwirkung.

Zugleich begrenzte das Konzept den Speicher der Suche. Nicht jeder Plan musste weiterleben. Erhalten wurden die günstigsten Vertreter genau jener Eigenschaftsklassen, die spätere Entscheidungen ändern konnten.

Auch Optimierung verbraucht Zeit

Die Zahl möglicher Join-Reihenfolgen wächst kombinatorisch; alle Permutationen nähern sich fakultativem Wachstum. Eine vollständige Suche könnte den Gewinn der späteren Ausführung aufzehren.

System R setzte dynamische Programmierung ein. Für Teilmengen von Relationen wurden beste Vertreter je interessanter Ordnung gespeichert und beim Aufbau größerer Mengen wiederverwendet. Kartesische Produkte wurden möglichst hinausgezögert, weil sie ohne Join-Bedingung große Zwischenmengen erzeugen.

Der Aufsatz beschreibt den Aufwand über Teilmengen und interessante Ordnungen und berichtet von Acht-Tabellen-Joins, die auf einer IBM 370/158 in Sekunden optimiert wurden. Die Suche wurde damit praktisch.

Beschneiden bedeutet jedoch nicht, jede vorstellbare physische Form geprüft zu haben. Dynamische Programmierung findet den besten Kandidaten innerhalb des Raums, den Enumerator, Operatoren, Baumformen und Aufbewahrungsregeln definieren. Eine globale Optimalitätsbehauptung ohne diese Grenzen wäre zu stark.

Optimierungszeit und Ausführungszeit bleiben getrennte Konten. Breitere Suche lohnt sich bei teuren Analysen, kann aber bei kurzen, häufigen Abfragen dominieren. Ein generischer vorbereiteter Plan spart Planung und verliert möglicherweise, wenn optimale Wege stark von Parametern abhängen.

Die Grenzen wurden veröffentlicht

Der Aufsatz von 1979 sagt offen, dass vorhergesagte Kosten als absolute Werte oft ungenau waren. Gleichzeitig wählte das Verfahren in der Mehrheit der Versuche den tatsächlich besten getesteten Zugriffspfad und sollte weiter validiert werden. Ein schlecht kalibrierter Wert kann sinnvoll ordnen.

Mackert und Lohman verglichen 1986 beim R*-Optimierer Schätzungen und tatsächlichen Ressourcenverbrauch. Große Teile des I/O-Modells waren brauchbar; CPU benötigte mehr Detail, Pufferannahmen spielten eine Rolle, und Nested Loops waren wegen Join-Kardinalität, äußerer Kardinalität und verfügbarer Seiten schwierig.

Diese Validierung machte die Formel überprüfbar. Mathematische Form schützt nicht vor Ausführungsevidenz. Konzentrierte Abweichungen weisen auf Statistiken, Gewichte, Operatorannahmen oder Feedback hin.

Spätere IBM-Arbeit zu Just-in-time-Statistiken folgt derselben Logik. Fehlt eine wichtige oder ist sie alt, kann der Optimierer beim Planen gezielt bessere Beobachtung anfordern. Nicht Allwissen, sondern wertvolle Information wird gekauft.

Selinger führte eine Teamleistung

Patricia G. Selinger kam 1975 zu IBM Research. IBM beschreibt ihre Leitung der System-R-Optimierung und spätere Verantwortung für R* und Datenbanktechnologie. 1994 wurde sie IBM Fellow, 1999 Mitglied der US National Academy of Engineering; 2018 ging sie bei IBM in den Ruhestand.

Der Aufsatz von 1979 trägt fünf Namen: P. Griffiths Selinger gemeinsam mit Morton M. Astrahan; hinzu kommen Donald D. Chamberlin, außerdem Raymond A. Lorie und schließlich Thomas G. Price. Chamberlin erinnert sich in seiner Oral History daran, dass Selinger die Optimierungsarbeit und den wegweisenden Text organisierte, und nennt Lorie, Price und Astrahan als wichtige Mitwirkende. IBMs größere Geschichte umfasst Edgar Codds Relationsmodell, SQL von Chamberlin und Raymond Boyce, Lories Compilerarbeit und das gesamte System-R-Programm.

Kollektiver Kredit präzisiert Führung. Selinger verband Statistik, Selektivität, Kardinalität, Kosten, physische Eigenschaften und begrenzte Suche zu einem implementierbaren Vertrag. Dafür braucht es weder den Mythos einer Einzelerfinderin noch das nachträgliche Etikett künstliche Intelligenz.

Dauerhaft war die korrigierbare Grenze

Die Leistung bestand nicht in einem für immer wahren Plan. Sie schuf eine Schicht, in der die Abfragebedeutung stabil bleibt und der physische Weg wechseln kann. Statistiken, Korrelationsmodelle, Gewichte, Operatoren und Laufzeitfeedback lassen sich verbessern, ohne jede SQL-Anweisung als Prozedur neu zu schreiben.

Der gewählte Plan ist eine autorisierte Prognose. Er gewann den tatsächlich implementierten Vergleich mit den verfügbaren Belegen. Die Ausführung hat ihn noch nicht bestätigt.

Wer Schätzung und Messung aufbewahrt, kann aus ihrer Differenz lernen. Ein reifer Optimierer verspricht nicht Fehlerfreiheit. Er macht sichtbar, was angenommen, gewählt und beobachtet wurde.

Quellen