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.

Destroy

As an aside, and as Guffa said, these two are not identical - the second option can return more than one value, the first one can't. – Auxochrome

Answer 1

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.

Longmire

I see. I imagine that linq2sql might optimize the sql for the first statement. If not sql-server might optimize the interpretation. If not, then I'll soon find out. Right? – Destroy

Actually trying is a good way to soon find out indeed :-) - but sure, that sounds right to me. – Longmire

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();

Markup

The above is no longer true for .NET 4.7.1. OrderBy returns an OrderedEnumerator, but it hasn't actually ordered the list on return. When you call First(), it just has to look through the objects, and come up with the item that would be first, and that is what it now does, not bothering to actually sort the list. It also seems to be O(n) if the list has been sorted. See github.com/dotnet/corefx/blob/… – Coerce

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.

Tubate

Added assignments for clarity. It'll execute now, won't it? – Destroy

@Martin: The first one will execute but not the second one. The first one will get the first item and assign to the variable, but the second one will create an expression that can return the result. The expression won't execute until you read the result from it, for example: List<Order> earlyOnes = y.ToList();. – Tubate

Answer 4

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.

Stubborn

While you are technically correct, I feel you're giving the wrong impression to the OP. – Leroylerwick

But First() is actually getting the first element so I am quite sure that the first row will indeed execute the OrderBy – Grosgrain

While true, it's not a difference. The While in the second query will not execute either until someone actually gets the result. – Tubate