Differences between IQueryable, List, IEnumerator?

IQueryable<T>: abstracts database access, supports lazy evaluation of queries
List<T>: a collection of entries. No support of lazy evaluation
IEnumerator<T>: supplies the ability of iterating over and IEnumerable<T> (which both IQueryable<T> and List<T> are)

The problem with that code is quite simple - it always executes the query when it is called. If you were to return db.User.Where(...) instead (which is an IQueryable<T>), you'd hold the evaluation of the query until it is actually needed (iterated over). Also, if the user of that method would need to specify further predicates, those also be executed in the database, which makes it way faster.

IQueryable<T> is intended to allow a query provider (for example, an ORM like LINQ to SQL or the Entity Framework) to use the expressions contained in a query to translate the request into another format. In other words, LINQ-to-SQL looks at the properties of the entities that you're using along with the comparisons you're making and actually creates a SQL statement to express (hopefully) an equivalent request.

IEnumerable<T> is more generic than IQueryable<T> (though all instances of IQueryable<T> implement IEnumerable<T>) and only defines a sequence. However, there are extension methods available within the Enumerable class that define some query-type operators on that interface and use ordinary code to evaluate these conditions.

List<T> is just an output format, and while it implements IEnumerable<T>, is not directly related to querying.

In other words, when you're using IQueryable<T>, you're defining an expression that gets translated into something else. Even though you're writing code, that code never gets executed, it only gets inspected and turned into something else, like an actual SQL query. Because of this, only certain things are valid within these expressions. For instance, you cannot call an ordinary function that you define from within these expressions since LINQ-to-SQL doesn't know how to turn your call into a SQL statement. Most of these restrictions are only evaluated at runtime, unfortunately.

When you use IEnumerable<T> for querying, you're using LINQ-to-Objects, which means you are writing the actual code that is used for evaluating your query or transforming the results, so there are, in general, no restrictions on what you can do. You can call other functions from within these expressions freely.

With LINQ to SQL

Going hand-in-hand with the distinction above, it's also important to bear in mind how this works out in practice. When you write a query against a data context class in LINQ to SQL, it produces an IQueryable<T>. Whatever you do against the IQueryable<T> itself is going to get turned into SQL, so your filtering and transformation will be done on the server. Whatever you do against this as an IEnumerable<T>, will be done at the application level. Sometimes this is desirable (in the case where you need to make use of a client-side code, for example), but in many cases this is unintentional.

For example, if I had a context with a Customers property representing a Customer table, and each customer has a CustomerId column, let's look at two ways to do this query:

var query = (from c in db.Customers where c.CustomerId == 5 select c).First();

This will produce SQL that queries the database for the Customer record with a CustomerId equaling 5. Something like:

select CustomerId, FirstName, LastName from Customer where CustomerId = 5

Now, what happens if we turn Customers into an IEnumerable<Customer> by using the AsEnumerable() extension method?

var query = (from c in db.Customers.AsEnumerable() where c.CustomerId == 5 select c).First();

This simple change has a serious consequence. Since we're turning Customers into an IEnumerable<Customer>, this will bring the entire table back and filter it on the client side (well, strictly speaking this will bring back every row in the table until it encounters one that fits the criteria, but the point is the same).

ToList()

Up until now, we've only talked about IQueryable and IEnumerable. This is because they are similar, complimentary interfaces. In both cases, you're defining a query; that is, you're defining where to find the data, what filters to apply, and what data to return. Both of these are queries

query = from c in db.Customers where c.CustomerId == 5 select c;
query = from c in db.Customers.AsEnumerable() where c.CustomerId == 5 select c;

Like we've talked about, the first query is using IQueryable and the second uses IEnumerable. In both cases, however, this is just a query. Defining the query doesn't actually do anything against the data source. The query is actually executed when code begins to iterate over the list. This can happen multiple ways; a foreach loop, calling ToList(), etc.

The query is executed the first and every time it's iterated. If you were to call ToList() on query two times, you would end up with two lists with completely distinct objects. They might contain the same data, but they would be different references.

Edit after comments

I just want to be clear about the distinction between when things are done client-side and when they're done server-side. If you're referencing an IQueryable<T> as an IEnumerable<T>, only the querying done after it's an IEnumerable<T> will be done client-side. For example, say I have this table and a LINQ-to-SQL context:

Customer
-----------
CustomerId
FirstName
LastName

I first construct a query based on FirstName. This creates an IQueryable<Customer>:

var query = from c in db.Customers where c.FirstName.StartsWith("Ad") select c;

Now I pass that query to a function that takes an IEnumerable<Customer> and does some filtering based on LastName:

public void DoStuff(IEnumerable<Customer> customers)
{
    foreach(var cust in from c in customers where c.LastName.StartsWith("Ro"))
    {
        Console.WriteLine(cust.CustomerId);
    }
}

We've done a second query here, but it's being done on an IEnumerable<Customer>. What's going to happen here is that the first query will be evaluated, running this SQL:

select CustomerId, FirstName, LastName from Customer where FirstName like 'Ad%'

So we're going to bring back everyone whose FirstName starts with "Ad". Note that there's nothing in here about LastName. That's because it's being filtered out client-side.

Once it brings back these results, the program will then iterate over the results and deliver only the records whose LastName starts with "Ro". The downside to this is that we brought back data--namely, all rows whose LastName doesn't start with "Ro"--that could have been filtered out on the server.