Build a SQL engine

// lexer.ts
export type Tok =
  | { k: 'kw';  v: string }
  | { k: 'id';  v: string }
  | { k: 'num'; v: number }
  | { k: 'str'; v: string }
  | { k: 'op';  v: string }
  | { k: 'eof' };

const KEYWORDS = new Set([
  'SELECT','FROM','WHERE','GROUP','BY','HAVING','ORDER','LIMIT',
  'JOIN','LEFT','INNER','ON','AS','AND','OR','NOT','NULL',
  'IS','IN','WITH','RECURSIVE','UNION','ALL','OVER','PARTITION',
  'ASC','DESC','COUNT','SUM','AVG','MIN','MAX','ROW_NUMBER'
]);

export function lex(src: string): Tok[] {
  const out: Tok[] = [];
  let i = 0;

  while (i < src.length) {
    const c = src[i];

    if (/\s/.test(c)) { i++; continue; }

    // comment
if (c === '-' && src[i+1] === '-') {
      while (i < src.length && src[i] !== '\n') i++;
      continue;
    }

    // string literal — '' is an escaped quote
if (c === "'") {
      let v = ''; i++;
      while (i < src.length) {
        if (src[i] === "'" && src[i+1] === "'") { v += "'"; i += 2; }
        else if (src[i] === "'") { i++; break; }
        else v += src[i++];
      }
      out.push({ k: 'str', v }); continue;
    }

    // number
if (/[0-9]/.test(c)) {
      let v = '';
      while (i < src.length && /[0-9.]/.test(src[i])) v += src[i++];
      out.push({ k: 'num', v: parseFloat(v) }); continue;
    }

    // identifier or keyword
if (/[A-Za-z_]/.test(c)) {
      let v = '';
      while (i < src.length && /[A-Za-z0-9_.]/.test(src[i])) v += src[i++];
      const up = v.toUpperCase();
      out.push(KEYWORDS.has(up) ? { k: 'kw', v: up } : { k: 'id', v });
      continue;
    }

    // multi-char operators first, then single
const two = src.substr(i, 2);
    if (['>=','<=','<>','!='].includes(two)) {
      out.push({ k: 'op', v: two === '!=' ? '<>' : two }); i += 2; continue;
    }
    out.push({ k: 'op', v: c }); i++;
  }

  out.push({ k: 'eof' });
  return out;
}

query      := [ with ] select
with       := WITH [RECURSIVE] cte { ',' cte }
cte        := id AS '(' select [ UNION ALL select ] ')'
select     := SELECT projList FROM tableRef { join }
              [ WHERE expr ] [ GROUP BY exprList ]
              [ HAVING expr ] [ ORDER BY ordList ] [ LIMIT num ]
join       := [LEFT|INNER] JOIN tableRef ON expr
expr       := orExpr
orExpr     := andExpr { OR andExpr }          -- lowest precedence
andExpr    := notExpr { AND notExpr }
notExpr    := [NOT] cmpExpr
cmpExpr    := addExpr [ (= | <> | < | > | <= | >= | IS [NOT] NULL) addExpr ]
addExpr    := mulExpr { (+ | -) mulExpr }
mulExpr    := atom { (* | /) atom }               -- highest precedence
atom       := num | str | id | func | '(' expr ')'

// plan.ts
// ── logical operators, in evaluation order (ch 6) ──
export type Logical =
  | { op:'scan';   table:string; alias:string }
  | { op:'join';   left:Logical; right:Logical; on:Expr; kind:'inner'|'left' }
  | { op:'filter'; src:Logical; pred:Expr }
  | { op:'group';  src:Logical; keys:Expr[]; aggs:Agg[] }
  | { op:'having'; src:Logical; pred:Expr }
  | { op:'window'; src:Logical; fns:WinFn[] }
  | { op:'project';src:Logical; exprs:Expr[]; names:string[] }
  | { op:'sort';   src:Logical; keys:{expr:Expr; desc:boolean}[] }
  | { op:'limit';  src:Logical; n:number };

