Spark：为层次结构DataFrame的每个节点构建递归树路径

Question

考虑一棵树及其DataFrame表示（左表）：

0             ┌───────┬───────┐           ┌───────┬───────┐
├──1          │   id  │ parent│           │   id  │ path  │
│  ├──2       ├───────┼───────┤           ├───────┼───────┤
│  └──3       │   5   │   0   │           │   5   │0/5    │
│     └──4    ├───────┼───────┤           ├───────┼───────┤
└──5          │   4   │   3   │           │   4   │0/1/3/4│
              ├───────┼───────┤     =>    ├───────┼───────┤
              │   3   │   1   │           │   3   │0/1/3  │
              ├───────┼───────┤           ├───────┼───────┤
              │   2   │   1   │           │   2   │0/1/2  │
              ├───────┼───────┤           ├───────┼───────┤
              │   1   │   0   │           │   1   │0/1    │
              ├───────┼───────┤           ├───────┼───────┤
              │   0   │ null  │           │   0   │0      │
              └───────┴───────┘           └───────┴───────┘

从树的每个节点（右表）获取树路径（从根开始）的最有效方法是什么？

允许所有可能的方法：SQL查询，DataFrame方法，GraphX等。

注意：带有递归连接的经典SQL解决方案不适用于Spark DataFrames。

Answer 1

这看起来像Spark Graph API任务。您可以查看Graphframes spark包。它是一个通过GraphX核心提供高级API的软件包（与RDD上的传统Spark Dataframe相同）。有了这个，您可以使用数据框架构建图形。

看看这个链接：https://mapr.com/blog/analyzing-flight-delays-with-apache-spark-graphframes-and-mapr-db/

它显示了航班数据的用例。如果你看一下Breadth First Search Graph Algorithm部分，你会看到一个完全符合你想要的算法：找到两个顶点之间的路径（给定一个maxPathLength参数）。

使用graphframes依赖项运行pyspark（根据您的spark版本）：

pyspark --packages graphframes:graphframes:0.6.0-spark2.3-s_2.11

构建数据框：

df = sc.parallelize([{"id": 5, "parent": 0}, {"id": 4, "parent": 3}, {"id": 3, "parent": 1}, {"id": 2, "parent": 1}, {"id": 1, "parent": 0}, {"id": 0, "parent": None}]).toDF()

创建图表：

df_vertices = df.selectExpr("id")
df_edges = df.withColumnRenamed("id", "dst").withColumnRenamed("parent", "src")

from graphframes import GraphFrame
graph  = GraphFrame(df_vertices, df_edges)

可视化路径（例如从0到4）：

graph.bfs(fromExpr="id = 0",toExpr="id = 4", maxPathLength=10).show(2)

结果：

+----+------+---+------+---+------+---+
|from|    e0| v1|    e1| v2|    e2| to|
+----+------+---+------+---+------+---+
| [0]|[1, 0]|[1]|[3, 1]|[3]|[4, 3]|[4]|
+----+------+---+------+---+------+---+