The Flatter, the Better — Query Compilation Based on the Flattening Transformation

Alexander UlrichTorsten Grust

Proceedings of the 34th ACM SIGMOD Int’l Conference on the Management of Data (SIGMOD 2015), Melbourne, Australia, June 2015.

We demonstrate the insides and outs of a query compiler based on the flattening transformation, a translation technique designed by the programming language community to derive efficient data-parallel implementations from iterative programs. Flattening admits the straightforward formulation of intricate query logic—including deeply nested loops over (possibly ordered) data or the construction of rich data structures. To demonstrate the level of expressiveness that can be achieved, we will bring a compiler frontend that accepts queries embedded into the Haskell programming language. Compilation via flattening takes places in a series of simple steps all of which will be made tangible by the demonstration. The final output is a program of lifted primitive operations which existing query engines can efficiently implement. We provide backends based on PostgreSQL and VectorWise to make this point—however, most set-oriented or data-parallel engines could benefit from a flattening-based query compiler.