/ Datenbanken

Kardinalität (Kreuzprodukt)

Zeilenanzahl eines kartesischen Produkts zweier Relationen: Ergebnis = KardA · KardB. Damit lassen sich auch Worst-Case-Zwischenergebnisse von Joins abschätzen.

01 · Eingabe

Kardinalität (Kreuzprodukt) berechnen

Zeilenanzahl eines kartesischen Produkts zweier Relationen: Ergebnis = KardA · KardB. Damit lassen sich auch Worst-Case-Zwischenergebnisse von Joins abschätzen.

Lösen für

Ergebnis = KardA · KardB

KardA Kardinalität A

KardB Kardinalität B

Worum geht es?

Das kartesische Produkt zweier Relationen A und B enthält jede Kombination aus einer Zeile von A und einer Zeile von B. Die resultierende Kardinalität ist schlicht das Produkt der Einzel-Kardinalitäten: |A × B| = |A| · |B|.

In SQL entsteht ein Kreuzprodukt durch CROSS JOIN oder durch FROM A, B ohne WHERE-Bedingung. Auch ein Inner Join produziert intern zunächst das Kreuzprodukt — der Optimizer reduziert es dann via Filter und Indizes. Die Formel ist deshalb der wichtigste Worst-Case-Anker für Join-Größenschätzungen.

Die Formel

Formel Kreuzprodukt

Ergebnis = KardA · KardB

Umstellungen:
    KardA = Ergebnis / KardB
    KardB = Ergebnis / KardA

Die Variablen

Symbol	Bedeutung	Einheit	Erklärung
KardA	Kardinalität A	—	Zeilenanzahl Tabelle A.
KardB	Kardinalität B	—	Zeilenanzahl Tabelle B.
Ergebnis	Ergebnis-Kardinalität	—	Zeilenanzahl des Kreuzprodukts.

Minimal-Beispiel

Tabelle Kunden (1.000 Zeilen) wird mit Produkte (50 Zeilen) gekreuzt:

Rechnung Cross Join

Ergebnis = 1 000 · 50
         = 50 000 Zeilen

Praxis-Beispiele

Beispiel 1 — Reporting-Matrix

Für einen Bericht „Umsatz pro Filiale × Monat" sollen alle Kombinationen erzeugt werden — 25 Filialen, 12 Monate:

Rechnung Matrix

Ergebnis = 25 · 12
         = 300 Zeilen

Beispiel 2 — Fehlender Join führt zu Explosion

Bestellungen (100 000) und Positionen (500 000) ohne Join-Bedingung:

Rechnung Worst Case

Ergebnis = 100 000 · 500 000
         = 5 · 10¹⁰ Zeilen

Ein vergessenes ON … = … produziert 50 Milliarden Zeilen — typischer Auslöser für „Query läuft seit Stunden".

Beispiel 3 — Umstellung nach KardA

Ein Kreuzprodukt liefert 1.000.000 Zeilen, eine Seite hat 200 Zeilen:

Rechnung Umstellung

KardA = Ergebnis / KardB
      = 1 000 000 / 200
      = 5 000 Zeilen