Skip to content

Evaluate OPTIONAL MATCH last, as a post-join pass after all required MATCHes #65

Description

@matiastoro

Motivation

Reorder query evaluation so all required MATCHes join first (maximally constraining the binding set), then apply OPTIONAL MATCH clauses last as left-outer extensions. Evaluating optionals against the smallest possible intermediate reduces work.

Current state (feasibility)

  • run_match_chain (src/runtime/engine.rs) threads the environment through the clause chain in source order. Each OPTIONAL MATCH is handled where it appears via either optional_via_bind_pushdown (correlated nested-loop, pinning shared Node vars) or left_outer_join per clause.
  • The typechecker models the left-join with outer_join (TLEFTJOIN, src/typing/type_environment.rs).
  • Query::has_any_optional() already distinguishes optional clauses.

Proposal

Split the chain into (required[], optional[]); evaluate the required join fully, then fold each optional as a final left-outer extension over the result.

Feasibility

Doable and mostly a scheduling change. Constraints to preserve:

  • ISO semantics: an optional that matches nothing must still yield the left row with nulls for its variables.
  • Correlation: an optional referencing a required variable still resolves it (already the case with bind-pushdown).
  • Variable scoping across the reorder must be unchanged.

Moderate effort. Should be measured against the current in-order pushdown (which already wins on IS5/IC4/IC10-style shapes) to confirm the reorder does not regress correlated cases.

Metadata

Metadata

Assignees

No one assigned

    Labels

    performanceSpeed / memory optimization

    Type

    No type

    Fields

    No fields configured for issues without a type.

    Projects

    No projects

    Milestone

    No milestone

    Relationships

    None yet

    Development

    No branches or pull requests

    Issue actions