How does LINQ Where() clause in .Net work?

Question

I want to know how the LINQ Where() is implemented. Does it perform a simple linear search on the collection? Or is there any optimization implemented?

Answer 1

Short answer: It depends.

Longer answer: The purpose of LINQ is to allow the developer to express intent of a query without having to provide how the query will be performed. We can use the same query syntax for nearly anything that can be represented as a set.

For LINQ to Objects, it currently simply does what you described - a linear traversal of the sequence. Under the hood, LINQ can use an IQueryProvider to defer the how to a more sophisticated implementation.

The provider's job is to turn the query (for example, Where(predicate)) into actual executing code. For something like LINQ to SQL or LINQ to Entities in the Entity Framework, it translates the query into SQL and executes it.

So at a basic level, the idea is "it doesn't matter" how it works - it's supposed to help developers be more productive by writing queries more declaratively. But it is helpful to look up the documentation for the specific LINQ provider you're using, so you can understand how to most effectively leverage it.

Answer 2

As MSDN documentation puts it:

LINQ introduces standard, easily-learned patterns for querying and updating data, and the technology can be extended to support potentially any kind of data store.

Therefore, how the Where function works essentially depends on which LINQ provider is used underneath the collection. LINQ to objects will perform a search similar to what you say, while LINQ to Entities will instead translate it to an SQL WHERE clause and execute it on the database to return the objects.

Answer 3

It simply iterates:

foreach (TSource element in source) { 
  if (predicate(element)) yield return element; 
}