Mini SQL Engine

কেন এই প্রজেক্ট

Compilers মডিউলে parser বানিয়েছেন, databases মডিউলে join algorithm পড়েছেন — Mini SQL Engine দুটোকে এক জায়গায় জোড়ে। SQL query-র জীবনও compiler-এর program-এর মতোই: tokenize → parse → AST → plan → execute। পার্থক্য শুধু একটাই: database-এর “code generation” ধাপটা runtime-এ data-র shape দেখে সিদ্ধান্ত নেয় — filter কোথায় নামবে, কোন join algorithm, কখন disk-এ spill।

এই প্রজেক্টের আসল ফসল EXPLAIN-এর চোখ: শেষদিনে আপনি EXPLAIN SELECT ... চালিয়ে plan-টা পড়তে পারবেন — কারণ ওই indented text ছাপার machine-টা আপনি নিজেই লিখেছেন। PostgreSQL-এর planner output তখন আর অজানা ভাষা লাগবে না।

ধাপে ধাপে

১. Tokenizer

import re

TOKEN_RE = re.compile(r"""
    (?P<ws>\s+)
  | (?P<num>\d+(?:\.\d+)?)
  | (?P<str>'[^']*')
  | (?P<ident>[A-Za-z_]\w*)
  | (?P<op><=|>=|<>|!=|=|<|>|\(|\)|,|\*|\.)
""", re.VERBOSE)

KEYWORDS = {"SELECT", "FROM", "WHERE", "JOIN", "ON", "GROUP", "BY",
            "ORDER", "LIMIT", "ASC", "DESC", "AND", "OR", "AS", "SUM", "COUNT", "MIN", "MAX"}

def tokenize(sql: str) -> list[Token]:
    out, pos = [], 0
    while pos < len(sql):
        m = TOKEN_RE.match(sql, pos)
        if not m:
            raise SyntaxError(f"bad char at {pos}: {sql[pos]!r}")
        pos = m.end()
        kind = m.lastgroup
        if kind != "ws":
            text = m.group()
            out.append(Token("KW" if text.upper() in KEYWORDS and kind == "ident" else kind.upper(), text))
    return out

<= আগে =-এর লিখুন — regex alternation বাঁ-থেকে-ডান মেলে, ভুল ক্রমে <= ভেঙে <=→<,= হয়ে যাবে। এই tokenizer bug সত্যিই ঘটে।

২. Pratt parser — SELECT subset

Grammar (EBNF-style, comment হিসেবে code-এ রাখুন):

query   := SELECT select_list FROM table
           [ JOIN table ON cond ] [ WHERE cond ]
           [ GROUP BY col_list ] [ ORDER BY expr [ASC|DESC] ]
           [ LIMIT num ]
expr    := or_expr ; or_expr > and_expr > cmp_expr > add_expr > mul_expr

Comparison আর boolean-এর binding power টেবিল:

BP = {"OR": 1, "AND": 2, "=": 3, "<>": 3, "<": 3, ">": 3, "<=": 3, ">=": 3,
      "+": 4, "-": 4, "*": 5, "/": 5}

def parse_expr(self, bp=0) -> Expr:
    left = self.parse_primary()               # literal | column | (expr)
    while self.peek().kind in BP and BP[self.peek().text] > bp:
        op = self.advance().text
        right = self.parse_expr(BP[op])       # right-assoc via bp param
        left = BinOp(op, left, right)
    return left

a = 1 AND b = 2 OR c = 3 parse করে AST print করুন — grouping ঠিক আছে কি না চোখে দেখুন। Pratt framework একবার বসলে নতুন operator মানে শুধু টেবিলে এক লাইন।

৩. AST + catalog + CSV loader

from dataclasses import dataclass

@dataclass
class Table:
    name: str
    columns: list[tuple[str, type]]          # [("id", int), ("amount", float)]
    rows: list[tuple]

def load_csv(path: str) -> Table:
    # header row + type inference: সব int? float? else str
    ...

CATALOG: dict[str, Table] = {
    "customers": load_csv("data/customers.csv"),
    "orders":    load_csv("data/orders.csv"),
}

Column reference resolve করার সময় scope মানুন — JOIN-এর পরে orders.amount আর bare amount ambiguity error দেবে। এটাই আপনার mini type-checker: unknown column আর type mismatch ('a' < 5) এখনই ধরুন, executor-এ না গিয়ে।

৪. Logical plan builder

AST থেকে algebraic tree:

@dataclass
class Scan:   table: str
@dataclass
class Filter: cond: Expr; child: Node
@dataclass
class HashJoin: on: Expr; left: Node; right: Node
@dataclass
class Aggregate: groups: list[Expr]; aggs: list[AggCall]; child: Node
@dataclass
class Sort: keys: list[tuple[Expr, bool]]     # (expr, is_desc)
@dataclass
class Limit: n: int; child: Node

Builder সরলরেখায় বসে: FROM→Scan, JOIN→HashJoin(left, right), WHERE→Filter… Logical plan এখনো খরচ দেখে না — শুধু কী হবে, কীভাবে নয়।

৫. Volcano executor — hash join + pushdown

