Why the order of LINQ to objects methods counts

Question

I read this question's answers that explain the order of the LINQ to objects methods makes a difference. My question is why?

If I write a LINQ to SQL query, it doesn't matter the order of the LINQ methods-projections for example:

session.Query<Person>().OrderBy(x => x.Id)
                       .Where(x => x.Name == "gdoron")
                       .ToList();

The expression tree will be transformed to a rational SQL like this:

  SELECT   * 
  FROM     Persons
  WHERE    Name = 'gdoron'
  ORDER BY Id; 

When I Run the query, SQL query will built according to the expression tree no matter how weird the order of the methods.
Why it doesn't work the same with LINQ to objects?
when I enumerate an IQueryable all the projections can be placed in a rational order(e.g. Order By after Where) just like the Data Base optimizer does.

Answer 1

Why it doesn't work this way with LINQ to objects?

LINQ to Objects doesn't use expression trees. The statement is directly turned into a series of method calls, each of which runs as a normal C# method.

As such, the following in LINQ to Objects:

   var results = collection.OrderBy(x => x.Id)
                   .Where(x => x.Name == "gdoron")
                   .ToList();

Gets turned into direct method calls:

   var results = Enumerable.ToList(
                   Enumerable.Where(
                     Enumerable.OrderBy(collection, x => x.Id),
                     x => x.Name = "gdoron"
                   )
                 );

By looking at the method calls, you can see why ordering matters. In this case, by placing OrderBy first, you're effectively nesting it into the inner-most method call. This means the entire collection will get ordered when the resutls are enumerated. If you were to switch the order:

   var results = collection
                   .Where(x => x.Name == "gdoron")
                   .OrderBy(x => x.Id)
                   .ToList();

Then the resulting method chain switches to:

   var results = Enumerable.ToList(
                   Enumerable.OrderBy(
                     Enumerable.Where(collection, x => x.Name = "gdoron"),
                     x => x.Id
                   )
                 );

This, in turn, means that only the filtered results will need to be sorted as OrderBy executes.

Answer 2

Linq to objects's deferred execution works differently than linq-to-sql's (and EF's).

With linq-to-objects, the method chain will be executed in the order that the methods are listed—it doesn't use expression trees to store and translate the whole thing.

Calling OrderBy then Where with linq-to-objects will, when you enumerate the results, sort the collection, then filter it. Conversely, filtering results with a call to Where before sorting it with OrderBy will, when you enumerate, first filter, then sort. As a result the latter case can make a massive difference, since you'd potentially be sorting many fewer items.