Query Optimizer — cost model আর plan search

লক্ষ্য: System-R-এর core loop হাতে লেখা — ছয় relation পর্যন্ত exhaustive, আর Selinger-এর insight-এর সবচেয়ে ছোট সম্পূর্ণ প্রমাণ।

from itertools import combinations

# ---------- input model ----------

SIZE = {'A': 1_000, 'B': 1_000, 'C': 1_000_000}

SEL = {frozenset({'A', 'B'}): 0.99,        # খারাপ জোড়া — প্রায় cartesian
       frozenset({'B', 'C'}): 1e-9,        # চমৎকার key join → ফল এক-row
       frozenset({'A', 'C'}): 0.99}
DEFAULT_SEL = 0.05                          # অজানা pair-দের অনুমান

def cross_sel(left_grp, right_grp):
    """দুই group-এর মধ্যে জানা সবচেয়ে শক্ত link — conservative estimate"""
    known = [s for p in ((a, b) for a in left_grp for b in right_grp)
             if (s := SEL.get(frozenset(p))) is not None]
    return min(known) if known else DEFAULT_SEL

def out_size(l_size, r_size, l_grp, r_grp):
    return max(1, round(l_size * r_size * cross_sel(l_grp, r_grp)))

def join_node_cost(l_size, r_size):
    return l_size + r_size      # node = দুই input-এর scan; leaf-এর নিজের cost ০

# ---------- System-R style DP over bitmasks ----------

NAMES = sorted(SIZE)
FULL = (1 << len(NAMES)) - 1

def splits(mask):
    """mask-এর সব (ছোট,বড়) partition — প্রতিটা ঠিক একবার"""
    sub = (mask - 1) & mask
    while sub:
        other = mask ^ sub
        if sub < other:
            yield sub, other
        sub = (sub - 1) & mask

def grp_of(mask):
    return frozenset(NAMES[i] for i in range(len(NAMES)) if mask >> i & 1)

def dp():
    best = {}                               # mask -> (cost, size, desc)
    finals = []                             # FULL mask-এর প্রতিটা candidate
    for i, n in enumerate(NAMES):
        best[1 << i] = (0, SIZE[n], n)
    for mask in range(1, FULL + 1):
        if bin(mask).count('1') < 2:
            continue
        for m1, m2 in splits(mask):
            c1, z1, d1 = best[m1]
            c2, z2, d2 = best[m2]
            cost = c1 + c2 + join_node_cost(z1, z2)
            desc = f'({d1}⋈{d2})'
            if mask == FULL:
                finals.append((cost, desc))
            if mask not in best or cost < best[mask][0]:
                best[mask] = (cost, out_size(z1, z2, grp_of(m1), grp_of(m2)),
                              desc)
    top3 = sorted({c: d for c, d in finals}.items())[:3]
    return best[FULL], top3

# ---------- greedy baseline: প্রতি ধাপে ছোট দুই group ----------
# (selectivity পুরো উপেক্ষা — ঐতিহাসিক naive heuristic)

def greedy():
    groups = {frozenset(n): (SIZE[n], n) for n in NAMES}
    total = 0
    while len(groups) > 1:
        cand = [(v1[0] + v2[0], g1, g2)
                for (g1, v1), (g2, v2)
                in combinations(list(groups.items()), 2)]
        _, g1, g2 = min(cand)
        z1, d1 = groups.pop(g1)
        z2, d2 = groups.pop(g2)
        total += join_node_cost(z1, z2)
        groups[g1 | g2] = (out_size(z1, z2, g1, g2), f'({d1}⋈{d2})')
    size, desc = groups[frozenset(NAMES)]
    return total, size, desc

if __name__ == '__main__':
    (c, s, d), top3 = dp()
    gc, gs, gd = greedy()
    print(f'DP optimal : cost={c:>12,}  final-size={s:>9,}  {d}')
    print('top-3 distinct plan costs:')
    for rank, (cc, dd) in enumerate(top3, 1):
        print(f'  #{rank} cost={cc:>12,}  {dd}')
    print(f'greedy     : cost={gc:>12,}  final-size={gs:>9,}  {gd}')
    print(f'greedy খরচ DP-র {gc / c:.2f}x — local choice-এর দাম')

প্রত্যাশিত output (skew-crafted data):

DP optimal : cost=   1,002,001  final-size=      990  (A⋈(B⋈C))
top-3 distinct plan costs:
  #1 cost=   1,002,001  (A⋈(B⋈C))
  #2 cost=   1,992,000  ((A⋈B)⋈C)
  #3 cost= 991,002,000  (B⋈(A⋈C))
greedy     : cost=   1,992,000  final-size=      990  (C⋈(A⋈B))
greedy খরচ DP-র 1.99x — local choice-এর দাম

Greedy প্রথম ধাপেই A,B জুড়েছে — ছোট দুই group, মোহনীয় local view! Result ৯.৯ লক্ষ-row intermediate, তার ওপর C-র পূর্ণ scan। DP জানত B⋈C-র দামি প্রথম ধাপ পরে এক-row-র ফসল দেয়, আর শেষ join তখন প্রায় free। Bushy tree-ও naturally এসেছে — split দুই side-ই composite হতে পারে।

নিজে বাড়ান:

1. Interesting orders: প্রতি subset-এ (cheapest, dept-sorted-cheapest) দুই candidate রাখুন — GROUP BY reuse simulate করুন
2. Left-deep-only mode toggle — bushy বনাম left-deep-এর optimal-gap মাপুন
3. Relation ৭-৮-এ DP runtime মাপুন — exponential wall নিজের stopwatch-এ