Will First() perform the OrderBy()?

Question

Is there any difference in (asymptotic) performance between

var a = Orders.OrderBy(order => order.Date).First()

and

var y = Orders.Where(order => order.Date == Orders.Min(x => x.Date)).ToList();

i.e. will First() perform the OrderBy()? I'm guessing no. MSDN says enumerating the collection via foreach och GetEnumerator does but the phrasing does not exclude other extensions.

Answer 1

It does not. THAT BEING SAID - naturally the orderby will execute the moment someone tries to actually GET the first element.

But as you said, the conditions may be further defined. As such, no - it does not execute at that moment.

Answer 2

First will return the first entry of the IEnumerable passed to it. Since the IEnumerable passed to First is the result of OrderBy your question can be rephrased to "Does OrderBy work", and, yes it does.

First cannot defer the execution of OrderBy because it returns the result right away. For example:

        var numbers = new int[] { 9, 3, 4, 6, 7 };

        var num = numbers.First();
        Console.WriteLine(num);

        num = numbers.OrderBy(i => i).First();
        Console.WriteLine(num);

        Console.ReadLine();

Answer 3

The First method will perform the OrderBy (that is, given that the First method is executed of course). When the First method pulls the first item from the result of the OrderBy, it will have to sort all the items to find out which one is the first one.

Depending on where and how the query is run (i.e. if the query engine can't optimise around it), the second query can perform quite badly. If Orders.Max is evaluated once for each item in Orders, it becomes an O(n*n) operation, which is pretty bad.

There is a functional difference also, the second query can return more than one item if there are duplicate dates.

Answer 4

A few things:

• OrderBy() orders from small to large, so your two alternatives return different elements
• Where() is typically lazy, so your second expression doesn't actually do any computation at all - not until used.
• In principle, the behavior in question depends on the query provider. For example, you might indeed expect the sql-server linq query provider to deal with this differently than the IEnumerable query provider. A query provider might choose to have the return value of "OrderBy" be sufficiently specialized such that calling First() on it recognizes (either at compile or run-time) that it's running on an ordered enumerable and instead of sorting, opts to return the (first) minimum element.
• Specifically for the IEnumerable<T> provider, OrderBy happens to return an enumerable that fully buffers and sorts the input each time the first element is retrieved - so, in the common basic Linq-to-objects case, OrderBy().First() is comparable to OrderBy().ToArray().

Remeber that linq is just a bunch of function names - each provider may choose to implement these differently, so the above only holds for the System.Linq IEnumerable query provider, and not necessarily others.