Query performance with not existing relationship check in Neo4j

user_7357621 0
Viewed 56

we are trying to optimize a query but the time explodes (~20 seconds) when having around 40K nodes in the database, but it should be way faster.

First, I will describe a simplified description of our schema. We have the following nodes:

  • Usergroup
  • Feature
  • Asset
  • Section

We also have the following relationships:

  • A Feature has only one Section (IS_IN_SECTION)
  • A Feature has one or more Asset (CONTAINS_ASSET)
  • An asset may be restricted for a Usergroup (HAS_RESTRICTED_ASSET)
  • A Feature may be restricted for a Usergroup (HAS_RESTRICTED_FEATURE)
  • A Section, and therefore, all the Feature of that Section, may be restricted for a Usergroup (HAS_RESTRICTED_SECTION)
  • A Usergroup may have a parent Usergroup (HAS_PARENT_GROUP) and it should fulfill its restrictions and those of its parents

The goal is, given a Usergroup, to list the top 20 assets ordered by date, that don't have any restrictions with the Usergroup.

The current query is similar to:

(1)
MATCH path=(:UserGroup {uid: $usergroup_uid})-[:HAS_PARENT_GROUP*0..]->(root:UserGroup)
  WHERE NOT (root)-[:HAS_PARENT_GROUP]->(:UserGroup)
  WITH nodes(path) AS usergroups
  UNWIND usergroups AS ug

(2)
MATCH (node:Asset)
  WHERE NOT (node)<-[:CONTAINS_ASSET]-(:Feature)-[:IS_IN_SECTION]->(:Section)<-[:HAS_RESTRICTED_SECTION {restriction_type: "view"}]-(ug) 
  AND NOT (node)<-[:HAS_RESTRICTED_ASSET {restriction_type: "view"}]-(ug)
  AND NOT (node)<-[:CONTAINS_ASSET]-(:Feature)<-[:HAS_RESTRICTED_FEATURE {restriction_type: "view"}]-(ug)

RETURN DISTINCT node 
ORDER BY node.date DESC
SKIP 0
LIMIT 20

We have a few more types of restrictions but here we have the main idea.

Some observations we have made are:

  • If we execute the query part (1) adding return ug after unwind, this query is solved in 1ms
  • If we change the query part (1) to MATCH (ug:Usergroup {uid: $usergroup_uid}) ignoring the parent groups, the query is solved in around 800ms. And if we add back the original part (1) it is solved in 8 seconds even if the Usergroup has no parents.

Currently, our database is small compared to the expected number of nodes (~6 millions), and the number of restrictions will grow, and we need to optimize this kind of queries.

For that, we have these questions:

  • The NOT <restrictions> (ex: NOT (node)<-[:HAS_RESTRICTED_ASSET {restriction_type: "view"}]-(ug)) conditions is correct in this kind of situation or are there other approachs to get the job done more efficiently?
  • Do we need any type of index?
  • Is the structure of the schema right, or are there any inefficiencies?
  • How can we rewrite the part (1) of the query or what do you thinks is causing the overhead with it?

The database version is Neo4j 3.5.X

Thanks in advance.

neo4j graph query-optimization performance
1 Answers

Let me answer your questions one by one:

  1. The NOT <restrictions> type of conditions can prove to be inefficient if provide a set of paths within restrictions because it can lead to duplicate work. Consider the following two sets of restrictions in your query.

    NOT (node)<-[:CONTAINS_ASSET]-(:Feature)-[:IS_IN_SECTION]->(:Section)<-[:HAS_RESTRICTED_SECTION {restriction_type: "view"}]-(ug) and NOT (node)<-[:CONTAINS_ASSET]-(:Feature)<-[:HAS_RESTRICTED_FEATURE {restriction_type: "view"}]-(ug)

In both of these checks, neo4j might look for the relationship CONTAINS_ASSET and nodes of type Feature separately, once for the first path match and then for the second. This duplicate processing should be reduced if it happens. You should profile your query in Neo4j Browser, to see how the query planner plans and executes the query.

  1. In terms of indexes you can create two indexes, the first is on the Usergroup uid field, and the second on the date field of the Asset node, this might help if you have a lot of asset nodes and date key stores a string. Again, profile your query to see what indexes are coming into play during execution.

  2. In terms of schema, I noticed that in second part of your query NOT (node)<-[:CONTAINS_ASSET]-(:Feature)-[:IS_IN_SECTION]->(:Section)<-[:HAS_RESTRICTED_SECTION {restriction_type: "view"}]-(ug) AND NOT (node)<-[:HAS_RESTRICTED_ASSET {restriction_type: "view"}]-(ug) AND NOT (node)<-[:CONTAINS_ASSET]-(:Feature)<-[:HAS_RESTRICTED_FEATURE {restriction_type: "view"}]-(ug) , all these three checks are basically looking for whether an asset is restricted for a user group, either directly, via a feature, or via a section. One thing we can do here is to create intermediate relationships, between an Asset and UserGroup node. For example, we can have IS_RESTRICTED_DUE_TO_A_FEATURE relationship between an asset and user group node, if an asset is part of a feature for which the user group has restricted access. In this way, your path match reduces from NOT (node)<-[:CONTAINS_ASSET]-(:Feature)<-[:HAS_RESTRICTED_FEATURE {restriction_type: "view"}]-(ug) to NOT (node)<-[:IS_RESTRICTED_DUE_TO_A_FEATURE]-(ug), which should be faster. Obviously, this change will impact your other CRUD operations, and you might want to store some properties in the new relationships as well.

  3. For this part, I am not sure, what is causing the overhead, but I suggest you add the index on the Usergroup uid field, if not present, and then modify your first part to this:

    MATCH (ug:UserGroup {uid: $usergroup_uid})-[:HAS_PARENT_GROUP*0..]->(root:UserGroup) WHERE NOT (root)-[:HAS_PARENT_GROUP]->(:UserGroup) RETURN ug

If it performs well, then try modifying your second part to this:

MATCH (node:Asset)
OPTIONAL MATCH (node)<-[rel1:CONTAINS_ASSET]-(f:Feature)-[rel2:IS_IN_SECTION]->(s:Section) 
  WITH node
  WHERE (s IS NULL OR NOT (s)<-[:HAS_RESTRICTED_SECTION {restriction_type: "view"}]-(ug)) 
  AND NOT (node)<-[:HAS_RESTRICTED_ASSET {restriction_type: "view"}]-(ug)
  AND (f IS NULL OR NOT (f)<-[:HAS_RESTRICTED_FEATURE {restriction_type: "view"}]-(ug))

RETURN DISTINCT node 
ORDER BY node.date DESC
SKIP 0
LIMIT 20

Please try out the above suggestions, also the above queries are not tested, so please modify them a bit, if the output format is unexpected. Do profile them out, to figure out the slowest part, in the queries. Hopefully, it helps.

user_123681540
Related