Optimization

Because every language is lowered into the same algebra, a query can be optimized holistically: the optimizer neither knows nor cares which language produced which part of the plan. A filter written at the end of an SQL query can end up pushed deep into a Cypher subtree that came from a nested LANG block, because to the optimizer both are just operators in one tree.

DortDB ships a rule-based optimizer. Cost-based optimizers generally do better, but they need statistics about the data. DortDB sources are schema-less by design and no statistics are collected, so instead the optimizer is an ordered, extensible set of rewrite rules. Each rule recognizes a pattern in the plan and replaces it with an equivalent, cheaper subtree.

See it in action

The Showcase demo lets you toggle and reorder individual rules and watch the logical plan change, the quickest way to build intuition for what each rule does.

This page describes the built-in rules. To write your own rule for a custom operator, see Optimizer Rules; for the practical configuration knobs (indices, hash joins, rule ordering), see Indexing & Performance.

Optimizer-only plan operators

Three operators exist purely to give the optimizer better targets. They are not part of the theoretical algebra (a plan is complete without them) but they enable substantial speedups: IndexScan, IndexedRecursion, and BidirectionalRecursion. See the Operator Reference for their signatures and semantics.

The rules, in default order

The defaultRules set applies the following rules in this order. Order matters: several rules exist to create patterns that a later rule can exploit.

Unnest Subqueries

Finds Calculations that contain a safe nested subquery and lifts the subquery out in front of the operator as a ProjectionConcat, replacing it in the calculation with a plain reference. A subquery is safe when it produces at most one value and is always evaluated, so (SELECT number FROM t) + 5 is unnested, but val IN (SELECT number FROM t) is not (the containing operator accepts a sequence). Unless the subquery is guaranteed to return a value, the ProjectionConcat is made outer.

This rewrite does not speed anything up on its own; it exposes the subquery to the rules below, which can turn it into a join.

Merge To/From Items

A MapFromItem sitting directly on top of a MapToItem (or vice versa) is redundant. Such pairs appear routinely after query rewrites and language switches. When MapFromItem is the source and both operators' keys match, both operators are removed outright; when MapToItem is the source, they collapse into a single-attribute Projection. The only exception is when the source MapToItem key is the Symbol(allAttrs). In that case, the merge is skipped.

Pushdown Selections

A Selection reduces cardinality, so it pays to evaluate it as early (as close to the leaves) as possible. This rule moves Selections down the tree, with the constraints needed to preserve meaning:

Past OrderBy and Distinct it always moves freely.
Past set operators (Union, Intersection, Difference) it is duplicated into both branches.
Past a Projection only if the predicate does not depend on newly computed attributes, and only if the required renaming is safe (no variable shadowing); this is exactly what the attribute rename checker verifies.
Into a Join, CartesianProduct, or ProjectionConcat branch that contains all the attributes the predicate needs, but never into the null-padded side of an outer join.

To avoid one un-pushable Selection blocking a whole chain behind it, the rule considers the entire chain of stacked Selections at once and pushes down only the parts that are eligible.

ProjectionConcat → Join

A ProjectionConcat whose mapping does not depend on the surrounding row (an uncorrelated subquery) is equivalent to a CartesianProduct. If the ProjectionConcat is outer, it becomes a left outer Join instead. This turns the subqueries unnested above into ordinary relational operators that later rules and the executor can handle efficiently.

Products → Joins

Merges a Selection with the CartesianProduct beneath it into a single Join, moving the predicate into the join condition. When the Selection cannot be pushed into either branch (because it references attributes from both), this is the rewrite that still makes it useful. Applied to an existing Join, it simply adds another condition rather than combining them into one.

Join Indices

The first half of the two-step index handling (described in Secondary indices below). It looks for a Join whose source side is an indexable data source and whose conditions match a registered index, and rewrites it into a ProjectionConcat shaped so the next rule can turn the source into an IndexScan. In practice the matched side may also carry chains of Selections, OrderBys, and Projections; index matching sees through renames and ignores newly computed attributes.

Index Scans

The second half: a filtered TupleSource or MapFromItem-wrapped ItemSource whose Selection matches a registered index is replaced by an IndexScan. The scan's access Calculation feeds the matching values straight into the index structure instead of scanning the whole source. Like Selection pushdown, it considers whole Selection chains at once.

Merge Projections

The most involved built-in rule. It combines two stacked Projections into one: unused attributes are dropped, and computed attributes are inlined, but only when a computed attribute is referenced once, so a potentially expensive calculation is never duplicated. For example, π([x → a, x → b], π([calc(1+1) → x], ...)) is left as-is, because merging would evaluate 1+1 twice.

Secondary indices

DortDB lets you register custom index types. Because it targets many data models, indexing is deliberately open-ended: any Calculation that contains no subquery is indexable. During optimization, registered indices are shown the access expressions in the plan and decide whether they apply: a hash-table index might require an equality check on one attribute, while a range index also handles inequalities. Currently the first matching index wins; this selection lives in the two replaceable rules above (Join Indices and Index Scans), so it can be swapped for a smarter algorithm.

See an example below of how the two rules work together:

// DortDB programmatic configuration:
db.createIndex(['t2'], ['a + b / 2'], MapIndex);

SELECT t1.foo, t2.bar FROM t1
JOIN t2
ON t2.a + t2.b / 2 = t1.id

This design is what lets Cypher accelerate graph traversal. Graph steps are lowered into Joins across node and edge sources, which by themselves ignore the underlying structure. The Cypher ConnectionIndex detects those Joins via the data adapter's isConnected condition and routes them through the adapter's neighbor-lookup methods instead. The index stores nothing itself (it is a thin wrapper over the adapter) and it is what makes IndexedRecursion and BidirectionalRecursion possible for graph queries.

Calculation building & language-specific rewrites

Two more optimizations happen outside the rule list.

Constant folding occurs while Calculations are built: a pure function whose arguments are all constants is evaluated once at plan time and replaced by its result, avoiding redundant work at execution time.

Because all languages share one algebra, optimizations that target a single language are rare; it is usually better to write a rule that applies universally. The exceptions live in the language packages, not the core. SQL, for instance, rewrites quantified comparisons during plan building: a > ALL (...) or similar subquery is replaced by an aggregation over the subquery, e.g.

SELECT x FROM a WHERE x < ALL (SELECT y FROM b)
-- is evaluated as:
SELECT x FROM a WHERE x < (SELECT min(y) FROM b)

Optimizer-only plan operators​

The rules, in default order​

Unnest Subqueries​

Merge To/From Items​

Pushdown Selections​

ProjectionConcat → Join​

Products → Joins​

Join Indices​

Index Scans​

Merge Projections​

Secondary indices​

Calculation building & language-specific rewrites​