TinkerPop extensions to go faster (long)

[Luca Garulli]

Hi all,

by talking about Blueprints with some Graph related people I've heard that Blueprints are slow and vendors can't extend them to go faster using native features. This is partially true because Blueprints interfaces are very simple and cover the basic requirements to work with Graphs. But this is also a very good thing because all the complexity is hidden to the developers and vendors.ueprints 

So how to get the best of both "easy to development" and "optimization"?

Here comes my idea.

The bigger reason why Blueprints could be slow with traversal (that is the most common/requested feature for a GraphDB!) is that creates a new Java object every time a vertex and an edge is traversed. If you have a vertex with 100 edges, then to traverse just 1 level in depth you have at least 1 (vertex) + 100 (edges) + 100 (connected vertexes) = 201 objects (at least but there are also iterators and other stuff).

With 2 levels things are much worst: 1 (vertex) + 100 (edges) + 100 (connected vertexes)  + 10,000 edges + 10,000 vertexes = 20,201 objects 

These objects are mostly temporary because are needed just to reach the good ones, but the Garbage Collector is quite stressed because has to count them, free, etc.

 

Today when I execute a GREMLIN statement this flow is executed:

GREMLIN -> PIPES -> BLUEPRINTS -> OrientDB API

So why don't add just few callbacks to optimize the built Pipes? If I had a listener interface I could reduce all the steps by using specific GraphDB vendor optimizations.

public interface PipeBuilding {

  void afterCreation( List<Pipes> pipes );

}

In this case I could replace the 3 traversal pipe entries with just one OrientDBOutE pipe implementation that execute the traversal of the 2 levels in just one command by using native API. The new path would be:

GREMLIN -> PIPES +---> BLUEPRINTS -> OrientDB VENDOR

                 |                    ^

                 |                    |

                 +--------------------+

Where some Pipe command can bypass Blueprints API to go directly at GraphDB level.

Think to Nth levels of depth, the benefits will be enormous.

WDYT? Any thoughts?

Luca Garulli

OrientDB

www.orientechnologies.com

[Darrick Wiebe]

Hi Luca,

I think you're right on. I've been thinking about building some implementation specific pipes that I could have Pacer automatically use rather than the vanilla pipes where possible. I don't have a super pressing need for that yet, but definitely will eventually, and the speed would be nice any time.

I'm curious how you could deal with the combinatorial explosion of the different types of pipes that may be chained together though. Even to handle basic traversals there are quite a few pipes!

Cheers,

Darrick

[Alex Averbuch]

Hey guys,

I'm not sure if I follow your email completely Luca but regarding the combinatorial explosion, is it possible to default to the vanilla pipes when no implementation specific version exists?

In the case when some pipe types don't have an implementation specific version, Gremlin would insert a vanilla pipe instead. 

E.g. OrientPipeX -> VanillaPipeY -> OrientPipeZ

With this approach there would also be a need for TranslatorPipes/BridgePipes though. For example, something that takes a graph Element and converts it to a native OrientDB element. 

E.g. OrientPipeX -> OrientVanillaBridge -> VanillaPipeY -> VanillaOrientBridge -> OrientPipeZ

Using this approach you wouldn't need to implement all pipe types at once... implementation specific pipes could be added lazily as needed, and Gremlin users wouldn't have to worry about what functionality is supported by what vendor (as that would be counter to the whole idea of blueprints as I understand it)... every graph db would support the same traversal types, but some may be more optimized for Gremlin than others.

[Luca Garulli]

Hi,

exactly. By default all works as before, but a vendor could optimize some steps in, for example, just one. Most/all GraphDBs have own API to traverse/search/index things in efficient way and in this way the entire TinkerPop stack would be not broken, but just "optimized" depending by the vendor.

Luca Garulli

OrientDB

www.orientechnologies.com

[Claudio Martella]

As the problem is with traversals, doesn't it make more sense to make
pipes implemented by different vendors, just like blueprints.

Blueprints would still make sense, because it would allow accessing
the api of graphdbs, pipes would allow vendors to implement pipes
efficiently but still keeping composability.

The design would still be completely transparent without weird callbacks.

--
    Claudio Martella
    claudio....@gmail.com

[Tobias Ivarsson]

Hi Luca,

I've been having the exact same thoughts, and prototyped it a few weeks ago - feels really nice. I discussed this with Marko last time I met him, but we didn't have time to get anywhere deeper into it.

But to summarize, I am all for providing a hook where the vendor gets the opportunity to optimize a pipeline.

What the actual SPI for that should look like is something to be discussed, but I agree with the idea.

Cheers,

Tobias

--
Tobias Ivarsson <tobias....@neotechnology.com>
Hacker, Neo Technology
www.neotechnology.com
Cellphone: +46 706 534857

