Friday, August 15, 2008 10:43 PM bart

The Most Funny Interface Of The Year … IQueryable<T>

Recently I delivered a talk at TechEd South Africa on “Custom LINQ Providers”. This is a very broad topic to cover in barely 60 minutes especially if one has to explain pretty “abstract” pieces of art like IQueryable<T>. Apparently I managed to do so looking at the scores <g>. But why is IQueryable<T> such a special specimen? This post will explain why.

 

What’s in a name?

Well, not that much: I and Queryable. “I” means there’s work to do if you want to use it – that’s precisely what interfaces are all about (the Imperative form of to Implement). “Queryable” is the promise of the interface – what we’ll get in return for the “I” labor.

So, what would you guess that needs to be implemented to get query capabilities in return? A blind guess would be: every query operator? Looking at all of the query operators we support with all their fancy overloads, that would mean 126 methods. Framework designers are sometimes masochistic but to such a large extent? Nah! There’s a magic threshold for interfaces which I would conservatively set to 10 methods. If you go beyond that threshold, only masochistic framework users will care to (try to) implement your interface. People have come up with brilliant (hmm) ideas to reduce the burden of interface implementation by trading the problem for another set of problems: abstract base classes. Right, we only have 47 distinct query operators and additional overloads can do with a default implementation in quite some cases, but still 47 abstract methods is way too much especially if most implementors will only be interested in a few of them, so you get a sparse minestrone soup with floating NotImplementedExceptions everywhere. And you’re facing the restrictions of the runtime with respect to single inheritance only, which is one of the reasons I don’t believe that much in abstract base classes as extensibility points (although there are cases where these work great).

We need something better. What about the silver bullet (hmm) to all complexity problems: refactoring? Oh yeah, we could have 47 interfaces each with a few methods (all having the same name since they would be overloads) with exciting names like IWhereable, ISelectable, IOrderable, IGroupable, etc. If it doesn’t scale against one axis, what about pivoting the whole problem and make it again not scale against the orthogonal axis? We’ve gained nothing really. Maybe there’s yet a better idea.

Time to step back a little. Remember the original promise of the interface? You implement me and I give you something with “queryable” characteristics in return. However, for ages the typical way of delivering on such a promise was symmetric to the implementation. It was really all about: “I know – but only abstractly – how to use something but only if you concretize that something for me.”. Hence interfaces for say serialization have predictable members like Serialize and Deserialize. And yes, the interface delivers on its promise of marking something that can do serialization as such but in a rather lame and predictable way. So what if we could deliver on the “queryable” promise without putting the burden of implementing all query operators directly on the implementor? This is where interfaces can also be “asymmetric” concerning their promise versus their implementation cost. (If I were in a really philosophical mood, I could start derailing the conversation introducing parallels with concave, convex and regular mirrors. Let’s not do this.) But how…?

 

An asymmetric interface (IImplement side)

In order to have useful query capabilities we really need two things:

  1. Write a query
  2. Enumerate over the results

From the latter promise we can already infer that IQueryable<T> ought to implement IEnumerable<T>, which makes our outstanding balance for the “implementor frustration threshold” (IFT for acronym lovers) two: a generic and non-generic equivalent of GetEnumerator:

interface IQueryable<T> : IEnumerable<T>
{
}

For the former promise we already came to the conclusion that it would be unreasonable to require 47 methods or so to be implemented (btw, that would also mean that in subsequent releases of LINQ, new query operators would have to go in an IQueryable2<T> interface since interfaces do not scale well on the versioning axis – remember COM?). So what if we could do all the heavy lifting for you, just giving you one piece of information that represents an entire query. That’s what expression trees are capable of doing. Now we end up with one more member to IQueryable<T>:

interface IQueryable<T> : IEnumerable<T>
{
    Expression Expression { get; }
}

Conceptually, we could stop here. You have an expression tree that can represent an entire query (but how does it get there?) and you have a method that demands (where lazy becomes eager) you to start iterating over the results. The two query capability requirements have been fulfilled. Oh, and it’s quite predictable how the GetEnumerator would work, right? Take the expression tree, translate it into a Domain Specific Query Language (DSQL if you will), optionally cache it, send it to whatever data store you’re about to query, fetch the results, new up objects and yield them back.

I already raised the question about where the expression tree property’s value comes from. The answer is we need a bit of collaboration from you, the implementor, through a property called QueryProvider:

interface IQueryable<T> : IEnumerable<T>
{
    Expression Expression { get; }
    IQueryProvider QueryProvider { get; }
}

An IQueryProvider is an object that knows how to create IQueryable objects, much like a factory. However, at certain points in time we’ll want you to do a different thing: instead of creating a new IQueryable, we might want you to execute a query on request (for example when you’re applying the First() query operator, eager evaluation results and we’ll need a way to kindly ask you for the value returned by the query):

interface IQueryProvider
{
    IQueryable<T> CreateQuery<T>(Expression ex);
    T Execute<T>(Expression ex);
}

