LEVEL 8 · Database Systems

Sort-Merge Join

সর্ট-মার্জ জয়েন

দুই input sorted key-অনুসারে পাশাপাশি merge — বড় data, range join আর already-sorted path-এর join।

also: merge-join, smj

i, j = 0, 0
while i < n and j < m:
    if   L[i].key < R[j].key: i += 1
    elif L[i].key > R[j].key: j += 1
    else: emit all equal-key pairs; advance

Sorted হলে streaming: O(n+m), memory O(1) — hash join-এর spill ছাড়াই বিশাল data
Range/non-equi condition-ও চলে (merge interval logic) — hash যেখানে অপারেশনাল নয়
Sort লাগলে O(n log n) যোগ — planner তখনই sort-merge নেয় যখন sort এমনিতে দরকার (ORDER BY downstream)

External merge sort + merge = unlimited size join; PostgreSQL-এ Sort → Merge Join plan shape চেনুন।