Skip to content

perf(post-1.0): hash-join disjunction inner loop #203

Closed

Description

@adityamukho

Roadmap source

ROADMAP.md: Post-1.0 Performance Backlog.

Problem

apply_or_clauses evaluates each branch against the full incoming binding set, causing O(seeds * facts) behavior. Roadmap benchmark observations: or_scale/10k around 74s and or_join_scale/10k around 73s.

Proposed fix

Evaluate each branch from an empty seed, then intersect/project results back onto incoming bindings with a hash lookup.

Acceptance criteria

  • Reduce disjunction inner-loop behavior from O(N^2) to O(N) per branch for the benchmarked shape.
  • Add or update benchmarks for or_scale and or_join_scale.
  • Preserve or / or-join semantics, including projection behavior.

Metadata

Metadata

Assignees

No one assigned

    Labels

    performanceBenchmark performance regressionsrustPull requests that update rust code

    Type

    No type

    Projects

    No projects

      Milestone

      No milestone

      Relationships

      None yet

      Development

      No branches or pull requests

      Issue actions