We defined a benchmarking framework and database rbench in order to benchmark multiple database systems with many problems and problem instances. rbench is a collection of programs for solving problems in the database systems and bash scripts that start the database systems and run the problem instances.

This work is based on the OpenRuleBench benchmarking suite.

We define some problems in a declarative way. We are interested in how different (kinds of) database systems faire in solving the problems. Of course, problem-specific implementations and algorithms are often faster, but we're interested in the declarative programming and specifications-as-programs.

A problem is a mapping from input to output. Where applicable we map from input to size of output in order to skip measuring the time it takes to write to standard output or a file. A problem has one or more instances (input data) that can be solved using the same program or solver.

Source code

References and Related Work

Systems

Our benchmarking system supports the following systems:

Problem: Transitive Closure (tcff)

The TCFF problem is generating a Transitive closure of a directed graph. The output is potentially quadratic in the input size.

tc(A, B) :- par(A, B).
tc(A, B) :- par(A, X), tc(X, B).

The instances are generated using our graphgen tool.

Input Graphs

Graph Nodes Edges In-Deg. Out-Deg. Cyc. TC Size. Iter. Rule Inst.
k500 500 250000 500 500 yes 250000 1 125250000
k1k 1000 1000000 1000 1000 yes 1000000 1 1001000000
k2k 2000 4000000 2000 2000 yes 4000000 1 8004000000
t500 500 124750 0-499 0-499 no 124750 1 62126000
t1k 1000 499500 0-999 0-999 no 499500 1 166666500
t2k 2000 1999000 0-1999 0-1999 no 1999000 1 1333333000
c1k 1000 1000 1 1 yes 1000000 1000 1001000
c2k 2000 2000 1 1 yes 4000000 2000 4002000
c3k 3000 3000 1 1 yes 9000000 3000 9003000
c4k 4000 4000 1 1 yes 16000000 4000 16004000
s1k_1 1000 2000 2 2 yes 1000000 500 2002000
s1k_2 1000 3000 3 3 yes 1000000 201 3003000
s1k_3 1000 4000 4 4 yes 1000000 250 4004000
s1k_4 1000 5000 5 5 yes 1000000 200 5005000
s1k_5 1000 6000 6 6 yes 1000000 42 6006000
s2k_1 2000 4000 2 2 yes 4000000 1000 8004000
s2k_2 2000 6000 3 3 yes 4000000 288 12006000
s2k_3 2000 8000 4 4 yes 4000000 500 16008000
s2k_4 2000 10000 5 5 yes 4000000 400 20010000
s2k_5 2000 12000 6 6 yes 4000000 127 24012000
p1k 1000 999 0-1 0-1 no 499500 999 499500
p2k 2000 1999 0-1 0-1 no 1999000 1999 1999000
p3k 3000 2999 0-1 0-1 no 4498500 2999 4498500
p4k 4000 3999 0-1 0-1 no 7998000 3999 7998000
m4_2ki 8192 6144 0-1 0-1 no 12288 3 12288
m16_512 8192 7680 0-1 0-1 no 61440 15 61440
m64_128 8192 8064 0-1 0-1 no 258048 63 258048
m256_32 8192 8160 0-1 0-1 no 1044480 255 1044480
m1ki_8 8192 8184 0-1 0-1 no 4190208 1023 4190208
m4ki_2 8192 8190 0-1 0-1 no 16773120 4095 16773120
b17 131071 131070 0-1 0-2 no 1966082 16 1966082
b18 262143 262142 0-1 0-2 no 4194306 17 4194306
b19 524287 524286 0-1 0-2 no 8912898 18 8912898
y500_4k 4500 4499 0-500 0-1 no 9998000 4000 9998000
y500_8k 8500 8499 0-500 0-1 no 35996000 8000 35996000
y1k_4k 5000 4999 0-1000 0-1 no 11998000 4000 11998000
y1k_8k 9000 8999 0-1000 0-1 no 39996000 8000 39996000
u1k_50k 1000 50000 46-51 46-51 yes 1000000 3 50050000
u1k_125k 1000 125000 122-127 122-127 yes 1000000 2 125125000
u1k_250k 1000 250000 248-251 248-251 yes 1000000 2 250250000
u2k_200k 2000 200000 98-101 98-101 yes 4000000 3 400200000
u2k_500k 2000 500000 248-251 248-251 yes 4000000 2 1000500000
u2k_1m 2000 1000000 499-502 499-502 yes 4000000 2 2001000000
a1k_50k 1000 50000 0-102 0-102 no 471621 8 15269270
a1k_125k 1000 125000 0-250 0-250 no 492680 5 40853746
a1k_250k 1000 250000 0-500 0-501 no 497763 4 82941061
a2k_200k 2000 200000 0-201 0-201 no 1944729 8 128420988
a2k_500k 2000 500000 0-500 0-500 no 1985321 6 330666855
a2k_1m 2000 1000000 0-1000 0-1000 no 1995698 4 666033613

