Nested loop join
Het eenvoudigste joinalgoritme: voor elke rij in de buitenste relatie wordt de binnenste doorzocht op overeenkomsten. In het algemeen O(N×M), O(N) als de binnenste een index op de joinsleutel heeft. Standaard voor OLTP-joins op weinig data.
Krachtig met een geïndexeerde binnenste relatie: elke buitenste rij levert één indexopzoeking op (logaritmisch). Rampzalig zonder index op grote relaties: 10k×10k = 100 miljoen bewerkingen. Een klassieke prestatieregressie: scheve statistieken doen de planner een nested loop kiezen in de veronderstelling dat de buitenste 10 rijen heeft, terwijl het er 10k zijn, en de query blijft hangen. Een hash join is een veiligere standaard bij onbekende cardinaliteit. PostgreSQL: een Materialize-node boven de binnenste cachet het resultaat als de buitenste dezelfde waarden herhaaldelijk doorloopt. Opzoekingen van één rij in OLTP eindigen bijna altijd als nested loop met een PK-index, en dat is optimaal.