How LINQ works internally?

I love using LINQ in .NET, but I want to know how that works internally?


It makes more sense to ask about a particular aspect of LINQ. It's a bit like asking "How Windows works" otherwise.

The key parts of LINQ are for me, from a C# perspective:

  • Expression trees. These are representations of code as data. For instance, an expression tree could represent the notion of "take a string parameter, call the Length property on it, and return the result". The fact that these exist as data rather than as compiled code means that LINQ providers such as LINQ to SQL can analyze them and convert them into SQL.
  • Lambda expressions. These are expressions like this:

    x => x * 2
    (int x, int y) => x * y
    () => { Console.WriteLine("Block"); Console.WriteLine("Lambda"); }
    

    Lambda expressions are converted either into delegates or expression trees.

  • Anonymous types. These are expressions like this:

    new { X=10, Y=20 }
    

    These are still statically typed, it's just the compiler generates an immutable type for you with properties X and Y. These are usually used with var which allows the type of a local variable to be inferred from its initialization expression.

  • Query expressions. These are expressions like this:

    from person in people
    where person.Age < 18
    select person.Name
    

    These are translated by the C# compiler into "normal" C# 3.0 (i.e. a form which doesn't use query expressions). Overload resolution etc is applied afterwards, which is absolutely key to being able to use the same query syntax with multiple data types, without the compiler having any knowledge of types such as Queryable. The above expression would be translated into:

    people.Where(person => person.Age < 18)
          .Select(person => person.Name)
    
  • Extension methods. These are static methods which can be used as if they were instance methods of the type of the first parameter. For example, an extension method like this:

    public static int CountAsciiDigits(this string text)
    {
        return text.Count(letter => letter >= '0' && letter <= '9');
    }
    

    can then be used like this:

    string foo = "123abc456";
    int count = foo.CountAsciiDigits();
    

    Note that the implementation of CountAsciiDigits uses another extension method, Enumerable.Count().

That's most of the relevant language aspects. Then there are the implementations of the standard query operators, in LINQ providers such as LINQ to Objects and LINQ to SQL etc. I have a presentation about how it's reasonably simple to implement LINQ to Objects - it's on the "Talks" page of the C# in Depth web site.

The way providers such as LINQ to SQL work is generally via the Queryable class. At their core, they translate expression trees into other query formats, and then construct appropriate objects with the results of executing those out-of-process queries.

Does that cover everything you were interested in? If there's anything in particular you still want to know about, just edit your question and I'll have a go.


LINQ is basically a combination of C# 3.0 discrete features of these:

  • local variable type inference
  • auto properties (not implemented in VB 9.0)
  • extension methods
  • lambda expressions
  • anonymous type initializers
  • query comprehension

For more information about the journey to get there (LINQ), see this video of Anders in LANGNET 2008:

http://download.microsoft.com/download/c/e/5/ce5434ca-4f54-42b1-81ea-7f5a72f3b1dd/1-01%20-%20CSharp3%20-%20Anders%20Hejlsberg.wmv