How lame you might think: it’s just asking me to create the IQueryable<T> on LINQ’s behalf. Yes, but you can carry out whatever tricks you need (such as propagating some connection information needed to connect to a database) inside the CreateQuery implementation. Oh, and both methods above have non-generic counterparts.

In addition to the two properties and two methods above, there’s one last property I should mention for completeness: ElementType. The idea of this property is to expose the type of the entities being queried. Why do we need this? Is IQueryable<T> not telling enough, namely T? Indeed, there’s even such a remark in the MSDN documentation:

The ElementType property represents the "T" in IQueryable<T> or IQueryable(Of T).

The reason we still have ElementType is for non-generic cases. For example, you might want to target a data store that doesn’t have an extensible schema, so you don’t need a generic parameter ‘T’. Instead, the type of the data returned by the provider is baked in, and ElementType is the way to retrieve that underlying type.

Finally, we end up with the following definition of IQueryable<T>:

interface IQueryable<T> : IEnumerable<T>
{
    Expression Expression { get; }
    IQueryProvider QueryProvider { get; }
    Type ElementType { get; }
}

All of this might still look fancy, so let’s turn to the consumer side to clarify things. That’s were the asymmetry becomes really apparent.

 

An asymmetric interface (IConsume side)

Let’s assume for a minute we have some Table<T> class that implements IQueryable<T>:

var products = new Table<Product>();

Given our derived interface definition for IQueryable<T> we don’t really get much “query capabilities”, do we? Right, we can ask this instance for things like ElementType (which really will be typeof(T)) and fairly abstract notions of Expression and QueryProvider. But no way we have query operators such a Where and Select available already. However, as you’ll know by know, LINQ relies on such operators. Indeed, take a look at the following query:

var products = new Table<Product>();
var res = from p in products where p.Price > 100 select p.Name;

The way this gets translated by the compiler looks as follows:

Table<Product> products = new Table<Product>();
var res = products.Where(p => p.Price > 100).Select(p => p.Name);

but where’s the Where? The answer lies in extension methods of course. Once we have System.Linq in scope, a (static) class called Queryable is in reach which exposes extension methods for IQueryable<T>. This is precisely why IQueryable<T> deserves the title of “funny interface” since it’s most likely the first interface that has been designed with a split view in mind. On the one hand, there’s the real “interface interface”, i.e. in CLR terms. But on top of that, extension methods provide the really useful interface functionality and act virtually as default method implementations in interfaces. That is, you don’t need to implement a whole bunch of query operator methods to get their functionality.

So, how do those methods work? Before going there, what about refreshing our mind on the LINQ to Objects implementation of those operators, as defined in System.Linq.Enumerable as extension methods on IEnumerable<T>. Just to pick one, consider Where:

static IEnumerable<T> Where<T>(this IEnumerable<T> source, Func<T, bool> predicate)
{
    foreach (T item in source)
        if (predicate(item))
            yield return item;
}

Note: I’ve omitted the (a little tricky to implement – why?) exception throwing code in case source or predicate are null; this is left as an exercise for the reader. Solutions can be found in www.codeplex.com/LINQSQO.

Besides client-side execution using iterators, there are a few important things to notice. First, here we’re extending on IEnumerable<T>. Although IQueryable<T> implements IEnumerable<T>, LINQ to Objects operators won’t be used when applying query operators on an IQueryable<T> data source because the latter type is more specific. If one wants to switch to LINQ to Objects semantics, AsEnumerable<T>() can be called. The second important thing is the type of the second parameter (on the call side this will look like the first and only parameter because we’re looking at an extension method). It’s just a Func<T, bool>, which is a delegate. This triggers the compiler to create an anonymous method:

IEnumerable<Product> products = new List<Product>();
IEnumerable<string> res = products.Where(delegate (Product p) { return p.Price > 100; }).Select(delegate (Product p) { return p.Name; });

Now, switch to the IQueryable<T> counterpart defined in System.Linq.Queryable, ignoring the implementation for a second:

static IQueryable<T> Where<T>(this IQueryable<T> source, Expression<Func<T, bool>> predicate)

Obviously the return type and first parameter type are different, but more importantly is the different type for the predicate parameter. This time it’s an Expression<…> of that same delegate Func<T, bool> type. When the compiler tries to assign a lambda expression to such an Expression<T> it emits code to create an expression tree, representing the lambda’s semantics, at runtime:

IQueryable<Product> products = new Table<Product>();

ParameterExpression p = Expression.Parameter(typeof(Product), “p”);
LambdaExpression <>__predicate = Expression.Lambda(Expression.Greater(Expression.Property(p, “Price”), Expression.Constant(100)), p);
LambdaExpression <>__projection = Expression.Lambda(Expression.Property(p, “Name”), p);

var res = products.Where(<>__predicate).Select(<>__projection);

So, we can already see how a LINQ query ends up as a chain of query operator method calls that are all implemented as extension methods on IQueryable<T> and take in their “function parameter” as an expression tree, so that interpretation and translation can be deferred till runtime. Indeed, an expression tree representing p => p.Price > 100 can easily be translated into a WHERE clause in SQL or whatever equivalent in another DSQL.

 

