The Beauty of Bulking -- Redux'prise

[Marko Rodriguez <ok...@gmail.com>]

Hello,

Many moons ago, I wrote an email to this list called “The Beauty of Bulking” which discussed the concept of traverser bulking.

This notion is perhaps the most important aspect of the Gremlin traversal machine. It is what makes OLAP scale, speedy complex path-calculations plausible, and runtimes on reverberant traversals extremely fast.

Bulking can be summed up easily:

1. If you have a stream of numbers, say [6, 5, 4, 4, 4, 6] you can map() those numbers by *10 and thus do 6 arithmetic operations to yield [60, 50, 40, 40, 40, 60].
2. However, if stream ordering does not matter (an important constraint to lift!), then you could get the “same” result with only 3 arithmetic operations and yield [60, 60, 50, 40, 40, 40].
3. In short, “bulk” your objects — 6(2), 5(1), 4(3). Then you only need to execute *10 three times.

Prior to this moment, the beauty of bulking has made itself apparent in every OLAP job executed as well as in repeat(), barrier(), and the epic work from Ted Wilmes on PathRetractionStrategy.

Kuppitz and I are adding to this subtle beauty with a rewrite of LazyBarrierStrategy and its inclusion into the default TraversalStrategies that are inherited (typically) by all graph system providers.

Lets look at what we have done to master/ and what you can expect in TinkerPop 3.2.3.

graph = TinkerGraph.open()
graph.io(gryo()).readGraph('data/grateful-dead.kryo')
g1 = graph.traversal().withoutStrategies(LazyBarrierStrategy.class)
g2 = graph.traversal()

From g1 (no beauty) and g2 (beautiful), lets see how various traversals perform.

gremlin> clock(10){g1.V().out().in().out().count().iterate()}
==>1073.5150449999999
gremlin> clock(10){g2.V().out().in().out().count().iterate()}
==>8.8109061

Deep traversals with lots of intersections do the best. A 1 second query is dropped to 8 milliseconds. Thats a 100x+ speed improvement.

gremlin> clock(1000){g1.V().out().values('name').iterate()}
==>1.1394026739999998
gremlin> clock(1000){g2.V().out().values('name').iterate()}
==>1.030407659

Not that much intersection above, but we still get a little bump in performance.

**DRUM ROLL — THE PHOENIX RISES FROM THE TEXTS OF EDFU**

Lets get practical. 

Graph analysis is all about “reverberation.” What does that mean? — look at any graph algorithm. Its not about just “getting data," its about seeing how paths intersect/overlay/loop amongst themselves and each other. Paths tell you a lot about the “structure” of your data — topological statistics. PageRank, Betweenness, Eccentricity, Eigenvectors, Recommendations, Spreading Activation, …. these algorithms are all about the paths, not “the data." Lets look at a classic Amazon.com <http://amazon.com/>-style recommendation algorithm:

	“Person ‘a' likes X. X are liked by people B. People B like Y. Recommend ‘a’ items from Y that are not in X.”

g.V(89).out('followedBy').aggregate('a').
  in('followedBy').out(‘followedBy').
    where(not(within('a'))).
  groupCount().by('name')

Okay. So lets do that walk on our toy graph, where Person ‘a’ is v[89].

gremlin> clock(100){g1.V(89).out('followedBy').aggregate('a').in('followedBy').out('followedBy').where(not(within('a'))).groupCount().by('name').iterate()}
==>23.73006225
gremlin> clock(100){g2.V(89).out('followedBy').aggregate('a').in('followedBy').out('followedBy').where(not(within('a'))).groupCount().by('name').iterate()}
==>1.4410725199999999

So there you have it. The classic, “everyone and their mother does it”-traversal went from 23ms to 1.4ms. A 20x performance improvement on a practical everyday example.

gremlin> g2.V(89).out('followedBy').aggregate('a').in('followedBy').out('followedBy').where(not(within('a'))).groupCount().by('name').explain()
==>Traversal Explanation
================================================================================================================================================================================================================================================================================================================
Original Traversal                 [GraphStep(vertex,[89]), VertexStep(OUT,[followedBy],vertex), AggregateStep(a), VertexStep(IN,[followedBy],vertex), VertexStep(OUT,[followedBy],vertex), WherePredicateStep(without([a])), GroupCountStep(value(name))]
...
LazyBarrierStrategy          [O]   [GraphStep(vertex,[89]), VertexStep(OUT,[followedBy],vertex), AggregateStep(a), VertexStep(IN,[followedBy],vertex), NoOpBarrierStep(10000), VertexStep(OUT,[followedBy],vertex), NoOpBarrierStep(10000), WherePredicateStep(without([a])), GroupCountStep(value(name))]
...
Final Traversal                    [TinkerGraphStep(vertex,[89]), VertexStep(OUT,[followedBy],vertex), AggregateStep(a), VertexStep(IN,[followedBy],vertex), NoOpBarrierStep(10000), VertexStep(OUT,[followedBy],vertex), NoOpBarrierStep(10000), WherePredicateStep(without([a])), GroupCountStep(value(name))]

Word to your mutha,
Marko.

http://markorodriguez.com