Recently I spent some time working with a customer who was working on converting an existing application which had originally been written against an old 4GL database technology to .Net and EF4.  The programming patterns used in the app were a lot different than what we would normally expect from an app written from scratch against the EF.  In one of the typical scenarios, for instance, a single web service call made more than 200 database queries, so you can imagine that they were very focused on eking out every bit of performance they could.  As we started working on the problem, they tried one of my standard recommendations which was to switch to no tracking queries, but we were surprised to find that it made no appreciable difference in performance.  This was explained when we took a look at the context at the end of running all the queries with the default AppendOnly merge option and discovered that all 200+ queries only retrieved something like 5 different entities.  The code they were migrating retrieved the same entities over and over again, so this app was a perfect candidate for a simple caching solution.

In this post I’ll use the solution we put together for this customer to illustrate a few things about the EF and another interesting feature or two added to .Net 4.  This is NOT a comprehensive, general purpose caching solution.  That’s something which is decidedly beyond the scope of a couple blog posts and that the EF team will look at for a future release.  For this customers’ particular scenario, though, the solution we’re going to look at was very effective.

The key observations that made this possible were:

1) The idea that a programmer can easily give a query a string constant name and use it to rendezvous on the same query elsewhere in their code, and if that’s done, the query name makes a good key for caching.  One of the tricks about compiling LINQ queries is that the expression tree of a LINQ query can’t be used as a key in a dictionary or the like, and trying to create a hash or something like that from the expression is itself quite expensive.  So just specifying a string name makes a lot of things easier.

2) If we specify LINQ queries as a Func taking an IQueryable of entities as its first argument and taking query parameters as the remaining arguments, then that Func is easy to author, it provides something which has the right shape to appease the compiler so that we get great usability in our new caching query API, and that same Func can be executed both against the EF and sent to the database and against an in memory collection with LINQ to Objects.

3) In this particular scenario, query results only need to be cached for the lifetime of a particular ObjectContext instance—we aren’t trying to build something that caches results for queries across multiple threads or multiple mid-tier servers.  This isn’t a second-level cache, but more like a first level one.

4) If we are going to add query caching, it’s critical that we also add query compilation, because for LINQ compilation of queries makes them *dramatically* faster.  A caching solution without compilation would be pretty much pointless.

Usage

What all this means is that we can write code which looks like this:

var cust = ctx.QueryWithCaching("query1", "ALFKI", 
    (IQueryable<Customer> customers, string id) => 
        customers.First(c => c.CustomerID == id));

and if I were to issue the same query again against the same context with the same parameter values, then there would be no roundtrip to the server—instead I would just get back the same results.  Without this new method, because the second run of the query is against the same context, identity resolution would cause me to receive the same object instance back, but the system would require a roundtrip to the database to determine those results.

Similarly, if we just want compilation but not caching, we can write:

var projList = ctx.QueryAutoCompiled("query2", "UK", 
    (IQueryable<Customer> customers, string country) =>
        from c in customers
        where c.Country == country
        select new CustomerProjection() 
        {
            Contact = c.ContactName,
            Country = c.Country
        });

Running this same query again, against this context or any other context, would still require a roundtrip to the database, but it would not require the system to translate the LINQ expression twice—that would happen only on the first call, and then the translation would be cached in a form which can be re-used.  This translation is one of the most expensive parts of performing a LINQ query (after making the roundtrip to the database), so even just this step can often be very useful.

Implementing QueryAutoCompiled

First let’s look at what it takes to implement QueryAutoCompiled, then we’ll take on caching (which uses this method when it actually executes a query against the database).  The auto-compiling task has three parts:

  1. Appeasing the Compiler - creating a set of flexible overloads
  2. Transforming the Lambda - changing the expression from what is passed to our method into the form required by CompiledQuery.Compile
  3. Compiling, Caching & Executing

Let’s take these in reverse order so that we can move from the easiest to the hardest.  Yes, in this case appeasing the compiler really is the hardest part—in fact, it’s appeasing the compiler which forces us to do part #2 at all, but we’ll get to that later.

Compiling, Caching & Executing

Assuming we can get the right lambda expression and have the appropriate parameter values, this process is pretty easy except for one thing—normally the pattern we recommend for compiled LINQ queries is to put the result into a static variable.  That way you only pay the price of translation once for your entire program execution.  Any thread anywhere in your program can access the one static variable which does not need to change and use it to execute a query.  In our case, we want to handle this in a central way, and we’ve got a great key in the form of the query name, so the easiest thing is to use a Dictionary, but we want to put that Dictionary in a static and make it thread safe.  Happily, .Net 4 now includes the parallel extensions and that means we have just the ticket: ConcurrentDictionary.

