Query Planning in ExDatalog: The Seam Between IR and Engine

Datalog evaluation looks direct — apply the rules, accumulate facts, stop at a fixpoint. Alongside the validated ExDatalog.IR and the semi-naive engine, ExDatalog ships a small planner whose job is to describe how a program will run before it runs. It is an inspection tool, not a stage in the evaluation path: the engine reads the IR directly. The planner is thin by design in v0.5.0, but it is the structure future optimizations hang from: join ordering, cost-based selection, and goal-directed evaluation all plug in here.

Why Datalog Needs a Planner

The IR describes what a program means: relations, rules, strata, safety-validated bodies. The engine describes how it runs: nested-loop joins, delta tracking, monotonic fixpoint iteration. Between the two, several decisions need a home:

• which evaluation strategy applies (semi-naive bottom-up vs. goal-directed magic sets);
• how each rule is stratified (already computed by the validator, but the engine wants the resolved IR.Rule structs grouped by stratum);
• which joins the engine will perform — one per positive body atom — and in what position, so the delta slot maps cleanly during semi-naive iteration;
• which predicates (constraints, aggregates, callbacks) must run, classified by kind so the engine can dispatch them uniformly;
• where telemetry fires so observers can profile planning without instrumenting every rule.

Putting these decisions in their own struct means the plan is a standalone, inspectable description of evaluation. The engine reads the IR directly (it does not consume the plan today), but keeping the description separate is what makes the planner the right seam for a future cost-based optimizer to plug into.

The Four Planner Structs

The plan is assembled from four small structs. Each is descriptive — it explains what the engine will do rather than dictating bytecode.

ExDatalog.Planner.Plan

The top-level plan records the chosen strategy, the planned strata, the flat list of joins, the flat list of predicates, and a small metadata map (currently carrying the goal, if any):

@enforce_keys [:strategy, :strata]
defstruct [:strategy, strata: [], joins: [], predicates: [], metadata: %{}]

@type strategy :: :semi_naive | :magic_sets

The plan is descriptive by construction. Aggregate and callback predicates do not get their own fields — they appear in predicates with kind: :aggregate / kind: :callback, so adding new predicate categories later does not change the struct.

ExDatalog.Planner.Stratum

A planned stratum wraps the IR stratum into a form the engine wants: the actual IR.Rule structs, not just their IDs, alongside the relations that belong to that stratum:

@enforce_keys [:index, :rules, :relations]
defstruct [:index, :rules, :relations]

The planner builds these by filtering rules whose stratum field matches each IR stratum's index:

defp build_strata(%IR{strata: strata, rules: rules}) do
  Enum.map(strata, fn %IR.Stratum{index: idx, relations: rels} ->
    stratum_rules = Enum.filter(rules, fn r -> r.stratum == idx end)
    %Stratum{index: idx, rules: stratum_rules, relations: rels}
  end)
end

This is where the validator's stratification work flows into the engine: each Stratum runs to a local fixpoint before the next begins, guaranteeing that negated relations are complete before any rule that negates them fires.

ExDatalog.Planner.Join

A join is one positive body atom position within a rule. position is the 0-based index of the atom within the rule's positive body; delta_position indicates the semi-naive delta slot it maps to; strategy records how the join is executed, defaulting to :nested_loop:

@enforce_keys [:relation, :position]
defstruct [:relation, :position, delta_position: nil, strategy: :nested_loop]

@type strategy :: :nested_loop | :indexed

The planner emits one join per positive body atom across all rules. For the classic transitive-closure program (path(X,Y) :- edge(X,Y) plus path(X,Z) :- edge(X,Y), path(Y,Z)), that's three joins — one for the first rule's body and two for the second rule's two positive atoms:

defp build_joins(%IR{rules: rules}) do
  Enum.flat_map(rules, fn rule ->
    rule.body
    |> Enum.filter(&match?({:positive, _}, &1))
    |> Enum.with_index()
    |> Enum.map(fn {{:positive, %IR.Atom{relation: rel}}, position} ->
      %Join{relation: rel, position: position, delta_position: position}
    end)
  end)
end

Negative atoms and constraints are deliberately excluded — they filter, they don't join. The delta_position mirrors position because, in the current engine, every positive atom of a recursive rule participates in the delta; future join reorderings will reassign this field.