[Rajeev B]

HI Luca,

You are very right about the object creation & garbage collection
overheads, I remember, java.io.File.list() is many times faster than
java.io.File.listFiles().

regards,
Rawjeev.

> www.orientechnologies.com <http://www.orientechnologies.com>
>

[Marko Rodriguez]

Hi everyone,

These are all very nice ideas. I have two comments.

----------------------

1. I will create a benchmark for doing a traversal using raw Neo4j and using Blueprints to see what the speed differences are. That is, to get a quantitative idea regarding how inefficient the "object wrapping" model that Blueprints employs is.

2. Instead of doing this seemingly complicated work around Blueprints (i.e. callbacks), it might be a good idea for graph database provides to provide native implementations of Blueprints. That is, for example in OrientDB, OGraphVertex implements Vertex. This way, there is no object wrapping and vendors can implement getOutEdges(), getInEdges(), etc. etc. as they see fit.

----------------------

I fear changing the flow of Gremlin --> Pipes --> Blueprints ---> GraphDB. I fear this because it feels like a workaround hack that simply drives the graph database vendors code further up the TinkerPop stack instead of being nicely abstracted by Blueprints. Moreover, it then yields a "free for all" on what Pipe operations exist for which vendors. This obviously then will bleed into Gremlin and could pollute Gremlin by yielding vendor specific code.

As such, I feel #2 is the best solution. If the vendors simply implement Blueprints by making their respective objects (e.g. Node in Neo4j, OGraphVertex in OrientDB) implement the Blueprints interfaces then two excellent things happen:

1. Blueprints is no longer the holder of all the Blueprints implementation code. Neo4j and OrientDB will simply release as "Blueprints-enabled."
2. There will no longer exist the "object wrapping" model as Blueprints interfaces are native to the underlying graphDB. Thus, seemingly much more efficient.

From there, working with the graph database vendors to ensure that the Blueprints interfaces have all the methods they need for efficient evaluation of traversals would come next. This will then alter which Pipes exist, and thus, what Gremlin looks like. This, of course, is a delicate matter that needs to balanced between all vendors so there isn't a rampart growth of methods/interfaces that make Blueprints difficult to adopt and comprehend.

Thanks,
Marko.

http://markorodriguez.com

>> GREMLIN -> PIPES -> BLUEPRINTS -> OrientDB API
>>

[Claudio Martella]

marko,

how do you see the idea of allowing vendors to implement pipes like
they implement now blueprints?

--
    Claudio Martella
    claudio....@gmail.com

[Marko Rodriguez]

HI Claudio,

> how do you see the idea of allowing vendors to implement pipes like
> they implement now blueprints?

If the vendors implement Blueprints "native" (that is, e.g., neo4j.Node implements Vertex), then there would be no need to implement their own Pipes. The desire to implement new pipes would be more of a desire to add new methods to Blueprints.

Again, the trick to all this is to not let the vendors ride *up* the stack or else it will be a versioning/API nightmare. My counter solution to Luca's is to push TinkerPop further *down* the stack where Blueprints is native to the vendor's object system.

Thanks,
Marko.

http://markorodriguez.com

[Marko Rodriguez]

Hello,

I performed a benchmark comparing Neo4j raw (Node, Relationship) and Blueprints Neo4jGraph (Vertex, Edge) to see if Blueprints object wrapping is in fact causing performance problems.

EXPERIMENT: Using the GratefulDead graph (809 vertices, 8049 edges), for each vertex in the graph, I traverse to a depth of 3. This touches 29,601,779 elements.

SUMMARY: Neo4j (Raw) takes, on average, 5.6 seconds to touch 29.6 million elements. Neo4jGraph (Blueprints) takes, on average, 6.0 seconds to touch 29.6 million elements.

Here are the results of the experiment. Attached is the source code of the experiment.

------------------------------------------------------------------------------------

NEO4J RAW --- GraphDatabase/Node/Relationship