To make this work we add to the partial class for our strongly typed context a private static ConcurrentDictionary<string, object> and use that to cache the compiled query.  The key type is obviously a string, for the value type we just use object because different compiled query expressions will have different types since they take different numbers of a parameters and produce different results.  I’m not sure, maybe there’s some way we could make this type actually be an expression base type, but it doesn’t provide a lot of extra type-safety because we need to cast the expression to a more specific version in order to execute it anyway.

private static ConcurrentDictionary<string, object> compiledQueryCache = 
    new ConcurrentDictionary<string, object>();

Given the existence of this variable, checking the dictionary for a cached value and doing the compile and caching it if that’s not found is pretty much what you would expect.  Leaving out the method signature and the query rewrite code which we will look at in the Transforming the Lambda section below, here’s the code for a scenario where we take one parameter (arg1) and where the type of the context this is associated with is NorthwindEntities:

object query = null;
if (!compiledQueryCache.TryGetValue(queryName, out query))
{
    // ... rewrite the query -- we’ll replace this comment with code in part 2 below ...
    query = CompiledQuery.Compile(rewritten);
    compiledQueryCache[queryName] = query;
}
var compiledQuery = (Func<NorthwindEntities, TArg1, TResult>)query;
return compiledQuery(this, arg1);

The last line actually executes the query and returns the results.

Transforming the Lambda

Next, let’s fill in the missing code above.  The whole reason for this code comes from the fact that we want our method to take a lambda (or a Func really—we don’t care if it’s source is a lambda or not) which has an IQueryable<Entity> as its first argument, but CompiledQuery.Compile which does the actual compilation for us instead takes a lambda whose first argument is an ObjectContext, and then it looks for ObjectQuery properties in the LINQ expression and assumes they are associated with that context.  One approach to solve this problem would be to just take a lambda of the same signature that Compile requires—the reason Compile works that way is so that you can use the same compiled query with multiple different context instances.  As you saw in the code above, executing the query amounts to invoking the delegate returned from Compile and passing in a context instance (in our case “this” since the QueryAutoCompiled method we are writing is a member of the context we want to execute the query on).  The problem with changing our method to take a Func of that form is first off that having a Func which only takes an ObjectContext as its first parameter makes things even messier with the compiler as we’ll see in the next section.  Secondly having a Func whose first parameter is an IQueryable of an Entity type makes it possible for us to apply that same Func to an in-memory collection of entities with LINQ to Objects as well as to remotely execute it against a database.  This can be handy for testing and other caching scenarios, so switching our code to use Funcs of this type not only simplifies our interactions with the compiler, but it can be handy for other reasons as well.

The trick here is to actually do this transformation.  When I initially ran into this problem I suspected this was possible, but I was a bit concerned that the code would be really nasty.  So I once again took advantage of one of the best perqs of working at Microsoft—especially on a team like the EF.  I got in a room with the dev who implemented most of the LINQ translation for LINQ to Entities, and he showed me what’s involved.  Given the public expression visitor in recent versions of .Net, it turns out that this is really quite easy.

The first requirement is that the argument to our method needs to be an Expression<Func<…>> rather than Func<…>.  All I have to do to make that happen is change my method signature.  The same exact calling code works with either signature as long as the caller restricts themselves to Funcs which are just expressions resulting in a value not statement blocks.  The difference between an Expression and just having a Func is that the Expression is a data structure representing the code while the Func is basically a pointer to the actual IL which will calculate the expression.  In fact, you can get a Func from an Expression by calling the .Compile method on the expression.  This will translate the expression into appropriate IL so that you can then invoke it.  In our case, we will create a new Expression based on the one passed in, and then let CompiledQuery.Compile do the compilation so that the Func we get back will be translated into the TSQL or other database query information needed to run the query against the DB rather than into IL which will use LINQ to Objects to run the query in memory.

To create that new expression, we first create a small class called ParameterSwapper which inherits from ExpressionVisitor.  In the class we override the VisitParameter method so that when we call the Visit method on the base class, it will iterate over the expression tree and call our overridden method on each node in the tree which represents a parameter.  When it finds a particular parameter value it will swap it out for a different paramter value.  In our case we will setup the ParameterSwapper to look for instances of the IQueryable<T> passed into the func and swap them out for an ObjectSet<T> created from our context.

sealed class ParameterSwapper : ExpressionVisitor
{
   readonly Expression replacement;
   readonly ParameterExpression parameter;