ExDatalog.Planner.Predicate

A predicate is any non-relational body element: a constraint, an aggregate, or a callback. kind groups it into one of the evaluation categories; op is the specific operator:

@enforce_keys [:kind, :op]
defstruct [:kind, :op, metadata: %{}]

@type kind ::
        :comparison | :arithmetic | :type | :string |
        :membership | :aggregate | :callback

Classification leans on ExDatalog.Constraint's operator predicates:

defp constraint_kind(op) do
  cond do
    Constraint.comparison_op?(op) -> :comparison
    Constraint.arithmetic_op?(op) -> :arithmetic
    Constraint.type_op?(op)       -> :type
    Constraint.string_op?(op)     -> :string
    Constraint.membership_op?(op) -> :membership
    Constraint.aggregate_op?(op)  -> :aggregate
    true                          -> :comparison
  end
end

This classification matters for the engine: comparison, type, string, and membership predicates filter bindings, while arithmetic predicates extend the binding environment with their result variable. The plan records that distinction once, so the engine dispatches on kind rather than re-deriving it per iteration.

plan/2 and explain_plan/1,2

The two public entry points cover the two use cases: programmatic planning for the engine, and human-readable planning for debugging.

plan/2

plan/2 takes a compiled IR and returns {:ok, %Plan{}}. It accepts two options:

• :strategy — :semi_naive (the default) or :magic_sets;
• :goal — a {relation, pattern} tuple used with :magic_sets (e.g. {"path", [:a, :_]} for goal-directed evaluation).

iex> alias ExDatalog.{Program, Rule, Atom, Term, Compiler, Planner}
iex> {:ok, ir} =
...>   Program.new()
...>   |> Program.add_relation("edge", [:atom, :atom])
...>   |> Program.add_relation("path", [:atom, :atom])
...>   |> Program.add_rule(
...>     Rule.new(
...>       Atom.new("path", [Term.var("X"), Term.var("Y")]),
...>       [{:positive, Atom.new("edge", [Term.var("X"), Term.var("Y")])}]
...>     )
...>   )
...>   |> Compiler.compile()
iex> {:ok, plan} = Planner.plan(ir)
iex> plan.strategy
:semi_naive
iex> length(plan.joins)
1

The magic-sets strategy is selected by simply passing the option:

{:ok, plan} = Planner.plan(ir, strategy: :magic_sets, goal: {"path", [:a, :_]})
plan.strategy            #=> :magic_sets
plan.metadata.goal       #=> {"path", [:a, :_]}

explain_plan/1,2

explain_plan/1,2 is the debugging surface. It accepts a Program rather than an IR, validates and compiles it, plans the result, and renders a human-readable summary:

iex> Planner.explain_plan(program) =~ "Strategy: semi_naive"
true

The output is a small multi-line string. For the transitive-closure program with one rule it reads:

Strategy: semi_naive
  Stratum 0: 1 rule(s), relations: edge, path
Joins: 1
Predicates: 0

Constraints surface as a parenthesized list of operators:

Predicates: 1 (gt)

The formatter is straightforward — it joins the header, the per-stratum lines, and the join/predicate counts with \n:

defp format_plan(%Plan{} = plan) do
  header = "Strategy: #{plan.strategy}"

  strata_lines =
    Enum.map(plan.strata, fn s ->
      "  Stratum #{s.index}: #{length(s.rules)} rule(s), relations: #{Enum.join(s.relations, ", ")}"
    end)

  join_line = "Joins: #{length(plan.joins)}"

  pred_line =
    "Predicates: #{length(plan.predicates)}" <>
      case plan.predicates do
        [] -> ""
        preds -> " (#{Enum.map_join(preds, ", ", & &1.op)})"
      end

  Enum.join([header | strata_lines] ++ [join_line, pred_line], "\n")
end

If the program fails to compile — say, an unsafe rule where Z is unbound — explain_plan returns an error string rather than raising:

iex> Planner.explain_plan(bad_program) =~ "compilation failed"
true

This makes explain_plan/1,2 cheap to wire into a REPL or a mix task without having to handle exception flows.

Strategy Selection

