selinger-join-optimizer

Answer

I implemented a full Selinger-style cost-based query optimizer in a single JavaScript module (selinger-optimizer.js). Here are the key components:

Core Architecture

1. Histogram (Histogram class) - Supports both equi-width and equi-depth histogram construction from raw values - Key methods: selectivityEq(value), selectivityRange(lo, hi), selectivityLessThan(value), estimateNDV() - Handles edge cases: single distinct values, empty histograms, out-of-range queries

2. Statistics Catalog (Catalog, TableStat, ColumnStat) - In-memory catalog storing table row counts and per-column histograms - ColumnStat tracks NDV, null fraction, and value distribution type

3. Selectivity Estimation (SelectivityEstimator) - Range predicates (<, >, <=, >=) — uses histogram bucket interpolation - Equality predicates (=) — assumes uniform distribution within each bucket - Join selectivity — uses 1 / max(NDV1, NDV2) formula - Combined selectivity — assumes independence (multiplicative) - Default heuristics when histograms are unavailable

4. Cost Model (CostModel) - Sequential scan: pages × seqPageCost + rows × cpuTupleCost - Index scan: separate clustered/unclustered costing (random I/O per row for unclustered) - Nested loop join: outerRowCount × innerAccessCost - Hash join: build + probe pages cost - Sort-merge join: sort cost (page-level N log N) + merge cost

5. Access Path Selection - Sequential scan is always available - Index scan selected when equality or range predicates exist on a column with a histogram - The optimizer compares costs and picks the cheapest

6. DP Join Order Optimizer (SelingerOptimizer.dynamicProgramJoin) - Selinger-style DP over subsets of tables using bitmask representation - For each subset, finds the cheapest left-deep tree by considering all possible last tables - Evaluates join predicates connecting the left and right sides - Supports nested-loop, hash, and sort-merge join methods (configurable) - Handles up to N tables (tested with 5)

7. Subquery Decorrelation (SelingerOptimizer.decorrelateSubqueries) - IN (subquery) → semi-join - NOT IN (subquery) → anti-join - EXISTS (subquery) → semi-join - NOT EXISTS (subquery) → anti-join - Scalar subquery comparison → join with grouping - Extracts correlation predicates between outer and inner query

8. Annotated Query Plan (QueryPlan) - Operator type, relation name, children, predicates, estimated rows, estimated cost - Index name tracking for index scans - Full annotation pass adds operator, relation, outputRows, totalCost, joinType annotations - toString() for readable plan output, toJSON()/fromJSON() for serialization

Key Implementation Details

// DP core — iterate subsets in increasing size
for (let size = 2; size <= n; size++) {
  for (const subsetMask of subsetsOfSize(n, size)) {
    for (const lastBit of BitSet.allBits(subsetMask)) {
      leftMask = subsetMask ^ (1 << lastBit);
      // ... evaluate join between left and right table
    }
  }
}

// Join selectivity calculation
joinSel *= this.selEst.estimateJoinSelectivity(t1, c1, t2, c2);

// Cost comparison
if (totalCost < bestCost) {
  bestCost = totalCost;
  bestPlan = new QueryPlan(joinType, null, left.plan, right.plan, ...);
}