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.

Metadata

Metadata

Assignees

No one assigned

    Labels

    No labels
    No labels

    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