Duy Hai Doan

Part 8 of 10 for the series Gremlin Recipes. The purpose is to explain the internal of <a href="http://tinkerpop.apache.org/docs/3.2.5/reference/#traversal">Gremlin</a> and give people a deeper insight into the query language to master it.

This blog post is the 8th from the series <a href="https://academy.datastax.com/content/gremlin-recipes">Gremlin Recipes</a>. It is recommended to read the previous blog posts first:

<ol>
	<li><a href="https://academy.datastax.com/content/gremlin-traversals">Gremlin as a Stream</a></li>
	<li><a href="https://academy.datastax.com/content/sql-tpo-p">SQL to Gremlin</a></li>
	<li><a href="https://academy.datastax.com/content/gremlin-recipes-3-%E2%80%93-recommendation-engine-traversal">Recommendation Engine traversal</a></li>
	<li><a href="https://academy.datastax.com/content/gremlin-recipes-4-%E2%80%93-recursive-traversals-1">Recursive traversals</a></li>
	<li><a href="https://academy.datastax.com/content/gremlin-recipes-5-%E2%80%93-path-object">Path object</a></li>
	<li><a href="https://academy.datastax.com/content/gremlin-recipes-6-%E2%80%93-projection-and-selection">Projection and selection</a></li>
	<li><a href="https://academy.datastax.com/content/gremlin-recipes-7-%E2%80%93-variables-handling-0">Variable handling</a> 
	&nbsp;</li>
</ol>

<h2>I KillrVideo dataset</h2>

To illustrate this series of recipes, you need first to create the schema for KillrVideo and import the data. See <a href="http://www.doanduyhai.com/blog/?p=13224#killrvideo_dataset">here</a> for more details.

The graph schema of this dataset is :

<h3><iframe height="400px" src="https://s3.amazonaws.com/datastax-graph-schema-viewer/index.html#/?schema=killr_video_small.json" width="100%"></iframe></h3>

<h2>II Introduction to <code>sack()</code></h2>

The <code>sack()</code> step was introduced recently to help people solving some problem more efficiently.

In some case people are writing Gremlin traversals that make use of data aggregation using path information. Typically, people will use <code>path()</code> and then perform “reduction” of the data in the path to get the specific result.

Unfortunately, this is inefficient as path calculations are expensive, not mergable. The same ca be now achieved using <code>sack()</code>.

A sack is a local datastructure relative to each traverser, unlike global datastructure as when using <code>aggregate()/store()/group(x)/subgraph(x)....</code> It mean that each traverser is now equipped with his own sack. A sack can contain any type of data structure:

<ul>
	<li>primitives: Int, Double, Long, …</li>
	<li>collections: List/Set/Map\</li>
</ul>

<h3>A. Defining the sack</h3>

The definition of this data structure should be placed right after the traversal object:

<code>gremlin&gt;g.withSack(1.0).&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; // Define a sack containing an initial double value 
V(). 
... </code>

<code>gremlin&gt;g.withSack([] as Set).&nbsp; &nbsp; &nbsp; // Define a sack containing an initial empty Set 
V(). 
... </code>

<code>gremlin&gt;g.withSack([1,2,3] as Set). // Define a sack containing a pre-initialized Set 
V(). 
... </code>

<code>gremlin&gt;g.withSack([] as List).&nbsp; &nbsp; &nbsp;// Define a sack containing an initial empty List 
V(). 
... </code>

<code>gremlin&gt;g.withSack([:]).&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;// Define a sack containing an initial empty Map 
V(). 
... </code>

<code>gremlin&gt;g.withSack([:].&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; // Define a sack containing an initial empty Map 
withDefault{key -&gt; [] as List}). // with default values being an empty list 
V().</code>

<code>... </code>

The complete signature of the <code>withSack()</code> step is <code>withSack(default_data_structure, split_operator, merge_operator)</code>

