Neo4j cypher query is too slow(too many dbhits) in bidirectional relationship

Question

Having the flowing data model:

(Phone{phoneNumber})-[:CALL]-(Phone{phoneNumber})        
(Person{personId})-[:KEEP]-(Phone{personId})    
(Case{caseId})-[:INVOLVE]-(Person{personId}) 

all these three are using bidirectional relationship. And created index on phoneNumber/personId/caseId.

User can input one or more strings which maybe represent as phoneNumber/ caseId/personId to query for their relationships(NOT consider direction and relationship depth can be 1 to 4).

Here is the cypher query:

match p = n-[r*1..4]-m 
with n,m,p 
where (n.phoneNumber in ["xxx","yyy"] 
       or n.caseSjNo in ["xxx","yyy"] 
       or n.identificationNumber in ["xxx","yyy"]) 
  and (m.phoneNumber in ["xxx","yyy"] 
       or m.caseSjNo in ["xxx","yyy"] 
       or m.identificationNumber in ["xxx","yyy"])
  and n <> m 
return p limit 1000 

I profiled this query string in shell console.Having 10,000 nodes in neo4j db, I found the Dbhits is amazing. Here is the result(depth = 1 and depth = 4):

neo4j-sh (?)$ profile match p = n-[r*1..1]-m with n,m,p where (n.phoneNumber in ["XXX","YYY"] or n.caseSjNo in ["XXX","YYY"] or n.identificationNumber in ["XXX","YYY"]) and (m.phoneNumber in ["XXX","YYY"]                       or m.caseSjNo in ["XXX","YYY"]                       or m.identificationNumber in ["XXX","YYY"]) and n <> m return p limit 1000;
==> +---+
==> | p |
==> +---+
==> +---+
==> 0 row
==> 
==> ColumnFilter(0)
==>   |
==>   +Slice
==>     |
==>     +Filter
==>       |
==>       +ColumnFilter(1)
==>         |
==>         +ExtractPath
==>           |
==>           +TraversalMatcher
==> 
==> +------------------+-------+--------+-------------+-----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------+
==> |         Operator |  Rows | DbHits | Identifiers |                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                               Other |
==> +------------------+-------+--------+-------------+-----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------+
==> |  ColumnFilter(0) |     0 |      0 |             |                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                      keep columns p |
==> |            Slice |     0 |      0 |             |                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                       {  AUTOINT12} |
==> |           Filter |     0 | 480776 |             | ((((any(-_-INNER-_- in Collection(List({  AUTOSTRING0}, {  AUTOSTRING1})) where Property(n,phoneNumber(3)) == -_-INNER-_-) OR any(-_-INNER-_- in Collection(List({  AUTOSTRING2}, {  AUTOSTRING3})) where Property(n,caseSjNo(0)) == -_-INNER-_-)) OR any(-_-INNER-_- in Collection(List({  AUTOSTRING4}, {  AUTOSTRING5})) where Property(n,identificationNumber(2)) == -_-INNER-_-)) AND ((any(-_-INNER-_- in Collection(List({  AUTOSTRING6}, {  AUTOSTRING7})) where Property(m,phoneNumber(3)) == -_-INNER-_-) OR any(-_-INNER-_- in Collection(List({  AUTOSTRING8}, {  AUTOSTRING9})) where Property(m,caseSjNo(0)) == -_-INNER-_-)) OR any(-_-INNER-_- in Collection(List({  AUTOSTRING10}, {  AUTOSTRING11})) where Property(m,identificationNumber(2)) == -_-INNER-_-))) AND NOT(n == m)) |
==> |  ColumnFilter(1) | 20034 |      0 |             |                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                keep columns n, m, p |
==> |      ExtractPath | 20034 |      0 |           p |                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                     |
==> | TraversalMatcher | 20034 |  50152 |             |                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                m,   UNNAMED11, m, r |
==> +------------------+-------+--------+-------------+-----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------+
==> 
==> Total database accesses: 530928