   internal ParameterSwapper(Expression replacement, ParameterExpression parameter)
   {
       this.replacement = replacement;
       this.parameter = parameter;
   }

   protected override Expression  VisitParameter(ParameterExpression node)
   {
       if (node == this.parameter)
       {
           return replacement;
       }
       return base.VisitParameter(node);
   }
}

Given that class, the code to rewrite the expression is just these three lines:

ObjectSet<TEntity> objectSet = this.CreateObjectSet<TEntity>();

Expression newBody = new ParameterSwapper(
        Expression.Constant(objectSet, typeof(ObjectSet<TEntity>)), 
        expression.Parameters[0])
    .Visit(expression.Body);

var rewritten = Expression.Lambda<Func<NorthwindEntities, TArg1, TResult>>(newBody, 
    Expression.Parameter(typeof(NorthwindEntities)), expression.Parameters[1]);

First we create an ObjectSet from the context which matches the entity type of the IQueryable.  Then we use the ParameterSwapper to visit the entire body of the lambda expression and create a new body with the first parameter of the lambda replaced by a constant expression referssing to the ObjectSet we just created.  Finally we construct a new lambda whose signature takes the context type as its first argument rather than the IQueryable and whose body is the result of the expression visitor operation.

With this little bit of magic we now have a new Func which is exactly like whatever was passed in except that it has the signature needed by CompiledQuery.Compile.  Those three lines can be pasted in place of the comment in the compiling, caching and execution section above.  Which brings us to the third and most difficult part of QueryAutoCompiled…

Appeasing the Compiler

Now that we have the core logic for all this down, we come to an interesting point.  To make this method as useful as possible, we want to be able to call it with a wide variety of lambdas returning a wide variety of results.  If we were in a very dynamic language, we could probably do this in a snap, but we’re not.  We’re using C# which for the most part requires strong typing.  Happily with generics, type inference, Funcs, Expressions, T4 and all the other things added in recent versions of c#, visual studio and .net, we have a strong set of tools to work with, and by playing a few tricks we can end up with something that is flexible in all the ways we want it to be but no others.

To do that, the first thing we encounter is that we need a family of overloads for our method where each overload takes a different number of parameters.  This mirrors the various versions of Func which take different numbers of parameters.  We could just cut, paste and edit the method as many times as needed to support various numbers of overloads, but not only would that be extremely tedious and error prone to produce the first time, but maintenance of the whole thing would be a nightmare if we ever want to change it.  So, T4 to the rescue!  We’ll just create a small T4 template that contains one definition of our method and then put some template code around it that outputs the method as many times as necessary with the appropriate parts replaced for the various parameters.  As a side benefit, this also means that adding this caching mechanism to an existing solution gets easier because we can just drop the template into a solution, edit one line at the top to point it to the EDMX, and then it will generate a partial class for the context with the appropriate methods on it.

