Skip to content
Engines, queries, and data for dynamic Datalog computation
Rust
Branch: master
Clone or download
Permalink
Type Name Latest commit message Commit time
Failed to load latest commit information.
differential-dataflow provide examples, validation May 30, 2019
problems provide examples, validation May 30, 2019
README.md provide examples, validation May 30, 2019

README.md

dynamic-datalog

Engines, queries, and data for dynamic Datalog computation


This repository maintains a list of dynamic Datalog engines, those that update query outputs in response to changes in the input fact sets.

The repository also maintains several paired Datalog queries and input data, meant to exercise dynamic Datalog execution engines in non-trivial ways. These can be found in the ./problems/ subdirectory. These problems may also be independently interesting for evaluating non-dynamic Datalog engines.

Engines

We also use the excellent Soufflé as a non-dynamic baseline.

Problems

Evaulations

For each problem we record reported times for various systems in various configurations, both to perform any query-specific compilation and then execution. These measurements are meant to be representative rather than definitive. All of the systems support multiple worker threads, and could be run in a variety of configurations on a variety of hardware platforms.

Soufflé can often benefit from join planning help; without this help it can take orders of magnitude longer than it could. Such help is currently only provided for the Doop benchmark, and measurements for other queries could improve in the future (especially for those runs in which it did not finish in 1,000 seconds). The Soufflé measurements are all directly using the query.dl file from the decompressed input directory, either with the -c flag (for compilation) or without (for interpretation).

Unlike other measurements, the Differential Dataflow measurements are for hand-written code in a larger language, and can reflect implementation and optimizations not easily available within Datalog. Links to this code should be forthcoming (it's just in a few different places at the moment).

The CRDT benchmark

Engine Compilation Evaluation Cores Notes
Soufflé (interpreted) 0s 1000s+ (DNF) 1 Laptop
Soufflé (compiled) 10.15s 1000s+ (DNF) 1 Laptop
Differential Dataflow 166.26s 3.44s 1 Laptop
Declarative Dataflow 0s
Differential Datalog
IncA

The CRDT benchmark contains stratified negation, as well as several "maximization" idioms represented in Datalog using a quadratic number of facts, which can be more efficiently implemented as data-parallel reduce operations.

The DOOP benchmark

Engine Compilation Evaluation Cores Notes
Soufflé (interpreted) 0s 762.14s 1 Laptop
Soufflé (compiled) 93.43s 111.76s 1 Laptop
Differential Dataflow 237.43s 161.58s 1 Laptop
Declarative Dataflow 0s
Differential Datalog
IncA

The DOOP benchmark is just really quite large.

The GALEN benchmark

Engine Compilation Evaluation Cores Notes
Soufflé (interpreted) 0s 1000s+ (DNF) 1 Laptop
Soufflé (compiled) 9.31s 198.19s 1 Laptop
Differential Dataflow 111.59s 123.54s 1 Laptop
Declarative Dataflow 0s
Differential Datalog
IncA

The GALEN benchmark contains joins on highly skewed keys, for which correct or adaptive join orders are important. The most problematic rule (IR4) is presented in the least problematic order for binary joins.

You can’t perform that action at this time.