What is the fundamental bytecode for TP4?

[Marko Rodriguez]

Hello,

As you know, one of the major objectives of TP4 is to generalize the virtual machine in order to support any data structure (not just graph).

Here is an idea that Kuppitz and I batted around yesterday and I spent this morning implementing on the tp4/ branch. 

From the Stream Ring Theory paper [https://zenodo.org/record/2565243], we know that universal computation is possible with branch, initial, map, flatmap, filter, reduce stream-based functions. If this is the case, why not make those instructions the TP4 VM instruction set. 

If 

arg = constant | bytecode | method call, 

then the general pattern for each instruction type is:

[branch, (arg, bytecode)*]

[initial, arg]

[map, arg]

[flatmap, arg]

[filter, ?predicate, arg]

[reduce, operator, arg]

Let this be called the “core instruction set."

Now check this out:

g.inject(7L).choose(is(7L), incr()).sum()

[initial(7), branch([filter(eq,7)],[map(number::add,1)]), reduce(sum,0)]

g.inject(Map.of("name", "marko", "age", 29)).hasKey(regex("[a].*[e]")).has("name", "marko").value("age");

[initial({age=29, name=marko}), filter([flatmap(map::keys), filter(regex,[a].*[e])]), filter([map(map::get,name), filter(eq,marko)]), map(map::get,age)]

These core bytecode chunks currently execute on Pipes and Beam processors as expected.

Pretty trippy eh? 

Now the beautiful thing about this is:

1. Implementing a TP4 VM is trivial. All you have to do is support 6 instruction types.

- You could rip out a TP4 VM implementation in 1-2 days time.

- We can create a foundational C#, Python, C/C++, etc. TP4 VM implementation.

- this foundation can then be evolved over time at our leisure. (see next point)

2. More advanced TP4 VMs will compile the the core bytecode to a TP4 VM-native bytecode.

- This is just like Java’s JIT compiler. For example, the core instruction:

  filter([map(dictionary::get,name), filter(eq,marko)])

is compiled to the TP4-Java instruction:

  has(name,marko)

- Every processor must be able to work with core bytecode, but can support VM native instructions such as has(), is(), path(), loops(), groupCount(), etc.

- These instructions automatically work for all integrating processors (e.g. Pipes, Beam, Akka — on the TP4-Java VM).

- these higher-level instructions don’t require any updates to the processors as these are still (abstractly) filter, flatmap, reduce, etc. functions.

3. Core bytecode is as data agnostic as you can possibly get.

- Data structures are accessed via method call references — e.g. map::keys, list::get, vertex::outEdges, etc.

- Adding new data structures is simply a matter of adding new datatypes.

- The TP4 VM can be used as a general purpose, universal stream-based VM.

Here is the conceptual mapping between Java and TP4 terminology:

Java sourcecode <=> Gremlin traversal

Java bytecode <=> Core bytecode

JIT trees <=> TP4-Java-native bytecode

Machine code <=> Processor execution plan

Its a pretty intense move and all the kinks haven’t been fully worked out, but its definitely something to consider.

Your questions and comments are welcome.

Take care,

Marko.

http://rredux.com

[Stephen Mallette]

Do you/kuppitz think that the reduced/core instruction set means that complex strategy development is simplified? on the surface, less instructions sounds like it will be easier to reason about patterns when providers go to build strategies, but I'm not sure. I kinda wonder if it just shoves the complexity down into analyzing the arguments of the instructions themselves or other contexts associated with the instructions.........maybe too early to tell. I'm just really hoping that TP4 can offer what TP3 didn't, which was an easy way to reason about complex query patterns. we promised that with "tools" in TP3 but those never really materialized (attempts were made, but nothing seemed to stick really). 

--
You received this message because you are subscribed to the Google Groups "Gremlin-users" group.
To unsubscribe from this group and stop receiving emails from it, send an email to gremlin-user...@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/gremlin-users/0C21D862-0F7A-4827-81F4-360E20E52B8F%40gmail.com.
For more options, visit https://groups.google.com/d/optout.

[Ben Krug]

As an outsider of sorts, this was my thought, too.  Supposedly 'mov' is Turing-complete, but I wouldn't want to program with just that.

(https://www.cl.cam.ac.uk/~sd601/papers/mov.pdf)  

Ideally, you have a core language that guides you in how to think, model, and approach, then probably extensions for greater flexibility.

(As in SQL to "guide" (force?) you, then PL/SQL or TSQL or UDFs, etc.)  The core should be simple, but not too simple, and avoid redundancy.

Hopefully that's the goal.

To view this discussion on the web visit https://groups.google.com/d/msgid/gremlin-users/CAA-H439KWqSjgzuznK-8NTbX5zGc4ovB8pyd4gZQCX-5p_9NeQ%40mail.gmail.com.

[Marko Rodriguez]

Hello,

(As in SQL to "guide" (force?) you, then PL/SQL or TSQL or UDFs, etc.)  The core should be simple, but not too simple, and avoid redundancy.

If you look at how I currently have it set up, we have “core instruction set” and “common instruction set.” Common is your standard count, group, sum, repeat, etc (~20 instructions). Core is only 6 instructions — branch, initial, map, flatmap, filter, and reduce. Every time an instruction is added to common, the respective core instruction is also added. The test suite for Pipes uses common and the test suite for Beam uses core. By just riding out these two instruction set branches I hope to see a pattern emerge and perhaps a “common/core instruction set” can be converged upon.

And yes, redundancy is a big flaw in the TP3 instruction set. This popped up on the radar early due to the stream ring theory article and initial stabs on TP4 development. I suspect that the common instruction set will have 1/3 of the instructions of TP3.

I kinda wonder if it just shoves the complexity down into analyzing the arguments of the instructions themselves or other contexts associated with the instructions.........maybe too early to tell. I'm just really hoping that TP4 can offer what TP3 didn't, which was an easy way to reason about complex query patterns. we promised that with "tools" in TP3 but those never really materialized (attempts were made, but nothing seemed to stick really).

The problem with TP3 reasoning is that you are reasoning at the “step” level, not at the “instruction” level. In TP3, after bytecode, the compilation goes to Pipes. This was a wrong move. It meant that we had to embed one execution engine (Pipes) into another (Spark, e.g.). In TP4, we compile from bytecode to CFunctions (coefficient functions). CFunctions do not assume an execution engine. They are simply Map, FlatMap, Reduce, Initial, Branch, and Filter functions (stateless functions). It is then up to the execution engine to coordinate these functions accordingly. Thus, the strategy reasoning in TP3 was awkward because you had to work at manipulating methods/fields on Pipe steps (i.e. object reasoning). In TP4, you manipulate [op,arg*]-instructions (i.e. primitive array reasoning).

I have not flushed out strategies to any great extent in TP4, but I believe they will be easier to write than in TP3. However, I sorta don’t think strategies are going to go the same direction as they did in TP3. I’m having some inklings that we are not thinking about bytecode optimization in the most elegant way… 

Take care,

Marko.

http://rredux.com

On Mar 30, 2019, at 10:00 AM, Ben Krug <ben....@datastax.com> wrote:

As an outsider of sorts, this was my thought, too.  Supposedly 'mov' is Turing-complete, but I wouldn't want to program with just that.

(https://www.cl.cam.ac.uk/~sd601/papers/mov.pdf)  

Ideally, you have a core language that guides you in how to think, model, and approach, then probably extensions for greater flexibility.

To view this discussion on the web visit https://groups.google.com/d/msgid/gremlin-users/CAG4Qc%2B64MaBLUwY9PiTje3T_1PxbbEaTN%2BcrZfywadDpU07o2Q%40mail.gmail.com.

[Daniel Kuppitz]

Do you/kuppitz think that the reduced/core instruction set means that complex strategy development is simplified?

It should be easier. Kinda. Strategies no longer have to check for all kind of combinations (like is there a filter() OR a where() OR an and() OR ....). Now, on the other hand, that also means, that bytecode becomes more complex (longer and more nestings), but if we can come up with a BytecodeHelper utility class, that makes it easier to identify patterns, then this shouldn't be a big problem.

Imagine how a pattern matching DSL would make that much simpler. E.g. to rewrite part of the EarlyLimitStrategy you would do something like this:

// move range() step behind the last step that was not a map- or sideEffect-step.

bytecode.instructions().is(without(map(), sideEffect())).as('a').

repeat(any()).

  until(is(range())).as('b').

select('a').addInstruction(select('b')).

select('b').drop()

Using Gremlin to optimize Gremlin, pretty sure that at least Marko is gonna like that :).

Supposedly 'mov' is Turing-complete, but I wouldn't want to program with just that.

You don't program with just that, you'll still have a neat step library, it's just the bytecode that's made of super simple core instructions.

Cheers,

Daniel

On Sat, Mar 30, 2019 at 6:15 AM Stephen Mallette <spmal...@gmail.com> wrote:

To view this discussion on the web visit https://groups.google.com/d/msgid/gremlin-users/CAA-H439KWqSjgzuznK-8NTbX5zGc4ovB8pyd4gZQCX-5p_9NeQ%40mail.gmail.com.

[Jerry Wang]

Hi,

> The problem with TP3 reasoning is that you are reasoning at the “step” level, not at the “instruction” level. In TP3, after bytecode, the compilation goes to Pipes. This was a wrong move. It meant that we had to embed one execution engine (Pipes) into another (Spark, e.g.). In TP4, we compile from bytecode to CFunctions (coefficient functions). CFunctions do not assume an execution engine. They are simply Map, FlatMap, Reduce, Initial, Branch, and Filter functions (stateless functions). It is then up to the execution engine to coordinate these functions accordingly. Thus, the strategy reasoning in TP3 was awkward because you had to work at manipulating methods/fields on Pipe steps (i.e. object reasoning). In TP4, you manipulate [op,arg*]-instructions (i.e. primitive array reasoning).

We have just made a cloud-native graph database (https://cn.aliyun.com/product/gdb) which implements TinkerPop 3.4. During the development process i felt that it's not so convenient to write customized optimization strategies with TP3 framework. Every strategy needs to care about so many kinds of steps, and our customers are often confused about them too. I'm also trying to classify the steps for the next version and it's now (Filter Branch FlatMap Reduce) + (SideEffect). I think that Map is just a concrete type of FlatMap which result count is always one, and Initial is also a concrete type of FlatMap which converts graph traversal source to a vertex/edge stream.

In addition, the embedded function/closure/UDF feature is very useful and widely used by our internal customers. But those steps are very difficult to be processed by the parallel execution engine, and it was disabled in public cloud version due to security issues. It's much harder to write graph algorithms with just pure gremlin steps. The function/closure/UDF feature is so important for our customers, and i think it would be easier to use if there was a standardized function/closure format defined in gremlin. It's also more friendly to the query optimization strategy and the execution engine.

Thanks

Jerry

http://rredux.com

To unsubscribe from this group and stop receiving emails from it, send an email to gremli...@googlegroups.com.

To view this discussion on the web visit https://groups.google.com/d/msgid/gremlin-users/0C21D862-0F7A-4827-81F4-360E20E52B8F%40gmail.com.
For more options, visit https://groups.google.com/d/optout.

--
You received this message because you are subscribed to the Google Groups "Gremlin-users" group.

To unsubscribe from this group and stop receiving emails from it, send an email to gremli...@googlegroups.com.

To view this discussion on the web visit https://groups.google.com/d/msgid/gremlin-users/CAA-H439KWqSjgzuznK-8NTbX5zGc4ovB8pyd4gZQCX-5p_9NeQ%40mail.gmail.com.
For more options, visit https://groups.google.com/d/optout.

--
You received this message because you are subscribed to the Google Groups "Gremlin-users" group.

To unsubscribe from this group and stop receiving emails from it, send an email to gremli...@googlegroups.com.

[Marko Rodriguez]

Hello Jerry,

We have just made a cloud-native graph database (https://cn.aliyun.com/product/gdb) which implements TinkerPop 3.4.

Nice product page. If you are interested in listing your database on our homepage, please read through our “listing policies” and get back to us:

http://tinkerpop.apache.org/policy.html

During the development process i felt that it's not so convenient to write customized optimization strategies with TP3 framework. Every strategy needs to care about so many kinds of steps, and our customers are often confused about them too. I'm also trying to classify the steps for the next version and it's now (Filter Branch FlatMap Reduce) + (SideEffect). I think that Map is just a concrete type of FlatMap which result count is always one, and Initial is also a concrete type of FlatMap which converts graph traversal source to a vertex/edge stream.

This is exactly what I think too. However, two amendments to your classification. First, a filter is just a flatmap that returns 0 or 1 elements. Second, you need to account for non-reducing barriers such as Order and Aggregate, where reduce is a type of barrier with a non-identity aggregation function. Thus, I believe that the most abstract categories are:

Branch

FlatMap

Barrier

SideEffect

However, with that said, if you keep Filter, you get nice algebraic properties such as idempotence and commutativity.  And if you keep Map, then you get inversion. Finally, if you keep Reduce, you know you have a many-to-one. These properties are important when reasoning with strategies. Thus, in practice, this seems to be the most useful classification:

Branch

Map

Filter

FlatMap

Barrier

Reduce

SideEffect

This is the classification used in TinkerPop4 (+ Initial, but you might be right about that category not being important). With your comment about “too many step types,” note that TP4 does not compile to steps like TP3. Instead, TP4 compiles bytecode to an intermediate non-parameterized function-based representation. This means that reasoning doesn’t require knowing what the steps are/do (beyond their abstract Branch/Map/Filter/etc. form). In other words, you don’t have to worry about tweaking the methods/fields of Step objects because there are none! This makes incorporating new processors into TP4 dead simple. With respects to strategies, TP4 applies strategies at the bytecode-level and yea, its a bunch of ops to consider. … :( … this is why I want to reduce our instruction set as much as possible. Moreover, I believe we are doing something wrong with strategies (in TP3 and TP4) but I don’t know a better way.

In addition, the embedded function/closure/UDF feature is very useful and widely used by our internal customers. But those steps are very difficult to be processed by the parallel execution engine, and it was disabled in public cloud version due to security issues. It's much harder to write graph algorithms with just pure gremlin steps. The function/closure/UDF feature is so important for our customers, and i think it would be easier to use if there was a standardized function/closure format defined in gremlin. It's also more friendly to the query optimization strategy and the execution engine.

That is a good idea. Instead of language-specific closures, we have a Gremlin-specific closure. That is smart.

I think we also need to clean up the language a bit. There are some algorithms that are hard/awkward to express. It would be great if we had a GoogleDoc of awkward queries so we could study them and realize patterns.

Fun email Jerry,

Marko.

http://rredux.com

To unsubscribe from this group and stop receiving emails from it, send an email to gremlin-user...@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/gremlin-users/f0832387-0892-4cf1-961c-33732ab0bb68%40googlegroups.com.

[Stephen Mallette]

Hi, Jerry, 

It looks like GDB already meets our listing requirements for the TinkerPop web site. I will post something to the dev list to ensure everyone is fine with the addition.

Are there any other links/references that you think would be useful to understanding your product? Or perhaps you could just post some of the key differentiating features that it is has?

Thanks,

Stephen

To unsubscribe from this group and stop receiving emails from it, send an email to gremlin-user...@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/gremlin-users/f0832387-0892-4cf1-961c-33732ab0bb68%40googlegroups.com.

[Jerry Wang]

Hi, Marko & Stephen,

Are there any other links/references that you think would be useful to understanding your product? Or perhaps you could just post some of the key differentiating features that it is has?

Thank you very much. Here is some information about Alibaba GDB:

- What is Alibaba GDB? Alibaba GDB is a real-time, reliable, cloud-native graph database service that supports property graph model. It's every efficient for storing and querying highly connected data. GDB is highly compatible with TinkerPop gremlin query language, provides fully ACID transaction guarantee, rich SDK, tools and multiple maintenance features.

- Public URL

https://cn.aliyun.com/product/gdb

- Documents https://help.aliyun.com/knowledge_detail/102799.html

- TinkerPop/Gremlin version

3.4.0

- Gremlin implementation differences https://help.aliyun.com/document_detail/102883.html

- Product Logo Please find the attached file for the logo.

Thanks

Jerry

[Jerry Wang]

Hi,

Sorry, I need to correct some words due to legal issues.

The english name of our product is `Alibaba Graph Database'.

- What is Alibaba Graph Database? Alibaba Graph Database (GDB) is a real-time, reliable, cloud-native graph database service that supports property graph model. It's every efficient for storing and querying highly connected data. GDB is highly compatible with TinkerPop gremlin query language, provides fully ACID transaction guarantee, rich SDK, tools and multiple maintenance features.

Thanks

Jerry