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)