/** build the logical plan in the ORDER THE ENGINE EVALUATES, not
    the order the clauses were written. this function IS chapter 6. */
export function toLogical(q: SelectAst): Logical {
  let node: Logical = { op:'scan', table:q.from.table, alias:q.from.alias };

  // 1. FROM + JOIN
for (const j of q.joins)
    node = { op:'join', left:node,
             right:{op:'scan', table:j.table, alias:j.alias},
             on:j.on, kind:j.kind };

  // 2. WHERE
if (q.where)   node = { op:'filter', src:node, pred:q.where };
  // 3. GROUP BY
if (q.groupBy)  node = { op:'group', src:node, keys:q.groupBy, aggs:q.aggs };
  // 4. HAVING
if (q.having)   node = { op:'having', src:node, pred:q.having };
  // 5. window functions
if (q.windows.length) node = { op:'window', src:node, fns:q.windows };
  // 6. SELECT — aliases come into existence HERE
  node = { op:'project', src:node, exprs:q.projExprs, names:q.projNames };
  // 8. ORDER BY — can see the aliases
if (q.orderBy)  node = { op:'sort', src:node, keys:q.orderBy };
  // 9. LIMIT
if (q.limit != null) node = { op:'limit', src:node, n:q.limit };

  return node;
}

// ── physical: choose algorithms. this is the optimizer. ──
export function toPhysical(l: Logical, cat: Catalog): Physical {
  switch (l.op) {
    case 'filter': {
      const src = l.src;
      // THE one optimization: a sargable predicate on an indexed
// column becomes a range scan instead of scan + filter (ch 73)
if (src.op === 'scan') {
        const range = sargable(l.pred, cat.indexes(src.table));
        if (range)
          return { op:'indexScan', table:src.table,
                   index:range.index, lo:range.lo, hi:range.hi };
      }
      return { op:'filter', src:toPhysical(src, cat), pred:l.pred };
    }
    case 'join':
      // equi-join on an indexed column → nested loop with index lookup
// otherwise → hash join (MySQL module ch 79)
return isEquiIndexed(l, cat)
        ? { op:'nestedLoop', ...toBoth(l, cat) }
        : { op:'hashJoin',  ...toBoth(l, cat) };
    default:
      return mapChildren(l, n => toPhysical(n, cat));
  }
}

/** is this predicate a bare column compared to a constant? (ch 73) */
function sargable(e: Expr, idx: Index[]) {
  if (e.kind !== 'cmp') return null;
  // the column must appear ALONE — a function call disqualifies it
if (e.left.kind !== 'col')  return null;
  if (e.right.kind !== 'lit') return null;
  const ix = idx.find(x => x.cols[0] === e.left.name);
  if (!ix) return null;
  switch (e.op) {
    case '=':  return { index:ix, lo:e.right.v, hi:e.right.v };
    case '>':
    case '>=': return { index:ix, lo:e.right.v, hi:Infinity };
    case '<':
    case '<=': return { index:ix, lo:-Infinity, hi:e.right.v };
    default:   return null;
  }
}

// exec.ts
export type Row = Record<string, any>;
export type Iter = Generator<Row>;

