Skip to content

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

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

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