Note: consider this post as a continuation of the “Making it interactive” post by Orri Erling.

I have now completed the Virtuoso TPC-H work, including scale out. Optimization possibilities extend to infinity but the present level is good enough. TPC-H is the classic of all analytics benchmarks and is difficult enough, I have extensive commentary on this on my blog (In Hoc Signo Vinces series), including experimental results. This is, as it were, the cornerstone of the true science. This is however not the totality of it. From the LDBC angle, we might liken this to the last camp before attempting a mountain peak.

So, we may now seriously turn to graph analytics. The project has enough left to run in order to get a good BI and graph analytics workload. In LDBC in general, as in the following, BI or business intelligence means complex analytical queries. Graph analytics means graph algorithms that are typically done in graph programming frameworks or libraries.

The BI part is like TPC-H, except for adding the following challenges:

• Joins of derived tables with group by, e.g. comparing popularity of items on consecutive time periods.

• Transitive dimensions - A geographical or tag hierarchy can be seen as a dimension table. To get the star schema plan with the selective hash join, the count of the transitive traversal of the hierarchy (hash build side) must be correctly guessed.

• Transitivity in fact table, i.e. average length of reply thread. There the cost model must figure that the reply link is much too high cardinality for hash build side, besides a transitive operation is not a good candidate for a build in multiple passes, hence the plan will have to be by index.

• Graph traversal with condition on end point and navigation step. The hierarchical dimensions and reply threads are in fact trees, the social graph is not. Again the system must know some properties of connectedness (in/out degree, count of vertices) to guess a traversal fanout. This dictates the join type in the step (hash or index). An example is a transitive closure with steps satisfying a condition, e.g. all connected persons have a specific clearance.

• Running one query with parameters from different buckets, implying different best plan.

• Data correlations, e.g. high selectivity arising from two interests seldom occurring together, in places where the correct estimation makes the difference between a good and a bad plan.

• Large intermediate results stored in tables, as in materializing complex summaries of data for use in follow up queries.

• More unions and outer joins.

The idea is to cover the base competences the world has come to expect and to build in challenges to last another 10-15 years.

For rules and metric, we can use the TPC-H or TPC-DS ones as a template. The schema may differ from an implementation of the interactive workload, as these things would normally run on different systems anyway. As another activity that is not directly LDBC, I will do a merge of SNB and Open Street Map. The geolocated things (persons, posts) will get real coordinates from their vicinity and diverse geo analytics will become possible. This is of some significant interest to Geoknow, another FP7 where OpenLink is participating.

Doing the BI mix and even optimizing the interactive part involves some redoing of the present support for transitivity in Virtuoso. The partitioned group by with some custom aggregates is the right tool for the job, with all parallelization, scale-out, etc ready. You see, TPC-H is very useful also in places one does not immediately associate with it.

As a matter of fact, this becomes a BSP (bulk synchronous processing) control structure. Run any number of steps, each item produces results/effects scattered across partitions. The output of the previous is the input of the next. We might say BSP is an attractor or “Platonic” control structure to which certain paths inevitably lead. Last year I did a BSP implementation in SQL, reading and writing tables and using transactions for serializable update of the border. This is possible but will not compete with a memory based framework and not enough of the optimization potential, e.g. message combining, is visible to the engine in this formulation. So, now we will get this right, as suggested.

So, the transitive derived table construct can have pluggable aggregations, e.g. remembering a path, a minimum length or such), reduction like a scalar-valued aggregate (min/max), different grouping sets like in a group by with cube or grouping sets, some group-by like reduction for message combining and so forth. If there is a gather phase that is not just the result of the scatter of the previous step, this can be expressed as an arbitrary database query, also cross partition in a scale-out setting.

The distributed/partitioned group by hash table will be a first class citizen, like a procedure scoped temporary table to facilitate returning multiple results and passing large data between multiple steps with different vertex operations, e.g. forward and backward in betweenness centrality.

This brings us to the graph analytics proper, which is often done in BSP style, e.g. Pregel, Giraph, Signal-Collect, some but not all Green-Marl applications. In fact, a Green-Marl back end for Virtuoso is conceivable, whether one will be made is a different matter.

With BSP in the database engine, a reference implementation of many standard algorithms is readily feasible and performant enough to do reasonable sizing for the workload and to have a metric. This could be edges or vertices per unit of time, across a mix of algorithms, for example. Some experimentation will be needed. The algorithms themselves may be had from the Green-Marl sample programs or other implementations. Among others, Oracle would presumably agree that this sort of functionality will in time migrate into core database. We will here have a go at this and along the way formulate some benchmark tasks for a graph analytics workload. Whenever feasible, this will derive from existing work such as graphbench.org but will be adapted to the SNB dataset.

The analytics part will be done with more community outreach than the interactive one. I will blog about the business questions, queries and choke points as we go through them. The interested may pitch in as the matter comes up.