Data Engineering: Topological Sort

Data Engineering Workflows

• Data engineering workflows manage and automate data processes.
• Example workflow: Node A performs data wrangling, Node B and C engineer features, Node D merges these features and Node E trains a model.

Ordering Dependencies

• A fundamental problem involves ordering tasks based on their prerequisites.
• This problem can be visualized as a directed graph, where courses are prerequisites for others.

Topological Sort

• Topological sort (aka topological ordering) is defined for a directed graph G.
• Given a directed graph G, with an edge from u to v if u must happen before v, it finds an order of vertices so all edges go from left to right, respecting dependencies.
• Topological sorts have a range of uses including compiling multiple files, graduating, and manufacturing workflows (assembly lines).

Directed Acyclic Graph (DAG)

• DAGs are directed graphs without cycles.
• A graph has a topological ordering if and only if it is a DAG.

Ordering a DAG

• If a vertex doesn't have incoming edges, it can be added to the ordering.
• Generally, if the only incoming edges are from vertices already in the ordering, it is safe to add.

Topological Ordering Algorithm

• The algorithm for topological sorting processes vertices based on incoming edges.
• It counts incoming edges for each vertex.
• Vertices with no incoming edges are added to a toProcess collection.
• While the toProcess collection is not empty, vertices are removed and added to a topOrder list.
• For each edge leaving the processed vertex (u, v), the incoming edge count of the destination vertex (v) decreases.
• Vertices whose incoming edge count becomes zero are added to the toProcess collection.

Connected Graphs

• A connected graph connects every vertex to every other vertex via some path, even without a direct edge between all vertices.
• A connected component is a subgraph where any two vertices are connected via some path and not connected to any additional vertices in the supergraph.
• A vertex with no edges forms a connected component on its own.

Strongly Connected Component

• Strongly Connected Component: A subgraph C such that every pair of vertices in C is connected via some path in both directions, and there is no other vertex which is connected to every vertex of C in both directions.

Strongly Connected Components (SCC) Problem

• The problem involves finding the strongly connected components in a directed graph G.
• Example: For a graph with nodes A, B, C, D, E, F, J, and K, the strongly connected components are {A}, {B}, {C, D, E, F}, {J, K}.

SCC Algorithm

• A basic approach to finding SCC involves running a Breadth-First Search (BFS) or Depth-First Search (DFS) from every vertex and recording reachable vertices.
• A more efficient algorithm exists with O(|V|+|E|) time complexity, leveraging depth-first search.
• The "smart" ordering from Depth First Search avoids recomputation of information.

Finding SCCs

• Finding SCCs allow you to collapse a graph to a meta-structure.
• A new graph (H) can be built from strongly connected components by creating a vertex for each component, and adding an edge from component 1 to component 2 if there's an edge from a vertex inside 1 to one inside 2.
• I can get from A (of G) in 1 to F (of G) in 3 if and only if I can get from 1 to 3 in H.

DAG

• The graph H is always a DAG.

Applications of DAGs in Data Engineering

• Finding SCCs lets you collapse your graph to the meta-structure and find a topological sort of your graph if (and only if) your graph is a DAG.
• Both these algorithms, SCC identification and topological sorting, run in linear time.
• You should think of these as “almost free” preprocessing of your graph.
• Your other graph algorithms only need to work on topologically sorted graphs and strongly connected graphs.

Efficient SCC

• To find all vertices in a strongly connected component efficiently, aim for time corresponding to the component size, not the whole graph.
• A DFS (or BFS) can work, but is constrained stay within the connected component.
• Run DFS in the reversed graph (where each edge points the opposite direction) to find a sink component.

ETL Pipelines in Data Engineering

• ETL (Extract, Transform, Load) processes are orchestrated using DAGs to manage data flow.
• Multiple Data Sources: Data can be extracted from various sources.
• Various formats: Data is transformed from a suitable format, and loading it into a target system.
• ETL tools: Apache Airflow and Luigi orchestrate ETL pipelines via DAGs.

DAG Applications

• Dag Applications integrate data from a CRM system, transforming it to align with your business needs, and loading it into a Snowflake data warehouse for analytics.
• DAG Applications help to monitor and log task runtimes in your ETL processes.
• This help identifying bottlenecks or tasks that require optimization.

Complex Workflow Orchestration

• DAGs manage complex data workflows that involve multiple tasks and dependencies.
• Uses include Feature engineering, model training, and model deployment.
• DAG in Apache Airflow may execute feature selection scripts and trigger model training only after the features are processed, ensuring dependency management and reproducibility.

Data Processing Pipelines

• DAGs manage data flow from multiple sources and transform it into valuable insights.
• An Apache Spark DAG processes website clickstream data, calculates session durations, and feeds insights into a dashboard.
• Framework Optimization: DAGs in Spark are created internally to optimize transformations.

Machine Learning Pipeline

• DAGs provide iterative and modular workflows
• DAGs enable experimentation with different preprocessing steps, algorithms, and hyperparameters.
• KubeFlow and MLflow: Tools like these manage machine learning workflows using DAGs.
• DAGs enable retraining pipelines triggered by data drift detection so models are accurate.

Data Engineering Tools

• Apache Airflow
• Kubeflow
• MLFlow
• Luigi
• Dagster