vaelii.impl.plan — com.vaelii/vaelii 0.1.0

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.

Three mechanisms, the first two of which the KB already had lying around unused:

Selectivity — the count-aware trie answers "how many facts are under this path prefix" in O(1) (count-at), 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. est-matches reads both.

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. So no literal is costed once and for all: an estimate is always taken under the variables bound at the point the literal would run.

The cartesian factors last, on structure rather than on cost — a literal sharing no variable with anything else in the conjunction narrows nothing and is narrowed by nothing, so wherever it runs it multiplies the row count of everything after it. Its own extent is then the wrong thing to rank it by, and rank it the wrong way: a selective isolated literal is the worst kind, because taking the cheapest available literal puts exactly that one first, where its factor is applied to the whole rest of the plan. deferring-isolated-order holds them to the back.

Sharing no variable is what makes such a literal unconstrained; it is not on its own what makes it a multiplier. A literal matching at most once multiplies by at most one, so it can only prune and belongs first — and the ground literal, which both chaining paths produce by substituting a rule's bindings before planning, has no variables to share and so satisfies the structural test vacuously. Both conditions are therefore checked, and cartesian-factors is where.

That placement is deliberately made on structure and not on an estimate. Whether a literal shares a variable is read off the conjunction; how big a join comes out is a guess the index can only bound from above, and those bounds do not compose — a plan chosen by minimizing estimated cost end to end multiplies the bound's error once per literal, and lands wide of one that never trusted it that far. So the estimate decides the order within each group, where it is compared once and locally, and structure decides which group a literal is in. The one thing an upper bound can settle is that a literal will not fan out at all — a bound of 1 is a proof of it — which is the only load the estimate carries in that decision.

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

Ties break on the literal's original position, so a plan is a function of the conjunction and the KB's counts, 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 children count-with-arg count-with-functor
                     context]
              :or {count-at p/count-at
                   children p/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 — which is what join ordering turns on.

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.

explain clj

(explain kb goals context)

(explain kb goals context opts)

The plan as data: each literal in execution order with the estimate it was chosen on and the variables bound when it runs. 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 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: cartesian-factors says why, and a flag that disagreed with the order it explains would be worse than no flag.

The flag is computed under the same guards order plans under, so a conjunction short enough to be returned untouched reports nothing as held back — there being nowhere to hold it.

order clj

(order kb goals context)

(order kb
       goals
       context
       {:keys [bound consequent-pred est-override] :or {bound #{}}})

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.