Nested loop — join bajarish algoritmi bo‘lib, tashqi oqimdagi har bir satr uchun ichki relationdan mos satrlarni qidiradi. U dasturlashdagi ichma-ich siklga o‘xshaydi, ammo database ichki tomonni index orqali qidirsa barcha satrlarni qayta-qayta to‘liq o‘qishi shart emas.
Ishlash prinsipi
Soddalashtirilgan ko‘rinish:
for each row in outer_input:
for each matching row in inner_input:
emit joined_row
Naive holatda tashqi tomonda M, ichki tomonda N satr bo‘lsa, M × N taqqoslash yuz berishi mumkin. Index nested loopda esa har tashqi kalit uchun ichki B-tree yoki boshqa access pathdan qidiruv bajariladi. Kichik tashqi natija va selective index mavjud bo‘lsa bu juda samarali.
Masalan, 20 ta yangi order uchun customer primary keyni topish: optimizer avval filterlangan 20 orderni oladi, so‘ng har biri uchun customers.id indexidan bir qator qidiradi. Butun customers jadvalini hash qilish yoki saralash bunga nisbatan ortiqcha bo‘lishi mumkin.
Tashqi va ichki tomon
Algoritmda inputlar roli simmetrik emas. Odatda kichikroq yoki kuchli filtrlangan relation tashqi tomonga, tez qidiriladigan relation ichki tomonga tanlanadi. Join turi va dependency bu erkinlikni cheklashi mumkin. Lateral yoki correlated subqueryda ichki reja tashqi satr qiymatiga bog‘liq bo‘ladi.
Ichki operator har safar qayta bajarilsa query planda loops soni katta ko‘rinadi. Bir loop vaqti kichik bo‘lsa ham million marta takrorlanishi umumiy latencyni oshiradi. Shu sabab plan tahlilida operatorning individual vaqti bilan birga necha marta ishlagani ko‘riladi.
Index va memoization
Join kalitiga mos index nested loopning asosiy kuchidir. Covering index kerakli ustunlarni o‘zida saqlasa, jadval heapiga qo‘shimcha murojaat kamayadi. Ammo har qidiruv random IO talab qilsa, katta tashqi oqimda xarajat tez o‘sadi.
Tashqi tomonda bir xil kalitlar ko‘p takrorlansa, ayrim database tizimlari ichki qidiruv natijasini memoize yoki materialize qilishi mumkin. Bu bir qiymatni qayta izlashni kamaytiradi, evaziga xotira ishlatadi. Cache hit ma’lumot taqsimotiga bog‘liq.
Boshqa joinlardan farqi
Hash join odatda katta, tartiblanmagan equi-join uchun bir tomondan hash jadval quradi. Merge join ikkala oqim join kaliti bo‘yicha tartiblanganida foydali. Nested loop esa tenglikdan tashqari range predicate bilan ham ishlay oladi va birinchi natijani tez chiqarishi mumkin.
Algoritmlardan biri har doim eng yaxshi emas. LIMIT, available index, xotira, parallelizm, row width va qiymatlar selectivitysi qarorni o‘zgartiradi. Query optimizer statistikaga asoslanadi; tashqi satrlar sonini keskin kam baholasa, amalda juda ko‘p index lookup qiladigan yomon nested loop tanlashi mumkin.
Diagnostika
Query planda nested loop ichidagi actual rows, loops, buffer read va vaqt tekshiriladi. Kutilmagan katta tashqi oqimning sababi yetishmagan filter, noto‘g‘ri join predicate yoki eskirgan statistika bo‘lishi mumkin. Faqat nested loopni o‘chirib qo‘yish o‘rniga estimation xatosi tuzatiladi.
Mos composite index yaratish, predicate tiplarini bir xil qilish, tashqi oqimni oldin kamaytirish yoki queryni qayta ifodalash yordam beradi. Productionga o‘xshash data bilan sinov zarur: kichik development bazasida yaxshi ko‘ringan nested loop ma’lumot ming marta o‘sganda samarasizlashishi mumkin.
Bog‘liq tushunchalar
Join algorithm, Index scan, Query plan, Hash join, Merge join, Cardinality estimation, Correlated subquery, B-tree