Соединение вложенными циклами (Nested loop join)
Простейший алгоритм соединения: для каждой строки внешнего отношения просматривается внутреннее и выдаются совпадения. В общем случае O(N×M), а если по ключу во внутреннем есть индекс — O(N). Выбор по умолчанию для небольших соединений в OLTP.
Силён при индексированной внутренней таблице: каждая внешняя строка порождает индексный поиск за логарифмическое время. Без индекса на больших таблицах — катастрофа: 10 000×10 000 = 100 млн операций. Классическая регрессия: из-за перекоса статистики планировщик выбирает nested loop, уверенный, что во внешней таблице 10 строк, а там 10 000 — и запрос зависает. На неизвестной кардинальности hash join надёжнее. В PostgreSQL узел Materialize над внутренней частью кэширует результат, если внешняя сторона несколько раз перебирает одни и те же значения. Поиск одной строки в OLTP почти всегда заканчивается nested loop по первичному ключу — и это оптимально.