Most efficient way to get all connected nodes in neo4j

Question

The answer to this question shows how to get a list of all nodes connected to a particular node via a path of known relationship types.

As a follow up to that question, I'm trying to determine if traversing the graph like this is the most efficient way to get all nodes connected to a particular node via any path.

My scenario: I have a tree of groups (group can have any number of children). This I model with IS_PARENT_OF relationships. Groups can also relate to any other groups via a special relationship called role playing. This I model with PLAYS_ROLE_IN relationships.

The most common question I want to ask is MATCH(n {name: "xxx") -[*]-> (o) RETURN o.name, but this seems to be extremely slow on even a small number of nodes (4000 nodes - takes 5s to return an answer). Note that the graph may contain cycles (n-IS_PARENT_OF->o, n<-PLAYS_ROLE_IN-o).

Is connectedness via any path not something that can be indexed?

Answer 1

Use label, e.g. :Group for your starting point and an index for :Group(name)

Then Neo4j can quickly find your starting point without scanning the whole graph.

You can easily see where the time is spent by prefixing your query with PROFILE.

Do you really want all arbitrarily long paths from the starting point? Or just all pairs of connected nodes?

If the latter then this query would be more efficient.

MATCH (n:Group)-[:IS_PARENT_OF|:PLAYS_ROLE_IN]->(m:Group)
RETURN n,m

Answer 2

As a first point, by not using labels and an indexed property for your starting node, this will already need to first find ALL the nodes in the graph and opening the PropertyContainer to see if the node has the property name with a value "xxx".

Secondly, if you now an approximate maximum depth of parentship, you may want to limit the depth of the search

I would suggest you add a label of your choice to your nodes and index the name property.