Deferred Execution and Multiple Enumeration: Paying for the Same Query Twice

Learning outcome

You can predict how many times a LINQ to Objects query does its work, spot accidental re-enumeration, and decide where to materialize. You will count predicate calls instead of guessing.

Intuition

A LINQ query over IEnumerable<T> is a plan. Building it costs almost nothing. Each enumeration can execute the plan again from the source. Terminal operations such as Count() and Any() may use fast paths that skip enumeration or parts of the pipeline. If the plan is O(n), three enumerations cost 3 × O(n). Big-O stays O(n), but the constant triples, and if the source is a file, a network stream or a database, the side effects repeat too.

flowchart LR
    Q["var q = source.Where(f)"] -->|"Any()"| R1["runs f until first match"]
    Q -->|"Count()"| R2["runs f on every element"]
    Q -->|"foreach"| R3["runs f on every element again"]
    Q -->|"ToList() once"| L["List: reuse for free"]

Deep dive

• Deferred (lazy) operators return an object that does the work later: Where, Select, SelectMany, Skip, Take, OrderBy, GroupBy, Join, Distinct, Concat, Zip, Chunk…
• Immediate operators run now and return a value or a collection: Count, Any, All, First, Single, Sum, Min, Max, Aggregate, Contains, ToList, ToArray, ToDictionary, ToHashSet, ToLookup.
• Deferred is not the same as streaming. OrderBy is deferred (nothing happens until you enumerate) but it buffers the whole input when you do. Lesson 3 and Lesson 4 split the two ideas.
• Materializing trades space for time. ToList() costs O(k) extra memory for the k results and turns every later pass into a cheap list walk.

The .NET analyzer CA1851 flags possible multiple enumerations of an IEnumerable<T>.

Code example: count the predicate calls

// L02: a deferred query re-runs its work on every enumeration.
int predicateCalls = 0;
bool IsExpensiveMatch(int x) { predicateCalls++; return x % 3 == 0; }

var source = Enumerable.Range(1, 30);

// Slow: the query is enumerated three times (Any, Count, foreach).
var query = source.Where(IsExpensiveMatch);
if (query.Any())
{
    int count = query.Count();
    int sum = 0;
    foreach (var x in query) sum += x;
    Console.WriteLine($"Deferred x3: count={count}, sum={sum}, predicate calls={predicateCalls}");
}

// Fast: materialize once at the boundary, then reuse the list.
predicateCalls = 0;
var matches = source.Where(IsExpensiveMatch).ToList();
if (matches.Count > 0)
{
    int count = matches.Count;
    int sum = 0;
    foreach (var x in matches) sum += x;
    Console.WriteLine($"Materialized once: count={count}, sum={sum}, predicate calls={predicateCalls}");
}

// Deferred means the source is read later: a change before enumeration is visible.
var numbers = new List<int> { 1, 2, 3 };
var doubled = numbers.Select(x => x * 2);
numbers.Add(4);
Console.WriteLine($"Deferred sees the later Add: [{string.Join(", ", doubled)}]");

// Immediate operators run now: Count(), ToList(), First(), Sum() ...
var snapshot = numbers.Select(x => x * 2).ToList();
numbers.Add(5);
Console.WriteLine($"Snapshot does not: [{string.Join(", ", snapshot)}]");

Output

Deferred x3: count=10, sum=165, predicate calls=63
Materialized once: count=10, sum=165, predicate calls=30
Deferred sees the later Add: [2, 4, 6, 8]
Snapshot does not: [2, 4, 6, 8]

Code walkthrough

• 63 predicate calls = 3 (Any stopped at the first match, 3) + 30 (Count) + 30 (foreach). The materialized version calls the predicate 30 times, once per element.
• The first doubled query saw the element added after the query was built, because the source is read at enumeration time.
• The ToList() snapshot did not see the later Add(5).

Complexity summary

Failure modes

• if (q.Any()) … q.Count() … foreach (q): three passes over an expensive pipeline.
• Returning IEnumerable<T> from a method that does I/O: every caller enumeration repeats the I/O.
• Materializing an infinite or huge stream: ToList() on File.ReadLines of a 10 GB log can exhaust memory. Materialize only bounded results.
• Assuming deferred means cheap: OrderBy and GroupBy are deferred and O(n) space once enumerated.

Interview angle

"Is this query executed twice?" is a classic trap. Answer by naming each enumeration point, then propose the fix: materialize once at the boundary if the result is bounded and reused; otherwise restructure into a single pass (for example compute count and sum in one foreach).

Practice questions

1. How many times does Expensive run? var q = items.Where(Expensive); var a = q.First(); var b = q.Last(); for items 1..100 where only item 50 matches.

Answer: It depends on the source type, which is the point. If items is a lazy sequence: First stops at item 50 (50 calls) and Last must read forward through all 100 (100 calls), total 150. If items is a List<int> or array, .NET's Where iterator for lists scans backward for Last, stopping at item 50 after 51 calls, total 101. (Verified on .NET 9.) Either way the query ran twice.

2. Is OrderBy deferred or immediate? Does it stream?

Answer: Deferred, but it buffers the entire source on the first MoveNext. Deferred ≠ streaming.

3. When should you not call ToList() to avoid multiple enumeration?

Answer: When the sequence is unbounded or very large and you can do the work in one pass, or when you need fresh data on each enumeration on purpose.

Revision checklist

• Each enumeration re-runs the plan from the source.
• Immediate operators: Count, Any, First, Sum, To*.
• ToList() = O(results) memory to avoid repeated O(n) passes.
• CA1851 detects possible multiple enumerations.

References

• Deferred execution and lazy evaluation (Microsoft Learn)
• Classification of standard query operators by manner of execution
• CA1851: Possible multiple enumerations of IEnumerable collection
• Where.cs (dotnet/runtime)