Skip to content

Plan builder does O(N²) schema re-inference and extension re-merging across verb chains #207

Closed

Description

@nielspardon

Follow-up cleanup from review of #204 (non-blocking; performance, not correctness).

Building a plan through the fluent substrait.frame / substrait.builders.plan verbs re-does whole-subtree work at every level:

  • Each verb's resolve() calls infer_plan_schema(...) (src/substrait/builders/plan.py:206 and ~15 other sites), and infer_rel_schema recurses over the entire subtree beneath it. Because plans are built as nested resolve() closures, an N-verb chain re-walks ~N²/2 relations.
  • _merge_extensions similarly re-deduplicates the cumulative extension_urns / extensions set at every level (merge_extension_declarations rescans the whole growing list), also O(N²).

This is a plan builder, not a hot data path, so it's not urgent — but it makes large pipelines quadratic.

Suggested direction:

  • Memoize the inferred schema per Rel (or thread the already-computed output NamedStruct upward, since each resolve() already has it) so a parent computes only its incremental schema.
  • Merge only the newly-introduced extension declarations into the child's already-deduped list instead of re-merging the whole cumulative set.

🤖 Filed with AI assistance as a follow-up to #204.

Activity

  1. tokoko commented on Jul 13, 2026

    @tokoko
    Contributor

    yeah... this it the big one. I desperately wanted to avoid introducing another higher-level plan wrapper in builders, which led to these perf issues. If we switch to (or allow) passing around Plan and ExtendedExpression wrappers in builders, they can be used to persist both schema + some sort of an extensions dict to speed up deduplication. Another option is to introduce a stateful context where both of those objects can be memoized: builders user-facing api stays "elegant", but a lot more magic going on under the hood. not sure which option I dislike more 😆

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Metadata

Metadata

Assignees

No one assigned

    Labels

    No labels
    No labels

    Type

    No type

    Projects

    No projects

      Milestone

      No milestone

      Relationships

      None yet

      Development

      No branches or pull requests

      Issue actions