algo.kShortestPath.stream throws OutOfMemory on small graph

[kcrimson]

Hi, I was playing recently with kShortestPath.stream (build from master), on rather small graph of 7184 nodes and 66067 relationships (airports and routes imported from here,

I am running following query (copy pasted from docs, with minor modifications):

MATCH (start:Airport{IATA:'KRK'}), (end:Airport{IATA:'DFW'})
CALL algo.kShortestPaths.stream(start, end, 4, 'distance' ,{})
YIELD index, nodeIds, path, costs
RETURN [node in algo.getNodesById(nodeIds) | node.city] AS places,
       costs,
       reduce(acc = 0.0, cost in costs | acc + cost) AS totalCost

It always ends up with OutOfMemory, even with 12G max heap size. I have managed to dump heap before full GC and found out that there is a local variable of type int[] and huge size. Call stack of this thread:

neo4j.BoltWorker-4 [bolt] [/127.0.0.1:35740] 
  at java.util.Arrays.copyOf([II)[I (Arrays.java:3284)
  at org.neo4j.graphalgo.core.utils.queue.IntPriorityQueue.ensureCapacityForInsert()V (IntPriorityQueue.java:242)
  at org.neo4j.graphalgo.core.utils.queue.IntPriorityQueue.add(ID)V (IntPriorityQueue.java:101)
  at org.neo4j.graphalgo.impl.yens.Dijkstra.lambda$dijkstra$2(DIIIJ)Z (Dijkstra.java:185)
  at org.neo4j.graphalgo.impl.yens.Dijkstra$$Lambda$494.accept(IIJ)Z (Unknown Source)
  at org.neo4j.graphalgo.core.heavyweight.AdjacencyMatrix.forEachOutgoing(ILorg/neo4j/graphalgo/api/RelationshipConsumer;)V (AdjacencyMatrix.java:340)
  at org.neo4j.graphalgo.core.heavyweight.AdjacencyMatrix.forEach(ILorg/neo4j/graphdb/Direction;Lorg/neo4j/graphalgo/api/RelationshipConsumer;)V (AdjacencyMatrix.java:287)
  at org.neo4j.graphalgo.core.heavyweight.HeavyGraph.forEachRelationship(ILorg/neo4j/graphdb/Direction;Lorg/neo4j/graphalgo/api/RelationshipConsumer;)V (HeavyGraph.java:93)
  at org.neo4j.graphalgo.impl.yens.Dijkstra.dijkstra(IILorg/neo4j/graphdb/Direction;I)Z (Dijkstra.java:172)
  at org.neo4j.graphalgo.impl.yens.Dijkstra.compute(III)Ljava/util/Optional; (Dijkstra.java:135)
  at org.neo4j.graphalgo.impl.yens.YensKShortestPaths.yens(IIILorg/neo4j/graphdb/Direction;I)V (YensKShortestPaths.java:93)
  at org.neo4j.graphalgo.impl.yens.YensKShortestPaths.compute(JJLorg/neo4j/graphdb/Direction;II)Lorg/neo4j/graphalgo/impl/yens/YensKShortestPaths; (YensKShortestPaths.java:69)
  at org.neo4j.graphalgo.KShortestPathsProc.yensStreaming(Lorg/neo4j/graphdb/Node;Lorg/neo4j/graphdb/Node;JLjava/lang/String;Ljava/util/Map;)Ljava/util/stream/Stream; (KShortestPathsProc.java:180)
  at sun.reflect.NativeMethodAccessorImpl.invoke0(Ljava/lang/reflect/Method;Ljava/lang/Object;[Ljava/lang/Object;)Ljava/lang/Object; (Native Method)
  at sun.reflect.NativeMethodAccessorImpl.invoke(Ljava/lang/Object;[Ljava/lang/Object;)Ljava/lang/Object; (NativeMethodAccessorImpl.java:62)
  at sun.reflect.DelegatingMethodAccessorImpl.invoke(Ljava/lang/Object;[Ljava/lang/Object;)Ljava/lang/Object; (DelegatingMethodAccessorImpl.java:43)
  at java.lang.reflect.Method.invoke(Ljava/lang/Object;[Ljava/lang/Object;)Ljava/lang/Object; (Method.java:498)
  at org.neo4j.kernel.impl.proc.ReflectiveProcedureCompiler$ReflectiveProcedure.apply(Lorg/neo4j/kernel/api/proc/Context;[Ljava/lang/Object;Lorg/neo4j/kernel/api/ResourceTracker;)Lorg/neo4j/collection/RawIterator; (ReflectiveProcedureCompiler.java:648)
  at org.neo4j.kernel.impl.proc.ProcedureRegistry.callProcedure(Lorg/neo4j/kernel/api/proc/Context;I[Ljava/lang/Object;Lorg/neo4j/kernel/api/ResourceTracker;)Lorg/neo4j/collection/RawIterator; (ProcedureRegistry.java:219)
  at org.neo4j.kernel.impl.proc.Procedures.callProcedure(Lorg/neo4j/kernel/api/proc/Context;I[Ljava/lang/Object;Lorg/neo4j/kernel/api/ResourceTracker;)Lorg/neo4j/collection/RawIterator; (Procedures.java:290)
  at org.neo4j.kernel.impl.newapi.AllStoreHolder.callProcedure(I[Ljava/lang/Object;Lorg/neo4j/internal/kernel/api/security/AccessMode;)Lorg/neo4j/collection/RawIterator; (AllStoreHolder.java:1072)
  at org.neo4j.kernel.impl.newapi.AllStoreHolder.procedureCallRead(I[Ljava/lang/Object;)Lorg/neo4j/collection/RawIterator; (AllStoreHolder.java:830)
  at org.neo4j.cypher.internal.runtime.interpreted.TransactionBoundQueryContext$$anonfun$4.apply([Ljava/lang/Object;)Lorg/neo4j/collection/RawIterator; (TransactionBoundQueryContext.scala:802)
  at org.neo4j.cypher.internal.runtime.interpreted.TransactionBoundQueryContext$$anonfun$4.apply(Ljava/lang/Object;)Ljava/lang/Object; (TransactionBoundQueryContext.scala:802)
  at org.neo4j.cypher.internal.runtime.interpreted.TransactionBoundQueryContext.callProcedure(Lscala/collection/Seq;Lscala/Function1;)Lscala/collection/Iterator; (TransactionBoundQueryContext.scala:875)
  at org.neo4j.cypher.internal.runtime.interpreted.TransactionBoundQueryContext.callReadOnlyProcedure(ILscala/collection/Seq;[Ljava/lang/String;)Lscala/collection/Iterator; (TransactionBoundQueryContext.scala:804)
  at org.neo4j.cypher.internal.compatibility.v3_4.ExceptionTranslatingQueryContext$$anonfun$callReadOnlyProcedure$1.apply()Lscala/collection/Iterator; (ExceptionTranslatingQueryContext.scala:146)
  at org.neo4j.cypher.internal.compatibility.v3_4.ExceptionTranslatingQueryContext$$anonfun$callReadOnlyProcedure$1.apply()Ljava/lang/Object; (ExceptionTranslatingQueryContext.scala:146)
  at org.neo4j.cypher.internal.compatibility.v3_4.ExceptionTranslationSupport$class.translateException(Lorg/neo4j/cypher/internal/compatibility/v3_4/ExceptionTranslationSupport;Lscala/Function0;)Ljava/lang/Object; (ExceptionTranslationSupport.scala:33)
  at org.neo4j.cypher.internal.compatibility.v3_4.ExceptionTranslatingQueryContext.translateException(Lscala/Function0;)Ljava/lang/Object; (ExceptionTranslatingQueryContext.scala:41)
  at org.neo4j.cypher.internal.compatibility.v3_4.ExceptionTranslationSupport$class.translateIterator(Lorg/neo4j/cypher/internal/compatibility/v3_4/ExceptionTranslationSupport;Lscala/Function0;)Lscala/collection/Iterator; (ExceptionTranslationSupport.scala:47)
  at org.neo4j.cypher.internal.compatibility.v3_4.ExceptionTranslatingQueryContext.translateIterator(Lscala/Function0;)Lscala/collection/Iterator; (ExceptionTranslatingQueryContext.scala:41)
  at org.neo4j.cypher.internal.compatibility.v3_4.ExceptionTranslatingQueryContext.callReadOnlyProcedure(ILscala/collection/Seq;[Ljava/lang/String;)Lscala/collection/Iterator; (ExceptionTranslatingQueryContext.scala:146)
  at org.neo4j.cypher.internal.runtime.LazyReadOnlyCallMode.callProcedure(Lorg/neo4j/cypher/internal/runtime/QueryContext;ILscala/collection/Seq;)Lscala/collection/Iterator; (ProcedureCallMode.scala:47)
  at org.neo4j.cypher.internal.runtime.interpreted.pipes.ProcedureCallPipe.org$neo4j$cypher$internal$runtime$interpreted$pipes$ProcedureCallPipe$$call(Lorg/neo4j/cypher/internal/runtime/QueryContext;Lscala/collection/Seq;)Lscala/collection/Iterator; (ProcedureCallPipe.scala:83)
  at org.neo4j.cypher.internal.runtime.interpreted.pipes.ProcedureCallPipe$$anon$$$$e6882d5096c8b8441ac36d3c0cc459e$$$$ateResultsByAppending$1.apply(Lorg/neo4j/cypher/internal/runtime/interpreted/ExecutionContext;)Lscala/collection/Iterator; (ProcedureCallPipe.scala:67)
  at org.neo4j.cypher.internal.runtime.interpreted.pipes.ProcedureCallPipe$$anon$$$$e6882d5096c8b8441ac36d3c0cc459e$$$$ateResultsByAppending$1.apply(Ljava/lang/Object;)Ljava/lang/Object; (ProcedureCallPipe.scala:65)
  at scala.collection.Iterator$$anon$12.nextCur()V (Iterator.scala:435)
  at scala.collection.Iterator$$anon$12.hasNext()Z (Iterator.scala:441)
  at scala.collection.Iterator$$anon$11.hasNext()Z (Iterator.scala:409)
  at scala.collection.Iterator$$anon$11.hasNext()Z (Iterator.scala:409)
  at org.neo4j.cypher.internal.compatibility.v3_4.runtime.ClosingIterator.hasNext()Z (ResultIterator.scala:60)
  at scala.collection.Iterator$$anon$11.hasNext()Z (Iterator.scala:409)
  at org.neo4j.cypher.internal.runtime.RuntimeJavaValueConverter$feedIteratorToVisitable.accept(Lorg/neo4j/cypher/result/QueryResult$QueryResultVisitor;)V (RuntimeJavaValueConverter.scala:53)
  at org.neo4j.cypher.internal.compatibility.v3_4.runtime.PipeExecutionResult.accept(Lorg/neo4j/cypher/result/QueryResult$QueryResultVisitor;)V (PipeExecutionResult.scala:115)
  at org.neo4j.cypher.internal.compatibility.ClosingExecutionResult$$anonfun$accept$2.apply$mcV$sp()V (ClosingExecutionResult.scala:174)
  at org.neo4j.cypher.internal.compatibility.ClosingExecutionResult$$anonfun$accept$2.apply()V (ClosingExecutionResult.scala:173)
  at org.neo4j.cypher.internal.compatibility.ClosingExecutionResult$$anonfun$accept$2.apply()Ljava/lang/Object; (ClosingExecutionResult.scala:173)
  at org.neo4j.cypher.exceptionHandler$runSafely$.apply(Lscala/Function0;Lscala/Function1;)Ljava/lang/Object; (exceptionHandler.scala:89)
  at org.neo4j.cypher.internal.compatibility.ClosingExecutionResult.accept(Lorg/neo4j/cypher/result/QueryResult$QueryResultVisitor;)V (ClosingExecutionResult.scala:173)
  at org.neo4j.bolt.v1.runtime.CypherAdapterStream.accept(Lorg/neo4j/bolt/v1/runtime/spi/BoltResult$Visitor;)V (CypherAdapterStream.java:74)
  at org.neo4j.bolt.v1.messaging.BoltMessageRouter$ResultHandler.onRecords(Lorg/neo4j/bolt/v1/runtime/spi/BoltResult;Z)V (BoltMessageRouter.java:146)
  at org.neo4j.bolt.v1.runtime.BoltStateMachine$State$3.lambda$pullAll$0(Lorg/neo4j/bolt/v1/runtime/BoltStateMachine;Lorg/neo4j/bolt/v1/runtime/spi/BoltResult;)V (BoltStateMachine.java:509)
  at org.neo4j.bolt.v1.runtime.BoltStateMachine$State$3$$Lambda$433.accept(Ljava/lang/Object;)V (Unknown Source)
  at org.neo4j.bolt.v1.runtime.TransactionStateMachine$State.consumeResult(Lorg/neo4j/bolt/v1/runtime/TransactionStateMachine$MutableTransactionState;Lorg/neo4j/function/ThrowingConsumer;)Z (TransactionStateMachine.java:422)
  at org.neo4j.bolt.v1.runtime.TransactionStateMachine$State$1.streamResult(Lorg/neo4j/bolt/v1/runtime/TransactionStateMachine$MutableTransactionState;Lorg/neo4j/function/ThrowingConsumer;)V (TransactionStateMachine.java:288)
  at org.neo4j.bolt.v1.runtime.TransactionStateMachine.streamResult(Lorg/neo4j/function/ThrowingConsumer;)V (TransactionStateMachine.java:104)
  at org.neo4j.bolt.v1.runtime.BoltStateMachine$State$3.pullAll(Lorg/neo4j/bolt/v1/runtime/BoltStateMachine;)Lorg/neo4j/bolt/v1/runtime/BoltStateMachine$State; (BoltStateMachine.java:508)
  at org.neo4j.bolt.v1.runtime.BoltStateMachine.pullAll(Lorg/neo4j/bolt/v1/runtime/BoltResponseHandler;)V (BoltStateMachine.java:267)
  at org.neo4j.bolt.v1.messaging.BoltMessageRouter.lambda$onPullAll$6(Lorg/neo4j/bolt/v1/runtime/BoltStateMachine;)V (BoltMessageRouter.java:114)
  at org.neo4j.bolt.v1.messaging.BoltMessageRouter$$Lambda$425.perform(Lorg/neo4j/bolt/v1/runtime/BoltStateMachine;)V (Unknown Source)
  at org.neo4j.bolt.runtime.DefaultBoltConnection.processNextBatch(IZ)Z (DefaultBoltConnection.java:195)
  at org.neo4j.bolt.runtime.DefaultBoltConnection.processNextBatch()Z (DefaultBoltConnection.java:143)
  at org.neo4j.bolt.runtime.ExecutorBoltScheduler.executeBatch(Lorg/neo4j/bolt/runtime/BoltConnection;)Z (ExecutorBoltScheduler.java:170)
  at org.neo4j.bolt.runtime.ExecutorBoltScheduler.lambda$scheduleBatchOrHandleError$2(Lorg/neo4j/bolt/runtime/BoltConnection;)Ljava/lang/Boolean; (ExecutorBoltScheduler.java:153)
  at org.neo4j.bolt.runtime.ExecutorBoltScheduler$$Lambda$417.get()Ljava/lang/Object; (Unknown Source)
  at java.util.concurrent.CompletableFuture$AsyncSupply.run()V (CompletableFuture.java:1590)
  at java.util.concurrent.ThreadPoolExecutor.runWorker(Ljava/util/concurrent/ThreadPoolExecutor$Worker;)V (ThreadPoolExecutor.java:1149)
  at java.util.concurrent.ThreadPoolExecutor$Worker.run()V (ThreadPoolExecutor.java:624)
  at java.lang.Thread.run()V (Thread.java:748)

Any clues what went wrong? I am running neo4j 34.5, graph algo build from master c92bc290ecf9944e2cdf93e65bc1b161cf504876 and java 1.8.0_171.

[mneedham]

Hi,

The paths are collected in a list before being streamed so I wonder if that's causing an issue. The int[] that you're seeing would likely be the collection of nodeIds that get returned.

To try and narrow down the problem could you try running the non streaming version and see if that works?

MATCH (start:Airport{IATA:'KRK'}), (end:Airport{IATA:'DFW'})
CALL algo.kShortestPaths(start, end, 4, 'distance' ,{})
YIELD index, nodeIds, path, costs
RETURN count(*)

Also are you using a public dataset / can you share it with me so I can debug further?

[kcrimson]

I run non streaming version and it ended up with the same OutOfMemory error.

I have attached datasets airports.txt routes.txt

Here are queries I used to import these datasets:

LOAD CSV FROM "file:///airports.dat" as airport
CREATE (:Airport {
AirportID : airport[0],
Name : airport[1],
City : airport[2],
Country : airport[3],
IATA: airport[4],
ICAO: airport[5],
Latitude: toFloat(airport[6]),
Longitude: toFloat(airport[7]),
Altitude: toInteger(airport[8]),
Timezone: airport[9],
DST: airport[10],
TZ: airport[11],
Type: airport[12],
Source: airport[13]
});

CREATE CONSTRAINT ON (a:Airport) ASSERT a.IATA IS UNIQUE;

LOAD CSV FROM "file:///routes.dat" as route
MATCH (s:Airport {AirportID: route[3]})
MATCH (d:Airport {AirportID: route[5]})
CREATE (s)-[:Route {Airline:route[1],Codeshare : [6]}]->(d);

MATCH (a:Airport)-[r:Route]->(b:Airport)
SET r.distance=distance(point({longitude: a.Longitude, latitude : a.Latitude}),point({longitude: b.Longitude, latitude : b.Latitude}))

[kcrimson]

Quick update, The problem is in number of routes between airports, when I limit traversal depth, it runs, but result is empty, and it shouldn't be. Let me give you an example

match p=shortestPath((:Airport {IATA : "KRK"})-[:Route*..4]->(:Airport {IATA : "CFU"})) return p

It returns path through Frankfurt airport. When I run the same, with kShortestPath

MATCH (start:Airport{IATA:'KRK'}), (end:Airport{IATA:'CFU'})
CALL algo.kShortestPaths.stream(start, end, 3, 'distance' ,{maxDepth: 4})
YIELD index, nodeIds, path, costs
RETURN [node in algo.getNodesById(nodeIds) | node.City] AS places,
       costs,
       reduce(acc = 0.0, cost in costs | acc + cost) AS totalCost

returns empty result set. Am I missing something from kShortestPath?

[mneedham]

Hi,

I'm able to reproduce although I had to tweak the loading instructions:

CREATE CONSTRAINT ON (a:Airport) ASSERT a.IATA IS UNIQUE;

LOAD CSV FROM "file:///airports.txt" as airport
MERGE (a:Airport {IATA: airport[4]})
set 
a.AirportID = airport[0],
a.Name = airport[1],
a.City = airport[2],
a.Country = airport[3],

a.ICAO = airport[5],
a.Latitude = toFloat(airport[6]),
a.Longitude = toFloat(airport[7]),
a.Altitude = toInteger(airport[8]),
a.Timezone = airport[9],
a.DST=  airport[10],
a.TZ = airport[11],
a.Type = airport[12],
a.Source = airport[13]
;

create index on :Airport(AirportID);

LOAD CSV FROM "file:///routes.txt" as route
MATCH (s:Airport {AirportID: route[3]})
MATCH (d:Airport {AirportID: route[5]})
CREATE (s)-[:Route {Airline:route[1],Codeshare : [6]}]->(d);

MATCH (a:Airport)-[r:Route]->(b:Airport)
SET r.distance=distance(point({longitude: a.Longitude, latitude : a.Latitude}),point({longitude: b.Longitude, latitude : b.Latitude}))

Will look at how to fix it now

[mneedham]

Hi @kcrimson,

Sorry for the delay in replying again. We have a fix for the OOM on this PR -https://github.com/neo4j-contrib/neo4j-graph-algorithms/pull/712 - but when we set maxDepth it's returning no results so we're still investigating that.

Will let you know when we've got both fixes merged in.

Cheers, Mark

[javarulezzz]

Hi, I faced the situation on release 3.5 when had to set maxDepth=10 in order to get the paths of 5 nodes only. I think the issue is in the verification order : package org.neo4j.graphalgo.impl.yens.Dijkstra

if (d >= maxDepth) {
  continue;
}
if (node == target) {
  return true;
}

By changing the order it returns the right results !

Please confirm