export function* exec(p: Physical, ctx: Ctx): Iter {
  switch (p.op) {

    case 'scan':
      yield* ctx.storage.scan(p.table);      // the B+tree (ch 84)
return;

    case 'indexScan':
      yield* ctx.storage.range(p.table, p.index, p.lo, p.hi);
      return;

    case 'filter':
      for (const r of exec(p.src, ctx))
        if (evalExpr(p.pred, r) === true)   // ← TRUE only. UNKNOWN is
yield r;                          //   discarded, per ch 8.
return;

    case 'project':
      for (const r of exec(p.src, ctx)) {
        const out: Row = {};
        p.exprs.forEach((e, i) => out[p.names[i]] = evalExpr(e, r));
        yield out;
      }
      return;

    case 'nestedLoop': {
      const right = [...exec(p.right, ctx)];   // materialize inner
for (const l of exec(p.left, ctx)) {
        let matched = false;
        for (const rr of right) {
          const joined = { ...l, ...rr };
          if (evalExpr(p.on, joined) === true) { matched = true; yield joined; }
        }
        // LEFT JOIN: emit the unmatched left row, NULL-padded (ch 14)
if (!matched && p.kind === 'left') yield { ...l, ...p.rightNulls };
      }
      return;
    }

    case 'hashJoin': {
      // build on the smaller side, probe with the larger (ch 79 MySQL)
const table = new Map<any, Row[]>();
      for (const r of exec(p.build, ctx)) {
        const k = evalExpr(p.buildKey, r);
        if (k == null) continue;            // NULL never matches (ch 9)
        (table.get(k) ?? table.set(k, []).get(k)!).push(r);
      }
      for (const r of exec(p.probe, ctx)) {
        const k = evalExpr(p.probeKey, r);
        for (const m of table.get(k) ?? []) yield { ...m, ...r };
      }
      return;
    }

    case 'group': {
      // BLOCKING: must consume everything before emitting (ch 13 MySQL)
const groups = new Map<string, { key:Row; rows:Row[] }>();
      for (const r of exec(p.src, ctx)) {
        const kv = p.keys.map(e => evalExpr(e, r));
        const id = JSON.stringify(kv);        // NULLs group together (ch 9)
if (!groups.has(id)) groups.set(id, { key:r, rows:[] });
        groups.get(id)!.rows.push(r);
      }
      for (const g of groups.values())
        yield { ...g.key, ...applyAggs(p.aggs, g.rows) };
      return;
    }

    case 'sort': {
      const all = [...exec(p.src, ctx)];        // also blocking
      all.sort((a, b) => {
        for (const k of p.keys) {
          const av = evalExpr(k.expr, a), bv = evalExpr(k.expr, b);
          if (av === bv) continue;
          const c = av == null ? -1 : bv == null ? 1 : (av < bv ? -1 : 1);
          return k.desc ? -c : c;
        }
        return 0;
      });
      yield* all;
      return;
    }

    case 'limit': {
      let n = 0;
      for (const r of exec(p.src, ctx)) {
        if (n++ >= p.n) return;   // ← stops pulling. the child is abandoned.
yield r;
      }
      return;
    }
  }
}

/** three-valued logic, implemented exactly as in chapter 8 */
function evalExpr(e: Expr, r: Row): any {
  switch (e.kind) {
    case 'lit': return e.v;
    case 'col': return r[e.name] ?? null;
    case 'cmp': {
      const a = evalExpr(e.left, r), b = evalExpr(e.right, r);
      if (a === null || b === null) return null;   // ← UNKNOWN
switch (e.op) {
        case '=':  return a === b;
        case '<>': return a !== b;
        case '<':  return a < b;
        case '>':  return a > b;
        case '<=': return a <= b;
        case '>=': return a >= b;
      }
    }
    case 'and': {
      const a = evalExpr(e.left, r), b = evalExpr(e.right, r);
      if (a === false || b === false) return false;  // FALSE wins
if (a === null  || b === null)  return null;
      return true;
    }
    case 'or': {
      const a = evalExpr(e.left, r), b = evalExpr(e.right, r);
      if (a === true || b === true) return true;     // TRUE wins
if (a === null || b === null) return null;
      return false;
    }
    case 'isNull': return evalExpr(e.arg, r) === null;  // always 2-valued
  }
}

// window.ts
export function* windowOp(src: Iter, fns: WinFn[]): Iter {
  const all = [...src];                       // blocking: needs everything
for (const fn of fns) {
    // 1. partition
const parts = new Map<string, Row[]>();
    for (const r of all) {
      const k = JSON.stringify(fn.partitionBy.map(e => evalExpr(e, r)));
      (parts.get(k) ?? parts.set(k, []).get(k)!).push(r);
    }

    for (const rows of parts.values()) {
      // 2. order within the partition
if (fn.orderBy.length) rows.sort(cmpBy(fn.orderBy));

      // 3. compute per row
      rows.forEach((r, i) => {
        if (fn.name === 'ROW_NUMBER') { r[fn.alias] = i + 1; return; }

        const [lo, hi] = frameBounds(fn, rows, i);
        r[fn.alias] = aggregate(fn.name, rows.slice(lo, hi + 1), fn.arg);
      });
    }
  }
  yield* all;
}

