How to avoid unnecessary evaluations in LINQ queries using OrderBy followed by multiple ThenBy clauses

BLUF: Define an extension function .ThenByLazy() and supporting helper classes that make use of the System.Lazy<T> class. This will defer property access to only when needed, while caching the result to prevent repeated accesses.

(Note: The extension functions below owe partial credit to Ivan Petrov's earlier answer. I have combined his ideas with mine in this answer.)

I will assume that:

You wish to minimize accesses to the Name property, because it is a relatively expensive property to evaluate in your real-world case. When that property is accessed during the sort, it should be accessed no more than once per item, and then only for items where Age is not unique.

You can accomplish this by using the Lazy class to defer accessing the property until its value is actually needed. The Lazy class will also cache the property result once it is accessed, preventing repeated property getter references.

Because the default comparator for the Lazy class compares the object references instead of the actual values, you will need to either define a custom comparator or wrap Lazy up in a subclass that defines its own value comparator. In both cases, a .ThenByLazy() extension function can be written to simplify the call.

For the first option, you can define the following custom comparator class:

public class LazyValueComparator<TKey>: Comparer<Lazy<TKey>> where TKey : IComparable { public override int Compare(Lazy<TKey> x, Lazy<TKey> y) { return x.Value.CompareTo(y.Value); } }

With a matching extension function:

public static class Extensions { public static IOrderedEnumerable<TSource> ThenByLazy<TSource, TKey> (this IOrderedEnumerable<TSource> source, Func<TSource, TKey> keySelector) where TKey : IComparable { return source.ThenBy( x => new Lazy<TKey>(() => keySelector(x)), new LazyValueComparator<TKey>()); } }

The second option is to define a custom Lazy subclass that has a .CompateTo() override:

public class LazyValueComparable<TKey> : Lazy<TKey>, IComparable<LazyValueComparable<TKey>> where TKey : IComparable { public LazyValueComparable(Func<TKey> keySelector) : base(keySelector) {} public int CompareTo(LazyValueComparable<TKey> other) { return this.Value.CompareTo(other.Value); } }

With a matching extension function:

public static class Extensions { public static IOrderedEnumerable<TSource> ThenByLazy<TSource, TKey> (this IOrderedEnumerable<TSource> source, Func<TSource, TKey> keySelector) where TKey : IComparable { return source.ThenBy(x => new LazyValueComparable<TKey>(() => keySelector(x))); } }

In both cases, you can then update your code to:

var sorted = data .OrderBy(x => Tracer("First criterion", x.Age)) .ThenByLazy(x => Tracer("Second criterion", x.Name));

If needed, a matching .ThenByLazyDescending() extension can also be easily added. Corresponding .OrderByLazy() and .OrderByLazyDescending() are also possible, but I envision no particular need for them, as there is little to be saved at the top level of the sort.

See this .NET Fiddle and this .NET Fiddle for demos of the first and second options (with added test data).

Both versions produce same output. Note that the Name property is never referenced more than once for a given item and is not referenced at all for items having unique Age values.

Computing First criterion key: 30 Computing First criterion key: 25 Computing First criterion key: 25 Computing First criterion key: 93 Computing First criterion key: 93 Computing First criterion key: 93 Computing First criterion key: 93 Computing First criterion key: 89 Computing First criterion key: 89 Computing First criterion key: 89 Computing First criterion key: 89 Computing First criterion key: 89 Computing First criterion key: 89 Computing First criterion key: 89 Computing First criterion key: 1 Computing First criterion key: 2 Computing First criterion key: 3 Computing First criterion key: 3 Computing Second criterion key: Happy Computing Second criterion key: Doc Computing Second criterion key: Sleepy Computing Second criterion key: Bashful Computing Second criterion key: Sneezy Computing Second criterion key: Dopey Computing Second criterion key: Curley Computing Second criterion key: Moe Computing Second criterion key: Larry Computing Second criterion key: Shemp Computing Second criterion key: Grumpy Computing Second criterion key: Bob Computing Second criterion key: Charlie Computing Second criterion key: Three-A Computing Second criterion key: Three-B One - 1 Two - 2 Three-A - 3 Three-B - 3 Bob - 25 Charlie - 25 Alice - 30 Bashful - 89 Doc - 89 Dopey - 89 Grumpy - 89 Happy - 89 Sleepy - 89 Sneezy - 89 Curley - 93 Larry - 93 Moe - 93 Shemp - 93

After you've confirmed the desired behavior, you can remove your Tracer() function references, yielding the following final code:

var sorted = data .OrderBy(x => x.Age) .ThenByLazy(x => x.Name);

Note that using the Lazy class and other techniques above have their own costs, including the creation of closures for the reference functions () => x.Name for each item. There may be some better ways that explicitly pass item references and property getter functions to a wrapper classes, but I have pursued those options at this time.