<ul>
	<li>split operator is used to split the data structure whenever traverser is facing a branch and needs to duplicate itself. Example: <code>V().has("user","userId", "u861").out("rated")</code>. From the User vertex now there are as many traversers as there are ratings to different movie. Thus the sack structure at User vertex get duplicated</li>
	<li>merge operator is used to merge different sack data structures together whenever all traversers are converging to a single point. Example: <code>g.V().hasLabel("movie").out("director").has("name", "Woody Allen")</code>. The traversers from many Movie vertices are converging to the single Person vertex which is Woody Allen. The sack at vertex Woody Allen is the merge of all sack data structures coming from his movies. If you do not define any merge operator, the sacks cannot be merged</li>
</ul>

Note: for primitive data type, split operator == value copy. For other data types like collection, if you don’t define any split operator, the same object reference will be copied to all branching traversers. Consequently all those traversers will shared the same data structure. Be very wary of this

Some example of defining collection as data structure for sack:

<code>// Define a sack with sum() as merge operator 
// The split operator is implicitly copy-by-value for primitives 
gremlin&gt;g.withSack(1.0, sum). 
&nbsp; &nbsp;V(). 
&nbsp; &nbsp;... </code>

<code>// Define a sack with initial empty Set 
// Split function == Set::clone() 
// Merge function == Set::appendAll() 
g.withSack([] as Set){set-&gt; set.clone()}{setA,setB -&gt; setA.appendAll(setB); setA}. 
&nbsp; &nbsp;V() 
&nbsp; &nbsp;... </code>

<code>// Define a sack with initial empty Map 
// Split function == Map::clone() 
// Merge function == Map::putAll() gremlin&gt;g.withSack([:]){it.clone}{mapA,mapB -&gt; mapA.putAll(mapB); mapA}. 
&nbsp; &nbsp;V(). 
&nbsp; &nbsp;... </code>

<h3>B. Mutating the sack</h3>

To mutate the content of the sack, you can use the step <code>sack(bi-function).by(projection_axis)</code>.

<ul>
	<li>bi-function is a function with signature: <code>DATA_STRUCTURE apply(DATA_STRUCTURE current, X projected_value)</code>

	<ul>
		<li>DATA_STRUCTURE is the type of the data structure inside the sack (primitives, collections, …) initially defined with <code>g.withSack(DATA_STRUCTURE)</code></li>
		<li>X is the type of the projected value on the current vertex/edge using the modulator <code>by()</code></li>
	</ul>
	</li>
	<li>projection_axis is the property/inner traversal result applied on a vertex/edge</li>
</ul>

<h3>C. Accessing the sack</h3>

The sack data structure can be accessed at any time by calling the step <code>sack()</code>. The data type returned by this step is <code>Iterator</code>

<h2>III Usage of <code>sack()</code></h2>

<code>gremlin&gt;g.withSack(0).V(). 
&nbsp; &nbsp;has("movie", "title", "Blade Runner").&nbsp; &nbsp; // Iterator<movie> </movie> 
&nbsp; &nbsp;<movie>inE("rated").&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;// Iterator<rated_edge> </rated_edge></movie> 
&nbsp; &nbsp;&nbsp; &nbsp;<movie><rated_edge>sack(sum).by("rating").&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; // iterator.sideEffect(sack -&gt; sack.get() + values("rating")) </rated_edge></movie> 
&nbsp; &nbsp;<movie><rated_edge>outV().&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;// Iterator<user> </user></rated_edge></movie> 
&nbsp; &nbsp;<movie><rated_edge><user>sack()&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; // Iterator<int> 
==&gt;6 
==&gt;5 
==&gt;8 </int></user></rated_edge></movie> 
<movie><rated_edge><user><int>==&gt;8 </int></user></rated_edge></movie><movie><rated_edge><user><int> 
==&gt;8 
==&gt;8 </int></user></rated_edge></movie><movie><rated_edge><user><int> 
==&gt;9 
... </int></user></rated_edge></movie></code>

In the above traversal the interesting step is <code>inE("rated").sack(sum).by("rating").outV()</code>. On each edge “rated”, we add the value “rating” into the sack value. Please note the usage of <code>by("rating")</code> acting as projection for the <code>sack()</code>. Sum is the bi-function <code>Int apply(Int current, Int projected_value)</code>