Testing testNeo4jRaw...
EmbeddedGraphDatabase [/tmp/blueprints_test]: 29601779 Neo4j raw elements touched in 8836.18994140625ms
EmbeddedGraphDatabase [/tmp/blueprints_test]: 29601779 Neo4j raw elements touched in 5439.324951171875ms
EmbeddedGraphDatabase [/tmp/blueprints_test]: 29601779 Neo4j raw elements touched in 5510.56787109375ms
EmbeddedGraphDatabase [/tmp/blueprints_test]: 29601779 Neo4j raw elements touched in 5315.5068359375ms
EmbeddedGraphDatabase [/tmp/blueprints_test]: 29601779 Neo4j raw elements touched in 4995.390869140625ms
EmbeddedGraphDatabase [/tmp/blueprints_test]: 29601779 Neo4j raw elements touched in 5152.767822265625ms
EmbeddedGraphDatabase [/tmp/blueprints_test]: 29601779 Neo4j raw elements touched in 5154.794921875ms
EmbeddedGraphDatabase [/tmp/blueprints_test]: 29601779 Neo4j raw elements touched in 5063.9501953125ms
EmbeddedGraphDatabase [/tmp/blueprints_test]: 29601779 Neo4j raw elements touched in 5472.148193359375ms
EmbeddedGraphDatabase [/tmp/blueprints_test]: 29601779 Neo4j raw elements touched in 5215.058837890625ms
Neo4jRaw: 1 Neo4j Raw experiment average time in 5615.570043945312ms

------------------------------------------------------------------------------------

NEO4J BLUEPRINTS --- Neo4jGraph/Vertex/Edge

Testing testNeo4jGraph...
neo4jgraph[EmbeddedGraphDatabase [/tmp/blueprints_test]]: 29601779 Neo4jGraph elements touched in 6556.494140625ms
neo4jgraph[EmbeddedGraphDatabase [/tmp/blueprints_test]]: 29601779 Neo4jGraph elements touched in 5934.42724609375ms
neo4jgraph[EmbeddedGraphDatabase [/tmp/blueprints_test]]: 29601779 Neo4jGraph elements touched in 6072.413818359375ms
neo4jgraph[EmbeddedGraphDatabase [/tmp/blueprints_test]]: 29601779 Neo4jGraph elements touched in 6182.333251953125ms
neo4jgraph[EmbeddedGraphDatabase [/tmp/blueprints_test]]: 29601779 Neo4jGraph elements touched in 6034.69580078125ms
neo4jgraph[EmbeddedGraphDatabase [/tmp/blueprints_test]]: 29601779 Neo4jGraph elements touched in 6133.049072265625ms
neo4jgraph[EmbeddedGraphDatabase [/tmp/blueprints_test]]: 29601779 Neo4jGraph elements touched in 6110.630859375ms
neo4jgraph[EmbeddedGraphDatabase [/tmp/blueprints_test]]: 29601779 Neo4jGraph elements touched in 6059.311767578125ms
neo4jgraph[EmbeddedGraphDatabase [/tmp/blueprints_test]]: 29601779 Neo4jGraph elements touched in 6037.650146484375ms
neo4jgraph[EmbeddedGraphDatabase [/tmp/blueprints_test]]: 29601779 Neo4jGraph elements touched in 5805.708984375ms
Neo4jGraph: 1 Neo4jGraph experiment average time in 6092.6715087890625ms

Thanks,
Marko.

http://markorodriguez.com

[Konrad]

Wonder how this numbers looks like with OrientDB...

[Darrick Wiebe]

Where I see the larger benefit is to build optimized pipes that use smarter ways to filter the data coming out of the database so that iteration over elements that will not be emitted does not happen at all. For instance, if I get the out edges labeled "x" from some vertices, right now pipes iterates all out edges regardless of label and filters out any one not labelled "x". That works great but I think some graph databases might be able to give you the filtered stream directly without iterating over the unwanted elements. In some cases that could be a massive optimization, if it's possible.

Darrick

[Marko Rodriguez]

Hi,

Yes. My argument to this is to extend the Blueprints API to support, e.g. getOutEdges(String label). This is already a ticket in Blueprints:

https://github.com/tinkerpop/blueprints/issues#issue/71

Once this is added to Blueprints, then a new Pipe can be created called VertexEdgeLabelFilterPipe. (or whatever name-wise). The point being though, this Pipe would be Blueprints-based, not vendor-based.

Take care,

Marko.

http://markorodriguez.com

[Claudio Martella]

That is exactly my point.

The idea of building pipes on blueprints brings to a necessary loss of
signal. You go from the semantics of a traversal to the semantics of
object retrieval. This way the graphdb/blueprints has to behave as
simple as possible.

--
    Claudio Martella
    claudio....@gmail.com

[Darrick Wiebe]

That makes sense to me, I like it.

[Claudio Martella]

Yes, that would solve Darrick's scenario.

I actually don't think neo4j would gain much from that pipe as neo4j
has to scan through the whole adjancency list anyway to extract
certain edges (the edges are not grouped by label at storage level).

So, to clarify my argument, I just mean that where, at storage level,
looking up an Element costs more than keep on going through a path by
following a pointer (so splitting and resuming the traversal per step
costs more than not splitting it), the implementation of pipes by
vendors would be more efficient. But then you might argue that it's
their design's fault as they're not designing on graphs efficiently.

And I'd agree with you :)

