srdatalog.ir.hir.plan

HIR Pass 4: Join Planning.

For each variant, compute:

• clause_order: execution order of body clauses (heuristic: deps → delta priority → max-overlap with bound vars)

• var_order: variable binding order (join vars first, starting from the delta clause for recursive rules; then remaining join vars in clause order; then non-join vars in clause order)

• access_patterns: per-positive-clause AccessPattern (rel, version, access_order, prefix_len, index_cols, clause_idx)

• negation_patterns: per-negation-clause AccessPattern (version forced to FULL)

Mirrors src/srdatalog/hir/join_planner.nim. Not yet ported: user-provided rule.plans (DSL doesn’t support them), split clauses (SplitClause), balanced partitioning pragmas, IfClause/LetClause/AggClause handling.

Module Contents

Classes

JoinPlannerPass
RuleAnalysis

Functions

analyze_rule
compute_access_pattern	Build the AccessPattern for one body clause (Atom or Negation).
compute_clause_order	Pick body clause execution order using the Nim heuristic:
compute_temp_vars	Variables that cross a rule’s split boundary: bound above the split AND used below (body clauses or head). Mirrors Nim’s computeTempVars.
compute_var_order_from_clauses	Derive variable binding order from clause execution order.
derive_clause_order_from_var_order	Mirror deriveClauseOrderFromVarOrder in join_planner.nim.
detect_split	Body index of the Split clause, or -1 if absent.
plan_joins	HIR Pass 4 entry. Mutates and returns the HirProgram.

API

class srdatalog.ir.hir.plan.JoinPlannerPass

info

‘PassInfo(…)’

run(hir: srdatalog.ir.hir.types.HirProgram) → srdatalog.ir.hir.types.HirProgram

class srdatalog.ir.hir.plan.RuleAnalysis

clause_vars: list[set[str]]

‘field(…)’

head_vars: set[str]

‘field(…)’

join_vars: set[str]

‘field(…)’

vars: set[str]

‘field(…)’

srdatalog.ir.hir.plan.analyze_rule(rule: srdatalog.dsl.Rule) → srdatalog.ir.hir.plan.RuleAnalysis

srdatalog.ir.hir.plan.compute_access_pattern(body, version: srdatalog.ir.hir.types.Version, join_vars: set[str], var_order: list[str], clause_idx: int) → srdatalog.ir.hir.types.AccessPattern

Build the AccessPattern for one body clause (Atom or Negation).

• access_order = var_order filtered to clause vars, plus any remaining clause vars appended in a deterministic (sorted) order.

• prefix_len: Atoms → count of join vars; Negations → count of non-wildcard vars.

• index_cols: maps access_order to column positions; then completes to full arity.

• For Negations: prepend constant-column indices and force version=FULL (caller).

srdatalog.ir.hir.plan.compute_clause_order(rule: srdatalog.dsl.Rule, delta_idx: int = -1) → list[int]

Pick body clause execution order using the Nim heuristic:

1. Dependency-gated runnable set (sorted by source idx for tie-breaking).

2. Delta clause first when runnable (for recursive variants).

3. Max overlap of clause vars with currently-bound vars.

srdatalog.ir.hir.plan.compute_temp_vars(rule: srdatalog.dsl.Rule, split_at: int) → list[str]

Variables that cross a rule’s split boundary: bound above the split AND used below (body clauses or head). Mirrors Nim’s computeTempVars.

Order: first the vars shared with below-split body clauses (join vars for Pipeline B), then head-only vars. Within each group, vars are walked in clause-walk insertion order (first occurrence in clauses 0..split_at-1, position-by-position).

Why insertion order: Nim uses HashSet[string] iteration which is hash-bucket order (hash & (cap-1), ascending slot, with linear probe on collision). For variable names that fit our codebase’s typical mnemonic style (e.g., blk, blockUsed, varr, varp), the FarmHash slots happen to come out in roughly insertion order. Insertion order is byte-equivalent to Nim’s hash-bucket order on every fixture in the test set, more deterministic across Python / Nim runs, and avoids needing to bit-port Nim’s hashFarm for strings. F1 fix; see ddisasm StackLiveVarBlockEnd1_D0_split{A,B}.

srdatalog.ir.hir.plan.compute_var_order_from_clauses(rule: srdatalog.dsl.Rule, clause_order: list[int], join_vars: set[str], delta_idx: int = -1) → list[str]

Derive variable binding order from clause execution order.

Pass 1 (recursive variants only): join vars appearing in the delta clause. Pass 2: remaining join vars, in clauseOrder. Pass 3: non-join vars, in clauseOrder.

srdatalog.ir.hir.plan.derive_clause_order_from_var_order(rule: srdatalog.dsl.Rule, var_order: list[str], delta_idx: int = -1) → list[int]

Mirror deriveClauseOrderFromVarOrder in join_planner.nim.

Walks var_order left to right; for each not-yet-bound variable, picks a runnable clause that introduces it (preferring the delta clause when applicable; source-order ties otherwise). Any unscheduled clauses (filters, disconnected negations) are appended at the end in a runnable sweep.

srdatalog.ir.hir.plan.detect_split(rule: srdatalog.dsl.Rule) → int

Body index of the Split clause, or -1 if absent.

srdatalog.ir.hir.plan.plan_joins(hir: srdatalog.ir.hir.types.HirProgram) → srdatalog.ir.hir.types.HirProgram

HIR Pass 4 entry. Mutates and returns the HirProgram.