Join Algorithms — nested loop, hash, merge

লক্ষ্য: theory-র তিন algorithm production-grade না হলেও semantics-complete হোক — duplicate, empty side, সব edge ঠিক। Benchmark-এ তাদের পার্থক্য নিজের চোখে।

import random
import time

random.seed(42)

# ---------- engines ----------

def nested_loop_join(left, right, lk, rk):
    out = []
    for l in left:                        # প্রতিটা left tuple-এ
        for r in right:                   # পুরো right scan
            if l[lk] == r[rk]:
                out.append((l, r))
    return out


def hash_join(left, right, lk, rk):
    ht = {}                               # build: right side
    for r in right:
        ht.setdefault(r[rk], []).append(r)
    out = []                              # probe: stream left
    for l in left:
        out.extend((l, m) for m in ht.get(l[lk], ()))
    return out


def sort_merge_join(left, right, lk, rk):
    L = sorted(left, key=lambda t: t[lk])
    R = sorted(right, key=lambda t: t[rk])
    out, i, j = [], 0, 0
    while i < len(L) and j < len(R):
        lv, rv = L[i][lk], R[j][rk]
        if lv < rv:
            i += 1
        elif lv > rv:
            j += 1
        else:                             # equi-zone: পুরো run × পুরো run
            i2 = i
            while i2 < len(L) and L[i2][lk] == lv:
                i2 += 1
            j2 = j
            while j2 < len(R) and R[j2][rk] == lv:
                j2 += 1
            out.extend((a, b) for a in L[i:i2] for b in R[j:j2])
            i, j = i2, j2
    return out


def ground_truth(left, right, lk, rk):
    idx = {}
    for r in right:
        idx.setdefault(r[rk], []).append(r)
    return [(l, m) for l in left for m in idx.get(l[lk], ())]

# ---------- data ----------

KEY_POOL = 5000                           # ইচ্ছাকৃত ছোট → duplicates guaranteed

def make_rows(n):
    return [{'k': random.randrange(KEY_POOL), 'p': f'r{i}'}
            for i in range(n)]

# ---------- correctness ----------

L, R = make_rows(300), make_rows(400)

def sig(rows):
    return sorted((a['p'], b['p']) for a, b in rows)

gt = sig(ground_truth(L, R, 'k', 'k'))
for name, fn in [('nested', nested_loop_join),
                 ('hash', hash_join),
                 ('merge', sort_merge_join)]:
    assert sig(fn(L, R, 'k', 'k')) == gt, f'{name} mismatch!'
print('correctness: ৩টা engine-ই ground truth multiset-এর সাথে মিলেছে')

# ---------- benchmark matrix ----------

ALGOS = [('nested', nested_loop_join), ('hash', hash_join), ('merge', sort_merge_join)]
MAX_PAIR_TESTS = 2 * 10 ** 7             # naive-এর জন্য safety cap

print(f"\n{'size':>13} | {'nested':>26} | {'hash':>10} | {'merge':>10}")
print('-' * 68)
for nl, nr in [(100, 100_000), (10_000, 10_000)]:
    left, right = make_rows(nl), make_rows(nr)
    cells = []
    for name, fn in ALGOS:
        if name == 'nested' and nl * nr > MAX_PAIR_TESTS:
            cells.append(f'skip (est {nl * nr:,} tests)')
            continue
        t0 = time.perf_counter()
        got = fn(left, right, 'k', 'k')
        dt = time.perf_counter() - t0
        cells.append(f'{dt * 1000:>9.1f} ms')
    print(f'{f"{nl}x{nr}":>13} | {cells[0]:>26} | {cells[1]:>10} | {cells[2]:>10}')

সাধারণ ফলাফল (laptop, Python 3.12 — সংখ্যা machine-ভেদে বদলাবে, pattern দেখুন):

correctness: ৩টা engine-ই ground truth multiset-এর সাথে মিলেছে

       size |                     nested |       hash |      merge
--------------------------------------------------------------------
   100x100000 |                   790.0 ms |     30.4 ms |   108.2 ms
  10000x10000 | skip (est 100,000,000 tests) |    16.6 ms |    31.9 ms

তিনটা reading: (১) hash-এর build cost amortize হয় — বড় probe-এ flat। (২) merge-এর খরচ মূলত sorting; input pre-sorted হলে সে সবাইকে ছাড়ায়। (৩) nested-এর quadratic curve ১০⁸ pair-test-এ minutes-এ ডুবত — planner বড় unindexed join-এ তাকে কেন বাছে না, benchmark-ই উত্তর।

নিজে বাড়ান:

1. Pre-sorted input দিয়ে merge মাপুন — sorted() call বাদ দিয়ে timing তুলনা
2. Grace-hash simulation: hash_join-এ max-memory-budget + partition-recurse যোগ করুন
3. Skew test: KEY_POOL = 10 করে equi-zone explosion দেখুন — merge-এর zone আর hash-এর bucket দুটোই ফুলে যাবে