প্রতিটা operator iterator; open/next/close নয়, Python-এ generator-ই Volcano:

def exec_scan(table):        yield from CATALOG[table].rows
def exec_filter(cond, child): yield from (r for r in child if eval_expr(cond, r))

def exec_hash_join(on, left, right):
    key_l, key_r = split_equi_cond(on)
    ht: dict = {}
    for r in left:
        ht.setdefault(eval_expr(key_l, r), []).append(r)   # build side
    for s in right:                                        # probe side
        for match in ht.get(eval_expr(key_r, s), ()):
            yield combine(match, s)

Filter pushdown এখানেই planner-এর একমাত্র বুদ্ধি: WHERE-এর conjunct গুলো ভেঙে যেগুলো এক table-এর, সেগুলো Filter হয়ে scan-এর ঠিক উপরে নেমে আসে — join-এ ঢোকার আগেই tuple ঝেড়ে ফেলা যায়। Pushdown on/off করে একই query-র runtime diff রাখুন, EXPLAIN-এ annotation দেখান।

Checkpoint: ১০k × ১০k cross product query pushdown ছাড়া চলতেই থাকে, pushdown দিলে মিলিসেকেন্ডে — এই বিশাল gap-টাই optimizer কেন আছে।

৬. Hash aggregation

from collections import defaultdict

def exec_aggregate(groups, aggs, child):
    acc = defaultdict(lambda: [a.init() for a in aggs])
    for row in child:
        slot = acc[tuple(eval_expr(g, row) for g in groups)]
        for i, a in enumerate(aggs):
            a.step(slot[i], row)
    for gvals, slots in acc.items():
        yield gvals + tuple(a.final(s) for a, s in zip(aggs, slots))

NULL group key আর empty input-এ COUNT=0 কিন্তু SUM=NULL — edge case দুটো golden test-এ ইচ্ছে করে রাখুন, সব real engine এখানে একসো খায়।

৭. ORDER BY external merge sort

Memory budget ছুঁলে sorted run ডিস্কে spill:

import heapq, tempfile

def external_sort(rows, keyfn, mem_rows=50_000):
    runs, buf = [], []
    for row in rows:
        buf.append(row)
        if len(buf) >= mem_rows:
            runs.append(spill(sorted(buf, key=keyfn)))     # temp file
            buf = []
    runs.append(iter(sorted(buf, key=keyfn)))
    return heapq.merge(*runs, key=keyfn)      # k-way merge, O(n log k)

mem_rows ছোট করে (যেমন ১০০) forced-spill path test করুন — নইলে external branch কোনোদিন চলবেই না আর তার bug লুকিয়ে থাকবে।

৮. EXPLAIN printer

Limit (n=10)
└─ Sort (total DESC)            [external]
   └─ Aggregate (groups=[customer_id], SUM(amount))
      └─ HashJoin (o.customer_id == c.id)
         ├─ Filter (o.amount > 100)         ← pushed down
         │  └─ Scan orders
         └─ Scan customers

Printer-টা plan tree walk করে এই text ছাপায় — recursion ১৫ লাইন। Golden test-এর EXPLAIN snapshot আর runtime result দুটোই compare হবে: plan বদলালে test ভাঙবে, ইচ্ছাকৃত change হলে snapshot update।

৯. Golden test suite — ২০টা query

QUERIES = ["q01_simple_select", ..., "q20_join_group_order_limit"]

@pytest.mark.parametrize("name", QUERIES)
def test_golden(name):
    sql = open(f"tests/{name}.sql").read()
    got = normalize(run(engine, sql))         # rows as tuples, sorted canonically
    want = csv_rows(f"tests/{name}.expected.csv")
    assert got == want, f"{name}\ngot:  {got[:5]}...\nwant: {want[:5]}..."

Query mix ভাবুন: point filter, range, equi/non-equi join, multi-group aggregate, order+limit, empty-result, NULL-heavy, ambiguous column error, type error, syntax error — ভুল case-ও golden suite-এর সদস্য।

নিজেকে চ্যালেঞ্জ করুন

LEFT/RIGHT OUTER JOIN — unmatched probe side-এ NULL-padded emit
Subquery in WHERE (IN (SELECT ...)) — semi-join হয়ে যায় কি না দেখুন
Index nested loop — Scan-এ optional sorted index attach করে planner choice
Predicate reordering — selectivity guess দিয়ে cheapest-filter-first
LIMIT pushdown through sort — top-k heap, O(n log k)-এ নামিয়ে আনুন
String intern + columnar row store — cache miss কমলো কি না benchmark

যা এখানে শিখলেন, পরে যেখানে লাগবে

এখানে	পরে
Plan tree abstraction	Level 8 PostgreSQL Lab — EXPLAIN output এখন পড়া যাবে
Volcano iterator	Streaming systems — একই pull model, backpressure সহ
Filter pushdown intuition	Level 12 Spark/Presto predicate pushdown-এর মূল বীজ
External sort/spill	Level 9 — distributed shuffle-এর একক-নোড version
Golden test discipline	Query engine refactor-এর একমাত্র নিরাপদ রাস্তা

মাইলস্টোন

আগে যা পড়া দরকার