直接邻居关系密码查询性能

Question

这个问题类似于这两个:16283441,15456345。

UPDATE:这里是一个数据库转储。

在一个有190K个节点和727K个关系(以及128MB的数据库磁盘使用)的数据库中，我想运行以下查询:

START start_node=node(<id>) 
MATCH (start_node)-[r:COOCCURS_WITH]-(partner), 
      (partner)-[s:COOCCURS_WITH]-(another_partner)-[:COOCCURS_WITH]-(start_node)  
RETURN COUNT(DISTINCT s) as num_partner_partner_links;

在这个数据库中，90%的节点有0个关系，剩下的10%有从1到670的关系，所以这个查询可以返回的最大网络不可能有超过220K的链接(670*670)/2)。

在partner_partner_links少于10K的节点上，查询需要2-4秒。对于更多连接的节点(20-45K链路)，大约需要40-50秒(不知道连接最多的节点需要多少时间)。

指定关系方向有一点帮助，但不是很多(但随后查询不返回我需要返回的内容)。

对其中一个最大节点上的查询进行分析:

==> ColumnFilter(symKeys=["  INTERNAL_AGGREGATE48d9beec-0006-4dae-937b-9875f0370ea6"], returnItemNames=["num_partner_links"], _rows=1, _db_hits=0)
==> EagerAggregation(keys=[], aggregates=["(  INTERNAL_AGGREGATE48d9beec-0006-4dae-937b-9875f0370ea6,Distinct)"], _rows=1, _db_hits=0)
==>   PatternMatch(g="(partner)-['r']-(start_node)", _rows=97746, _db_hits=34370048)
==>     TraversalMatcher(trail="(start_node)-[  UNNAMED3:COOCCURS_WITH WHERE true AND true]-(another_partner)-[s:COOCCURS_WITH WHERE true AND true]-(partner)", _rows=116341, _db_hits=117176)
==>       ParameterPipe(_rows=1, _db_hits=0)
neo4j-sh (0)$ 

我不明白为什么会这么慢，大部分的东西应该在RAM中。是否有可能在100ms以下或neo4j达不到这一点?如果有帮助的话，我可以把整个数据库放在某个地方。

最大的困惑是，当重写相同的查询以使用不同的节点符号时，运行速度会变慢:)

START n=node(36) 
MATCH (n)-[r:COOCCURS_WITH]-(m), 
      (m)-[s:COOCCURS_WITH]-(p)-[:COOCCURS_WITH]-(n) 
RETURN COUNT(DISTINCT s) AS num_partner_partner_links;
START start_node=node(36) 
MATCH (start_node)-[r:COOCCURS_WITH]-(partner), 
      (partner)-[s:COOCCURS_WITH]-(another_partner)-[:COOCCURS_WITH]-(start_node)  
RETURN COUNT(DISTINCT s) AS num_partner_partner_links;

前者总是运行在+4.2秒，后者在3.8以下，无论我运行多少次一个和另一个(交错)!?

SW/HW details: (advanced) Neo4j v1.9。RC2, JDK 1.7.0.10，带有SSD磁盘的macbook pro, 8gb内存，2核i7, neo4j配置如下:

neostore.nodestore.db.mapped_memory=550M
neostore.relationshipstore.db.mapped_memory=540M
neostore.propertystore.db.mapped_memory=690M
neostore.propertystore.db.strings.mapped_memory=430M
neostore.propertystore.db.arrays.mapped_memory=230M
neostore.propertystore.db.index.keys.mapped_memory=150M
neostore.propertystore.db.index.mapped_memory=140M
wrapper.java.initmemory=4092 
wrapper.java.maxmemory=4092

Answer 1

将查询更改为下面的查询。在我的笔记本电脑上，配置比你的低得多，执行时间减半。

START start_node=node(36) 
MATCH (start_node)-[r:COOCCURS_WITH]-(partner)
WITH start_node, partner
MATCH (partner)-[s:COOCCURS_WITH]-(another_partner)-[:COOCCURS_WITH]-(start_node)
RETURN COUNT(DISTINCT s) AS num_partner_partner_links;

另外，与默认设置相比，使用您的设置不会对性能产生太大影响。恐怕你不能得到你想要的性能，但是这个查询是朝着正确方向迈出的一步。

通常遍历API会比Cypher快，因为你显式地控制遍历。我模仿了如下查询:

public class NeoTraversal {
public static void main(final String[] args) {
    final GraphDatabaseService db = new GraphDatabaseFactory()
            .newEmbeddedDatabaseBuilder("/neo4j")
            .loadPropertiesFromURL(NeoTraversal.class.getClassLoader().getResource("neo4j.properties"))
            .newGraphDatabase();
    final Set<Long> uniquePartnerRels = new HashSet<Long>();
    long startTime = System.currentTimeMillis();
    final Node start = db.getNodeById(36);
    for (final Path path : Traversal.description()
            .breadthFirst()
            .relationships(Rel.COOCCURS_WITH, Direction.BOTH)
            .uniqueness(Uniqueness.NODE_GLOBAL)
            .evaluator(Evaluators.atDepth(1))
            .traverse(start)) {
        Node partner = start.equals(path.startNode()) ? path.endNode() : path.startNode();
        for (final Path partnerPath : Traversal.description()
                .depthFirst()
                .relationships(Rel.COOCCURS_WITH, Direction.BOTH)
                .uniqueness(Uniqueness.RELATIONSHIP_PATH)
                .evaluator(Evaluators.atDepth(2))
                .evaluator(Evaluators.includeWhereEndNodeIs(start))
                .traverse(partner)) {
            uniquePartnerRels.add(partnerPath.relationships().iterator().next().getId());
        }
    }
    System.out.println("Execution time: " + (System.currentTimeMillis() - startTime));
    System.out.println(uniquePartnerRels.size());
}
static enum Rel implements RelationshipType {
    COOCCURS_WITH
}
}

这显然优于cypher查询，因此这对您来说可能是一个不错的选择。

Answer 2

似乎对于深度/广度优先遍历之外的任何东西，neo4j都不是那么"快"。我通过预先计算所有网络并将它们存储到MongoDB来解决这个问题。描述网络的节点文档是这样的:

{
    node_id : long, 
    partners : long[],
    partner_partner_links : long[]
}

Partners和partner_partner_links是描述节点的文档的id。获取整个网络需要2个查询:一个用于此文档，另一个用于边缘属性(也包含节点属性):

db.edge.find({"_id" : {"$in" : network.partner_partner_links}});