Statistics ও Cardinality Estimation — optimizer-এর চোখ

লক্ষ্য: ANALYZE যা করে তার হ্রাসপ্রাপ্ত প্রতিরূপ — ছোট sample থেকে estimator বানিয়ে full-data truth-র সাথে মেপে দেখা।

import random
from collections import Counter

random.seed(7)

# ---------- synthetic skewed data ----------

N = 200_000

def make_data(n):
    # jittered Pareto: ঘন নিম্নমান, দীর্ঘ tail, কোনো duplicate-edge trap নেই
    return [min(999_999,
                int((random.paretovariate(1.15) - 1 + random.random()) * 30_000))
            for _ in range(n)]

DATA = make_data(N)

# ---------- estimators ----------

class EquiDepthHistogram:
    """equi-depth: প্রতি bucket-এ sample-এর ~সমান সংখ্যক value"""

    def __init__(self, sample, buckets=20):
        s = sorted(sample)
        self.buckets = buckets
        self.edges = [s[round(k * (len(s) - 1) / buckets)]
                      for k in range(buckets + 1)]

    def range_selectivity(self, lo, hi):
        hits = 0.0
        for k in range(self.buckets):
            blo, bhi = self.edges[k], self.edges[k + 1]
            width = max(bhi - blo, 1)
            overlap = min(hi, bhi) - max(lo, blo)
            if overlap > 0:
                hits += min(overlap, width) / width
        return hits / self.buckets


class MCVEstimator:
    """value-র বদলে stripe (v // 10000)-এ MCV — repeated discrete unit"""

    def __init__(self, sample, k=10):
        stripes = [v // 10_000 for v in sample]
        self.total = len(stripes)
        self.mcv = Counter(stripes).most_common(k)
        self.freq = {s: c / self.total for s, c in self.mcv}
        self.rest_mass = max(0.0, 1.0 - sum(self.freq.values()))
        self.n_other = max(1, len(set(stripes)) - len(self.mcv))

    def equality_selectivity(self, stripe):
        return self.freq.get(stripe, self.rest_mass / self.n_other)

# ---------- ground truth (full data brute force) ----------

def exact_range(lo, hi):
    return sum(1 for x in DATA if lo <= x <= hi) / N

def exact_eq(stripe):
    return sum(1 for x in DATA if x // 10_000 == stripe) / N

# ---------- experiment: sample-size ladder ----------

QUERIES_R = [(2000, 6000), (0, 90000), (150000, 160000), (400000, 700000)]
QUERIES_E = [0, 1, 2]

def evaluate(frac):
    m = max(int(N * frac), 50)
    sample = random.sample(DATA, m)
    hist = EquiDepthHistogram(sample)
    mcv = MCVEstimator(sample)
    errs_r = [abs(hist.range_selectivity(lo, hi) - exact_range(lo, hi))
              / max(exact_range(lo, hi), 1e-4) for lo, hi in QUERIES_R]
    errs_e = [abs(mcv.equality_selectivity(s) - exact_eq(s))
              / max(exact_eq(s), 1e-4) for s in QUERIES_E]
    return m, 100 * sum(errs_r) / len(errs_r), 100 * sum(errs_e) / len(errs_e)

print(f"{'sample':>7} | {'rows':>7} | {'range err%':>10} | {'equality err%':>13}")
print('-' * 47)
for frac in (0.001, 0.01, 0.10):
    m, er, ee = evaluate(frac)
    print(f'{frac:>6.1%} | {m:>7,} | {er:>9.1f}% | {ee:>12.1f}%')

সাধারণ ফলাফল (seed=7 — আপনার সংখ্যা কাছাকাছি হবে):

 sample |    rows | range err% | equality err%
-----------------------------------------------
   0.1% |     200 |       34.4% |         24.7%
   1.0% |   2,000 |       19.6% |          7.8%
  10.0% |  20,000 |       10.3% |          3.1%

Reading: sample ১০০ গুণ বাড়ায় error উভয়ই ~৩× নেমেছে — sampling error ∝ 1/sqrt(n)-এর বাস্তব ছায়া। Range-এর error তুলনামূলক বেশি থাকে কারণ interpolation long-tail bucket-এ সবচেয়ে কাঁপে; equality দ্রুত ঠিক হয় কারণ ঘন stripe-গুলো তাড়াতাড়ি MCV list-এ ঢোকে। Production lesson: ANALYZE কোটি-row table-এও মাত্র ৩০,০০০ row দেখে — তবু যথেষ্ট, কারণ planner perfect estimate না, সঠিক order-এর estimate চায়।

নিজে বাড়ান:

1. Buckets সংখ্যা sweep করুন 50 — ছোট sample-এ বেশি bucket কি সাহায্য করে না ক্ষতি করে?
2. Uniform histogram (equi-width) variant লিখে skewed data-তে তুলনা করুন — equi-depth কেন standard তার প্রমাণ
3. Join-selectivity mini-sim: দুই independent column-এর estimated sel গুণ করে exact join-size-এর সাথে error compounding দেখুন