The inner workings of the beast

Remaining question is how System.Linq.Queryable.* methods are implemented. Obviously no iterators, there’s nothing that can be done client-side. Instead we want to end up with a giant expression tree representing a query, originating from a chain of query operator method calls:

products.Where(<>__predicate).Select(<>__projection)

The query above contains no less than 5 ingredients:

  1. The query source, i.e. “products”, containing all the relevant information to connect to the data store.
  2. First we want to filter the data using a “Where” clause which
    1. takes in a predicate as an expression tree
  3. Next we want to project the results of the previous operator using
    1. a projection represented as an expression tree

After executing the line of code above, we get an IQueryable<string> in return (a string because the projection maps the Product objects onto strings using p.Name), one that should contain all of the information outlined above. Breaking this down, products is an IQueryable<Product> and hence it has an Expression property representing point ‘1’ above – data about the query source. When applying Where to this, we take all existing query information (from the “left hand side of the .”) through the Expression property and add the knowledge we’re about to apply Where with a given predicate (point ‘2’ above), resulting in a new IQueryable<Product>. Finally, Select is applied, again taking the original information via the Expression property, extending it with “Select some projection”, resulting in a new IQueryable<string> in this case. To wrap up this sample, the code above creates no less than three distinct IQueryable<T> instances (that is, including “products” in this count).

A picture is worth a thousand words:

image

Inside the implementation of Where<T>, we:

  1. ask the original source for the expression tree that represents all the information about the query gathered so far (really the left of the ‘.’ when calling Where<T> through extension method syntax);
  2. combine this with the passed in predicate expression tree;
  3. grab the MethodInfo for the currently executing method, i.e. Queryable.Where, which will act as the representation for the query operator in the resulting expression tree;
  4. combine all of the above in a MethodCallExpression;
  5. feed the resulting MethodCallExpression into the IQueryProvider’s CreateQuery<T> method to end up with a new IQueryable<T>.

Subsequent query operator calls, e.g. to Select<T,R>, will continue this process of taking the original query expression and building a new one out of it by extending it with information about the query operator and its arguments (e.g. the projection lambda expression).

 

Conclusion

Quite often, the recommendation for using extension methods is to use them only to “extend” (sealed) classes with helper methods, if you don’t have a way to extend those yourself. In other words, if you’re the owner of a class, you should consider extending the class’s functionality rather than using extension methods are your primary extension mechanism. This recommendation is absolutely correct. However, when dealing with (what I refer to as) “asymmetric” interfaces, extension methods offer an interesting – albeit advanced – capability to separate the bare minimum extensibility points (the real “CLR interface”) from the offered functionality (brought in scope – or “woven in” – through extension methods via a namespace import) to reduce the tension between interface creator and implementor. In this post, you’ve seen one of the pioneers employing this technique: IQueryable<T>. Before you even consider following this technique, think about all the options you have: pure interfaces (keeping the “implementor frustration threshold” in mind), abstract base classes (keeping the single inheritance restriction in mind) and extension method based interface asymmetry.

Enjoy!

Del.icio.us | Digg It | Technorati | Blinklist | Furl | reddit | DotNetKicks

Filed under: ,

Comments

# Dew Drop - August 16, 2008 | Alvin Ashcraft's Morning Dew

Saturday, August 16, 2008 7:16 AM by Dew Drop - August 16, 2008 | Alvin Ashcraft's Morning Dew

Pingback from  Dew Drop - August 16, 2008 | Alvin Ashcraft's Morning Dew

# IQueryable under the cover

Sunday, August 17, 2008 2:02 AM by Marco Russo

In the Programming Microsoft LINQ book we dedicated two whole chapters (76 pages) about the writing of

# IQueryable under the cover

Sunday, August 17, 2008 2:03 AM by SQLBI - Marco Russo

In the Programming Microsoft LINQ book we dedicated two whole chapters (76 pages) about the writing of

# Reflective Perspective - Chris Alcock &raquo; The Morning Brew #160

Pingback from  Reflective Perspective - Chris Alcock  &raquo; The Morning Brew #160

# User links about "grab" on iLinkShare

Wednesday, August 20, 2008 12:30 AM by User links about "grab" on iLinkShare

Pingback from  User links about "grab" on iLinkShare

# WMOC#16 - Continuations, Currying and Recursion - Service Endpoint

Pingback from  WMOC#16 - Continuations, Currying and Recursion - Service Endpoint

# How to Use LINQ SelectMany

Thursday, October 09, 2008 8:49 AM by How to Use LINQ SelectMany

Pingback from  How to Use LINQ SelectMany

# Recent Links Tagged With "schema" - JabberTags

Sunday, November 09, 2008 2:04 PM by Recent Links Tagged With "schema" - JabberTags

Pingback from  Recent Links Tagged With "schema" - JabberTags

# Implementing service queryables: IQueryable to IEnumerable and back | Search RounD

Pingback from  Implementing service queryables: IQueryable to IEnumerable and back | Search RounD