The quest of OpenLink
Software is to bring flexibility, efficiency, and expressive
power to people working with data. For the past several years, this
has been focused on making graph data models viable for the
enterprise. Flexibility in schema evolution is a central aspect of
this, as is the ability to share identifiers across different
information systems, i.e., giving things URIs instead of synthetic
keys that are not interpretable outside of a particular
application.
With Virtuoso
7, we dramatically improve the efficiency of all this. With
databases in the billions of relations (also known as triples, or
3-tuples), we can fit about 3x as many relations in the same space
(disk and RAM) as with Virtuoso 6. Single-threaded query speed is
up to 3x better, plus there is intra-query parallelization even in
single-server configurations. Graph data workloads are all about
random lookups. With these, having data in RAM is all-important.
With 3x space efficiency, you can run with 3x more data in the same
space before starting to go to disk. In some benchmarks, this can
make a 20x gain.
Also the Virtuoso scale-out support is fundamentally reworked,
with much more parallelism and better deployment flexibility.
So, for graph data, Virtuoso 7 is a major step in the coming of
age of the technology. Data keeps growing and time is getting
scarcer, so we need more flexibility and more performance at the
same time.
So, let’s talk about how we accomplish this. Column stores have
been the trend in relational data warehousing for over a decade.
With column stores comes vectored execution, i.e., running any
operation on a large number of values at one time. Instead of
running one operation on one value, then the next operation on the
result, and so forth, you run the first operation on thousands or
hundreds-of-thousands of values, then the next one on the results
of this, and so on.
Column-wise storage brings space efficiency, since values in one
column of a table tend to be alike -- whether repeating, sorted,
within a specific range, or picked from a particular set of
possible values. With graph data, where there are no columns as
such, the situation is exactly the same -- just substitute the word
predicate for column. Space efficiency brings speed
-- first by keeping more of the data in memory; secondly by having
less data travel between CPU and memory. Vectoring makes sure that
data that are closely located get accessed in close temporal
proximity, hence improving cache utilization. When there is no
locality, there are a lot of operations pending at the same time,
as things always get done on a set of values instead of on a single
value. This is the crux of the science of columns and
vectoring.
Of the prior work in column stores, Virtuoso may most resemble
Vertica, well described in Daniel Abadi’s famous PhD
thesis. Virtuoso itself is described in IEEE Data
Engineering Bulletin, March
2012 (PDF). The
first experiments in column store technology with Virtuoso were in
2009, published at the SemData workshop at VLDB 2010 in Singapore. We tried
storing TPC H as
graph data and in relational tables, each with both rows and
columns, and found that we could get 6 bytes per quad space
utilization with the RDF-ization of TPC H, as opposed to 27 bytes
with the row-wise compressed RDF storage model. The row-wise
compression itself is 3x more compact than a row-wise
representation with no compression.
Memory is the key to speed, and space efficiency is the key to
memory. Performance comes from two factors: locality and
parallelism. Both are addressed by column store technology. This
made me a convert.
At this time, we also started the EU FP7 project, LOD2, most specifically working with
Peter
Boncz of CWI, the king of the column store, famous for MonetDB and VectorWise. This cooperation goes
on within LOD2 and has extended to LDBC,
an FP7 for designing benchmarks for graph and RDF databases. Peter
has given us a world of valuable insight and experience in all
aspects of avant garde database, from adaptive techniques to
query optimization and beyond. One thing that was recently
published is the results for
Virtuoso cluster at CWI, running analytics on 150 billion
relations on CWI’s SciLens cluster.
The SQL relational table-oriented databases and property
graph-oriented databases (Graph for short) are both rooted in
relational database science. Graph management simply introduces
extra challenges with regards to scalability. Hence, at OpenLink
Software, having a good grounding in the best practices of
relational columnar (or column-wise) database management technology
is vital.
Virtuoso is more prominently known for high-performance
RDF-based graph database technology, but the entirety of its SQL
relational data management functionality (which is the foundation
for graph store) is vectored, and even allows users to choose
between row-wise and column-wise physical layouts, index by
index.
It has been asked: is this a new NoSQL engine? Well, there isn’t
really such a thing. There are of course database engines that do
not have SQL support and it has become trendy to call them "NoSQL."
So, in this space, Virtuoso is an engine that does support
SQL, plus SPARQL, and is designed to do big joins and aggregation
(i.e., analytics) and fast bulk load, as well as ACID transactions
on small updates, all with column store space efficiency. It is not
only for big scans, as people tend to think about column stores,
since it can also be used in compact embedded form.
Virtuoso also delivers great parallelism and throughput in a
scale-out setting, with no restrictions on transactions and no
limits on joining. The base is in relational database science, but
all the adaptations that RDF and graph workloads need are built-in,
with core level support for run-time data-typing, URIs as native
Reference types, user-defined custom data types, etc.
Now that the major milestone of releasing Virtuoso 7 (open
source and commercial
editions) has been reached, the next steps include enabling our
current and future customers to attain increased agility from big
(linked) open data exploits. Technically, it will also include
continued participation in DBMS industry benchmarks, such as those
from the TPC, and others under development
via the Linked Data Benchmark Council (LDBC), plus other
social-media-oriented challenges that arise in this exciting data
access, integration, and management innovation continuum. Thus,
continue to expect new optimization tricks to be introduced at
frequent intervals through the open source development branch at
GitHub, between major commercial
releases.
Related
since 2005.
