[jira] [Created] (BEAM-11355) pipeline_from_stages after sort_stages can return non-topologically ordered pipelines

["Yifan Mai (Jira)" <ji...@apache.org>]

Yifan Mai created BEAM-11355:
--------------------------------

             Summary: pipeline_from_stages after sort_stages can return non-topologically ordered pipelines
                 Key: BEAM-11355
                 URL: https://issues.apache.org/jira/browse/BEAM-11355
             Project: Beam
          Issue Type: Bug
          Components: sdk-py-core
            Reporter: Yifan Mai
            Assignee: Yifan Mai


translations.sort_stages() sorts stages in topological order. However, calling translations.pipeline_from_stages() on sorted stages can result in a pipeline that is not topologically ordered. This is because of how it constructs the tree of parent to subtransforms.

Example pipeline:
 * Leaf transforms are A, B and C.
 * Composite transform D has subtransforms B and C.
 * Root transform E has subtransforms A and D.
 * A produces an output that is an input to C, and B produces an output that is an input to C.
 * After optimizations and sort stages, the order of leaf stages is B, A, C (this is a valid ordering)

Under the current implementation of translations.pipeline_from_stages():
 # B is added to the pipeline first, which also adds its parent D and its grandparent E to the pipeline. D is added as the first subtransform of E and B is added as the first subtransform of D.
 # A is added to the pipeline second. A is added as the second subtransform of E.
 # C is added to the pipeline third. C is added as the second subtransform of D.

The order is now E(D(B, C), A) which is invalid because C must follow A. A valid order would be E(A, D(B, C)).

The easiest fix is to change translations.pipeline_from_stages() such that whenever a leaf transform is added to the pipeline, all its ancestors are moved to the last position of the subtransforms of their respective parent.



--
This message was sent by Atlassian Jira
(v8.3.4#803005)