title: Neo4j Cypher path finding slow in undirected graph
body: <p>In a graph with 165k nodes and 266k relationships I'd like to run the following Cypher query:</p>
  
  <pre><code>START n=node:NodeIds('id:firstId'), t=node:NodeIds('id:secondId')   
  MATCH (n)-[:RELATIONSHIP_TYPE*1..3]-(t)   
  RETURN count(*)
  </code></pre>
  
  <p>where <code>firstId</code> and <code>secondId</code> is a valid entry for the NodeIds Lucene index.</p>
  
  <p>The query takes about 4 seconds to execute from the Neo4j console and I'd like to understand why is it so slow and how it could be made faster.</p>
  
  <p>The index lookup from this takes about 40ms (i.e. a query just returning the two nodes takes that much) so that can't be the issue.</p>
  
  <p>I run Neo4j on a Windows 8 machine with the default settings by starting from Neo4j.bat. I don't think hardware can be an issue as the query only causes a short 10% CPU spike and a barely visible spike in disk usage.</p>
  
  <p>BTW the first node has a degree of 40, the second 2 and the result is 1.</p>
  
  <p>Any help would be appreciated.</p>
  
  <p><strong>Edit 1, memory config:</strong></p>
  
  <p>I was running Neo4j with OOTB config by starting from Neo4j.bat with the following defaults regarding memory (if I'm not mistaken and those are the only memory-related configs):</p>
  
  <pre><code>wrapper.java.initmemory=16
  wrapper.java.maxmemory=64
  
  neostore.nodestore.db.mapped_memory=25M
  neostore.relationshipstore.db.mapped_memory=50M
  neostore.propertystore.db.mapped_memory=90M
  neostore.propertystore.db.strings.mapped_memory=130M
  neostore.propertystore.db.arrays.mapped_memory=130M
  </code></pre>
  
  <p>Shooting one into the dark I raised these values to the following:</p>
  
  <pre><code>wrapper.java.initmemory=128
  wrapper.java.maxmemory=1024
  
  neostore.nodestore.db.mapped_memory=225M
  neostore.relationshipstore.db.mapped_memory=250M
  neostore.propertystore.db.mapped_memory=290M
  neostore.propertystore.db.strings.mapped_memory=330M
  neostore.propertystore.db.arrays.mapped_memory=330M
  </code></pre>
  
  <p>This indeed increased Neo4j memory usage (I mean the memory usage of the java.exe instance running Neo4j) without a good increase in performance (the query takes roughly the same time, with probably a 2-300ms increase occasionally). There are GBs of RAM free so there's no hardware constraint.</p>
  
  <p><strong>Edit 2, profiler data:</strong>
  Running the profiler for the query in question yields the following results:</p>
  
  <pre><code>neo4j-sh (0)$ profile START n=node:NodeIds('id:4000'), t=node:NodeIds('id:64599') MATCH path = (n)-[:ASSOCIATIVY_CONNECTION*1..3]-(t) RETURN count(*);
  ==&gt; +----------+
  ==&gt; | count(*) |
  ==&gt; +----------+
  ==&gt; | 1        |
  ==&gt; +----------+
  ==&gt; 1 row
  ==&gt; 0 ms
  ==&gt; 
  ==&gt; ColumnFilter(symKeys=["  INTERNAL_AGGREGATE-939275295"], returnItemNames=["count(*)"], _rows=1, _db_hits=0)
  ==&gt; EagerAggregation(keys=[], aggregates=["(  INTERNAL_AGGREGATE-939275295,CountStar)"], _rows=1, _db_hits=0)
  ==&gt;   ExtractPath(name="path", patterns=["  UNNAMED3=n-[:ASSOCIATIVY_CONNECTION*1..3]-t"], _rows=1, _db_hits=0)
  ==&gt;     PatternMatch(g="(n)-['  UNNAMED3']-(t)", _rows=1, _db_hits=0)
  ==&gt;       Nodes(name="t", _rows=1, _db_hits=1)
  ==&gt;         Nodes(name="n", _rows=1, _db_hits=1)
  ==&gt;           ParameterPipe(_rows=1, _db_hits=0) 
  </code></pre>
  
  <p>It says 0ms but I don't know what that is supposed to mean: the result is returned after multiple seconds and the same query executed in the Data Browser's console takes about 3,5s (this is what it displays) and roughly the same amount of time fetched through the RESTful endpoint.</p>
  
  <p><strong>Edit 3, the real data set:</strong>
  Enough with the theory :-), this is the data set what I'm really talking about: <a href="http://associativy.com/Media/Default/Associativy/Wiki.zip" rel="nofollow noreferrer">http://associativy.com/Media/Default/Associativy/Wiki.zip</a> It's a graph generated by using the interlinks between Wikipedia articles, created from Wikipedia dump files. It's just the beginning.</p>
  
  <p>The real query I'm trying to run is actually the following one, returning the nodes building up the paths between two nodes:</p>
  
  <pre><code>START n=node:NodeIds('id:4000'), t=node:NodeIds('id:64599')   MATCH path = (n)-[:ASSOCIATIVY_CONNECTION*1..3]-(t)   RETURN nodes(path) AS Nodes
  </code></pre>
  
  <p>I showed the count query because I wanted the simplest query that shows the symptoms.</p>
  
  <p><strong>Edit 4:</strong></p>
  
  <p>I <a href="https://stackoverflow.com/questions/15549573/optimize-neo4j-cypher-path-finding-with-limited-paths-in-an-undirected-graph">opened another question</a> specifically for the path-returning query.</p>