Relationales Modell, SQL als Mengendenken und Indizes

Track Konzepte · Datenbanken · ca. 45 Min.

Worum es geht

Eine Seite lädt langsam, und eine einzige Abfrage liest 2 Millionen Zeilen, obwohl nur eine gebraucht wird. Das findest du nur, wenn du SQL als Mengenoperation (set operation) denkst und weißt, wie die Datenbank Abfragen plant (query plan). Am Ende von Teil 1 kannst du eine Frage wie “Kunden ohne Bestellung” als Mengenoperation formulieren, einen Query Plan lesen, erklären, was ein Index ist und was er kostet, und begründen, warum der Query Planner manchmal trotz Index einen Sequential Scan wählt (full table scan, die ganze Tabelle lesen).

Alles läuft hier mit sqlite3 direkt im Browser. Wichtig: SQLite ist eine kleine Datenbank mit einem einfachen Planner. Große Systeme wie PostgreSQL entscheiden feiner, aber die Konzepte sind dieselben. Plan-Texte unterscheiden sich zwischen Datenbanken und sogar zwischen SQLite-Versionen, darum prüfen die Übungen nur Teilstrings wie SEARCH oder COVERING INDEX. Zweiter Teil: Mehrspaltige Indizes, Joins und N+1.

Von JS/TS her gedacht

Du filterst in JS mit filter, map, Set. SQL macht dasselbe, aber deklarativ (declarative): Du sagst, welche Menge du willst, nicht wie sie berechnet wird. Das Wie wählt der Planner.

Aufgabe JS/TS (imperativ) SQL (deklarativ)
Kunden ohne Bestellung kunden.filter(k => !bestellt.has(k.id)) LEFT JOIN ... WHERE b.id IS NULL oder EXCEPT
Bestellungen mit Kundenname verschachtelte Schleife oder Map JOIN
Summe pro Kunde reduce in einer Schleife GROUP BY
Schnelles Nachschlagen Map/Object nach Schlüssel Index

Das filter aus der Tabelle, mit Node ausgeführt (bestellt = Kunden-IDs mit Bestellung):

const bestellt = new Set([1, 2, 4, 5]);
console.log([1, 2, 3, 4, 5, 6].filter(id => !bestellt.has(id)));   // [ 3, 6 ]

Der Unterschied zu JS: Ein JS-Objekt als Lookup baust du selbst. In der Datenbank entscheidest du nur, welche Lookups sich lohnen (Indizes), der Rest ist Planung.

Konzept

Schritt 1: Das relationale Modell

Ein relationales Modell (relational model) besteht aus Tabellen (relations). Jede Zeile (row) hat einen Primary Key (eindeutige Identität). Eine Beziehung entsteht über einen Foreign Key (Fremdschlüssel): bestellung.kunde_id zeigt auf kunde.id. Normalisierung heißt: Jede Tatsache steht genau einmal, z. B. der Kundenname nur in kunde, nicht in jeder Bestellung. Das verhindert widersprüchliche Kopien. Der Preis: Du musst die Tabellen beim Lesen per Join wieder zusammensetzen.

Unser Übungsmodell für die ganze Lektion (Kunden und Bestellungen, jeder dritte Kunde hat noch nie bestellt):

