Mehrspaltige Indizes, Joins und das N+1-Problem

Track Konzepte · Datenbanken · ca. 45 Min.

Was du aus Teil a brauchst

Du weißt, dass SQL eine Menge beschreibt, dass ein Index eine sortierte Struktur ist und dass EXPLAIN zeigt, ob er benutzt wird (SEARCH gegen SCAN). Falls nicht: Teil 1.

Worum es geht

Ein Index auf der falschen Spalte oder in der falschen Reihenfolge hilft nichts, und eine Liste mit 100 Einträgen kann 101 Datenbankabfragen auslösen. Am Ende von Teil 2 kannst du einen mehrspaltigen Index richtig herum bauen (Leftmost Prefix), Covering und Partial Indexes erklären, drei Join-Algorithmen unterscheiden und ein N+1-Problem erkennen und reparieren.

Das Übungsmodell ist dasselbe wie in Teil 1: kunde (id, name, email, land) und bestellung (id, kunde_id, status, datum, betrag), jeder dritte Kunde hat noch nie bestellt. Die Hilfsfunktionen shop_db und plan setzt die folgende Zelle neu:

Konzept

Schritt 7: Mehrspaltige Indizes und die Reihenfolge

Ein zusammengesetzter Index (composite index) auf (kunde_id, datum) ist erst nach kunde_id sortiert und innerhalb gleicher kunde_id nach datum, wie ein Telefonbuch (erst Nachname, dann Vorname). Daraus folgt die Leftmost-Prefix-Regel: Der Index hilft für kunde_id allein und für kunde_id plus datum, aber nicht für datum allein. Ein Gleichheitsvergleich (=) auf der ersten Spalte, dann ein Bereich (>=) auf der zweiten, ist das ideale Muster.

Ausgabe: SEARCH bestellung USING INDEX idx_kd (kunde_id=? AND datum>?), dann SEARCH bestellung USING INDEX idx_kd (kunde_id=?), dann SCAN bestellung. Drehst du die Reihenfolge zu (datum, kunde_id), grenzt der Index bei der ersten Abfrage nur noch über datum ein und kunde_id filtert erst danach.

Schritt 8: Covering und Partial Indexes

Ein Covering Index enthält alle Spalten, die die Abfrage braucht. Dann muss die Datenbank die Tabelle gar nicht mehr lesen. Die Abfrage SELECT datum ... WHERE kunde_id = ? ist mit dem Index oben ein Covering Index, denn datum steckt im Index:

Ausgabe: SEARCH bestellung USING COVERING INDEX idx_kd (kunde_id=?). Ein Partial Index (Teilindex) indiziert nur Zeilen, die eine Bedingung erfüllen. Das spart Platz und Schreibaufwand, wenn du fast immer nur diese Teilmenge abfragst (z. B. offene Bestellungen). Er greift nur, wenn die Abfrage die Bedingung enthält:

Ausgabe: SEARCH b USING INDEX i_offen (kunde_id=?) und SCAN b. Neuere SQLite-Versionen schreiben hier COVERING INDEX, weil status = 'offen' schon im Index steckt. Wichtig ist der Unterschied SEARCH gegen SCAN.

Schritt 9: Join-Algorithmen

Wie zwei Mengen gepaart werden, ist ebenfalls Sache des Planners. Die drei klassischen Algorithmen:

Algorithmus Idee Gut wenn
Nested Loop für jede Zeile links alle Zeilen rechts prüfen (oder per Index nachschlagen) eine Seite klein, die andere hat einen Index
Hash Join eine Seite in eine Hash-Tabelle laden, die andere nachschlagen große Mengen ohne Index, Gleichheitsjoin
Merge Join beide Seiten sortiert, im Gleichschritt durchlaufen beide Seiten schon sortiert (z. B. per Index)

In SQLite siehst du in Plänen praktisch nur geschachtelte Schleifen (SCAN gefolgt von SEARCH), Hash und Merge Join kennt z. B. PostgreSQL (bitte prüfen, bevor du dich darauf verlässt). Nested Loop gegen Hash Join, nachgebaut mit 200 Kunden und 600 Bestellungen, gezählt wird jeder Zugriff:

Ausgabe: 600 120000 600 800. Gleiches Ergebnis, 120000 gegen 800 Zugriffe. Die Hash-Tabelle ist in dieser Rechnung genau der Index, den der Nested Loop nicht hatte.

Schritt 10: Das N+1-Problem

Du lädst 100 Kunden (1 Abfrage) und holst dann für jeden einzelnen seine Bestellsumme (100 Abfragen). Zusammen N+1 Abfragen. Jede für sich ist schnell, aber jede kostet einen Netzwerk-Roundtrip. Typisch bei ORMs mit Lazy Loading, aber auch von Hand schnell gebaut. In TS sieht das so aus (Node, Zähler zeigt die Abfragen):

let anzahl = 0;
const db = { query: async (sql: string, params: unknown[] = []) => { anzahl++; return []; } };

const kunden = Array.from({ length: 100 }, (_, i) => ({ id: i + 1 }));
await db.query("SELECT id FROM kunde");
for (const k of kunden) {
  await db.query("SELECT SUM(betrag) FROM bestellung WHERE kunde_id = ?", [k.id]);
}
console.log(anzahl);   // 101

