In this post we will look at running the LDBC SNB on Virtuoso.

First, let’s recap what the benchmark is about:

1. fairly frequent short updates, with no update contention worth
   mentioning
2. short random lookups
3. medium complex queries centered around a person’s social environment

The updates exist so as to invalidate strategies that rely too heavily
on precomputation. The short lookups exist for the sake of realism;
after all, an online social application does lookups for the most part.
The medium complex queries are to challenge the DBMS.

The DBMS challenges have to do firstly with query optimization, and
secondly with execution with a lot of non-local random access patterns.
Query optimization is not a requirement, per se, since imperative
implementations are allowed, but we will see that these are no more free
of the laws of nature than the declarative ones.

The workload is arbitrarily parallel, so intra-query parallelization is
not particularly useful, if also not harmful. There are latency
constraints on operations which strongly encourage implementations to
stay within a predictable time envelope regardless of specific query
parameters. The parameters are a combination of person and date range,
and sometimes tags or countries. The hardest queries have the potential
to access all content created by people within 2 steps of a central
person, so possibly thousands of people, times 2000 posts per person,
times up to 4 tags per post. We are talking in the millions of key
lookups, aiming for sub-second single-threaded execution.

The test system is the same as used in
the TPC-H series:
dual Xeon E5-2630, 2x6 cores x 2 threads, 2.3GHz, 192 GB RAM. The
software is the feature/analytics branch of v7fasttrack, available from www.github.com.

The dataset is the SNB 300G set, with:

As an initial step, we run the benchmark as fast as it will go. We use
32 threads on the driver side for 24 hardware threads.

Below are the numerical quantities for a 400K operation run after 150K
operations worth of warmup.

Duration: 10:41.251
Throughput: 623.71 (op/s)

The statistics that matter are detailed below, with operations ranked in
order of descending client-side wait-time. All times are in
milliseconds.

At this point we have in-depth knowledge of the choke points the
benchmark stresses, and we can give a first assessment of whether the
design meets its objectives for setting an agenda for the coming years
of graph database development.

The implementation is well optimized in general but still has maybe 30%
room for improvement. We note that this is based on a compressed column
store. One could think that alternative data representations, like
in-memory graphs of structs and pointers between them, are better for
the task. This is not necessarily so; at the least, a compressed column
store is much more space efficient. Space efficiency is the root of cost
efficiency, since as soon as the working set is not in memory, a random
access workload is badly hit.

The set of choke points (technical challenges) actually revealed by the
benchmark is so far as follows:

• Cardinality estimation under heavy data skew — Many queries take
  a tag or a country as a parameter. The cardinalities associated
  with tags vary from 29M posts for the most common to 1 for the least
  common. Q6 has a common tag (in top few hundred) half the time and a
  random, most often very infrequent, one the rest of the time. A
  declarative implementation must recognize the cardinality implications
  from the literal and plan accordingly. An imperative one would have to
  count. Missing this makes Q6 take about 40% of the time instead of 4.1%
  when adapting.
• Covering indices — Being able to make multi-column indices that
  duplicate some columns from the table often saves an entire table
  lookup. For example, an index onpost by author can also contain
  the post’s creation date.
• Multi-hop graph traversal — Most queries access a two-hop
  environment starting at a person. Two queries look for shortest paths of
  unbounded length. For the two-hop case, it makes almost no difference
  whether this is done as a union or a special graph traversal operator.
  For shortest paths, this simply must be built into the engine; doing
  this client-side incurs prohibitive overheads. A bidirectional shortest
  path operation is a requirement for the benchmark.
• Top K — Most queries returning posts order results by
  descending date. Once there are at least k results, anything older
  than the __k__th can be dropped, adding a dateselection as early as
  possible in the query. This interacts with vectored execution, so that
  starting with a short vector size more rapidly produces an initial
  top k.
• Late projection — Many queries access several columns and touch
  millions of rows but only return a few. The columns that are not used in
  sorting or selection can be retrieved only for the rows that are
  actually returned. This is especially useful with a column store, as
  this removes many large columns (e.g., text of a post) from the working
  set.
• Materialization — Q14 accesses an expensive-to-compute edge weight,
  the number of post-reply pairs between two people. Keeping this
  precomputed drops Q14 from the top place. Other materialization would be
  possible, for example Q2 (top 20 posts by friends), but since Q2 is just
  1% of the load, there is no need. One could of course argue that this
  should be 20x more frequent, in which case there could be a point to
  this.
• Concurrency control — Read-write contention is rare, as updates are
  randomly spread over the database. However, some pages get read very
  frequently, e.g., some middle level index pages in the post table.
  Keeping a count of reading threads requires a mutex, and there is
  significant contention on this. Since the hot set can be one page,
  adding more mutexes does not always help. However, hash partitioning the
  index into many independent trees (as in the case of a cluster) helps
  for this. There is also contention on a mutex for assigning threads to
  client requests, as there are large numbers of short operations.

In subsequent posts, we will look at specific queries, what they in fact
do, and what their theoretical performance limits would be. In this way
we will have a precise understanding of which way SNB can steer the
graph DB community.

SNB Interactive Series

• SNB Interactive, Part 1: What is SNB Interactive Really About?
• SNB Interactive, Part 2: Modeling Choices
• SNB Interactive, Part 3: Choke Points and Initial Run on Virtuoso