/** THE chapter 32 distinction, in one function */
function frameBounds(fn: WinFn, rows: Row[], i: number): [number, number] {
  const mode = fn.frame?.mode ?? 'RANGE';        // ← the DEFAULT is RANGE
const start = 0;                              // UNBOUNDED PRECEDING
if (mode === 'ROWS') return [start, i];      // exactly this row
// RANGE: extend to include every PEER — rows whose ORDER BY
// values equal the current row's. this is the "jump" (ch 32).
let end = i;
  const cur = fn.orderBy.map(o => evalExpr(o.expr, rows[i]));
  while (end + 1 < rows.length) {
    const nxt = fn.orderBy.map(o => evalExpr(o.expr, rows[end + 1]));
    if (JSON.stringify(cur) !== JSON.stringify(nxt)) break;
    end++;
  }
  return [start, end];
}

// recursive.ts
export function* recursiveCte(
  cte: RecursiveCte, ctx: Ctx, maxIter = 1000
): Iter {

  // 1. the anchor runs ONCE
let working: Row[] = [...exec(cte.anchor, ctx)];
  yield* working;

  let iterations = 0;

  // 2-4. loop until an iteration produces nothing
while (working.length > 0) {
    if (++iterations > maxIter)
      throw new Error(`recursion exceeded ${maxIter} iterations`);

    // the self-reference resolves to the WORKING TABLE — only the
// previous iteration's rows, never the accumulated result.
    ctx.cteRows.set(cte.name, working);

    const next = [...exec(cte.recursive, ctx)];
    yield* next;

    working = next;        // ← becomes the new working table
  }
}

// UNION (not ALL): dedupe against everything seen so far.
// this alone terminates a cyclic graph.
const seen = new Set<string>();
const next = [...exec(cte.recursive, ctx)]
  .filter(r => {
    const k = JSON.stringify(r);
    if (seen.has(k)) return false;
    seen.add(k); return true;
  });

// cycle detection by path, as in chapter 44 — carry the visited
// set per row rather than deduping globally, so genuine distinct
// paths to the same node are preserved.

// engine.ts
import { MiniDB } from '../minidb/db';        // MySQL module, part 11
import { lex } from './lexer';
import { parse } from './parser';
import { toLogical, toPhysical } from './plan';
import { exec } from './exec';

export class Engine {
  constructor(private db: MiniDB) {}

  query(sql: string): Row[] {
    const ast  = parse(lex(sql));
    const log  = toLogical(ast);
    const phys = toPhysical(log, this.db.catalog);

    const trx  = this.db.begin();
    const view = this.db.readView(trx);      // MVCC snapshot (ch 42)
try {
      return [...exec(phys, {
        storage: {
          // full scan → walk the leaf chain, MVCC-filtered
          *scan(table: string) {
            for (const rec of this.db.tree(table).range(-Infinity, Infinity)) {
              const row = this.db.visible(rec, view);
              if (row) yield row;
            }
          },
          // index range → ONE descent, then a sideways walk (ch 24 MySQL)
          *range(table: string, index: string, lo: any, hi: any) {
            for (const rec of this.db.tree(table, index).range(lo, hi)) {
              const row = this.db.visible(rec, view);
              if (row) yield row;
            }
          }
        },
        cteRows: new Map()
      })];
    } finally {
      this.db.commit(trx);
    }
  }
}

// ── and it runs ──
const engine = new Engine(new MiniDB('app.db', 'app.wal'));

engine.query(`
  SELECT u.name, COUNT(o.id) AS orders
  FROM users u
  LEFT JOIN orders o ON o.user_id = u.id
  WHERE u.id > 100
  GROUP BY u.name
  ORDER BY orders DESC
  LIMIT 10
`);