We compare the performance of logic programming systems with tabling (XSB, YAP) and new Datalog implementations (Sou e, our BAM) with the performance of relational database systems (SQLite, PostgreSQL, MariaDB). These databases support recursive views, and can compute, e.g. the transitive closure and same generation cousins. We also tried the RDF store Apache Jena and the graph database Neo4j. The main contributions compared to previous benchmarking approaches like OpenRuleBench [4] are: (1) We created a number of additional graphs of di erent structure when we identi ed a problem with the OpenRuleBench test graphs. (2) We developed a database to store and analyze benchmark measurements. It is much more general than the previous result data les, and supports detailed evaluations of the data. (3) We propose a formula to predict the runtime of the transitive closure benchmark based on parameters of the input graph. This work on runtime prediction is only the beginning of using machine learning techniques on runtime data.
Benchmarks can be a useful tool to compare performance between systems and evaluate how well di erent kinds of systems and evaluation schemes perform against each other. Especially comparing di erent models of computation and evaluation schemes can be helpful for system developers in identifying shortcomings and furthering cross-pollination between disciplines.
In the area of deductive databases/rule-based systems, OpenRuleBench [
However, the OpenRuleBench scripts run each benchmark only once, and do not support comparing runtimes of the same benchmark for di erent option settings or program versions, or even on di erent machines. We have developed a database and new benchmark execution scripts in order to overcome these restrictions. The scripts measure all runtimes externally, and collect also information about the used main memory (where possible). Furthermore, the test graphs used in OpenRuleBench for the transitive closure have a very speci c (dense) structure, and even graphs declared as non-cyclic contain loops. We solved this problem and used a much larger collection of di erent test graphs.
In this paper, we show results for only two of the OpenRuleBench benchmark problems, namely the transitive closure, and the same generation cousins (our project web pages contain some more benchmark results). However, we analyze the benchmark results in detail. In particular, we investigate formulas to predict the runtime of a system based on characteristics of the graph. We believe that for declarative programming, it is important that one can get a rough estimate of the runtime on an abstract level (without need to understand implementation details). At least, one wants to be sure that for all inputs that might occur (even larger ones), the runtime will be acceptable. If the runtime would suddenly \explode" for speci c inputs, the system would be unreliable.
Database optimizers have done runtime estimation for a long time. But this uses internal information of the system, such as the availability of indexes and sizes of data structures. We took a \black box" approach and measure runtime, and try to approximate the results with a formula based on characteristics of the given problem (input and output). If this works, it helps to understand the runtime behaviour of the system, and gives the user some trust into its reliable performance. Furthermore, it helps to \compress" the many single numbers for the runtime measurements into a few understandable parameters of the formula. This compression is not lossless, but it helps to see the \big picture".
The runtimes of transitive closure in relational databases have already been
investigated in [
We are especially interested in performance and performance measurements
since we are developing an implementation of our \Push" method for bottom-up
evaluation of Datalog [
There is a renewed interest in Datalog, probably mostly due to new
applications. E.g. the Sou e system [
We also checked classical logic programming systems, in particular, XSB [
The OpenRuleBench scripts [
When measuring other systems, we feel obliged to do some tests with di erent option settings (or di erent indexes) and choose the best settings we could nd (with our limited expertise). Thus, the situation gets more complicated than in the OpenRuleBench, since we have di erent implementation variants of the same benchmark for the same system.
Furthermore, as developers we use di erent machines with di erent operating systems. In order to keep the overview of the di erent runtime measurements, we decided to develop a benchmark database. The database of measurements also allows us to easily run statistical analyses on any kind of dataset.
SYS_TYPE # * STYPE U* SEQ_NO * HEADLINE
TEST_SYS # * SYS U* SEQ_NO * FULL_NAME oURL oREMARK
SYS_VER # * VER * VER_ADDTEXT oVER_DATE oREMARK
BENCHMARK # * BENCH U* SEQ_NO * HEADLINE
BENCH_IMPL # * IMPL * STATUS oDESCRIPTION
SYS_INSTALL # * INST_NO * COMPILER * STATUS oREMARK
MACHINE # * MACHINE U* SEQ_NO * STATUS oMODEL oYEAR oMONTH *oPNRUIMC_ECPUS
BENCH_RUN # * RUN_DATE # * RUN_NO * WITH_OUTPUT oLOAD_TIME oEXEC_TIME oTOTAL_TIME oUSER_TIME oSYS_TIME * REAL_TIME oMEM * STATUS oREMARK
GRAPH_TYPE # * GTYPE U* SEQ_NO * NAME
INPUT_SET # * SET_ID
INPUT_TYPE # * ITYPE U* SEQ_NO * HEADLINE * DESCRIPTION
INPUT_FILE # * FILE_ID U* SEQ_NO * LINES * BYTES * FILENAME oDESCRIPTION
INPUT_GRAPH oPARAM_1 oPARAM_2 * NUM_NODES * NUM_EDGES * DUP_EDGES * LOOPS * MIN_IN_DEGREE * MAX_IN_DEGREE * MIN_OUT_DEGREE * MAX_OUT_DEGREE * CYCLES
OTHER_INPUT
We also implemented a number of views to analyze the data. The generation of tables in LATEX and HTML format is done by means of SQL queries. Our views also help to check for outliers to get more con dence in the data. One can also query for the best implementation variant of a benchmark for a system. 3
Transitive Closure and Same Generation For space reasons, we can discuss only two benchmark problems in this paper. The rst is the well known task to compute the transitive closure of a binary relation, i.e. the reachability relation between nodes in a graph, where the edges are given. The standard tail-recursive formulation in Datalog/Prolog is: tc(X,Y) :- par(X,Y).
tc(X,Y) :- par(X,Z), tc(Z,Y).
The name \par" stands for \parent" or \parameter" (of tc). It is the edge relation of a directed graph. The nodes in the test graphs (see Section 4) are integers, thus a large set of facts of the form par(1,2) is given. The benchmark is to compute the entire tc relation, i.e. the predicate tc is queried with both arguments \free". Therefore this benchmark is called \TCFF".
The second problem is the \same generation" problem (\SGFF"), which is
also part of the OpenRuleBench collection [
sg(X,Y) :- par(X,A), sg(A,B), par(Y,B).
While this program rst looks very similar to the transitive closure, performance is quite di erent, because the program is not tail-recursive.
Since many of the test graphs are cyclic, a standard Prolog system would not terminate with these programs. We need systems that support tabling to detect repeated calls to the recursively de ned predicate. We used XSB version 3.8.0, and YAP version 6.2.2.
XSB has some tuning parameters, and we tried ten di erent settings for the same generation benchmark. The best we could get was using subsumptive tabling, load_dync for loading the data, and an index on par(2,1). For this benchmark, the trie index gave bad results.
We also tried the Sou e system [
Of course, native code gives an advantage over systems based on an abstract machine, such as XSB, YAM, and our \Bottom-Up Abstract Machine" BAM. For Prolog systems, a rule of thumb is that native code gives on average a factor of 3 over emulators of the Warren abstract machine. Experiments we did with a native code implementation of our Push method vs. our BAM showed only a factor of 1.5{2. 3.1
Recursive view de nitions were introduced in the SQL-99 standard. Most modern relational database systems support them, and therefore can compute the transitive closure.
The query is (using a recursive \common table subexpression", i.e. a local view de nition):
SELECT par.a, par.b from par UNION
SELECT par.a, tc.b from par JOIN tc ON par.b = tc.a ) SELECT Count(*) FROM tc; The query for the same generation problem is analogous. As a table de nition for the par-table, we used the following de nition, with slight alterations and additions depending on the used database system.
CREATE INDEX par_fb ON par (b);
For SQLite, we used a temporary in-memory table for the par relation. We added PRAGMA temp store = MEMORY; in order to deactivate using temporary les. We used SQLite3 version 3.24.0.
PostgreSQL is a server-based database system. As CPU time, we record in our database the time the server process of the session used. However, the main comparison is done on real time, which is simpler for server-based systems (it also gives parallel implementations an advantage). The startup time of the server is not included in the time measurements. We used version 9.4.15.
MariaDB is the community fork of the server-based MySQL database system. We used both the InnoDB storage engine and the Memory storage engine for the par relation. For the latter we set max head table size to 4 10243. The support of recursive CTEs is new (since version 10.2.2). We used version 10.3.9. 3.2
Transitive Closure and Same Generation are included in the OpenRuleBench
suite for the graph database system Apache Jena using the Java API for the
included OWL reasoner. Since SPARQL 1.1 added Property Paths [
SELECT (count(*) as ?resultcount) WHERE {?a :par+ ?b} This does not work for the same generation, because there we need two paths of the same length. For the transitive closure benchmark, we used Apache Jena version 3.8.0 on OpenJDK 1.8 (Java 8), and had to increase the JVM's thread stack size to 16MB (JVM ARGS=-Xss16m).
Since the two benchmark problems are graph problems, we also tried the well-known graph database Neo4j. However, the following query in the graph query language Cypher did not give competitive performance:
MATCH (a)-[*]->(b)
RETURN DISTINCT a,b; There are other possibilities to formulate this query (e.g., via shortest paths), but they do not work for arbitrary graphs.
It is possible to formulate the same generation problem in Cypher, but since one computes rst arbitrary pairs of paths ending in the same node, and then selects paths of equal length, the performance is bad. One would need a clever query optimizer. 3.3
We executed the benchmarks on a HP Blade server with two Intel Xeon CPUs E5-2630 v4@2.20GHz with 10 cores and 20 threads each. As far as we know, Jena is the only one of the tested systems that uses multiple threads for the test query. The machine has 128 GB of RAM. The operating system is Debian x86_64 GNU/Linux 8.10 (3.16.0).
The overall execution time (\elapsed wall clock time" and CPU time) and the memory (\maximum resident set size") for each test of the standalone programs was measured with the Linux /usr/bin/time program.
For the server based systems we took a snapshot of the status information
provided by /proc/[pid]/stat [
Most tests were run ten times and the time average values were calculated.
In the comparison table (Fig. 2 below), we use real time. 4
The OpenRuleBench collection [
Because of this, we developed generators for graphs with properties that are easily analyzed in the context of the given recursive problems. The number of edges in the graph is the input size of the problem. The maximum of the lengths of the shortest path between any two connected vertices is the number of iterations until the xed point of the Tp operator is found for the transitive closure (Ntc). We label vertices incrementally starting from 1.
{ The complete graph Kn has n vertices, n2 edges and Ntc(Kn) = 1.
The set of edges is E = f(i; j) j i = 1; : : : ; n; j = 1; : : : ; ng. { The maximum acyclic graph Tn is a subset of Kn without the edges (a; b) with a b. It has n vertices, n(n2 1) edges and Ntc(Tn) = 1. { The cycle graph Cn has n vertices, n edges and Ntc(Cn) = n.
E = f(i; i + 1) j i = 1; : : : ; n 1g [ f(n; 1)g. { The cycle graph with shortcuts Sn;k is a directed graph that is a superset of the cycle graph Cn where n 1 > k > 0 additional edges per vertex are n added, skipping k+1 vertices in the cycle. n should be divisible by k + 1. One additional edge per vertex allows skipping 21 of the cycle, while two edges would allow skipping 31 or 23 of the cycle. Ntc(Sn;k) = k+n1 . The set of edges is E = f(i; 1 + (i 1 + kn+t1 ) mod n) j t = 1; : : : ; k; i = 1; : : : ; ng [ Cn. { The path Pn has n vertices and n 1 edges: E = f(i; i + 1)ji = 1; : : : ; n 1g.
Ntc(Pn) = n 1. The transitive closure of Pn is Tn. { The multi-path graph Mn;k is a directed graph that contains n k vertices that form k pairwise vertex-disjoint paths of length n 1. The set of edges is E = f(i; i + k)ji = 1; : : : ; (n 1) kg. Ntc(Mn;k) = n 1. Mn;1 is Pn. { The binary tree graph Bh of height h > 0 is a directed graph that contains 2h 1 vertices and 2h 2 edges. Ntc(Bh) = h 1. The set of edges is E = f(i; 2i) j i = 1; : : : ; 2h 1 1g [ f(i; 2i + 1) j i = 1; : : : ; 2h 1 1g. { The graph Vn is the reverse of Bn (all edges point towards the root). { The Y-graph Yn;k is a directed graph with n + k vertices. It consists of n vertices with edges to the center vertex n + 1, which is attached to a path of k vertices: E = f(i; n + 1) j i = 1; : : : ; ng [ f(i 1; i) j i = n + 2; : : : ; n + kg.
The number of iterations for the tc computation is Ntc(Yn;k) = k. { The W-graph Wn;k (with k n) has a single level of edges, where each vertex in a set of n vertices points to k vertices from a disjoint set of another n vertices. The graph has 2n vertices, n k edges, and Ntc(Wn;k) = 1. The set of edges is E = f(i; n + 1 + (i + j 1) mod n) j i = 1; : : : ; n; j = 1 : : : ; kg. { The X-graph Xn;k consists of n vertices pointing to a central vertex, which in turn points to k vertices (the default for k is n). The set of edges is E = f(i; n + 1 j i = 1; : : : ; ng [ f(n + 1; n + 1 + j) j j = 1; : : : ; kg. The graph has n + k + 1 vertices, n + k edges, and Ntc(Xn;k) = 2. 4.1
As a rst try to estimate the runtime, we look at the number of applicable rule instances in the given logic program. I.e. this is the total number of variable assignments that satisfy the body (condition) of the rules. The standard seminaive evaluation would look at each such rule instance exactly once.
As an example, consider the transitive closure program applied to the complete graph K100 (100 vertices, 10 000 edges). The (non-recursive) starting rule tc(X,Y) :- par(X,Y) tc(X,Z) :- par(X,Y), tc(Y,Z) is applicable 10 000 times (once for each of the input facts). For the rule there are 10 000 facts in the par relation and each one has 100 join partners in the tc relation (the number of tuples with a given Y value). Thus the total size of the join par(X,Y), tc(Y,Z) is 1 000 000. Of course, in this example, the second rule generates only duplicates, but they must be computed and eliminated. The associated costs for the rules are added and we get a total cost of 1 010 000.
Note that this cost measure is purely declarative, and does not look at the sequence in which facts are computed. For the applicable rule instances, we only need the nal version of the tc/sg-relation in the minimal model. Graph Kn Tn Cn Sn;k Pn Mn;k Bh Vh Yn;k Wn;k Xn;k The average runtimes of the main systems for the some test graphs are shown in Fig. 2. We give the runtime of XSB in seconds (real time), and for all other systems, we list the factor of the runtime of that system compared to XSB. Thus, an entry less than 1 means that the system is faster than XSB. The average factor at the bottom of the table is determined over all 50 graphs we measured, not only the ones shown in the table. All data are available on our web page.
Although the transitive closure is a typical problem for a logic programming system such as XSB, the relational databases PostgreSQL and SQLite are for most graphs only 3{5 times slower (for PostgreSQL, the worst factor in our TCFF tests was 7:0, for SQLite 9:7). For MariaDB there are ve examples where it is more than 100 times slower than XSB. Performance seems to go down for larger problem instances. Sou e is very fast on some problem instances, but slower than XSB on others (remember that we used Sou e in single-threaded nativecode mode). The numbers for our own prototype look promising, but there are a few problem instances that have potential for further optimization.
Figure 3 shows the relation between the runtime and the cost measure for the graphs. For some systems, such as XSB, the relationship between the cost measure (the number of applicable rule instances) and the runtime looks to be more or less linear. A rst try for runtime prediction for XSB and the transitive closure program is to assume a speed of 5:3 106 rule instances per second.
XSB (s) BAM YAP SQLite PostgreSQL MariaDB Jena Sou e Graph
For other systems, including our own BAM, there are graphs where the more or less linear relationship is severely violated. Of course, these inputs are interesting for the system developers. We also have to look at other cost factors besides the number of applicable rule instances. One such approach is the subject of the next subsection. 5.2
We assume that the main computation consists of the following four components: { Initialize is the time it takes to initialize the program (e.g. for parsing and optimizing the query, and allocating memory). Since we consider only a single query, this time is a system-dependent constant IS (for the system S). { Loading and preprocessing is the process of reading input data from the le system and storing it into some other data structure. This includes creating any indexes. While reading from the le system is expected to be done in linear time, creating indexes may take log-linear time. Therefore, we assume that this phase costs LS e(G) log(e(G)), where e(G) is the number of edges in the input graph G and LS is a system-dependent constant. { Deduction is the work of applying the rules to derive new facts, in this case for the tc predicate. This is where the previously discussed cost measure is used. We assume that the time needed is DS R(G), where DS is a systemdependent constant, and R(G) is the number of applicable rule instances. { Answer processing is the work of processing a computed answer to the query. We assume that the time needed is AS T (G), where AS is a systemdependent constant, and T (G) is the size of the tc-relation (i.e. the answer).
Note that R(G) T (G) is the number of non-successful rule applications, s100 n i e 50 m i t 0
0 s400 n i e200 m i t 0
0 i.e. rule applications that computed only duplicates of already known answers. With the two parameters DS and AS , it is possible to treat successful and non-successful rule applications di erently.
Given the partial costs above, we estimate the runtime ES (G) for a speci c system S and for an input G as the sum of the components, i.e. ES (G) = SI 10 3 + LS e(G) log(e(G)) + DS
R(G) + AS
T (G) 10 9.
The factors mean that SI is measured in milliseconds, whereas the other constants are in milliseconds per one million cost units. E.g. DS are the milliseconds per one million rule applications.
Let us consider an estimate as acceptable if the real value di ers less than 20% from the estimate, i.e. lies between 0:8 ES (G) and 1:2 ES (G). We used a simple optimization program to search for good values for the parameters. The average error was a secondary optimization criterion (of lower priority than improving the number of graphs with acceptable prediction). Obviously, for some systems, we have not yet the right cost parameters. E.g., currently, non-successful joins are not counted at all. For MariaDB, it seems that we need an additional factor for large data (that presumably do not t in the main memory bu er). The runtimes for the same generation benchmark and some selected input graphs are shown in Fig. 4. Data for more graphs and the plots relating runtime to the number of applicable rule instances are available on the web page.
XSB (s) BAM YAP SQLite PostgreSQL MariaDB Sou e
Since we are developing our own Datalog system, we of course need to do
systematic runtime measurements. We started with some benchmarks of the
OpenRuleBench [
Further information (including source code, data les, SQL scripts to create the database, and benchmark results) is available on the web page of the project: http://dbs.informatik.uni-halle.de/rbench/.