--
    Claudio Martella
    claudio....@gmail.com

[Konrad]

I like that idea too!

Doing some smart integration/glue between a property-matching pipe and the index support (of most graphs) maybe?

/Konrad

[Paul Jackson]

It would seem that any native functionality a vendor might need at the
pipes level could be abstracted at the blueprints level. In the
iterate-by-property example, if the blueprints interface included a
method for that, the vendor could implement it efficiently. This
means that the blueprint interface could begin to bloat, but I would
suggest that blueprints could include an abstract class with a core
set of methods left abstract and default implementations for the
rest. Then a vendor can optionally override any methods that they can
perform more efficiently with native calls.

Thanks,
-Paul

On Feb 11, 12:27 pm, Claudio Martella <claudio.marte...@gmail.com>
wrote:

> > On Fri, Feb 11, 2011 at 11:59 AM, Konrad <konrad.eriks...@gmail.com> wrote:
>
> >> Wonder how this numbers looks like with OrientDB...
>
> --
>     Claudio Martella

>     claudio.marte...@gmail.com

[Marko A. Rodriguez]

Hello,

Luca has been working hard on the new OrientDB/Blueprints connector.
Below is the results of using raw OrientDB vs. using Blueprints
OrientGraph. NOTE: Once OrientDB 0.9.25 releases, we will release the
next version of Blueprints.

-----

EXPERIMENT: Using the GratefulDead graph (809 vertices, 8049 edges),
for each vertex in the graph, I traverse to a depth of 3. This touches
29,601,779 elements.

SUMMARY: OrientDB (Raw) takes, on average, 7.2 seconds to touch 29.6
million elements. OrientGraph (Blueprints) takes, on average, 7.9

seconds to touch 29.6 million elements.

Testing testOrientGraph... (BLUEPRINTS)
orientgraph[/tmp/blueprints_test/graph]: 29601779 OrientGraph
elements touched in 8146.876220703125ms
orientgraph[/tmp/blueprints_test/graph]: 29601779 OrientGraph
elements touched in 8436.0068359375ms
orientgraph[/tmp/blueprints_test/graph]: 29601779 OrientGraph
elements touched in 8110.18994140625ms
orientgraph[/tmp/blueprints_test/graph]: 29601779 OrientGraph
elements touched in 8731.837890625ms
orientgraph[/tmp/blueprints_test/graph]: 29601779 OrientGraph
elements touched in 7435.18994140625ms
orientgraph[/tmp/blueprints_test/graph]: 29601779 OrientGraph
elements touched in 7492.3017578125ms
orientgraph[/tmp/blueprints_test/graph]: 29601779 OrientGraph
elements touched in 7416.652099609375ms
orientgraph[/tmp/blueprints_test/graph]: 29601779 OrientGraph
elements touched in 7533.107177734375ms
orientgraph[/tmp/blueprints_test/graph]: 29601779 OrientGraph
elements touched in 7767.848388671875ms
orientgraph[/tmp/blueprints_test/graph]: 29601779 OrientGraph
elements touched in 8656.845703125ms
OrientGraph: 1 OrientGraph experiment average in 7972.685595703125ms

Testing testOrientRaw... (ORIENTDB)
OrientDB[/tmp/blueprints_test/graph]: 29601779 Orient raw elements
touched in 7319.750244140625ms
OrientDB[/tmp/blueprints_test/graph]: 29601779 Orient raw elements
touched in 7080.5009765625ms
OrientDB[/tmp/blueprints_test/graph]: 29601779 Orient raw elements
touched in 6780.31689453125ms
OrientDB[/tmp/blueprints_test/graph]: 29601779 Orient raw elements
touched in 6991.20703125ms
OrientDB[/tmp/blueprints_test/graph]: 29601779 Orient raw elements
touched in 8712.87109375ms
OrientDB[/tmp/blueprints_test/graph]: 29601779 Orient raw elements
touched in 7404.9970703125ms
OrientDB[/tmp/blueprints_test/graph]: 29601779 Orient raw elements
touched in 7168.717041015625ms
OrientDB[/tmp/blueprints_test/graph]: 29601779 Orient raw elements
touched in 6860.284912109375ms
OrientDB[/tmp/blueprints_test/graph]: 29601779 Orient raw elements
touched in 7210.66796875ms
OrientDB[/tmp/blueprints_test/graph]: 29601779 Orient raw elements
touched in 6749.993896484375ms
OrientRaw: 1 OrientDB Raw experiment average in 7227.930712890625ms
*** TOTAL TIME [OrientBenchmarkTestSuite]: 207396.31323242188 ***

Thanks,
Marko.

http://markorodriguez.com

>  Neo4jBenchmarkTestSuite.java
> 4KViewDownload