Nested Loop Join
Der einfachste Join-Algorithmus: für jede Zeile der äußeren Relation wird die innere Relation durchsucht und Treffer ausgegeben. O(N×M) im Allgemeinen, O(N) mit Index auf dem Join-Key der inneren Relation. Standard für kleine OLTP-Joins.
Stark bei indiziertem Inner — jede äußere Zeile löst einen Index-Lookup aus (logarithmisch). Katastrophal ohne Index bei großen Relationen: 10.000 × 10.000 sind 100 Millionen Operationen. Klassische Performance-Regression: eine verzerrte Statistik lässt den Planer glauben, die äußere Relation habe 10 Zeilen statt tatsächlich 10.000, wählt Nested Loop — und die Query hängt. Hash Join ist bei unbekannter Kardinalität die sicherere Wahl. In PostgreSQL cacht ein Materialize-Knoten über dem Inner das Ergebnis, falls der Outer dieselben Werte mehrfach durchläuft. OLTP-Einzelzeilen-Lookups landen fast immer als Nested Loop mit Primärschlüsselindex — und das ist genau optimal.