When the traversal reaches step <code>outV()</code> there are as many traversers as there are users rating Blade Runner and each of those traversers carries a sack containing the value of the rating. When calling <code>sack()</code> the content of each sack is extracted and therefor we have an <code>Iterator</code>

Computing Blade Runner average rating with <code>sack()</code> is really easy:

<code>gremlin&gt;g.withSack(0).V(). 
&nbsp; &nbsp;has("movie", "title", "Blade Runner").&nbsp; &nbsp; // Iterator<movie> </movie> 
&nbsp; &nbsp;<movie>inE("rated").&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;// Iterator<rated_edge> </rated_edge></movie> 
&nbsp; &nbsp;&nbsp; &nbsp;<movie><rated_edge>sack(sum).by("rating").&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; //&nbsp;iterator.sideEffect(sack -&gt; sack.get()&nbsp;+ values("rating")) </rated_edge></movie> 
&nbsp; &nbsp;<movie><rated_edge>outV(). </rated_edge></movie>&nbsp; &nbsp; &nbsp; &nbsp; &nbsp;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp;&nbsp; &nbsp; &nbsp; &nbsp;<movie><rated_edge>// Iterator<user> </user></rated_edge></movie> 
&nbsp; &nbsp;<movie><rated_edge><user>sack(). </user></rated_edge></movie>&nbsp; &nbsp; &nbsp; &nbsp; &nbsp;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp;&nbsp; &nbsp; &nbsp; &nbsp;<movie><rated_edge><user>// Iterator<int> </int></user></rated_edge></movie> 
&nbsp; &nbsp;<movie><rated_edge><user><int>mean() </int></user></rated_edge></movie> 
<movie><rated_edge><user><int>==&gt;8.20353982300885 </int></user></rated_edge></movie></code>

Now let’s see how we can use <code>sack()</code> for useful purposes. First you need to import the schema of London Tube as described in this <a href="http://www.doanduyhai.com/blog/?p=13320">previous post</a>.

Then switch g alias to London_Tube

<code>gremlin&gt;:remote config alias g London_Tube.g</code>

<code>==&gt;g=London_Tube.g</code>

One of the goal in this blog post was to find the shortest path between South Kensington and Marble Arch tube stations. Shortest path can mean either least stations count or least line changes.

<h3>Shortest path by least stations count</h3>

<code>gremlin&gt;g.withSack(0).V(). 
&nbsp; &nbsp;has("station", "name", "South Kensington"). // Iterator<station> </station> 
&nbsp; &nbsp;<station>emit(). </station>&nbsp; &nbsp;<station>repeat(timeLimit(400). </station> 
&nbsp; &nbsp;&nbsp; &nbsp;<station>bothE("connectedTo"). </station> 
&nbsp; &nbsp;&nbsp; &nbsp;<station>otherV(). </station> 
&nbsp; &nbsp;&nbsp; &nbsp;<station>sack(sum).by(constant(1)). // +1 </station> 
&nbsp; &nbsp;&nbsp; &nbsp;<station>simplePath()). </station> 
&nbsp; &nbsp;<station>has("name", "Marble Arch"). </station> 
&nbsp; &nbsp;<station>order(). // Order each journey </station> 
&nbsp; &nbsp;&nbsp; &nbsp;<station>by(sack(),incr). // by the sack value, </station><station> 
ASCENDING </station> 
&nbsp; &nbsp;<station>limit(1). </station> 
&nbsp; &nbsp;<station>path().by( </station> 
&nbsp; &nbsp;&nbsp; &nbsp;<station>choose(label). </station> 
&nbsp; &nbsp;&nbsp; &nbsp;<station>option("station", values("name")). </station> 
&nbsp; &nbsp;&nbsp; &nbsp;<station>option("connectedTo", constant("--&gt;"))) 
==&gt;[South Kensington, --&gt;, Knightsbridge, --&gt;, Hyde Park Corner, --&gt;, Green Park, --&gt;, Bond Street, --&gt;, Marble Arch] </station></code>

The interesting pieces are:

