3 ms·

What's the current state of the art in Datalog performance?

by jules 7y ago

chubot 7y ago
Take a look at the Souffle Datalog compiler: https://souffle-lang.github.io/ https://souffle-lang.github.io/ Some benchmarks here showing it beating a lot of other engines: https://souffle-lang.github.io/pdf/cc.pdf https://souffle-lang.github.io/pdf/cc.pdf (this paper also cites LogixBlox) They translate datalog into a straightforward relational bytecode, then use Futamura projections to compile that bytecode into a template-heavy "monolithic" C++ program. As far as I remember one of use of C++ templates is to specialize for different sizes of tuples, so fast assembly is generated for particular queries/facts. They are doing at least 3 nontrivial transformations, and the last step really leverages C++. The generated C++ is also multi-threaded, which is a big win. I watched a talk on Rust where Niko M said he prototyped the new borrow checker with Souffle I believe. It's somewhere on YouTube.
frankmcsherry 7y ago
Depending on what you are looking for, DDlog (https://github.com/vmware/differential-datalog https://github.com/vmware/differential-datalog) is interesting. I'm casually involved, for people weirded out by that, but it supports arbitrary changes to the input facts without recomputation.
- j-pb 7y ago
  invents new incremental computational paradigm that is hyped everywhere "I'm casually involved," Humble understatement of the year! Thank you for your work!
JimmyRuska 7y ago
RDFox uses datalog to apply inference rules to graph data, it has some state of the art algorithms for making datalog multi-core. It still uses SparQL, which is really similar to datalog for querying. There's some recent work on horizontally scaling datalog queries, but I hadn't seen anything in production. Probably the most popular implementation is datomic and its free variants. Which has a lot of convenience to it as you can embed custom java functions. It's not datalog but cypher has a lot of amazing ideas like easily combining algorithms to potentially recursive relationship queries, eg, "Give me the all shortest paths between these two peoples where there's at most 6 hops" -> allShortestPaths((n1:Person)-[*..6]->(n2:Person)) .
- refset 7y ago
  I work on Crux [0], which is also a Java-friendly Datalog database. It sits on top of lazy EAV indexes in RocksDB/LMDB so it's pretty fast and scales well (though technologies like Neo4j/GraphBLAS will be faster!). We don't have online REPL just yet but Nextjournal is pretty great if you want to play through the tutorials interactively [1]. The other unique angle is that Crux gives you "bitemporal" Datalog queries. Oh and the MIT license :) [0] https://opencrux.com https://opencrux.com [1] https://nextjournal.com/crux-tutorial/ https://nextjournal.com/crux-tutorial/

What's the current state of the art in Datalog performance?

by jules 7y ago

What's the current state of the art in Datalog performance?

Take a look at the Souffle Datalog compiler: https://souffle-lang.github.io/ https://souffle-lang.github.io/ Some benchmarks here showing it beating a lot of other engines: https://souffle-lang.github.io/pdf/cc.pdf https://souffle-lang.github.io/pdf/cc.pdf (this paper also cites LogixBlox) They translate datalog into a straightforward relational bytecode, then use Futamura projections to compile that bytecode into a template-heavy "monolithic" C++ program. As far as I remember one of use of C++ templates is to specialize for different sizes of tuples, so fast assembly is generated for particular queries/facts. They are doing at least 3 nontrivial transformations, and the last step really leverages C++. The generated C++ is also multi-threaded, which is a big win. I watched a talk on Rust where Niko M said he prototyped the new borrow checker with Souffle I believe. It's somewhere on YouTube.

frankmcsherry 7y ago

Depending on what you are looking for, DDlog (https://github.com/vmware/differential-datalog https://github.com/vmware/differential-datalog) is interesting. I'm casually involved, for people weirded out by that, but it supports arbitrary changes to the input facts without recomputation.

j-pb 7y ago
invents new incremental computational paradigm that is hyped everywhere "I'm casually involved," Humble understatement of the year! Thank you for your work!

JimmyRuska 7y ago

RDFox uses datalog to apply inference rules to graph data, it has some state of the art algorithms for making datalog multi-core. It still uses SparQL, which is really similar to datalog for querying. There's some recent work on horizontally scaling datalog queries, but I hadn't seen anything in production. Probably the most popular implementation is datomic and its free variants. Which has a lot of convenience to it as you can embed custom java functions. It's not datalog but cypher has a lot of amazing ideas like easily combining algorithms to potentially recursive relationship queries, eg, "Give me the all shortest paths between these two peoples where there's at most 6 hops" -> allShortestPaths((n1:Person)-[*..6]->(n2:Person)) .

refset 7y ago
I work on Crux [0], which is also a Java-friendly Datalog database. It sits on top of lazy EAV indexes in RocksDB/LMDB so it's pretty fast and scales well (though technologies like Neo4j/GraphBLAS will be faster!). We don't have online REPL just yet but Nextjournal is pretty great if you want to play through the tutorials interactively [1]. The other unique angle is that Crux gives you "bitemporal" Datalog queries. Oh and the MIT license :) [0] https://opencrux.com https://opencrux.com [1] https://nextjournal.com/crux-tutorial/ https://nextjournal.com/crux-tutorial/