Principle:Apache Beam Pipeline Graph Construction

Field	Value
Principle Name	Pipeline Graph Construction
Overview	Process of traversing a pipeline's transform hierarchy to build an immutable execution graph that captures producer-consumer relationships.
Domains	Pipeline_Orchestration, Graph_Theory
Related Implementation	Implementation:Apache_Beam_DirectGraphVisitor
last_updated	2026-02-09 04:00 GMT

Description

After transform overrides are applied, the pipeline must be converted into an execution graph -- an immutable data structure that the runner uses for scheduling, watermark propagation, and execution ordering. This process involves a topological traversal of the pipeline's TransformHierarchy to extract the primitive transforms and their data dependencies.

The graph construction process performs the following steps:

1. Topological traversal -- The pipeline is visited using the PipelineVisitor pattern. The visitor enters composite transforms, visits primitive transforms, and visits PValues (PCollections) associated with each transform.
2. Primitive transform recording -- Each primitive (non-composite) transform is recorded in the graph. Composite transforms are entered but not directly recorded; only their leaf-level primitive expansions are captured.
3. Producer-consumer mapping -- For each PCollection, the graph records which transform produces it (the producer) and which transforms consume it (the consumers). This establishes the directed edges of the graph.
4. Root transform identification -- Transforms with no input PCollections (such as Read or Create) are classified as root transforms. These are the starting points for execution.
5. Step name assignment -- Each primitive transform is assigned a unique step name (e.g., s0, s1, s2) for internal identification during execution and logging.
6. Immutable graph creation -- Once traversal is complete and the root node is left, the visitor finalizes itself and produces an immutable graph object that cannot be further modified.

The resulting execution graph provides the runner with several critical lookup operations:

• getRootTransforms() -- Returns the set of transforms that serve as execution starting points.
• getProducer(PValue) -- Returns the transform that produces a given PCollection.
• getPerElementConsumers(PValue) -- Returns the transforms that consume a given PCollection as per-element input (excluding side inputs).
• getStepName(AppliedPTransform) -- Returns the assigned step name for a transform.
• getProduced(AppliedPTransform) -- Returns the PValues produced by a transform.

The graph also tracks additional relationships needed for Direct Runner execution:

• Side input views -- Maps PCollectionView objects to the WriteView transforms that materialize them.
• Consumed views -- Tracks which views are consumed by ParDo.MultiOutput transforms, enabling validation that all consumed views have corresponding writers.

Usage

Pipeline graph construction is required by any runner that needs to reason about data dependencies between transforms. Specific use cases include:

• Execution scheduling -- The graph determines which transforms can execute in parallel (no data dependency) and which must wait for upstream results.
• Watermark propagation -- The producer-consumer relationships define the paths along which watermark information flows from sources to sinks.
• Quiescence detection -- Root transforms define the initial work, and the graph structure determines when all downstream work has completed.
• Pipeline visualization -- The graph can be rendered as a visual DAG for debugging and monitoring purposes.

The Direct Runner invokes graph construction immediately after performing transform overrides and before setting up the execution context.

Theoretical Basis

Pipeline graph construction is based on Directed Acyclic Graph (DAG) theory applied to dataflow systems. The key theoretical foundations include:

• DAG structure -- The graph is acyclic because Beam disallows cycles in the pipeline (a PCollection cannot be both an input and output of the same transform chain). This guarantees that topological ordering exists and execution can proceed without deadlocks.
• Producer-consumer relationships -- Each edge in the graph represents a PCollection flowing from a producer transform to one or more consumer transforms. This is the fundamental abstraction of the dataflow model, where data flows along edges and is transformed at nodes.
• Topological sort -- The traversal order respects the DAG's topological order, ensuring that producers are visited before consumers. This property is essential for correct watermark initialization and execution scheduling.
• Immutability after construction -- The graph is made immutable after traversal to prevent race conditions during concurrent execution. This follows the publish-then-use pattern common in concurrent systems.

The Dataflow Model (Akidau et al., VLDB 2015) defines the logical graph structure; pipeline graph construction is the process of extracting the runner-internal physical graph representation from the user-facing logical graph.

Related Pages

• Implementation:Apache_Beam_DirectGraphVisitor -- Concrete implementation that builds a DirectGraph from pipeline traversal.

Sources

• Paper -- The Dataflow Model -- Akidau et al., VLDB 2015.