We ran the
Dbpedia benchmark queries again with different
configurations of
Virtuoso. I had not studied the details of the
matter previously but now did have a closer look at the
queries.
Comparing numbers given by different parties is a constant
problem. In the case reported here, we loaded the full
Dbpedia 3,
all languages with about 198M triples on
Virtuoso 5 and 6 cluster,
all on the same 4 core 2GHz Xeon with 8G RAM. All databases were
striped on 6 disks. The cluster configuration was with 4 processes
in the same box.
We ran the queries in two variants: The first was with graph
specified in the
SPARQL from clause, using the default indices. The
second variant was with no graph specified anywhere, using an
alternate indexing scheme.
The times below are for the sequence of 5 queries, individual
query times are not reported. I did not do a line by line review of
the execution plans since they seem to run well enough. We could
get some extra mileage from cost model tweaks, specially for the
numeric range conditions but we will do this when somebody comes up
with better times.
First about 5: Because there is a query in the set that
specifies no condition on S or O and only P, this simply cannot be
done with the default indices. With 6 it sort of can because 6 is
more space efficient.
So we added the index:
create bitmap index rdf_quad_pogs on rdf_quad (p, o, g, s);
5 with gspo, ogps, pogs
cold 210s
warm 0.600s
6 cluster with gspo, ogps
cold 136s
warm 4.01 s
6 cluster with gspo, ogpps, pogs
cold 33.4s
warm 0.628 s
OK, so now let us do it without a graph being specified. For
all platforms, we do:
- Drop any existing indices.
create table r2 (g iri_id_8, s, iri_id_8, p iri_id_8, o any, primary key (s, p, o, g))
alter index R2 on R2 partition (s int (0hexffff00));
log_enable (2);
insert into r2 (g, s, p, o) select g, s, p, o from rdf_quad;
drop table rdf_quad;
alter table r2 rename RDF_QUAD;
create bitmap index rdf_quad_opgs on rdf_quad (o, p, g, s) partition (o varchar (-1, 0hexffff));
create bitmap index rdf_quad_pogs on rdf_quad (p, o, g, s) partition (o varchar (-1, 0hexffff));
create bitmap index rdf_quad_gpos on rdf_quad (g, p, o, s) partition (o varchar (-1, 0hexffff));
The code is identical for 5 and 6, except that with 5 we use
iri_id (32 bit) for the type, not iri_id_8 (64 bit). We note that
we run out of id's with 5 around a few billion triples, so with 6
we have double the id length and still manage to be vastly more
space efficient.
With the above 4 indices, we can query the
data pretty much in
any combination without hitting a full scan of any index. We note
that all indices that do not begin with s end with s as a bitmap.
This is about 60% of the space of a non-bitmap index for
data such
as Dbpedia.
If you intend to do completely arbitrary RDF queries in
Virtuoso, then chances are you are best off with the above index
scheme.
5 with spog, pogs, opgs, gpos
warm 0.595 s
6 cluster with spog, pogs, opgs, gpos
warm 0.617 s
The cold times were about the same as above, so not
reproduced.
Graph or No Graph?
It is in the
SPARQL spirit to specify a graph and for pretty
much any application, there are entirely sensible ways of keeping
the data in graphs and specifying which ones are concerned by
queries. This is why Virtuoso is set up for this by default.
On the other hand, for the open web scenario, dealing with an
unknown large number of graphs, enumerating graphs is not possible
and questions like which graph of which source asserts x become
relevant. We have two distinct use cases which warrant a different
setup of the database, simple as that.
The latter use case is not really within the SPARQL spec, so
implementations may or may not support this. For example
Oracle or
Vertica would not do this well since they partition data according
to graph or predicate, respectively. On the other hand stores that
work with one quad table, which is most of the ones out there
should do it maybe with some configuring, as shown above.
Frameworks like Jena are not to my
knowledge geared towards
having a wildcard for graph, although I would suppose this can be
arranged by adding some "super-graph" object, a graph of all
graphs. I don't think this is directly supported and besides most
apps would not need it.
Once the indices are right, there is no difference between
specifying a graph and no graph with the queries considered. With
more complex queries, specifying a graph or set of graphs does
allow some optimizations that cannot be done with graph missing.
For example, bitmap intersections are possible only when all
leading key parts are given.
Conclusions
The best warm cache time is with 5, the five queries under
600 ms after the first go. This is to show that all in memory with
a single thread of execution is hard to beat.
The 6 cluster performs the same in 623 ms. What is gained in
parallelism is lost in latency if all operations complete in
microseconds. On the other hand, 6 cluster leaves 5 in the dust in
any situation that has less than 100% hit rate. This is due to
actual benefit from parallelism if operations take longer than a
few microseconds, such as in the case of disk reads. 6 has
substantially better data layout on disk, as well as fewer pages to
load for the same content.
This makes it possible to run the queries without the pogs
index on 6 even when 5 took prohibitively long.
The morale of the story is to have a lot of RAM and space
efficient data representation.
The Dbpedia benchmark does not specify any random access
pattern that would give a measure of sustained throughput under
load, so we are left with the extremes of cold and warm cache of
which neither is quite realistic.
Chris Bizer and I have talked on and off about benchmarks and
I have made suggestions that we will see incorporated into the
Berlin SPARQL benchmark, which will, I believe, be much more
informative.
Appendix: Query Text
For reference, the query text is below, with graph given. To
run without specifying the graph, just drop the from
<
http://dbpedia.org>. The returned row counts are indicated
below the query text.
sparql SELECT ?p ?o from <http://dbpedia.org> WHERE {
<http://dbpedia.org/resource/Metropolitan_Museum_of_Art> ?p ?o };
-- 1337 rows
sparql PREFIX p: <http://dbpedia.org/property/>
SELECT ?film1 ?actor1 ?film2 ?actor2
from <http://dbpedia.org> WHERE {
?film1 p:starring <http://dbpedia.org/resource/Kevin_Bacon> .
?film1 p:starring ?actor1 .
?film2 p:starring ?actor1 .
?film2 p:starring ?actor2 . };
-- 23910 rows
sparql PREFIX p: <http://dbpedia.org/property/>
SELECT ?artist ?artwork ?museum ?director from <http://dbpedia.org>
WHERE {
?artwork p:artist ?artist .
?artwork p:museum ?museum .
?museum p:director ?director };
-- 303 rows
sparql PREFIX geo: <http://www.w3.org/2003/01/geo/wgs84_pos#>
PREFIX foaf: <http://xmlns.com/foaf/0.1/>
PREFIX xsd: <http://www.w3.org/2001/XMLSchema#>
SELECT ?s ?homepage from <http://dbpedia.org> WHERE {
<http://dbpedia.org/resource/Berlin> geo:lat ?berlinLat .
<http://dbpedia.org/resource/Berlin> geo:long ?berlinLong .
?s geo:lat ?lat .
?s geo:long ?long .
?s foaf:homepage ?homepage .
FILTER (
?lat <= ?berlinLat + 0.03190235436 &&
?long >= ?berlinLong - 0.08679199218 &&
?lat >= ?berlinLat - 0.03190235436 &&
?long <= ?berlinLong + 0.08679199218) };
-- 56 rows
sparql PREFIX geo: <http://www.w3.org/2003/01/geo/wgs84_pos#>
PREFIX foaf: <http://xmlns.com/foaf/0.1/>
PREFIX xsd: <http://www.w3.org/2001/XMLSchema#>
PREFIX p: <http://dbpedia.org/property/>
SELECT ?s ?a ?homepage from <http://dbpedia.org> WHERE {
<http://dbpedia.org/resource/New_York_City> geo:lat ?nyLat .
<http://dbpedia.org/resource/New_York_City> geo:long ?nyLong .
?s geo:lat ?lat .
?s geo:long ?long .
?s p:architect ?a .
?a foaf:homepage ?homepage .
FILTER (
?lat <= ?nyLat + 0.3190235436 &&
?long >= ?nyLong - 0.8679199218 &&
?lat >= ?nyLat - 0.3190235436 &&
?long <= ?nyLong + 0.8679199218) };
-- 13 rows