The planner records the requested strategy; it does not perform the rewrite itself. Passing strategy: :magic_sets sets the plan's strategy field and stashes the goal in metadata:

Planner.plan(ir)                                       # :semi_naive
Planner.plan(ir, strategy: :magic_sets, goal: {"path", [:a, :_]})

The actual goal-directed rewrite is a separate concern, performed by ExDatalog.MagicSets during materialize/2 — not by the planner. So the two layers play complementary roles:

• Planner.plan/2 lets tooling predict and display which strategy a call will use, without running anything.
• ExDatalog.materialize(program, strategy: :magic_sets, goal: ...) actually applies the magic-sets transformation and evaluates the rewritten program (see the magic-sets article for details).

Both consume the same Plan/Stratum/Join/Predicate vocabulary, which is why a future cost-based optimizer can change the plan a program produces without changing call sites.

Telemetry Events

plan/2 emits one set of telemetry events per call — never per rule — so observers see the planning cost as a whole:

The implementation wraps the planning body in try/rescue so any failure still emits the :exception event before re-raising:

:telemetry.execute([:ex_datalog, :planner, :start], %{system_time: System.system_time()}, metadata)
start = System.monotonic_time()

try do
  plan = %Plan{strategy: strategy, strata: build_strata(ir), joins: build_joins(ir),
               predicates: build_predicates(ir), metadata: %{goal: goal}}
  :telemetry.execute([:ex_datalog, :planner, :stop], %{duration: System.monotonic_time() - start},
                      Map.put(metadata, :strategy, strategy))
  {:ok, plan}
rescue
  e ->
    :telemetry.execute([:ex_datalog, :planner, :exception], %{duration: System.monotonic_time() - start},
                       Map.merge(metadata, %{kind: :error, reason: e}))
    reraise e, __STACKTRACE__
end

Attach with :telemetry.attach/4 to react to slow planning, or use :telemetry.span/3 wrappers in higher-level tooling that wants a single composite event. The per-call (rather than per-rule) granularity keeps planning telemetry cheap: a thousand-rule program still emits exactly three events on failure.

Where the Planner Sits

The planner is a standalone inspection tool, not a stage in the evaluation pipeline. The runtime path validates and compiles a program to IR, then hands the IR directly to the engine:

Program (DSL or builder)
   │  ExDatalog.materialize/2  (validate → compile → evaluate)
   ▼
IR  (relations, facts, rules, strata, metadata)
   │  Engine.Naive.evaluate/2
   ▼
Knowledge  (materialized relations: MapSet of tuples)
   │  Schema.query/2, find/where
   ▼
result

The planner consumes the same validated IR, but off to the side, when you want to inspect what evaluation will do:

IR  ──►  ExDatalog.Planner.plan/2  ──►  Plan (strategy, strata, joins, predicates)

plan/2 accepts already-validated IR, which is why explain_plan/2's "compilation failed" path goes through ExDatalog.compile/1 (which bundles validation) rather than re-validating inside the planner. The planner is a pure consumer of validated IR.

The Plan is descriptive, not executable. The engine does not consume it — it reads the IR directly. Each Stratum in the plan corresponds to one fixpoint loop in the engine; each Join corresponds to one nested-loop scan; each Predicate corresponds to one filter or binding extension. The plan exists so that tooling (and future optimizers) have a structured, serializable view of the evaluation shape without having to re-derive it from the IR.

Practical Notes

• The plan is cheap to build. A few Enum.flat_map passes over the rules; no allocation per fact.
• Use explain_plan/1 for debugging. It compiles for you and returns a string you can IO.puts without touching data structures.
• Use plan/2 for tooling. It gives you the structs you can serialize, diff, or compare across program versions.
• Attach telemetry once. [:ex_datalog, :planner, :stop] carries the :strategy and the rules/relations counts — enough to build a dashboard without parsing the plan.
• Magic sets is live, but the planner does not drive it. The :strategy recorded in a Plan is informational. The actual goal-directed rewrite happens in ExDatalog.MagicSets when you call materialize/2 with strategy: :magic_sets and a :goal (see the magic-sets article). The planner reports the requested strategy; it does not perform the transformation.

The planner is small on purpose: descriptive structs, honest strategy reporting, and telemetry from day one. It is the seam where a real cost-based optimizer can land later without changing call sites.