erDiagram
    kunde ||--o{ bestellung : "gibt auf"
    kunde {
        int id PK
        text name
        text email
        text land
    }
    bestellung {
        int id PK
        int kunde_id FK
        text status
        text datum
        int betrag
    }

Schritt 2: SQL als Mengendenken

Eine Tabelle ist eine Menge von Zeilen. Operationen erzeugen neue Mengen:

  • WHERE ist ein Filter (Auswahl, selection).
  • SELECT spalten ist eine Projektion (projection).
  • JOIN paart Zeilen zweier Mengen nach einer Bedingung.
  • UNION, INTERSECT, EXCEPT sind Vereinigung, Schnitt und Differenz.
  • GROUP BY teilt eine Menge in Gruppen und fasst jede zu einer Zeile zusammen.

Die Frage “Welche Kunden haben nie bestellt?” ist eine Differenz: alle Kunden minus Kunden mit Bestellung. Zwei Wege, dieselbe Menge:

Ausgabe: [('Kunde 3',), ('Kunde 6',)] [('Kunde 3',), ('Kunde 6',)]. Der zweite Weg heißt Anti-Join: Ein LEFT JOIN behält alle Kunden. Wo keine Bestellung passt, sind die Bestellspalten NULL. Wer NULL hat, hat nie bestellt.

NULL-Falle: NOT IN (...) sieht wie die natürliche Lösung aus. Sobald die Unterabfrage ein NULL enthält (z. B. eine Gast-Bestellung ohne kunde_id), ist id NOT IN (..., NULL) für jede Zeile unbekannt statt wahr, und du bekommst gar keine Zeile zurück:

Ausgabe: erst [('Kunde 3',), ('Kunde 6',)], nach der Gast-Bestellung []. Das ist dreiwertige Logik (three-valued logic: wahr, falsch, unbekannt), die in JS kein Gegenstück hat.

Schritt 3: Wie die Datenbank deine Abfrage ausführt

Du beschreibst die Menge, der Query Planner (auch Query Optimizer) wählt den Weg. Er schätzt anhand von Statistiken (z. B. wie viele Zeilen die Tabelle hat, wie viele verschiedene Werte eine Spalte hat) die Kosten mehrerer möglicher Pläne und nimmt den billigsten.

flowchart LR
    A[SQL Text] --> B[Parser]
    B --> C[Query Planner]
    S[(Statistiken)] --> C
    I[(vorhandene Indizes)] --> C
    C --> D[Query Plan]
    D --> E[Executor]
    E --> F[Ergebnis]

Den gewählten Plan zeigt dir EXPLAIN (in SQLite EXPLAIN QUERY PLAN). Das ist das wichtigste Werkzeug, um langsame Abfragen zu verstehen. Ohne Index:

Ausgabe: SCAN kunde. SCAN heißt: Die Tabelle wird Zeile für Zeile gelesen (Sequential Scan). Jetzt ein Index:

Ausgabe: SEARCH kunde USING INDEX idx_kunde_email (email=?). SEARCH heißt: gezielter Zugriff über den Index.

Schritt 4: Was ein Index ist

Ein Index ist eine zusätzliche, sortierte Struktur, meist ein B-Baum (B-tree), die Spaltenwerte auf Zeilen abbildet. Der B-Baum ist ein breiter, flacher Suchbaum: Mit wenigen Schritten findest du einen Wert, und weil er sortiert ist, liegt auch ein Wertebereich (>, BETWEEN) beieinander. Das Prinzip kennst du von der binären Suche. Zum Vergleich (kein echter B-Baum, aber dieselbe Idee “sortiert, darum halbieren”): 100000 sortierte Zahlen, Suche nach 150000, gezählt wird jeder Vergleich:

Ausgabe: 100000 75001 16. Linear 75001 Vergleiche, sortiert halbiert nur 16. Genau das ist der Gewinn eines Index.

Der Preis: Lesen wird schneller, Schreiben langsamer, denn jede Änderung muss auch jeden Index nachführen. Gemessen als Anzahl der SQLite-Rechenschritte (über set_progress_handler, zählt interne Instruktionen) für 2000 INSERT:

Ausgabe bei SQLite 3.51.0 lokal: 24003 36003 56003. Der genaue Wert hängt von der SQLite-Version ab, aber mehr Indizes bedeuten mehr Arbeit pro Schreibvorgang. Mit drei Indizes ist es hier mehr als doppelt so viel wie ohne.

Schritt 5: Warum nicht immer ein Index? Selektivität

Selektivität (selectivity) sagt, welcher Anteil der Zeilen zu einem Wert passt. Ein Wert, der wenige Zeilen trifft, ist selektiv: Der Index springt direkt hin. Trifft ein Wert fast alle Zeilen, muss der Index trotzdem fast jede Zeile besuchen, und zwar zusätzlich über Umwege (erst Index, dann Tabelle). Dann ist einmal komplett durchlesen oft billiger. Genau deshalb wählt ein Planner manchmal einen Sequential Scan trotz vorhandenem Index. Gemessen (5000 Zeilen, 98 % offen, 2 % storniert, jeweils einmal per Index erzwungen mit INDEXED BY und einmal ohne Index mit NOT INDEXED):

Ausgabe bei SQLite 3.51.0 lokal: offen Index: 34311 kein Index: 34608 und storniert Index: 709 kein Index: 15407. Beim seltenen Wert spart der Index mehr als 95 %, beim häufigen fast nichts (die Zahlen können in deinem Browser abweichen, das Verhältnis bleibt). Die Entscheidung trifft der Planner anhand von Statistiken. Sind sie veraltet (viele Änderungen seit der letzten Statistik-Aktualisierung, in SQLite ANALYZE), schätzt er falsch. Ob er richtig geschätzt hat, siehst du in PostgreSQL mit EXPLAIN (ANALYZE): Es führt die Abfrage wirklich aus und zeigt neben dem Plan die geschätzte und die tatsächliche Zeilenzahl. Weichen beide stark voneinander ab, sind die Statistiken der Verdächtige (bitte prüfen, siehe Quellenvermerk). Das brauchst du in Übung 5.

Schritt 6: Index-Fallen

Drei typische Gründe, warum ein vorhandener Index nicht greift, jeweils aus dem Index-Prinzip “sortiert nach dem Spaltenwert” abgeleitet:

  1. Funktion auf der Spalte: WHERE lower(email) = ?. Der Baum ist nach email sortiert, nicht nach lower(email). Abhilfe: Index auf dem Ausdruck (expression index).
  2. Platzhalter vorn: LIKE '%@beispiel.de'. Ohne bekannten Anfang kann der sortierte Baum nichts eingrenzen.
  3. Falsche Spaltenreihenfolge im mehrspaltigen Index (nächster Schritt).

Ausgabe: SCAN kunde und SEARCH kunde USING INDEX i_le (<expr>=?). Der Index auf email allein hilft hier nicht, erst der Ausdrucksindex.

Falle

  1. Index vorhanden heißt nicht Index benutzt. Funktion auf der Spalte, Platzhalter vorn, oder der Planner schätzt, dass ein Scan billiger ist. Du erfährst es nur mit EXPLAIN.
  2. NOT IN mit NULL liefert leer statt der erwarteten Menge. Nimm NOT EXISTS, Anti-Join oder EXCEPT.
  3. Index auf jede Spalte “für alle Fälle”. Jeder Index kostet bei jedem Schreiben und braucht Platz.

Übungen

Übung 1: Welche Abfrage nutzt den Index? (ca. 8 Min.)

Auf kunde(email) liegt ein Index (CREATE INDEX idx_kunde_email ON kunde(email)). Vier Abfragen:

  1. SELECT * FROM kunde WHERE email = 'k5@beispiel.de'
  2. SELECT * FROM kunde WHERE lower(email) = 'k5@beispiel.de'
  3. SELECT * FROM kunde WHERE email LIKE '%@beispiel.de'
  4. SELECT * FROM kunde WHERE email > 'k5'

Trage für jede Abfrage True ein, wenn der Plan einen gezielten Zugriff (SEARCH) über den Index zeigt, sonst False.

Der Index ist nach email sortiert. Frage bei jeder Abfrage: Kann der Planner damit einen Startpunkt im sortierten Baum finden?

antwort = (True, False, False, True)
antwort

Gleichheit und Bereich auf der indizierten Spalte nutzen die Sortierung. lower(email) ist ein anderer Wert als email, und bei % vorn ist der Anfang unbekannt, also bleibt nur Scan.

Übung 2: Kunden ohne Bestellung als Mengenoperation (ca. 10 Min.)

Schreibe eine SQL-Abfrage, die die Namen (eine Spalte name) aller Kunden liefert, die noch nie bestellt haben. Beachte: In bestellung kann kunde_id NULL sein (Gast-Bestellung). Die Prüfung testet vier Datensätze, darunter einen mit Gast-Bestellung.

“Alle Kunden minus die mit Bestellung.” Es gibt zwei Wege aus Schritt 2. Einer davon hat eine Falle, wenn eine Spalte NULL enthält. Der andere nicht: Welcher, und warum?

sql = """
SELECT k.name
FROM kunde k
LEFT JOIN bestellung b ON b.kunde_id = k.id
WHERE b.id IS NULL
"""
sql

Gleichwertig: WHERE NOT EXISTS (SELECT 1 FROM bestellung b WHERE b.kunde_id = k.id). Nicht gleichwertig: NOT IN, wegen NULL.

Übung 3: Warum Seq Scan trotz Index? (ca. 8 Min.)

Prüfstein der Quelle, jetzt als Fall: In PostgreSQL liegt auf bestellung.status ein Index. Die Tabelle hat 2 Millionen Zeilen, 97 % davon haben status = 'offen'. Die Abfrage SELECT * FROM bestellung WHERE status = 'offen' zeigt im EXPLAIN einen Sequential Scan. Was stimmt, und wie findest du es heraus? Gib den Buchstaben zurück.

  • A: Der Index ist beschädigt. Nach einem REINDEX nutzt der Planner ihn wieder, und der Plan wird zum Index-Zugriff.
  • B: Indizes greifen nur bei UNIQUE-Spalten. Weil status viele doppelte Werte hat, ignoriert der Planner den Index.
  • C: Der Wert trifft fast alle Zeilen. Dann ist einmal komplett lesen billiger als Millionen Index-Sprünge. Ob die Schätzung stimmt, zeigt EXPLAIN (ANALYZE).
  • D: Ab 1 Million Zeilen wählt der Planner grundsätzlich einen Scan, ganz gleich, wie selten der gesuchte Wert vorkommt.

Erinnere dich an Schritt 5: Wie viele Zeilen muss der Index besuchen, wenn der Wert fast alle trifft? Was kostet jeder Besuch im Vergleich zum Durchlesen?

antwort = "C"
antwort

Der Planner vergleicht geschätzte Kosten aus Statistiken. Bei einer Selektivität von 97 % ist der Scan günstiger. Du erkennst das mit EXPLAIN (ANALYZE) (Schätzung gegen Wirklichkeit) und siehst bei Abweichungen nach, ob die Statistiken veraltet sind. Frage dieselbe Abfrage mit dem seltenen Wert ('storniert') und der Plan wechselt zum Index.

Merksatz

SQL beschreibt eine Menge, der Planner wählt den Weg anhand von Statistiken, und ob ein Index hilft, steht im EXPLAIN, nicht in deiner Vermutung.

Prüfstein

Warum wählt der Query Planner einen Sequential Scan trotz vorhandenem Index, und wie findest du das heraus? Nenne mindestens drei Gründe (Selektivität, Statistiken, Form der Abfrage) und das Werkzeug.

Weiter mit Teil 2: Mehrspaltige Indizes, Joins und N+1.

Quelle: quellen/konzeptuebersicht-software-grundlagen.md, Abschnitt “5. Datenbanken” (Relationales Modell, SQL als Denkmodell, Indizes); quellen/konzeptuebersicht-software-fortgeschritten.docx, Schicht 5 (Query-Verarbeitung: Planner und Statistiken; Storage Engines: B-Tree). Über die Quelle hinaus (allgemeines Fachwissen): Erklärungen zu Selektivität, NULL und NOT IN, Expression Index, SQLite-Plantexte (alle mit SQLite 3.51.0 lokal ausgeführt). Das Verhalten von EXPLAIN (ANALYZE) in PostgreSQL: bitte prüfen.