I found this to be a great introduction to Datalog solving generally. Here is my summary: https://danglingpointers.substack.com/p/optimizing-datalog-f...
Also surfacing this comment I noticed which points out some pretty big caveats with the paper:
> As a heavy Datalog user, here's my opinion of the paper.
> Generally, my objection to this work would be that almost all "Datalog" programs they evaluate (7 programs in total) are either just SQL (i.e., they only have joins, no recursion) or they are transitive closure (i.e., they only have linear recursion). This is not Datalog. This is provably (one of the few things we can prove in complexity theory) a lower complexity class than Datalog. So, there is very strong reason to believe that these results do not translate to full Datalog. Transitive closure can be sped up arbitrarily much, compared to more complex recursion.
> The authors only evaluate one program (out of the 7) that has complex recursion. That one is "context-sensitive program analysis" (CSPA). However:
> a) the souffle version is not optimized for complex recursion, I strongly suspect it can be sped up by 2 orders of magnitude, so I really doubt the GPU speedup for this one
> b) despite the name, the analysis is not "context-sensitive", but let's just say this is an oversight
> c) it's still just a 10-line program, hardly representative of full Datalog.
> Methodologically, I cannot reproduce anything from this paper, at least not without talking to the authors directly. The artifact link in the paper (https://file.io/YZE8MKx12iqX) is broken already. In the repo, most of the large inputs are replaced with git lfs links and the github repo doesn't seem to serve git lfs, e.g., https://github.com/harp-lab/gdlog/blob/main/data/cspa/httpd/...
I will also mention that our group has follow-on work from this (I cannot share this widely due to reviewing reasons but a preprint is available if you would like to search) which significantly addresses Yiannais' concerns. In the engine cited here, we scale to small programs (tens of lines): our engine does not support large, tricky queries for interesting, asymptotic reasons (which are also shared by other Datalog engines based upon binary joins, not unique to our engines). Our new engines port a significantly more complex class of join algorithms to the GPU, and we have used these new algorithms (and our novel GPU-based implementation) to run 500-1000-line Datalog programs which beat all existing state-of-the-art program analysis engines by 20-50x.
In sum, I strongly disagree with the "pretty big caveats" remark. Dr. Smaradgakis' comments are quite firm in nature and I very much respect them. But I encourage you to check out my rebuttal and also (regarding scaling to larger subsets of Datalog and "real" programs) our recent follow-on work.
If you would like proof, please email me, we are happy to help you evaluate for yourself. My email is always open: kkmicins@syr.edu.