<ul>
	<li><code>sack(sum).by(constant(1))</code>: for each traversed station, we increment the counter by +1</li>
	<li><code>order().by(sack(),incr)</code>: order each journey by the counter in each sack, ASCENDING order</li>
</ul>

<h3>Shortest path by least line changes</h3>

<code>gremlin&gt;g.withSack([] as Set){it.clone()}{a,b -&gt; a.addAll(b); a}. 
&nbsp; &nbsp;V(). 
&nbsp; &nbsp;has("station", "name", "South Kensington"). // Iterator<station> </station> 
&nbsp; &nbsp;<station>emit(). </station> 
&nbsp; &nbsp;<station>repeat(timeLimit(400). </station> 
&nbsp; &nbsp;&nbsp; &nbsp;<station>bothE("connectedTo"). </station> 
&nbsp; &nbsp;&nbsp; &nbsp;<station>sack{set,val -&gt; set.add(val); set}.by("line"). </station> 
&nbsp; &nbsp;&nbsp; &nbsp;<station>otherV(). </station> 
&nbsp; &nbsp;&nbsp; &nbsp;<station>simplePath()). </station> 
&nbsp; &nbsp;<station>has("name", "Marble Arch"). </station><station></station> 
&nbsp; &nbsp;<station>order().</station><station>&nbsp;// Order each journey by(sack().count(local),incr). // by the sack number of element, ASCENDING </station> 
&nbsp; &nbsp;<station>limit(1). </station> 
&nbsp; &nbsp;<station>path().by( </station> 
&nbsp; &nbsp;&nbsp; &nbsp;<station>choose(label). </station> 
&nbsp; &nbsp;&nbsp; &nbsp;<station>option("station", values("name")). </station> 
&nbsp; &nbsp;&nbsp; &nbsp;<station>option("connectedTo", constant("--&gt;"))) 
==&gt;[South Kensington, --&gt;, Gloucester Road, --&gt;, High Street Kensington, --&gt;, Notting Hill Gate, --&gt;, Queensway, --&gt;, Lancaster Gate, --&gt;, Marble Arch] </station></code>

Let’s dig into the traversal:

<ul>
	<li><code>withSack([] as Set)</code>: defines a sack with an empty Set</li>
	<li><code>{it.clone()}</code>: defines the split operator for the set, which is just cloning the set itself</li>
	<li><code>{a,b -&gt; a.addAll(b); a}</code>: defines the merge operator for the set, which is just appending all contents of the sets together</li>
	<li>Please notice the Groovy closure syntax to pass lambdas as arguments to the <code>withSack()</code> method. More details about this syntax is given <a href="http://groovy-lang.org/semantics.html#_calling_a_method_accepting_a_sam_type_with_a_closure">here</a></li>
	<li><code>sack{set,val -&gt; set.add(val); set}.by("line")</code>: on each traversed “connectedTo” edge, we add the “line” property to our set inside the sack</li>
	<li><code>order().by(sack().count(local),incr)</code>: we order the journeys by the number of lines inside each sack. Please notice the usage of <code>sack().count(local)</code>. Since the sack() type is now an <code>Iterator&gt;</code> we need the local keyword to count the number of element in the nested set</li>
</ul>

And that’s all folks! Do not miss the other Gremlin recipes in this series.

If you have any question about Gremlin, find me on the <a href="http://datastaxacademy.slack.com/">datastaxacademy.slack.com</a>, channel dse-graph. My id is @doanduyhai

Gremlin Recipes: 8 – Sack() Operator

Duy Hai Doan

Discover more

Share

Share

I KillrVideo dataset

II Introduction to sack()

A. Defining the sack

B. Mutating the sack

C. Accessing the sack

III Usage of sack()

Shortest path by least stations count

Shortest path by least line changes

More Technology

How Winweb Built its AI Assistant with DataStax Astra DB and LangChain

Vercel + Astra DB: Get Data into Your GenAI Apps Fast

Simplifying Agent Development with Astra DB Connector for Vertex AI Search

Making Astra DB easier for MongoDB developers

One-stop Data API for Production GenAI