------------------------------------------------------
------------------------------------------------------
neo4j-sh (?)$ profile match p = n-[r*1..4]-m with n,m,p where (n.phoneNumber in ["XXX","YYY"] or n.caseSjNo in ["XXX","YYY"] or n.identificationNumber in ["XXX","YYY"]) and (m.phoneNumber in ["XXX","YYY"]                       or m.caseSjNo in ["XXX","YYY"]                       or m.identificationNumber in ["XXX","YYY"]) and n <> m return p limit 1000 ;
==> +---+
==> | p |
==> +---+
==> +---+
==> 0 row
==> 
==> ColumnFilter(0)
==>   |
==>   +Slice
==>     |
==>     +Filter
==>       |
==>       +ColumnFilter(1)
==>         |
==>         +ExtractPath
==>           |
==>           +TraversalMatcher
==> 
==> +------------------+---------+-----------+-------------+-----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------+
==> |         Operator |    Rows |    DbHits | Identifiers |                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                               Other |
==> +------------------+---------+-----------+-------------+-----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------+
==> |  ColumnFilter(0) |       0 |         0 |             |                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                      keep columns p |
==> |            Slice |       0 |         0 |             |                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                       {  AUTOINT12} |
==> |           Filter |       0 | 120244220 |             | ((((any(-_-INNER-_- in Collection(List({  AUTOSTRING0}, {  AUTOSTRING1})) where Property(n,phoneNumber(3)) == -_-INNER-_-) OR any(-_-INNER-_- in Collection(List({  AUTOSTRING2}, {  AUTOSTRING3})) where Property(n,caseSjNo(0)) == -_-INNER-_-)) OR any(-_-INNER-_- in Collection(List({  AUTOSTRING4}, {  AUTOSTRING5})) where Property(n,identificationNumber(2)) == -_-INNER-_-)) AND ((any(-_-INNER-_- in Collection(List({  AUTOSTRING6}, {  AUTOSTRING7})) where Property(m,phoneNumber(3)) == -_-INNER-_-) OR any(-_-INNER-_- in Collection(List({  AUTOSTRING8}, {  AUTOSTRING9})) where Property(m,caseSjNo(0)) == -_-INNER-_-)) OR any(-_-INNER-_- in Collection(List({  AUTOSTRING10}, {  AUTOSTRING11})) where Property(m,identificationNumber(2)) == -_-INNER-_-))) AND NOT(n == m)) |
==> |  ColumnFilter(1) | 5010178 |         0 |             |                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                keep columns n, m, p |
==> |      ExtractPath | 5010178 |         0 |           p |                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                     |
==> | TraversalMatcher | 5010178 |  20070774 |             |                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                m,   UNNAMED11, m, r |
==> +------------------+---------+-----------+-------------+-----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------+
==> 
==> Total database accesses: 140314994

Although results came out, this took too long time. Any tips of query optimization.

UPDATE When having 1,000,000(1M) nodes in db, out of memory error occurred.

Answer 1

Why do you use bidirectional relationships in the first place? In Neo4j you can always navigate on both directions.

1. update to a recent Neo4j version (2.2.2)
2. use single directional relationships
3. use labels
4. create label indexes
5. the with in between doesn't help as it separates the conditions from the pattern
6. as you have a "generic" entity concept (x can be "anything") I recommend to add an :Entity label and use an id field there with an index.
7. are you really interested in all paths ? or just allShortestPaths?

see:

create index on :Entity(id);


match (n:Entity),(m:Entity) 
where n.id in ["xxx","yyy"] and m.id in ["xxx","yyy"] and n<>m
match p = (n)-[r*1..4]-(m)
return p 
limit 1000

Otherwise split it up into 6 different statements and use a union.

   match p = (n:Person)-[r*1..4]-(m:Case) 
   where n.identificationNumber in ["xxx","yyy"] and m.caseSjNo in ["xxx","yyy"]
   return p limit 500
   UNION
   match p = (n:Person)-[r*1..4]-(m:Phone) 
   where n.identificationNumber in ["xxx","yyy"] and m.phoneNumber in ["xxx","yyy"]
   return p limit 500
   UNION
   ...