Das Beispiel wurde als JavaScript mit Node ausgeführt und gibt 101 aus. In Python mit Zähler-Wrapper um execute:

Ausgabe: 101 und 1 True. Gleiches Ergebnis mit einer Abfrage. Die Faustregel: Eine Schleife, die in jedem Durchlauf die Datenbank fragt, ist verdächtig.

Falle

  1. Zwei Einzelindizes statt eines zusammengesetzten. (kunde_id) und (datum) getrennt ersetzen (kunde_id, datum) nicht. SQLite nutzt hier meist nur einen davon pro Tabelle.
  2. Falsche Reihenfolge im zusammengesetzten Index. Gleichheitsspalte nach vorn, Bereichsspalte dahinter, sonst grenzt der Index schlechter ein.
  3. N+1 versteckt sich hinter Hilfsfunktionen (lade_summe(kunde)), die in einer Schleife aufgerufen werden.

Übungen

Übung 1: Einen Index richtig herum bauen (ca. 12 Min.)

Zwei häufige Abfragen auf bestellung:

  • Q1: SELECT * FROM bestellung WHERE kunde_id = ? AND datum >= ?
  • Q2: SELECT datum FROM bestellung WHERE kunde_id = ?

Lege genau einen Index an, der beide bedient: Q1 soll sowohl kunde_id als auch datum im Plan nutzen (kunde_id=? AND datum>?), und Q2 soll ein Covering Index sein (COVERING INDEX, die Tabelle wird nicht gelesen). Ergänze die Spaltenliste.

Der Index ist wie ein Telefonbuch erst nach der ersten Spalte sortiert, innerhalb davon nach der zweiten. Welche Spalte muss feststehen, damit die zweite überhaupt eingrenzen kann? Und welche Spalten braucht Q2 insgesamt?

indizes = [
    "CREATE INDEX idx_best ON bestellung(kunde_id, datum)",
]
indizes

kunde_id steht vorn (Gleichheit), datum dahinter (Bereich innerhalb eines Kunden). Q2 braucht nur kunde_id und datum, beide stecken im Index, also ist er Covering.

Übung 2: Greift der Teilindex? (ca. 7 Min.)

Auf der Tabelle ticket (id, projekt_id, status, titel) liegt dieser Partial Index:

CREATE INDEX idx_offen ON ticket(projekt_id) WHERE status = 'offen'

Vier Abfragen:

  1. SELECT * FROM ticket WHERE status = 'offen' AND projekt_id = 3
  2. SELECT * FROM ticket WHERE projekt_id = 3
  3. SELECT * FROM ticket WHERE status = 'geschlossen' AND projekt_id = 3
  4. SELECT * FROM ticket WHERE status = 'offen' AND projekt_id > 3

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

Der Teilindex enthält nur bestimmte Zeilen. Darf der Planner ihn benutzen, wenn die Abfrage nicht garantiert, dass sie nur solche Zeilen sucht?

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

Der Teilindex greift nur, wenn die Abfrage die Index-Bedingung (status = 'offen') selbst enthält. Ohne sie (Abfrage 2) oder mit einem anderen Wert (Abfrage 3) fehlen dem Index Zeilen, also bleibt nur Scan. Bei Abfrage 4 passt die Bedingung, und projekt_id > 3 ist ein Bereich auf der sortierten Spalte.

Übung 3: N+1 reparieren (ca. 12 Min.)

Die Funktion liefert pro Kunde den Gesamtumsatz ({name: summe}), Kunden ohne Bestellung mit 0. Sie ist korrekt, aber N+1. Baue sie so um, dass sie mit höchstens 2 Abfragen auskommt, egal wie viele Kunden es gibt. Das Ergebnis muss gleich bleiben. Die Prüfung läuft mit 3 und mit 60 Kunden und zählt die execute-Aufrufe über einen Wrapper (db.execute(sql, params)).

Die Datenbank kann Mengen in einer einzigen Abfrage zusammensetzen und zusammenfassen. Was muss mit Kunden ohne Bestellung passieren, und was liefert SUM für eine leere Gruppe?

def umsatz_pro_kunde(db):
    zeilen = db.execute("""
        SELECT k.name, COALESCE(SUM(b.betrag), 0)
        FROM kunde k
        LEFT JOIN bestellung b ON b.kunde_id = k.id
        GROUP BY k.id
    """).fetchall()
    return dict(zeilen)

umsatz_pro_kunde

Merksatz

Bei einem zusammengesetzten Index zählt die Reihenfolge (Gleichheit zuerst, Bereich danach), und eine Schleife, die in jedem Durchlauf die Datenbank fragt, ist verdächtig.

Prüfstein

Du hast einen Index auf (kunde_id, datum). Für welche Filter hilft er, für welche nicht, und woran erkennst du ein N+1-Problem im Code?

Zurück zu Teil 1.

Quelle: quellen/konzeptuebersicht-software-fortgeschritten.docx, Schicht 5 (Query-Verarbeitung: Join-Algorithmen, Covering und Partial Indexes). Über die Quelle hinaus (allgemeines Fachwissen): Leftmost-Prefix-Regel, N+1, SQLite-Plantexte (alle mit SQLite 3.51.0 lokal ausgeführt). Dass PostgreSQL Hash und Merge Join kennt: bitte prüfen.