Optimizer Rules

The optimizer applies an ordered list of rewrite rules to the logical plan. Each rule recognizes a pattern and replaces it with an equivalent, cheaper one. Writing a rule is how you teach the optimizer about a custom plan operator, but a rule can be as small as removing a redundant pair of operators.

The three parts of a rule

A PatternRule has one field and two methods:

• operator is the plan-operator class the rule starts matching at (or an array of classes, or null to consider every node). The optimizer only calls you on nodes of that type, so this is a cheap pre-filter.
• match(node) decides whether the pattern actually applies here. Return { bindings } capturing whatever transform will need, or null.
• transform(node, bindings) returns the operator that replaces node.

A worked rule: merging nested limits

A subquery with its own LIMIT inside an outer LIMIT produces two Limit operators separated by the subquery's Projection:

Limit(skip=1, limit=2)
  Projection
    Limit(skip=0, limit=5)
      Projection
        TupleSource

A projection is one-to-one on rows, so the two limits can be folded into one. The rule matches the three-node shape, splices the inner Limit out, and returns a single merged one:

import * as plan from '@dortdb/core/plan';
import { PatternRule } from '@dortdb/core/optimizer';

interface LimitBindings {
  proj: plan.Projection;
  inner: plan.Limit;
}

const mergeLimits: PatternRule<plan.Limit, LimitBindings> = {
  operator: plan.Limit,

  match: (node) => {
    const proj = node.source;
    if (!(proj instanceof plan.Projection)) return null;
    const inner = proj.source;
    if (!(inner instanceof plan.Limit)) return null;
    return { bindings: { proj, inner } };
  },

  transform: (node, { proj, inner }) => {
    proj.replaceChild(inner, inner.source);
    return new plan.Limit(
      node.lang,
      inner.skip + node.skip,
      Math.min(node.limit, Math.max(0, inner.limit - node.skip)),
      proj,
    );
  },
};

The arithmetic is the whole substance of the rule: the inner limit has already skipped inner.skip rows and kept at most inner.limit, so after the outer limit skips node.skip more, at most inner.limit - node.skip remain available.

Two habits worth copying:

• match does the checking, transform does the work. By the time transform runs, everything it needs is in bindings and no case can fail.
• Rewire the tree with replaceChild rather than assigning to source directly; it keeps the parent links consistent.

Register it

Rules are entries in the optimizer's ordered rules array, and order matters. Several built-in rules exist only to create patterns a later rule can exploit. Place a new rule where it should run relative to the others:

new DortDB({
  mainLang: SQL(),
  optimizer: { rules: [...defaultRules, mergeLimits] },
});

// or swap the rule set at runtime
db.optimizer.reconfigure({ rules: [...defaultRules, mergeLimits] });

A rule that needs the database itself can be supplied as a class instead of an object; the optimizer instantiates it with the database interface, see PatternRuleConstructor. The built-in rules range from small local rewrites to whole algorithms, and are the best source of further examples.