Why is CodeQL so fast and have such excellent performance?

[Raindragon-abc]

I am deeply interested in the underlying mechanics of CodeQL's internal DIL (Datalog Intermediate Language) optimizations. Prior to this, I’ve gained foundational knowledge of query rewriting techniques in Soufflé(another open-source Datalog engine), I am also familiar with some simple optimizations item such as join order.
I am particularly interested in learning which specific optimization passes CodeQL employs on its DIL representation. Furthermore, among these, which top 3–5 optimizations optimizations yield the most significant performance gains in practice？
Sincerely appreciate any of your responses and assistance.

[smowton]

I recommend taking a look at the QL academic publications (https://codeql.github.com/publications/), which give an overview of the CodeQL datalog implementation and some of the more noteworthy optimisations used.

[devhorizon999]

Thanks for the pointer.

I’ll go through the QL academic publications first, especially the papers around Datalog optimization, type inference, and magic-set style transformations. That sounds like the closest public source for understanding CodeQL’s performance model.

My current understanding is that CodeQL’s speed probably comes from a combination of things rather than one single optimization: extracting code into a relational database, compiling QL/Datalog into optimized relational operations, using type information to reduce the search space, and applying demand-driven / magic-set-like rewrites where possible.

I was mainly hoping to find a more implementation-level description of the DIL optimization pipeline, for example which passes are applied and which ones matter most in practice. But if that level of detail is not public, the publications should still be a good basis for describing the general ideas.

Thanks again — I’ll start from those papers.