Measurements

For xsb we show the absolute time and for all other systems the relative time as a factor.

Graph XSB (s) BAM YAP SQLite PostgreSQL MariaDB Jena Soufflé
k500 15.101 s 0.26 0.69 4.88 2.85 4.18 1.79 0.09
k1k 122.002 s 0.26 0.66 5.00 3.26 4.37 1.66 0.07
t500 2.777 s 0.50 0.79 4.25 2.40 4.77 2.56 0.13
t1k 18.929 s 0.55 0.77 5.16 2.78 4.38 2.03 0.09
c1k 0.643 s 0.09 0.80 3.44 2.37 2.23 5.55 1.20
c2k 1.840 s 0.16 1.25 4.62 2.96 25.94 4.47 1.64
c3k 3.694 s 0.23 1.40 5.34 3.29 43.47 4.05 1.84
c4k 6.638 s 0.44 1.50 5.29 3.30 50.64 3.59 1.73
s1k_1 0.712 s 0.13 1.05 3.84 2.69 2.79 5.52 0.77
s1k_3 0.937 s 0.18 1.33 3.95 2.65 3.24 4.79 0.46
s1k_4 1.038 s 0.19 1.46 4.02 2.67 3.31 4.45 0.42
s2k_1 2.167 s 0.21 1.50 5.02 3.26 40.48 4.37 0.95
s2k_3 3.508 s 0.22 1.46 4.38 2.80 42.48 3.11 0.46
s2k_4 4.110 s 0.22 1.60 4.21 2.73 43.82 2.79 0.37
p1k 0.396 s 0.11 0.68 2.98 2.14 2.71 6.70 1.61
p2k 1.178 s 0.12 0.92 3.52 2.29 7.02 4.47 1.89
p3k 2.104 s 0.16 1.17 4.39 2.73 30.77 4.25 2.36
p4k 3.632 s 0.19 1.28 4.50 2.78 41.11 3.93 2.27
m4_2ki 0.117 s 0.00 0.43 1.03 1.32 0.95 16.56 0.43
m16_512 0.180 s 0.00 0.50 1.46 1.45 1.42 12.03 0.86
m64_128 0.316 s 0.15 0.79 2.21 1.69 2.00 7.82 1.29
m256_32 0.765 s 0.14 1.13 2.86 2.02 2.53 5.09 1.64
m1ki_8 2.128 s 0.15 1.35 4.06 2.56 27.17 4.21 1.91
m4ki_2 7.156 s 0.47 1.41 5.30 3.07 51.36 3.65 2.32
b17 1.417 s 0.26 0.92 3.02 2.44 5.12 5.81 0.37
b18 2.385 s 0.69 1.06 3.67 2.95 20.69 6.48 0.41
b19 4.725 s 1.70 1.09 3.89 3.13 31.33 7.10 0.36
y500_4k 4.268 s 0.24 1.16 5.08 3.14 51.53 3.86 2.48
y500_8k 14.954 s 1.06 1.34 6.08 3.40 68.38 3.89 2.74
y1k_4k 4.632 s 0.31 1.09 5.80 3.36 57.13 4.20 2.52
y1k_8k 16.239 s 1.23 1.30 6.35 3.42 68.37 3.93 2.66
u1k_50k 6.649 s 0.26 2.03 5.29 3.41 4.00 2.28 0.12
u1k_125k 14.620 s 0.30 2.27 5.67 3.70 4.29 2.15 0.10
u1k_250k 28.911 s 0.31 2.18 5.64 3.77 4.15 1.95 0.10
u2k_200k 48.136 s 0.32 2.66 6.45 4.32 116.40 2.00 0.08
u2k_500k 117.980 s 0.34 2.55 5.93 4.57 115.66 1.89 0.08
u2k_1m 223.119 s 0.37 2.48 6.02 5.16 115.89 1.82 0.09
a1k_50k 2.150 s 0.29 1.17 4.91 2.91 3.83 3.12 0.16
a1k_125k 5.017 s 0.32 1.51 5.18 3.16 4.05 2.57 0.16
a1k_250k 10.169 s 0.33 1.77 5.14 3.32 3.92 2.21 0.14
a2k_200k 15.172 s 0.41 1.22 6.31 4.75 43.77 2.36 0.11
a2k_500k 37.856 s 0.42 1.65 5.99 4.62 99.87 2.15 0.10
a2k_1m 78.214 s 0.43 2.10 5.64 4.94 69.92 1.99 0.11

Problem Instances

We use our instance generator graphgen to generate graph instances. The repository includes shell scripts to generate the instances we used for specific publications or experiments.

Graphgen generates problem instances in the following formats:

We provide our current working set of instances to download. We also provide specific sets of instances:

Authors

This page was last updated on 2018-10-10.