vaelii.impl.plan — com.vaelii/vaelii 0.5.1

Conjunctive query planning: the order a conjunction's literals are solved in.

A conjunction is commutative — [(parentOf Tom ?y) (dog ?y)] and its reverse have exactly the same solutions — but it is not equicost. Solved left to right, the first literal's matches are enumerated in full and each one re-drives the second; so the first literal's fan-out multiplies everything after it. Leading with the selective literal is the whole game, and on a measured three-literal join it ran 7x faster than leading with the general one.

Two estimators, two contracts

Both read the count-aware trie and neither fetches a record, but they answer different questions and are not interchangeable:

• est-matches is a sound upper bound on how many facts one literal matches. Its one-sided guarantee is load-bearing — an estimate of 1 is a proof that a literal matches at most once, and therefore cannot fan the plan out — and that proof is what the placement rules below rest on. It says nothing usable about how two literals combine: maxima of products do not factor.
• est-rows is an expected cardinality, with the distinct-value count of each variable beside it, and is explicitly allowed to be wrong in both directions. That is the property that makes it compose — expectations of products do factor under independence — so it is the quantity a join is costed in.

A summary is what est-rows returns and what the planner threads through its fold: {:rows 400 :vars #{?x ?y} :distinct {?x 20}}. A variable in :vars and absent from :distinct is one the index cannot count, which the join formula reads as 1 — so max(d_A(v), d_B(v)) defers to whichever side of the join can count it.

Three mechanisms

Selectivity — the count-aware trie answers "how many facts are under this path prefix" in O(1) (count-at), "how many distinct values sit at the next level" in O(1) too (count-children, which is its own read rather than (count (children …)) — that one materializes the child set, so asking it once per literal makes planning a fixed conjunction scale with the KB), and the secondary argument roots answer "how many facts have this term at position n" (count-with-arg) for the ground arguments the trie cannot reach. Both estimators read those and nothing else: there is no statistics table, and there is not to be one, because a second source of truth about cardinality would need maintaining on every write.

Every one of those counts spans all contexts, since the trie key ends with the context and no prefix the walk builds reaches past the arguments. A read is scoped to one context and the genlContext cone above it, so the counts are an over-estimate by a sentence's context multiplicity — which leaves est-matches sound (a cone is a subset of what is stored, so the bound can only be too large) and puts the error on est-rows's :rows alone, :distinct sitting a level above the contexts. A ground literal is clamped to one row and never sees it. docs/inference.md states the size of it; context reaches the estimators only for the subtype fan below.

Sideways information passing — a literal's cost is not fixed, it depends on what is already bound when it runs. (parentOf ?x ?y) is the whole extent of parentOf; the same literal after ?x is bound is one person's children. In the summary algebra that is not a special case: the variables already bound are a one-row relation, and joining a literal onto it divides its extent by the literal's own distinct count at that position — which is exactly the average branch a per-literal model charges, reached by the general rule instead of by a rule of its own.

Blocks, on structure rather than on cost — two literals sharing a variable constrain each other; two that share none do not, and no ordering within one group changes what the other costs. So the generators are split into connected components (components), the split is exact and free because it is read off the conjunction, and the estimate is then asked only the two questions it can answer: which literal to take next inside a block, and which block to run first.

Ordering the blocks

A block that produces n rows at internal intermediate cost s, placed after a prefix of P rows, costs P·s; run before another block it also multiplies that one by n. Two blocks therefore compare by adjacent transposition —

cost[i,j] = P·(sᵢ + nᵢ·sⱼ)   against   cost[j,i] = P·(sⱼ + nⱼ·sᵢ)
i first  ⟺  sᵢ/(nᵢ−1) ≥ sⱼ/(nⱼ−1)

— so a descending sort on s/(n−1) is optimal, in O(k log k) and with no search. It degenerates correctly, which is the check that it is the right law: a single-literal block has s = n, so its ratio n/(n−1) decreases in n and the law reduces to taking the smallest extent first; a block of one row ranks +∞ and leads; a block of none would make the ratio change sign, so n ≤ 1 is ranked first structurally rather than by the formula.

A block's literals run consecutively, which is an assumption rather than a theorem — interleaving two blocks is a legal plan the law does not consider — and it is measured rather than asserted: on a conjunction of two disconnected pairs the contiguous plan is the cheapest of all twenty-four permutations, interleaved ones included.

Two placements sit outside the law, and both are claims the estimate cannot make:

• A block that cannot multiply runs first. est-matches bounds each literal from above, so a block whose literals each bound to 1 is proved to match at most once: it can only prune, never fan out, and belongs wherever it is cheapest, which is first. The case that makes this load-bearing is the ground literal — (dog Bob) once a rule's bindings are substituted in, the shape both chaining paths hand the planner. It has no variables, so it is a block of its own with nothing to share; held back, a false one costs the entire join to reach a test that refutes it in one lookup.
• The anchored block runs before the rest. Every component touching the already-bound variables, a deferred (evaluable) literal or the recursive literal is fused into one component, and that one leads. It is the only block the pins reach: its literals feed the evaluables, which prune, and are narrowed by bindings the caller already has — neither of which the summary algebra models, since an evaluable's selectivity is a function of values rather than of counts. Running it first is what makes those prunes land before another block multiplies them.

Why a sort and not a search

Costing whole orders — the sum of a plan's intermediate row counts, minimized by a subset search — is refuted over est-matches, and measurably: on randomized joins it ran a mean 2.31× the best permutation's actual rows against cheapest-first's 1.19×, losing 3 trials of 9 and winning none. The reason is not that a search is the wrong shape but that it was minimizing a sum of incomparable quantities — a bound for some literals and an average for others. est-rows exists to fix that, and once the numbers compose the ordering does not need a search at all: the transposition law sorts.

What is never reordered

Ordering here is an execution decision and must not change the answer set. Two classes of literal are held back, exactly as sentex/canonicalize-rule holds them back when it canonicalizes a rule for storage:

• Deferred (evaluable) literals — evaluate, lessThan, greaterThan. These consume bindings rather than produce them; (evaluate ?z (+ ?x ?y)) run before ?x is bound does not throw, it quietly yields no solutions. They are never hoisted above a literal that binds them. They are, however, pulled forward to the first point where all their variables are bound — a test that can run early prunes the search early, which the storage canonicalization (which parks them uniformly last) does not attempt.

• The recursive literal of a rule — an antecedent whose functor is the rule's own consequent functor. It stays last among the generators, because a backward chainer executes the conjunction left to right and one that re-enters the rule before generating anything has nothing to recurse on.

  Note what this is not protecting against. A rule's antecedents are put into canonical order at storage (sentex/canonicalize-rule), which is where an author's spelling stops being observable — assert the same rule with the recursive literal written first and the stored antecedents are identical. So left-recursion is not a state a rule can reach here, and this pin is the cost model being kept from re-introducing one, not a rescue.

Determinism

Every number in the decision is derived from the conjunction and the KB's counts, and ties break on the literal's original position — so a plan is a function of content, never of iteration order. Same knowledge, same plan: the order independence the rest of the engine holds to (see vaelii.impl.jtms) applied to execution rather than belief.

*enabled* clj

Bind to false to run every conjunction in the order it was written.

Planning is a pure cost decision — it must never change the answer set, only how fast it is reached — and that is a claim worth being able to test rather than assert. Binding this false gives the unplanned execution to compare against, which is what plan_test does over every permutation of a conjunction.

est-matches clj

(est-matches kb goal bound)

(est-matches kb
             goal
             bound
             {:keys [count-at count-children count-with-arg count-with-functor
                     context]
              :or {count-at p/count-at
                   count-children p/count-children
                   count-with-arg p/count-with-arg
                   count-with-functor p/count-with-functor}})

Estimated number of stored facts a literal matches, given the variables already bound. This is the literal's fan-out — the number by which it multiplies the cost of everything sequenced after it.

Every input is an upper bound on the true match count, so the minimum of them is the tightest bound available without touching a record. That one-sidedness is the contract: this number may be far too large and may never be too small, so a reading of 1 proves the literal cannot fan out, which is the only claim the placement rules take from it. For how much a literal fans out — a quantity that has to compose across a join — see est-rows, which is the other estimator and is not a bound.

est-rows clj

(est-rows kb goal)

(est-rows kb goal opts)

The expected shape of the relation a literal denotes: how many rows it produces, and how many distinct values each of its variables takes over them.

(est-rows kb '(parentOf ?x ?y))
;; => {:rows 400 :vars #{?x ?y} :distinct {?x 20}}

This is the other estimator, and it is not est-matches. That one is a sound upper bound and this one is a point estimate, wrong in both directions by design — which is the property that lets it compose, since expectations of products factor under independence where maxima of products do not. Use est-matches to prove a literal cannot fan out; use this to say how much it does.

:distinct holds only what the index can count. The trie narrows left to right, so the one variable it counts exactly is the one at the first position the known prefix cannot extend past — (parentOf Tom ?y) counts ?y, (parentOf ?x ?y) counts ?x and leaves ?y out. A variable in :vars and absent from :distinct is uncounted, not zero, and the join formula reads it as the neutral 1 so that whichever side of a join can count a variable is the side that decides.

There is deliberately no bound argument, and the asymmetry with est-matches is the point: a literal's own shape does not depend on what the plan has bound, and the narrowing that binding buys is what the join formula computes. A planner seeds its prefix with the bound variables as a one-row relation and gets the same number the per-literal model charged for them, by the general rule.

explain clj

(explain kb goals context)

(explain kb goals context opts)

The plan as data: each literal in execution order with what it was costed at, the variables bound when it runs, and the reason it is where it is. What core/query-plan reports for a conjunction, and the way to see why an order was chosen rather than just what it was.

Three numbers, because the decision turns on three:

• :est-matches — the sound upper bound on this literal's own fan-out, under the bindings in hand. What proves a literal cannot multiply.
• :est-rows — the expected size of the relation the literal denotes, on its own and irrespective of the plan. What a join is costed in.
• :est-prefix — the model's expected row count for the whole plan up to and including this literal. This is the number the ordering actually turned on, and the one to read a surprising plan against: a literal placed early on a small :est-matches whose :est-prefix then jumps is the cost model being wrong about a join rather than about a literal.

And three flags, because a literal's position is decided by one of three different things and a plan is only diagnosable if it says which. :deferred? and :recursive? mark the operational pins. :isolated? marks a cartesian factor that was held to the back for being one — read it as the answer to "why is this last", not as a structural property of the literal. Without it a selective one reads as a small number sitting last, which looks like the planner erred; it is the one position the estimate beside it does not account for. A literal sharing no variable but matching at most once is not flagged, because it is not held back, and neither is one whose block the ranking put first.

:block is the rest of that answer, and the part :isolated? cannot give: the index of the block the literal was placed in, blocks running in the order shown. Two literals sharing a variable with each other and with nothing else are a cartesian block just as much as one literal is, and neither is :isolated?; the block number is what says they moved together. It is nil wherever no block ranking ran — planning off, or fewer than two reorderable literals, which a two-literal conjunction reaches whenever one of them is an evaluable. The deferred literal is still pulled forward there; what is absent is blocks for it to be pulled forward through.

The flags are read off the plan that ran rather than recomputed beside it, so a conjunction returned untouched reports nothing as held back — there being nowhere to hold it — and none of them can name a rule that did not fire. The three numbers are recomputed, since the plan keeps only the block-local prefixes it ranked on and these are threaded across the whole execution order; they are computed by the same two calls plan-pairs costs with, :est-override included, so a reported number and the number that chose the order are one cost model rather than two.

order clj

(order kb goals context)

(order kb goals context opts)

Order goals — a conjunction — for execution, and return the reordered vector.

opts: :bound variables already bound when the conjunction starts (default none). Callers that have already substituted their bindings into the goals can leave this empty; the substituted values make the literals ground on their own. :consequent-pred the functor of the rule these goals are the antecedents of, if they are. Identifies the recursive literal, which is pinned last (see the namespace docstring). :est-override (fn [goal bound]) -> estimate or nil. Consulted before the index model, so a caller whose executor is not the index — the prover registry, say — can cost a goal the way it will actually be answered.

A conjunction of fewer than two reorderable literals is returned untouched, without reading the index at all: the overwhelmingly common prove call is a single goal and must not pay for a planner it cannot use.