Merge join — ikkita input oqimini join kaliti bo‘yicha tartiblangan holda bir vaqtda yurib, mos kalitlarni birlashtiradigan database join algoritmi. U ayniqsa katta relationlar allaqachon kerakli tartibda kelganda yoki range/tenglik bo‘yicha keng natija olinayotganda samarali bo‘lishi mumkin.
Ishlash prinsipi
Algoritm ikki tartiblangan ro‘yxat boshidan boshlaydi. Chap kalit kichik bo‘lsa chap pointer, o‘ng kalit kichik bo‘lsa o‘ng pointer oldinga siljiydi. Kalitlar teng bo‘lsa mos satrlar natijaga chiqariladi. Har ikkala oqim bir marta ketma-ket ko‘rib chiqilishi mumkin, shuning uchun asosiy merge bosqichi taxminan chiziqli xarajatga ega.
Duplicate kalitlar alohida e’tibor talab qiladi. Chapda uchta va o‘ngda to‘rtta bir xil kalit bo‘lsa, barcha 12 kombinatsiya qaytarilishi kerak. Engine bir tomondagi teng kalitlar guruhini belgilab, ikkinchi guruh bilan birlashtiradi. Natijaning o‘zi katta bo‘lsa, hech bir algorithm output hajmi xarajatini yo‘q qila olmaydi.
Tartibni olish
Input B-tree indexdan kerakli tartibda o‘qilishi yoki alohida sort operatoridan o‘tishi mumkin. Agar har ikkala katta jadvalni avval saralash zarur bo‘lsa, hash join arzonroq chiqishi ehtimoli bor. Biroq sort boshqa ORDER BY, GROUP BY yoki keyingi merge uchun ham kerak bo‘lsa, uning xarajati bir nechta maqsadga xizmat qiladi.
Composite join kalitida sort ustunlari va yo‘nalishi mos bo‘lishi kerak. Expression, collation yoki data type farqi mavjud tartibdan foydalanishni cheklashi mumkin. Query plan har inputda Sort, Index Scan yoki boshqa order-preserving operator borligini ko‘rsatadi.
Qo‘llanish xususiyatlari
Merge join ko‘p tizimlarda equi-join uchun ishlatiladi. Ayrim engine’lar inequality yoki band joinlarning cheklangan ko‘rinishlarini ham merge usulida bajara oladi. Full outer join uchun ikki tartiblangan oqimdagi mos bo‘lmagan qatorlarni aniqlash tabiiy tarzda amalga oshadi.
Hash join butun build tomonni hash xotirasiga joylashtirishi kerak; merge join esa tartiblangan oqimni ketma-ket o‘qiydi. Bu juda katta ma’lumotda yoki mavjud index orderidan foydalanilganda afzal bo‘lishi mumkin. Nested loop esa kichik tashqi oqim va selective inner indexda ko‘pincha tezroq.
Xotira va disk
Merge bosqichining o‘zi odatda kam xotira talab qiladi, lekin sort katta xotira ishlatishi mumkin. Sort memory limitdan oshsa temporary diskka spill bo‘ladi va qo‘shimcha IO yuz beradi. Duplicate guruh juda katta bo‘lsa, engine mark/restore yoki materialization uchun resurs sarflaydi.
Parallel bajarilishda har worker tartiblangan bo‘lak yaratishi, keyin gather merge orqali global orderga birlashishi mumkin. Aniq implementatsiya database mahsulotiga bog‘liq.
Plan tahlili
EXPLAIN ANALYZEda merge condition, input sortlari, sort usuli, memory, disk spill va actual rows ko‘riladi. Sortning kutilmagan paydo bo‘lishi mos index yo‘qligi yoki orderning kichik farqi bilan bog‘liq bo‘lishi mumkin. Shunchaki merge joinni majburlash queryni tezlatishini kafolatlamaydi.
Statistika duplicate darajasini va filter selectivitysini noto‘g‘ri baholasa optimizer natija hajmini xato taxmin qiladi. Testlar faqat kichik ma’lumot bilan emas, real kalit taqsimoti bilan bajariladi. Index qo‘shish write va storage xarajati keltirgani uchun uning foydasi boshqa querylar bilan birga baholanadi.
Bog‘liq tushunchalar
Join algorithm, Sort, B-tree index, Hash join, Nested loop, FULL OUTER JOIN, Query plan, Cardinality