Avalanche-Safe LINQ Compilation

Torsten GrustJan RittingerTom Schreiber

Proceedings of the VLDB Endowment, Volume 3, September 2010 (VLDB 2010), Singapore, September 2010.

We report on a query compilation technique that enables the construction of alternative efficient query providers for Microsoft’s Language Integrated Query (LINQ) framework. LINQ programs are mapped into an intermediate algebraic form, suitable for execution on any SQL:1999-capable relational database system.

This compilation technique leads to query providers that (1) faithfully preserve list order and nesting, both being core features of the LINQ data model, (2) support the complete family of LINQ’s Standard Query Operators, (3) bring database support to LINQ to XML where the original provider performs in-memory query evaluation, and, most importantly, (4) emit SQL statement sequences whose size is only determined by the input query’s result type (and thus independent of the database size).

A sample query scenario uses this LINQ provider to marry database resident TPC-H and XMark data—resulting in a unique query experience that exhibits quite promising performance characteristics, especially for large data instances.