Neo4j

Question

我迷路了，尝试了我能想到的一切。也许你能帮我。

我正在尝试查找给定软件包的所有依赖项。在这种特殊情况下，我正在使用 Node.js / JavaScript 生态系统并抓取整个 npm 注册表。我的数据模型很简单，我有包，一个包可以有多个版本。

在我的数据库中，我有 113.339.030 个依赖关系和 19.753.269 个版本。

我的整个代码工作正常，直到我发现一个包具有如此多的依赖项（直接和传递），以至于我的所有查询都崩溃了。它被称为react-scripts。这里可以看到包裹信息。

https://registry.npmjs.org/react-scripts

一个可视化工具永远不会完成

https://npm.anvaka.com/#/view/2d/react-scripts

另一个创建的依赖图太大以至于难以分析。

https://npmgraph.js.org/?q=react-scripts

起初我尝试使用递归通用 table 表达式的 PostgreSQL。

with recursive cte as (
    select
        child_id
    from
        dependencies
    where
        dependencies.parent_id = 16674850
    union
    select
        dependencies.child_id
    from
        cte
    left join dependencies on
        cte.child_id = dependencies.parent_id 
    where
        cte.child_id is not null
)
select * from cte;

那个returns1.726个元素里面好像还行。 https://deps.dev/npm/react-scripts/4.0.3/dependencies returns 1.445 个依赖项。

但是我想获取节点的路径，这不适用于 PostgreSQL 和 UNION。您必须使用 UNION ALL 但查询会更加复杂和缓慢。这就是为什么我认为我会给 Neo4j 一个机会。

我的节点具有属性

version_id: 整数
name: 字符串
version: 字符串

我从我认为是简单的查询开始，但它已经失败了。从具有 version_id 16674850 的版本开始，并提供所有依赖项。

MATCH p = (a:Version {version_id: 16674850})-[:DEPENDS_ON*..11]->(b:Version)
return DISTINCT b;

我在 version_id 上有一个索引。

CREATE INDEX FOR (version:Version) ON (version.version_id)

直到我将深度设置为可变长度或更大 12。

然后查询将永远运行。这是查询计划。

Neo4j 在 Docker 中运行。我增加了一些内存设置。

- NEO4J_dbms_memory_heap_initial__size=2G
- NEO4J_dbms_memory_heap_max__size=2G
- NEO4J_dbms_memory_pagecache_size=1G

有什么想法吗？我现在真的迷路了，不想放弃我的“软件依赖分析图”。在过去的 6 周里，我一直在解决这个问题。非常感谢！

编辑 28/09/2021

我上传了样本数据集。这是链接

https://s3.amazonaws.com/blog.spolytics.com/versions.csv (737.1 MB)
https://s3.amazonaws.com/blog.spolytics.com/dependencies.csv (1.7 GB)

这是导入数据的脚本。

neo4j-admin import \
    --database=deps \
    --skip-bad-relationships \
    --id-type=INTEGER \
    --nodes=Version=import/versions.csv \
    --relationships=DEPENDS_ON=import/dependencies.csv

这可能有助于在你这边做一些实验并重现我的问题。

Answer 1

我没有像你这样的大型数据集，但我认为你可以通过过滤 b 节点来减少路径数量。作为开始，这行得通吗？

MATCH p = (a:Version {version_id: 16674850})-[:DEPENDS_ON*..11]->(b:Version)
WHERE NOT EXISTS ((b)-[:DEPENDS_ON]->())
UNWIND nodes(p) AS node
return COUNT(DISTINCT node)

要检查是否可以 return 更长的路径，您可以

MATCH p = (a:Version {version_id: 16674850})-[:DEPENDS_ON*..12]->(b:Version)
WHERE NOT EXISTS ((b)-[:DEPENDS_ON]->())
RETURN count(p)

现在，如果可行，我会这样做：

MATCH p = (a:Version {version_id: 16674850})-[:DEPENDS_ON*..12]->(b:Version)
WHERE NOT EXISTS ((b)-[:DEPENDS_ON]->())
RETURN p LIMIT 10

查看路径是否正确

有时 UNWIND 会导致 n 个问题。要获取唯一节点集，您还可以尝试 APOC

MATCH p = (a:Version {version_id: 16674850})-[:DEPENDS_ON*..12]->(b:Version)
WHERE NOT EXISTS ((b)-[:DEPENDS_ON]->())
RETURN apoc.coll.toSet(
         apoc.coll.flatten(
           COLLECT(nodes(p))
         )
       ) AS unique nodes

Answer 2

这里的问题是 Cypher 有兴趣找到与模式匹配的所有可能路径。当您只想要不同的可到达节点时，这可能会产生问题，在这种情况下您真的不关心扩展到每个不同的路径，而只是寻找节点并忽略通向已访问节点的任何替代路径。

此外，计划者在笛卡尔积计划上做出了错误的选择，这会使问题变得更糟。

我建议为此使用 APOC 过程，因为有些过程经过优化以扩展到不同的节点并忽略到已访问节点的路径。 apoc.path.subgraphNodes()是程序。

这是一个使用示例：

MATCH (a:Version {version_id: 16674850})
CALL apoc.path.subgraphNodes(a, {relationshipFilter:'DEPENDS_ON>', labelFilter:'>Version', maxLevel:11}) YIELD node as b
RETURN b

关系过滤器中的箭头指示方向，因为它指向右侧，所以它指的是遍历传出关系。如果我们有兴趣改为遍历传入关系，我们会在关系名称的开头看到指向左侧的箭头。

对于标签过滤器，前缀>表示标签是结束标签，这意味着我们只对返回给定标签的节点感兴趣。

如果您希望它成为无界扩展，您可以删除 maxLevel 配置属性。

此处有更多选项和详细信息：

https://neo4j.com/labs/apoc/4.1/graph-querying/expand-subgraph-nodes/

Neo4j - 可变长度大于 11 永远运行并且从不查询 returns

Neo4j - Variable length greater 11 runs forever and query never returns

common-table-expression

cypher