<#
for (int numArgs = 0; numArgs<15; numArgs++)
{
#>
    public TResult QueryAutoCompiled<<#=GetArgTypes(numArgs)#><#=numArgs > 0 ? ", " : ""#>TEntity, TResult>
            (string queryName, 
             <#=GetArgDeclarations(numArgs)#>Expression<Func<IQueryable<TEntity>, 
             <#=GetArgTypes(numArgs)#><#=numArgs > 0 ? ", " : ""#>TResult>> expression)
        where TEntity : class
    {
	// ... do all that caching and compiling stuff described above ...		
        var compiledQuery = (Func<<#=code.Escape(container)#>, 
		                  <#=GetArgTypes(numArgs)#><#=numArgs > 0 ? ", " : ""#>TResult>)query;
       	return compiledQuery(this<#=numArgs > 0 ? ", " : ""#><#=GetArgs(numArgs)#>);
    }

<#
}
#>

Naturally this bit of code needs to be surrounded in the template by code that looks in the EDMX to figure out the name of the context type and things like that, but this represents the core interesting part.  You can see that the QueryAutoCompiled method is surrounded by a loop which iterates from 0 to 14.  The method output for the 4th iteration (which takes 3 parameters) looks like this:

public TResult QueryAutoCompiled<TArg1, TArg2, TArg3, TEntity, TResult>
        (string queryName, 
         TArg1 arg1, TArg2 arg2, TArg3 arg3, 
         Expression<Func<IQueryable<TEntity>, TArg1, TArg2, TArg3, TResult>> expression)
    where TEntity : class
{
    // ... do all that caching and compiling stuff described above ...
    var compiledQuery = (Func<NorthwindEntities, TArg1, TArg2, TArg3, TResult>) query;
   	return compiledQuery(this, arg1, arg2, arg3);
}

Basically we take places where the code needs to change based on the number of arguments and replace them with calls out to simple methods written in the template that take the number of arguments as a parameter and return an appropriate string.  Things like GetArgTypes which returns a series of TArg1, TArg2, etc. and GetArgDeclarations which returns TArg1 arg1, TArg2 arg2, etc.  We also have places which output the name of the context type where needed.

Of course you will notice that this method is a giant generic with many type arguments.  Happily the c# compiler is now pretty darn good at type inference so in almost every case you can ignore all those type arguments when calling the method, and they just provide the right bits needed when we need to refer to those types in the implementation of the method.  If you did have to specify all the generic parameters, the code for using this method gets really, really ugly—especially in cases where you have multiple query parameters, and sadly this is the core of the reason why we needed the visitor code to transform the expression above.  If the first argument to the Func is just ObjectContext, then the compiler can’t properly infer some of the types, and you end up having to manually specify all the generic parameters.  By making the argument an IQueryable, the compiler ends up with enough information to figure everything out for us.

You may also notice that there is a type constraint on the TEntity generic parameter which requires that it be a class rather than a value type.  This is needed because one of the places we use that type in the body of the method has the same constraint.  If we didn’t have it, then the compiler would complain about that type. 

Once we have the multiple arguments thing figured out, we run into the next problem which is that in a few small ways we want to handle passed in expressions that return a set of values differently from those which return exactly one value.  The most important of these cases comes from the fact that if you have a compiled query which returns a set of things, and the resulting delegate’s return type is an IQueryable, then further refinements of the query will cause it to be recompiled transparently—which means the whole refined query will execute on the server but every time you execute it there will be a recompile step.  For me this is usually not what I want.  So if I have a query returning a set of things, after I compile it, I want my execution method to call AsEnumerable on the result and convert it to an IEnumerable rather than an IQueryable so that further refinements will happen using LINQ to Objects rather than be remoted to the database.  If the query just returns a single object, though, you can’t call AsEnumerable.  To allow us to separate out these differences, I put two overloads of the method into the body of the T4 template loop.  One overload is the one above which takes a Func that just returns TResult, and the other overload takes a Func which returns IQueryable<TResult>.  When faced with these two overloads, compiler is smart enough to select the more precise IQueryable<TResult> overload for cases where the Func returns an IQueryable even though if you only had the first overload everything (including things returning IQueryable) would be directed to it.

So the second overload (in T4 form) looks like this:

public IEnumerable<TResult> QueryAutoCompiled<<#=GetArgTypes(numArgs)#><#=numArgs > 0 ? ", " : ""#>TEntity, TResult>
	(string queryName, 
	 <#=GetArgDeclarations(numArgs)#>Expression<Func<IQueryable<TEntity>, 
	 <#=GetArgTypes(numArgs)#><#=numArgs > 0 ? ", " : ""#>IQueryable<TResult>>> expression)
   		where TEntity : class
{
    // ... do all the caching and compiling stuff ...
    var compiledQuery = (Func<<#=code.Escape(container)#>, 
			      <#=GetArgTypes(numArgs)#><#=numArgs > 0 ? ", " : ""#>IQueryable<TResult>>)query;
    return compiledQuery(this<#=numArgs > 0 ? ", " : ""#><#=GetArgs(numArgs)#>).AsEnumerable();
}

If you compare this to the other overload, you will see that the only differences are that the overall method result is IEnumerable<TResult>, the Func’s result type parameter is IQueryable<TResult> and the last line which returns the results calls AsEnumerable() after invoking the delegate.

Once we put both of these overloads inside the loop in the template, we end up generating our QueryAutoCompiled method with 30 overloads (0-14 parameters x 2) which is a bit crazy, but the result is a simple way to execute a linq query and have it sort of auto-magically just run faster the second time.  Given that you have to pass the same query name and Func each time you want to call it, I’d recommend wrapping up the call to QueryAutoCompiled in a method of your own so that you can easily find and call it from wherever in your code.

Finally…  Implementing QueryWithCaching

Now that we’ve built up this method and all the techniques used in it, creating the code to enable caching is pretty simple.  The QueryWithCaching method takes the same signature as QueryAutoCompiled, and we use the same T4 template with dual overrides for single results and sets of things described above. 

In this case we only want to cache the results for the lifetime of the context (not in a static that can be used across multiple contexts).  So we just add a regular Dictionary field to the context:

private Dictionary<object, object> queryResultCache = new Dictionary<object, object>();

The big trick with this dictionary is that the key to it cannot just be the query name string like we used for the compiled query delegate caching above.  In this case we want a separate entry in the dictionary not just for each query but for each combination of parameter values and each query.  To accomplish that we take advantage of another new .Net 4 feature: Tuple.  Tuple is basically a simple generic type that holds a series of values.  Like Func, Tuple comes in a whole series of variants which take different numbers of generic types, but a single Tuple will only hold up to 8 types.  Of course, since the types in a Tuple can be anything, you can always get more things in a Tuple by making the last Type of the Tuple another Tuple, and that’s exactly what we do.  So we create a key for the query result cache by building a Tuple where the first member is the string query name and the remaining members are from 0 to 14 objects—one for each of the query parameters.  Once we have an instance of such a tuple, we can use it as the key for our Dictionary, and the beauty of Tuple is that its equality comparison will make sure that each of the members are equal.

The portion of the T4 template for the single result overload of the method ends up looking like this:

public TResult QueryWithCaching<<#=GetArgTypes(numArgs)#><#=numArgs > 0 ? ", " : ""#>TEntity, TResult>
	(string queryName, 
	 <#=GetArgDeclarations(numArgs)#>Expression<Func<IQueryable<TEntity>, 
	 <#=GetArgTypes(numArgs)#><#=numArgs > 0 ? ", " : ""#>TResult>> expression) 
    where TEntity : class 
{
    var queryKey = <#=GetQueryKey(numArgs)#>;
	
    object result;
    if (!queryResultCache.TryGetValue(queryKey, out result))
    {
        result = this.QueryAutoCompiled(
            queryName<#=numArgs > 0 ? ", " : ""#><#=GetArgs(numArgs)#>, expression);
        queryResultCache[queryKey] = result;
    }
    return (TResult) result;
}

This template fragment depends especially on the following support function added elsewhere in the template:

string GetQueryKey(int numArgs)
{
    if (numArgs == 0)
    {
        return "queryName";
    }
	
    if (numArgs < 8)
    {
        return "new Tuple<string, " + GetArgTypes(numArgs) +  ">(queryName, " + GetArgs(numArgs) + ")";
    }
	
    return "new Tuple<string, " + GetArgTypes(6) + ", Tuple<" + GetArgTypes(7, numArgs) + ">>" + 
        "(queryName, " + GetArgs(6) + ", " + 
        "new Tuple<" + GetArgTypes(7, numArgs) + ">(" + GetArgs(7, numArgs) + "))";
}

The method just captures the three cases: 0 parameters returns just the query name, less than 8 parameters returns a single Tuple with the query name and the parameters, and more than 8 parameters returns a Tuple containing the query name, the first 6 parameters, and then another Tuple with the remaining parameters.

The resulting overload for two parameters, for example, looks like this:

public TResult QueryWithCaching<TArg1, TArg2, TEntity, TResult>
    (string queryName, 
     TArg1 arg1, TArg2 arg2, Expression<Func<IQueryable<TEntity>, 
     TArg1, TArg2, TResult>> expression) 
    where TEntity : class 
{
   var queryKey = new Tuple<string, TArg1, TArg2>(queryName, arg1, arg2);
    
    object result;
    if (!queryResultCache.TryGetValue(queryKey, out result))
    {
        result = this.QueryAutoCompiled(
            queryName, arg1, arg2, expression);
       queryResultCache[queryKey] = result;
   }
   return (TResult) result;
}

As you can see, this code just follows the same basic pattern as the code for dealing the compiled query cache except in this case when it can’t find the result in the cache, it just calls QueryAutoCompiled to run the query (with compilation if needed) and get the result.

The one last wrinkle is the overloads which return sets of results rather than single results.  These overloads need to be different from the single result versions, because once we execute the query we need to copy the results into a List by calling ToList() rather than just sticking the IEnumerable in the cache.  If we put the IEnumerable in the cache, then we wouldn’t have a copy of the query result values but rather sort of a promise to get them when asked, and if one bit of calling code enumerated them, the next bit would find the results already “used up” and not get back what they expected.  So these versions just add a call to ToList at the end of the call to QueryAutoCompiled, looking something like this:

result = this.QueryAutoCompiled(queryName, arg1, arg2, expression).ToList();

That’s it!  Queries with simple caching, and all you have to do is drop a template into your project, edit the line at the top to point to your EDMX file, and then change your query execution code to call one of these methods.

If you want the whole solution strung together, you can find it here.  But don’t forget the caveats: This isn’t full production tested code, and the caching only works for the lifetime of a single context instance.  Real, full-featured caching will have to wait for a future release of the EF.

- Danny