Shortestpath using Cypher and Java is too slow

[Jonathan D'Orleans]

Hello Guys,

I have an application that will have 40 millions of nodes.
At the moment, I'm doing some tests using a sample graph of 4 millions of nodes, 11M relationships and 30M props.

I have imported my old database to neo4j, then I made some tests using neo4j Webadmin.
One of them was to use the ShortestPath algorithm:

TEST 1: Using Cypher in Webadmin

start s=node(id1), e=node(id2)
match p=shortestPath( s-[*..1000]->e )
return length(p), path

The result of the first test was:

    Length = 658
    Query took 34503ms

If I rerun this test it will take around 1500ms. That was great and everything was ok!


TEST 2: Using Cypher and GraphAlgoFactory with SpringData

After testing my data in webadmin I'd like to test it into my java app using Spring-Data-Neo4j (2.2.1.RELEASE).
Then I made 2 use cases:

1. Using Cypher with @Query into my repository;

    @Query( " START s=node(id1), e=node(id2) " +
            " MATCH p=shortestPath( s-[*..700]->e ) " +
            " RETURN nodes(p) ")

2. Using Java: GraphAlgoFactory

int maxDepth = 700;
PathExpander expander = Traversal.pathExpanderForAllTypes(Direction.OUTGOING);
PathFinder<Path> finder = GraphAlgoFactory.shortestPath(expander, maxDepth, 1);        
Path path = finder.findSinglePath(template.getNode(origin), template.getNode(destiny));

The Problem and Questions:

In both tests the application take too much time and never return the result.
Sometimes I got a exception of out-of-memory even with 6Gb of memory allocated only to this application.
I'd like your help guys to understand what's is going different of the webadmin test.

Since it's the same cypher query, why I never get a response?

Is webadmin queries optimized somehow?

Am I doing something wrong?


Thanks a lot,

Jonathan D'Orleans

[Michael Hunger]

Is your SDN running on an embedded db?

How do you set up your ApplicationContext?

The cypher query should work if you used parameters, can you share more of your repository?

@Query( " START s=node({0}), e=node({1}) " +

            " MATCH p=shortestPath( s-[*..700]->e ) " +
            " RETURN nodes(p) ")

Perhaps start by just returning length(p)

How do you set up the database for the GraphAlgoFactory? With an embedded instance?

Michael

--
You received this message because you are subscribed to the Google Groups "Neo4j" group.
To unsubscribe from this group and stop receiving emails from it, send an email to neo4j+un...@googlegroups.com.
For more options, visit https://groups.google.com/groups/opt_out.
 
 

[Jonathan D'Orleans]

Hi Michael,

Thanks for responding me.

I have tested the shortestpath algo with a path length <= 10. Something like: n1-[*..10]->n2
That's just working fine, but when I go to bigger path it's not.
So, I'm assuming that SDN is setting my Neo4j DB fine.

More explanation about my test and code:

1. SDN is running on an embedded neo4j db.
I'm using the following settings to my JVM: -d64 -Xms3g -Xmx6g -XX:+UseParallelGC -XX:PermSize=256m -XX:MaxPermSize=512m


2. My AppContext config XML is:

    <context:component-scan base-package="com.package1.package2" />
    <context:spring-configured />
   
    <neo4j:config storeDirectory="data" />
    <neo4j:repositories base-package="com.package1.package2.repository" />

    <tx:annotation-driven mode="proxy" />

I'm starting my AppContext and testing my application in a Main Class like this:

ApplicationContext ctx = new AnnotationConfigApplicationContext(AppConfig.class);
MyService service = ctx.getBean(MyService.class);
service.testShortestPath();

3. My Node Repository:

public interface MyNodeRepository extends GraphRepository<MyNode> {
   
    @Query( " START s=node(310203), e=node(900000) " +

            " MATCH p=shortestPath( s-[*..700]->e ) " +
            " RETURN nodes(p) ")

    public Iterator<MyNode> findShortestPathTest();
   
}

4. Into My Service:

@Autowired
private MyNodeRepository repository;

public Iterator<MyNode> testShortestPath() {
       System.out.println( repository.findShortestPathTest() );
}

Notes:
Like I said before, if I run the same test with a smaller path like length < 100 it's working fine.
I don't understand why it works at webadmin and not in my app when I try a bigger path.

thx,

--
You received this message because you are subscribed to a topic in the Google Groups "Neo4j" group.
To unsubscribe from this topic, visit https://groups.google.com/d/topic/neo4j/YRmDlhnBB2k/unsubscribe?hl=en.
To unsubscribe from this group and all its topics, send an email to neo4j+un...@googlegroups.com.

For more options, visit https://groups.google.com/groups/opt_out.
 
 

--

Jonathan D'Orleans
Engenheiro de Software

SagaranaTech

(85) 8920-4792
jdor...@sagaranatech.com

[Michael Hunger]

Where do you get the OOM.

How many paths do you expect it to return? Just one or more?

Could you instead of printing it, actually iterate over the result iterator (actually can you try Iterable<MyNode>) and for instance count the rows?

Michael

[Jonathan D'Orleans]

1. OOM Exception:

For this cypher shotestpath test I was just returning length(p) and I got the following exception:

Exception in thread "main" java.lang.OutOfMemoryError: Java heap space
    at org.neo4j.graphalgo.impl.util.PathImpl.<init>(PathImpl.java:114)
    at org.neo4j.graphalgo.impl.util.PathImpl.<init>(PathImpl.java:34)
    at org.neo4j.graphalgo.impl.util.PathImpl$Builder.build(PathImpl.java:84)
    at org.neo4j.graphalgo.impl.path.ShortestPath.hitsToPaths(ShortestPath.java:571)
    at org.neo4j.graphalgo.impl.path.ShortestPath.internalPaths(ShortestPath.java:170)
    at org.neo4j.graphalgo.impl.path.ShortestPath.findSinglePath(ShortestPath.java:139)
    at org.neo4j.cypher.internal.commands.expressions.SingleShortestPathFOO.findResult(ShortestPathExpression.scala:93)
    at org.neo4j.cypher.internal.commands.expressions.ShortestPathExpression.getMatches(ShortestPathExpression.scala:48)
    at org.neo4j.cypher.internal.commands.expressions.ShortestPathExpression.apply(ShortestPathExpression.scala:41)
    at org.neo4j.cypher.internal.pipes.ShortestPathPipe$$anonfun$createResults$1.apply(ShortestPathPipe.scala:41)
    at org.neo4j.cypher.internal.pipes.ShortestPathPipe$$anonfun$createResults$1.apply(ShortestPathPipe.scala:40)
    at scala.collection.Iterator$$anon$21.hasNext(Iterator.scala:371)
    at scala.collection.Iterator$$anon$19.hasNext(Iterator.scala:334)
    at scala.collection.Iterator$$anon$19.hasNext(Iterator.scala:334)
    at org.neo4j.cypher.PipeExecutionResult.hasNext(PipeExecutionResult.scala:138)
    at scala.collection.Iterator$$anon$19.hasNext(Iterator.scala:334)
    at scala.collection.JavaConversions$IteratorWrapper.hasNext(JavaConversions.scala:562)
    at org.neo4j.helpers.collection.IteratorUtil.singleOrNull(IteratorUtil.java:115)
    at org.neo4j.helpers.collection.IteratorUtil.singleOrNull(IteratorUtil.java:260)
    at org.springframework.data.neo4j.conversion.QueryResultBuilder$1.singleOrNull(QueryResultBuilder.java:94)
    at org.springframework.data.neo4j.repository.query.GraphRepositoryQuery.dispatchQuery(GraphRepositoryQuery.java:108)
    at org.springframework.data.neo4j.repository.query.GraphRepositoryQuery.execute(GraphRepositoryQuery.java:81)
    at org.springframework.data.repository.core.support.RepositoryFactorySupport$QueryExecutorMethodInterceptor.invoke(RepositoryFactorySupport.java:312)
    at org.springframework.aop.framework.ReflectiveMethodInvocation.proceed(ReflectiveMethodInvocation.java:172)
    at org.springframework.transaction.interceptor.TransactionInterceptor.invoke(TransactionInterceptor.java:110)
    at org.springframework.aop.framework.ReflectiveMethodInvocation.proceed(ReflectiveMethodInvocation.java:172)
    at org.springframework.dao.support.PersistenceExceptionTranslationInterceptor.invoke(PersistenceExceptionTranslationInterceptor.java:155)
    at org.springframework.aop.framework.ReflectiveMethodInvocation.proceed(ReflectiveMethodInvocation.java:172)
    at org.springframework.aop.framework.JdkDynamicAopProxy.invoke(JdkDynamicAopProxy.java:204)
    at com.sun.proxy.$Proxy31.findByShostestPathTest(Unknown Source)
    at sun.reflect.NativeMethodAccessorImpl.invoke0(Native Method)
    at sun.reflect.NativeMethodAccessorImpl.invoke(NativeMethodAccessorImpl.java:57)

2. I expect only one path. It can be the first shortest path found.

3. I'm able to iterate for a short path (length < 100). For the biggest ones I still getting the exception above.

Could the use of embedded neo4j be a problem? Is there any magic that make it work in webadmin?

[Michael Hunger]

Can you try it without SDN just with cypher?

GraphDatabaseService gdb = new EmbeddedGraphDatabase("data");

ExecutionEngine engine = new ExecutionEngine(gdb);

Iterable<Node> nodes = engine.execute(" START s=node(310203), e=node(900000) MATCH p=shortestPath( s-[*..700]->e ) RETURN nodes(p) as res").columnAs("res").next();

for (Node n : nodes) {

  count++;

}

sout(count);

And would it be possible to share your db or a generator? So that we can try to reproduce it?

Thanks a lot

Michael

[Jonathan D'Orleans]

Holy f... It works... but, let's clarify everything!

TEST 1: Using the code and tip you provided

1. I have removed all code;

2. At Main class, I created only one method to test my use case.
Then, I made it like you said.

Result: I had no success! I got the same issue as before (eternal waiting).


TEST 2: Similar to Test 1 + changing dependencies

1. I made everything like test1;

2. I changed my dependencies at pom.xml.
2.1. I removed every Spring Data and Neo4j dependencies
2.2. Then, I imported the latest Neo4j (2.0.0-M02)

Result: I got the following exception:

Caused by: java.lang.IllegalStateException: No such store[data/neostore.nodestore.db.labels] for org.neo4j.kernel.DefaultFileSystemAbstraction@11c1cc4a
    at org.neo4j.kernel.impl.nioneo.store.CommonAbstractStore.checkStorage(CommonAbstractStore.java:151)
    at org.neo4j.kernel.impl.nioneo.store.CommonAbstractStore.<init>(CommonAbstractStore.java:112)
    at org.neo4j.kernel.impl.nioneo.store.AbstractDynamicStore.<init>(AbstractDynamicStore.java:75)
    at org.neo4j.kernel.impl.nioneo.store.DynamicArrayStore.<init>(DynamicArrayStore.java:57)
    at org.neo4j.kernel.impl.nioneo.store.StoreFactory.newNodeStore(StoreFactory.java:191)
    at org.neo4j.kernel.impl.nioneo.store.StoreFactory.attemptNewNeoStore(StoreFactory.java:122)
    at org.neo4j.kernel.impl.nioneo.store.StoreFactory.newNeoStore(StoreFactory.java:111)
    at org.neo4j.kernel.impl.nioneo.xa.NeoStoreXaDataSource.start(NeoStoreXaDataSource.java:283)
    at org.neo4j.kernel.lifecycle.LifeSupport$LifecycleInstance.start(LifeSupport.java:491)

NOTE: Maybe it could be a bug of the new version.


TEST 3: Like Test 2 + using another version of Neo4j (1.9.RC2 and 1.9.M05)

1. I made everything like Test 2;
2. I changed the Neo4j version to test with 1.9.RC2 and 1.9.M05

Result: finally the SUCCESS! The print was:

Shortest Path using Cypher Query (No SDN) -- Starting at: 15:53:07
Node[310203] -- > Node[310201] -- > [... ... ...] -- > Node[949070] -- > Node[899999] -- > Node[900000]
Completed at: 15:53:14 -- COUNT: 659

7 seconds for this one at one shot.


CONCLUSION:

1. It seems SDN (2.2.1.RELEASE) is using a bugged or not improved version of Neo4j for shortestPath algorithms.
2. Neo4j 2.0.0 is return some odd exception at starting. So, I'm not able to test it neither to explain the new problem.
3. Both Neo4j version 1.9.RC2 and 1.9.M05 worked just fine without SDN.
4. The initial tests I've made in Webadmin were done using 'neo4j-community-1.9.RC2'. It explains why they worked.


QUESTIONS:

1. How I solve my problem using SDN? Is it possible to get SDN with Neo4j 1.9.RC2 or 1.9.M05?
2. What's wrong in Neo4j 2.0.0? Why I'm getting that exception? (maybe I should create a new topic for that one)
3. Have we enough information to help us solve the problem?

[Peter Neubauer]

Glad to hear that Jonathan!

/peter

Cheers,

/peter neubauer

G: neubauer.peter
S: peter.neubauer
P: +46 704 106975
L: http://www.linkedin.com/in/neubauer
T: @peterneubauer

Neo4j 1.9 GA is out -
http://blog.neo4j.org/2013/05/neo4j-19-general-availability.html
Neo4j questions? Please use SO - http://stackoverflow.com/search?q=neo4j

[Jonathan D'Orleans]

Thx Peter,

So is there any available SDN which Neo4j versions are 1.9.RC2 or 1.9.M05 ?

Jon