Uploaded image for project: 'Beam'
  1. Beam
  2. BEAM-11355

pipeline_from_stages after sort_stages can return non-topologically ordered pipelines

    XMLWordPrintableJSON

    Details

    • Type: Bug
    • Status: Resolved
    • Priority: P2
    • Resolution: Fixed
    • Affects Version/s: None
    • Fix Version/s: None
    • Component/s: sdk-py-core
    • Labels:
      None

      Description

      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():

      1. 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.
      2. A is added to the pipeline second. A is added as the second subtransform of E.
      3. 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.

        Attachments

          Issue Links

            Activity

              People

              • Assignee:
                myffical@gmail.com Yifan Mai
                Reporter:
                myffical@gmail.com Yifan Mai
              • Votes:
                0 Vote for this issue
                Watchers:
                1 Start watching this issue

                Dates

                • Created:
                  Updated:
                  Resolved:

                  Time Tracking

                  Estimated:
                  Original Estimate - Not Specified
                  Not Specified
                  Remaining:
                  Remaining Estimate - 0h
                  0h
                  Logged:
                  Time Spent - 1h
                  1h