Pipeline components and DAGs in MLOps - Time & Space Complexity

Time Complexity: Pipeline components and DAGs

O(n * d)

Understanding Time Complexity

When working with pipelines and DAGs, it is important to know how the time to run tasks grows as the pipeline gets bigger.

We want to understand how the number of tasks affects the total execution time.

Scenario Under Consideration

Analyze the time complexity of the following pipeline execution code.

for task in dag.tasks:
    if all(dep.is_complete() for dep in task.dependencies):
        task.run()

This code runs each task in a DAG only after its dependencies are complete.

Identify Repeating Operations

Look at what repeats as the pipeline runs.

• Primary operation: Checking dependencies for each task.
• How many times: Once per task, and for each dependency of that task.

How Execution Grows With Input

As the number of tasks grows, the checks increase based on how many dependencies each task has.

Input Size (n tasks)	Approx. Operations
10	About 30 checks if each task has 3 dependencies
100	About 300 checks
1000	About 3000 checks

Pattern observation: The total checks grow roughly in proportion to the number of tasks times their dependencies.

Final Time Complexity

Time Complexity: O(n * d)

This means the time grows with the number of tasks multiplied by the average number of dependencies per task.

Common Mistake

[X] Wrong: "The time to run the pipeline grows only with the number of tasks, ignoring dependencies."

[OK] Correct: Each task must check all its dependencies, so dependencies add to the total work.

Interview Connect

Understanding how pipeline execution time grows helps you design efficient workflows and explain your reasoning clearly in interviews.

Self-Check

"What if tasks could run in parallel without waiting for dependencies? How would the time complexity change?"

Practice

1. What does a Directed Acyclic Graph (DAG) represent in an MLOps pipeline?

easy

A. Tasks and their dependencies without any cycles

B. A loop of tasks that repeat indefinitely

C. Random tasks executed in parallel without order

D. Only the final output of a pipeline

Solution

1. Step 1: Understand DAG structure

   A DAG is a graph with nodes and edges where edges show dependencies and no cycles exist.

2. Step 2: Relate DAG to pipeline tasks

   In MLOps, tasks are nodes and dependencies are edges, ensuring tasks run in order without loops.

3. Final Answer:

   Tasks and their dependencies without any cycles -> Option A

4. Quick Check:

   DAG = tasks + dependencies without loops [OK]

Hint: DAG means no loops, just tasks linked in order [OK]

Common Mistakes:

• Thinking DAG allows loops
• Confusing DAG with random task order
• Assuming DAG only shows final output

2. Which of the following is the correct syntax to define a simple DAG in Apache Airflow?

easy

A. dag = DAG('my_dag', interval='daily')

B. dag = DAG('my_dag' schedule='daily')

C. dag = DAG('my_dag', schedule='everyday')

D. dag = DAG('my_dag', schedule_interval='@daily')

Solution

1. Step 1: Check Airflow DAG syntax

   The DAG constructor requires a name and a schedule_interval parameter for timing.

2. Step 2: Validate options

   dag = DAG('my_dag', schedule_interval='@daily') uses correct parameter 'schedule_interval' with valid value '@daily'. Others use wrong parameter names or values.

3. Final Answer:

   dag = DAG('my_dag', schedule_interval='@daily') -> Option D

4. Quick Check:

   Correct DAG syntax uses schedule_interval [OK]

Hint: Use schedule_interval='@daily' for daily DAGs [OK]

Common Mistakes:

• Using 'schedule' instead of 'schedule_interval'
• Wrong interval value formats
• Missing commas between parameters

3. Given this Airflow DAG snippet, what is the order of task execution?

task1 = DummyOperator(task_id='task1', dag=dag)
task2 = DummyOperator(task_id='task2', dag=dag)
task3 = DummyOperator(task_id='task3', dag=dag)
task1 >> task2 >> task3

medium

A. task3, then task2, then task1

B. task1, then task2, then task3

C. task2, then task1, then task3

D. All tasks run in parallel

Solution

1. Step 1: Analyze task dependencies

   The '>>' operator sets order: task1 before task2, task2 before task3.

2. Step 2: Determine execution sequence

   Tasks run in sequence: task1 first, then task2, then task3.

3. Final Answer:

   task1, then task2, then task3 -> Option B

4. Quick Check:

   task1 >> task2 >> task3 means sequential order [OK]

Hint: >> means run left task before right task [OK]

Common Mistakes:

• Assuming tasks run in reverse order
• Thinking tasks run in parallel
• Ignoring the '>>' operator meaning

4. You wrote this DAG code but get an error: TypeError: 'DAG' object is not iterable. What is the likely cause?

with DAG('example_dag', schedule_interval='@daily') as dag:
    task1 = DummyOperator(task_id='task1')
    task2 = DummyOperator(task_id='task2')
    task1 >> task2

for task in dag:
    print(task.task_id)

medium

A. DAG object is not iterable, so 'for task in dag' causes error

B. DummyOperator requires a 'dag' parameter outside the context

C. Missing import for DummyOperator

D. schedule_interval '@daily' is invalid

Solution

1. Step 1: Identify error cause

   The error says 'DAG' object is not iterable, likely from trying to loop over dag object.

2. Step 2: Understand DAG iterability

   DAG objects in Airflow are not iterable directly; looping over them causes this error.

3. Final Answer:

   DAG object is not iterable, so 'for task in dag' causes error -> Option A

4. Quick Check:

   DAG is not iterable; use dag.tasks list instead [OK]

Hint: DAG is not iterable; use dag.tasks to loop [OK]

Common Mistakes:

• Trying to loop directly over DAG object
• Assuming DummyOperator needs dag param outside context
• Misreading error as import issue

5. You want to create a pipeline where task A runs first, then tasks B and C run in parallel, and finally task D runs after both B and C finish. Which DAG structure correctly represents this?

hard

A. [A, B] >> C >> D

B. A >> B >> C >> D

C. A >> [B, C] >> D

D. A >> D >> [B, C]

Solution

1. Step 1: Understand task order requirements

   Task A runs first, then B and C run at the same time, then D runs after both finish.

2. Step 2: Translate to DAG syntax

   Using Airflow syntax, 'A >> [B, C] >> D' means A before B and C in parallel, then D after both.

3. Final Answer:

   A >> [B, C] >> D -> Option C

4. Quick Check:

   Parallel tasks in list brackets between sequential tasks [OK]

Hint: Use brackets [] for parallel tasks in DAG [OK]

Common Mistakes:

• Placing tasks in wrong order
• Not using brackets for parallel tasks
• Assuming linear order for all tasks