You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@airflow.apache.org by GitBox <gi...@apache.org> on 2022/10/28 19:43:49 UTC

[GitHub] [airflow] bbovenzi opened a new pull request, #27356: Separate dataset deps into individual graphs

bbovenzi opened a new pull request, #27356:
URL: https://github.com/apache/airflow/pull/27356

   Calculate the individual dataset "pipelines" and when a dataset is selected only show its pipeline.
   
   <img width="1586" alt="Screen Shot 2022-10-28 at 1 42 39 PM" src="https://user-images.githubusercontent.com/4600967/198719288-20facee9-96a0-4f90-9ad4-1515a6cd6b80.png">
   
   ---
   **^ Add meaningful description above**
   
   Read the **[Pull Request Guidelines](https://github.com/apache/airflow/blob/main/CONTRIBUTING.rst#pull-request-guidelines)** for more information.
   In case of fundamental code changes, an Airflow Improvement Proposal ([AIP](https://cwiki.apache.org/confluence/display/AIRFLOW/Airflow+Improvement+Proposals)) is needed.
   In case of a new dependency, check compliance with the [ASF 3rd Party License Policy](https://www.apache.org/legal/resolved.html#category-x).
   In case of backwards incompatible changes please leave a note in a newsfragment file, named `{pr_number}.significant.rst` or `{issue_number}.significant.rst`, in [newsfragments](https://github.com/apache/airflow/tree/main/newsfragments).
   


-- 
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

To unsubscribe, e-mail: commits-unsubscribe@airflow.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


[GitHub] [airflow] bbovenzi merged pull request #27356: Separate dataset deps into individual graphs

Posted by GitBox <gi...@apache.org>.
bbovenzi merged PR #27356:
URL: https://github.com/apache/airflow/pull/27356


-- 
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

To unsubscribe, e-mail: commits-unsubscribe@airflow.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


[GitHub] [airflow] bbovenzi commented on pull request #27356: Separate dataset deps into individual graphs

Posted by GitBox <gi...@apache.org>.
bbovenzi commented on PR #27356:
URL: https://github.com/apache/airflow/pull/27356#issuecomment-1307508262

   > Really cool feature. Tested locally and looking good!
   > 
   > The computation to find disconnected subgraphs seems pretty expensive, on the bright side it is only run once.
   > 
   > Even if this seems to be the correct approach, still doing a quick research to see if there is something more efficient out there. (for sanity).
   
   Yeah, I'm not a big fan of all the calculation for the subgraphs. Eventually this should be done on the webserver instead.


-- 
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

To unsubscribe, e-mail: commits-unsubscribe@airflow.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


[GitHub] [airflow] pierrejeambrun commented on a diff in pull request #27356: Separate dataset deps into individual graphs

Posted by GitBox <gi...@apache.org>.
pierrejeambrun commented on code in PR #27356:
URL: https://github.com/apache/airflow/pull/27356#discussion_r1014633359


##########
airflow/www/static/js/api/useDatasetDependencies.ts:
##########
@@ -75,15 +82,130 @@ const generateGraph = ({ nodes, edges, font }: GenerateProps) => ({
   edges: edges.map((e) => ({ id: `${e.source}-${e.target}`, sources: [e.source], targets: [e.target] })),
 });
 
+interface SeparateGraphsProps extends DatasetDependencies {
+  graphs: DatasetDependencies[];
+}
+
+const graphIndicesToMerge: Record<number, number[]> = {};
+const indicesToRemove: number[] = [];
+
+// find the downstream graph of each upstream edge
+const findDownstreamGraph = (
+  { edges, nodes, graphs = [] }: SeparateGraphsProps,
+): DatasetDependencies[] => {
+  const newGraphs = [...graphs];
+  let filteredEdges = [...edges];
+
+  graphs.forEach((g, i) => {
+    // find downstream edges
+    const downstreamEdges = edges.filter((e) => g.edges.some((ge) => ge.target === e.source));
+    const downstreamNodes: DepNode[] = [];
+
+    downstreamEdges.forEach((e) => {
+      const newNode = nodes.find((n) => n.id === e.target);
+      if (newNode) {
+        downstreamNodes.push(newNode);
+
+        // check if the node already exists in a different graph
+        const existingGraphIndex = newGraphs
+          .findIndex(((ng) => ng.nodes.some((n) => n.id === newNode.id)));
+
+        // mark if the graph needs to merge with another
+        if (existingGraphIndex > -1) {
+          indicesToRemove.push(existingGraphIndex);
+          graphIndicesToMerge[i] = [...(graphIndicesToMerge[i] || []), existingGraphIndex];
+        }
+
+        // add node and edge to the graph
+        newGraphs[i] = {
+          nodes: [...newGraphs[i].nodes, newNode],
+          edges: [...newGraphs[i].edges, e],
+        };
+
+        // remove edge from edge list
+        filteredEdges = filteredEdges
+          .filter((fe) => !(fe.source === e.source && fe.target === e.target));
+      }
+    });
+  });
+
+  // once there are no more filtered edges left, merge relevant graphs
+  // we merge afterwards to make sure we captured all nodes + edges
+  if (!filteredEdges.length) {
+    Object.keys(graphIndicesToMerge).forEach((key) => {
+      const realKey = key as unknown as number;
+      const values = graphIndicesToMerge[realKey];
+      values.forEach((v) => {
+        newGraphs[realKey] = {
+          nodes: unionBy(newGraphs[realKey].nodes, newGraphs[v].nodes, 'id'),
+          edges: [...newGraphs[realKey].edges, ...newGraphs[v].edges]
+            .filter((e, i, s) => (
+              i === s.findIndex((t) => t.source === e.source && t.target === e.target)
+            )),
+        };
+      });
+    });
+    return newGraphs.filter((g, i) => !indicesToRemove.some((j) => i === j));
+  }
+
+  return findDownstreamGraph({ edges: filteredEdges, nodes, graphs: newGraphs });
+};
+
+// separate the list of nodes/edges into distinct dataset pipeline graphs
+const separateGraphs = ({ edges, nodes }: DatasetDependencies): DatasetDependencies[] => {
+  const separatedGraphs: DatasetDependencies[] = [];
+  let remainingEdges = [...edges];
+  let remainingNodes = [...nodes];
+
+  edges.forEach((edge) => {
+    const isDownstream = edges.some((e) => e.target === edge.source);
+
+    // if the edge is not downstream of anything, then start building the graph
+    if (!isDownstream) {
+      const connectedNodes = nodes.filter((n) => n.id === edge.source || n.id === edge.target);
+
+      // check if the node is already connected to a separated graph
+      const nodesInUse = separatedGraphs
+        .findIndex((g) => g.nodes.some((n) => connectedNodes.some((nn) => nn.id === n.id)));
+
+      if (nodesInUse > -1) {
+        // if the node is in use, merge the graphs

Review Comment:
   ```suggestion
           // if one of the connected nodes is already in use, merge the graphs
   ```



-- 
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

To unsubscribe, e-mail: commits-unsubscribe@airflow.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


[GitHub] [airflow] pierrejeambrun commented on a diff in pull request #27356: Separate dataset deps into individual graphs

Posted by GitBox <gi...@apache.org>.
pierrejeambrun commented on code in PR #27356:
URL: https://github.com/apache/airflow/pull/27356#discussion_r1014633359


##########
airflow/www/static/js/api/useDatasetDependencies.ts:
##########
@@ -75,15 +82,130 @@ const generateGraph = ({ nodes, edges, font }: GenerateProps) => ({
   edges: edges.map((e) => ({ id: `${e.source}-${e.target}`, sources: [e.source], targets: [e.target] })),
 });
 
+interface SeparateGraphsProps extends DatasetDependencies {
+  graphs: DatasetDependencies[];
+}
+
+const graphIndicesToMerge: Record<number, number[]> = {};
+const indicesToRemove: number[] = [];
+
+// find the downstream graph of each upstream edge
+const findDownstreamGraph = (
+  { edges, nodes, graphs = [] }: SeparateGraphsProps,
+): DatasetDependencies[] => {
+  const newGraphs = [...graphs];
+  let filteredEdges = [...edges];
+
+  graphs.forEach((g, i) => {
+    // find downstream edges
+    const downstreamEdges = edges.filter((e) => g.edges.some((ge) => ge.target === e.source));
+    const downstreamNodes: DepNode[] = [];
+
+    downstreamEdges.forEach((e) => {
+      const newNode = nodes.find((n) => n.id === e.target);
+      if (newNode) {
+        downstreamNodes.push(newNode);
+
+        // check if the node already exists in a different graph
+        const existingGraphIndex = newGraphs
+          .findIndex(((ng) => ng.nodes.some((n) => n.id === newNode.id)));
+
+        // mark if the graph needs to merge with another
+        if (existingGraphIndex > -1) {
+          indicesToRemove.push(existingGraphIndex);
+          graphIndicesToMerge[i] = [...(graphIndicesToMerge[i] || []), existingGraphIndex];
+        }
+
+        // add node and edge to the graph
+        newGraphs[i] = {
+          nodes: [...newGraphs[i].nodes, newNode],
+          edges: [...newGraphs[i].edges, e],
+        };
+
+        // remove edge from edge list
+        filteredEdges = filteredEdges
+          .filter((fe) => !(fe.source === e.source && fe.target === e.target));
+      }
+    });
+  });
+
+  // once there are no more filtered edges left, merge relevant graphs
+  // we merge afterwards to make sure we captured all nodes + edges
+  if (!filteredEdges.length) {
+    Object.keys(graphIndicesToMerge).forEach((key) => {
+      const realKey = key as unknown as number;
+      const values = graphIndicesToMerge[realKey];
+      values.forEach((v) => {
+        newGraphs[realKey] = {
+          nodes: unionBy(newGraphs[realKey].nodes, newGraphs[v].nodes, 'id'),
+          edges: [...newGraphs[realKey].edges, ...newGraphs[v].edges]
+            .filter((e, i, s) => (
+              i === s.findIndex((t) => t.source === e.source && t.target === e.target)
+            )),
+        };
+      });
+    });
+    return newGraphs.filter((g, i) => !indicesToRemove.some((j) => i === j));
+  }
+
+  return findDownstreamGraph({ edges: filteredEdges, nodes, graphs: newGraphs });
+};
+
+// separate the list of nodes/edges into distinct dataset pipeline graphs
+const separateGraphs = ({ edges, nodes }: DatasetDependencies): DatasetDependencies[] => {
+  const separatedGraphs: DatasetDependencies[] = [];
+  let remainingEdges = [...edges];
+  let remainingNodes = [...nodes];
+
+  edges.forEach((edge) => {
+    const isDownstream = edges.some((e) => e.target === edge.source);
+
+    // if the edge is not downstream of anything, then start building the graph
+    if (!isDownstream) {
+      const connectedNodes = nodes.filter((n) => n.id === edge.source || n.id === edge.target);
+
+      // check if the node is already connected to a separated graph
+      const nodesInUse = separatedGraphs
+        .findIndex((g) => g.nodes.some((n) => connectedNodes.some((nn) => nn.id === n.id)));
+
+      if (nodesInUse > -1) {
+        // if the node is in use, merge the graphs

Review Comment:
   ```suggestion
           // if one of the nodes is already in use, merge the graphs
   ```



-- 
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

To unsubscribe, e-mail: commits-unsubscribe@airflow.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


[GitHub] [airflow] pierrejeambrun commented on a diff in pull request #27356: Separate dataset deps into individual graphs

Posted by GitBox <gi...@apache.org>.
pierrejeambrun commented on code in PR #27356:
URL: https://github.com/apache/airflow/pull/27356#discussion_r1014633257


##########
airflow/www/static/js/api/useDatasetDependencies.ts:
##########
@@ -75,15 +82,130 @@ const generateGraph = ({ nodes, edges, font }: GenerateProps) => ({
   edges: edges.map((e) => ({ id: `${e.source}-${e.target}`, sources: [e.source], targets: [e.target] })),
 });
 
+interface SeparateGraphsProps extends DatasetDependencies {
+  graphs: DatasetDependencies[];
+}
+
+const graphIndicesToMerge: Record<number, number[]> = {};
+const indicesToRemove: number[] = [];
+
+// find the downstream graph of each upstream edge
+const findDownstreamGraph = (
+  { edges, nodes, graphs = [] }: SeparateGraphsProps,
+): DatasetDependencies[] => {
+  const newGraphs = [...graphs];
+  let filteredEdges = [...edges];
+
+  graphs.forEach((g, i) => {
+    // find downstream edges
+    const downstreamEdges = edges.filter((e) => g.edges.some((ge) => ge.target === e.source));
+    const downstreamNodes: DepNode[] = [];
+
+    downstreamEdges.forEach((e) => {
+      const newNode = nodes.find((n) => n.id === e.target);
+      if (newNode) {
+        downstreamNodes.push(newNode);
+
+        // check if the node already exists in a different graph
+        const existingGraphIndex = newGraphs
+          .findIndex(((ng) => ng.nodes.some((n) => n.id === newNode.id)));
+
+        // mark if the graph needs to merge with another
+        if (existingGraphIndex > -1) {
+          indicesToRemove.push(existingGraphIndex);
+          graphIndicesToMerge[i] = [...(graphIndicesToMerge[i] || []), existingGraphIndex];
+        }
+
+        // add node and edge to the graph
+        newGraphs[i] = {
+          nodes: [...newGraphs[i].nodes, newNode],
+          edges: [...newGraphs[i].edges, e],
+        };
+
+        // remove edge from edge list
+        filteredEdges = filteredEdges
+          .filter((fe) => !(fe.source === e.source && fe.target === e.target));
+      }
+    });
+  });
+
+  // once there are no more filtered edges left, merge relevant graphs
+  // we merge afterwards to make sure we captured all nodes + edges
+  if (!filteredEdges.length) {
+    Object.keys(graphIndicesToMerge).forEach((key) => {
+      const realKey = key as unknown as number;
+      const values = graphIndicesToMerge[realKey];
+      values.forEach((v) => {
+        newGraphs[realKey] = {
+          nodes: unionBy(newGraphs[realKey].nodes, newGraphs[v].nodes, 'id'),
+          edges: [...newGraphs[realKey].edges, ...newGraphs[v].edges]
+            .filter((e, i, s) => (
+              i === s.findIndex((t) => t.source === e.source && t.target === e.target)
+            )),
+        };
+      });
+    });
+    return newGraphs.filter((g, i) => !indicesToRemove.some((j) => i === j));
+  }
+
+  return findDownstreamGraph({ edges: filteredEdges, nodes, graphs: newGraphs });
+};
+
+// separate the list of nodes/edges into distinct dataset pipeline graphs
+const separateGraphs = ({ edges, nodes }: DatasetDependencies): DatasetDependencies[] => {
+  const separatedGraphs: DatasetDependencies[] = [];
+  let remainingEdges = [...edges];
+  let remainingNodes = [...nodes];
+
+  edges.forEach((edge) => {
+    const isDownstream = edges.some((e) => e.target === edge.source);
+
+    // if the edge is not downstream of anything, then start building the graph
+    if (!isDownstream) {
+      const connectedNodes = nodes.filter((n) => n.id === edge.source || n.id === edge.target);
+
+      // check if the node is already connected to a separated graph

Review Comment:
   ```suggestion
         // check if one of the nodes is already connected to a separated graph
   ```



-- 
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

To unsubscribe, e-mail: commits-unsubscribe@airflow.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


[GitHub] [airflow] pierrejeambrun commented on a diff in pull request #27356: Separate dataset deps into individual graphs

Posted by GitBox <gi...@apache.org>.
pierrejeambrun commented on code in PR #27356:
URL: https://github.com/apache/airflow/pull/27356#discussion_r1014633359


##########
airflow/www/static/js/api/useDatasetDependencies.ts:
##########
@@ -75,15 +82,130 @@ const generateGraph = ({ nodes, edges, font }: GenerateProps) => ({
   edges: edges.map((e) => ({ id: `${e.source}-${e.target}`, sources: [e.source], targets: [e.target] })),
 });
 
+interface SeparateGraphsProps extends DatasetDependencies {
+  graphs: DatasetDependencies[];
+}
+
+const graphIndicesToMerge: Record<number, number[]> = {};
+const indicesToRemove: number[] = [];
+
+// find the downstream graph of each upstream edge
+const findDownstreamGraph = (
+  { edges, nodes, graphs = [] }: SeparateGraphsProps,
+): DatasetDependencies[] => {
+  const newGraphs = [...graphs];
+  let filteredEdges = [...edges];
+
+  graphs.forEach((g, i) => {
+    // find downstream edges
+    const downstreamEdges = edges.filter((e) => g.edges.some((ge) => ge.target === e.source));
+    const downstreamNodes: DepNode[] = [];
+
+    downstreamEdges.forEach((e) => {
+      const newNode = nodes.find((n) => n.id === e.target);
+      if (newNode) {
+        downstreamNodes.push(newNode);
+
+        // check if the node already exists in a different graph
+        const existingGraphIndex = newGraphs
+          .findIndex(((ng) => ng.nodes.some((n) => n.id === newNode.id)));
+
+        // mark if the graph needs to merge with another
+        if (existingGraphIndex > -1) {
+          indicesToRemove.push(existingGraphIndex);
+          graphIndicesToMerge[i] = [...(graphIndicesToMerge[i] || []), existingGraphIndex];
+        }
+
+        // add node and edge to the graph
+        newGraphs[i] = {
+          nodes: [...newGraphs[i].nodes, newNode],
+          edges: [...newGraphs[i].edges, e],
+        };
+
+        // remove edge from edge list
+        filteredEdges = filteredEdges
+          .filter((fe) => !(fe.source === e.source && fe.target === e.target));
+      }
+    });
+  });
+
+  // once there are no more filtered edges left, merge relevant graphs
+  // we merge afterwards to make sure we captured all nodes + edges
+  if (!filteredEdges.length) {
+    Object.keys(graphIndicesToMerge).forEach((key) => {
+      const realKey = key as unknown as number;
+      const values = graphIndicesToMerge[realKey];
+      values.forEach((v) => {
+        newGraphs[realKey] = {
+          nodes: unionBy(newGraphs[realKey].nodes, newGraphs[v].nodes, 'id'),
+          edges: [...newGraphs[realKey].edges, ...newGraphs[v].edges]
+            .filter((e, i, s) => (
+              i === s.findIndex((t) => t.source === e.source && t.target === e.target)
+            )),
+        };
+      });
+    });
+    return newGraphs.filter((g, i) => !indicesToRemove.some((j) => i === j));
+  }
+
+  return findDownstreamGraph({ edges: filteredEdges, nodes, graphs: newGraphs });
+};
+
+// separate the list of nodes/edges into distinct dataset pipeline graphs
+const separateGraphs = ({ edges, nodes }: DatasetDependencies): DatasetDependencies[] => {
+  const separatedGraphs: DatasetDependencies[] = [];
+  let remainingEdges = [...edges];
+  let remainingNodes = [...nodes];
+
+  edges.forEach((edge) => {
+    const isDownstream = edges.some((e) => e.target === edge.source);
+
+    // if the edge is not downstream of anything, then start building the graph
+    if (!isDownstream) {
+      const connectedNodes = nodes.filter((n) => n.id === edge.source || n.id === edge.target);
+
+      // check if the node is already connected to a separated graph
+      const nodesInUse = separatedGraphs
+        .findIndex((g) => g.nodes.some((n) => connectedNodes.some((nn) => nn.id === n.id)));
+
+      if (nodesInUse > -1) {
+        // if the node is in use, merge the graphs

Review Comment:
   ```suggestion
           // if on of the nodes is already in use, merge the graphs
   ```



-- 
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

To unsubscribe, e-mail: commits-unsubscribe@airflow.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org