Monty’s Gush

Caching the results of LINQ queries

Posted on: August 7, 2008

An essential feature of many applications is a caching architecture. What if your query layer could offer an easy way to optionally cache the result of any query issued against it? Ideally, this would

  • work for any LINQ query (over objects, XML, SQL, Entities…)
  • work for anonymous type projections, as well as business entities
  • be statically type safe (no casting required)
  • deal transparently with cache key creation
  • look syntactically like a custom query operator
var q = from c in context.Customers
        where c.City == "London"
        select new { c.Name, c.Phone };

var result = q.Take(10).FromCache();

The FromCache extension method offers a nice way to opt in for local result caching on any LINQ query. Here’s the method signature:

/// <summary>
/// Returns the result of the query; if possible from the cache, otherwise
/// the query is materialized and the result cached before being returned.
/// </summary>
public static IEnumerable<T> FromCache<T>(this IQueryable<T> query) { ... }

Note that this works for any IQueryable<T>, and for any T (including anonymous types). The complete source is available at the bottom of the article. There’s an additional overload to allow more sophisticated caching policies to be specified, and of course you could easily add more.

Formulating the cache key

The main challenge is to automatically generate a cache key which is sufficiently unique for the query, using only the query and no additional user-supplied information. Normally, cache key generation logic tends to permeate application code and really clutter it up. Handliy, LINQ queries are self-describing – what “identifies” a query is the expression it represents, and this is completely captured by the query’s expression tree.

Clearly it is possible to generate a textual representation of an expression tree – that’s almost exactly what they were designed for, and exactly how LINQ to SQL works. All we need to do is build a query evaluater which, instead of generating SQL, returns a suitable textual representation of the query.

Luckily the ToString method on the Expression class already does almost exactly this. Look what it produces for this simple predicate expression:

Expression<Func<Customer, bool>> predicate = c => c.Name.StartsWith("Smith");

Console.WriteLine(predicate.ToString());
"c => c.Name.StartsWith(\"Smith\")"

The information contained in the expression tree data structure allows the Expression.ToString implementation to produce a string representation which looks something like the query’s source code. This is a great candidate for our cache key!

Partial evaluation

A subtle problem is that the ToString output won’t be unique enough if the expression contains “local” nodes which haven’t been evaluated yet. In particular, the way the C# and VB compilers implement closures means that local variable values you might expect to be present in the query are actually on the other end of closure references.

string pattern = "Smith";
predicate = c => c.Name.StartsWith(pattern);

Console.WriteLine(predicate.ToString());
"c => c.Name.StartsWith(value(App.Program+<>c__DisplayClass1).pattern)"

Unfortunately, exactly the same string representation would be also produced by a query for “Jones”. This is because the expression now contains a reference to an unevaluated member of a captured variable. This is what Matt Warren calls the closure mess.

Recall that LINQ queries are not evaluated until the last possible opportunity. If we were to build a query provider, we would need to evaluate all such unevaluated local expressions just before we generated our SQL (or whatever). If only we had a function like so:

predicate = Evaluator.PartialEval(predicate)

Such a sample implementation of partial query evaluation is provided by Microsoft in Creating an IQueryable LINQ Provider. Applying the PartialEval function to the expression walks the tree, evaluates locally-evaluable nodes and returns the simplified expression. This neatly gets us back to our original ToString expression representation.

"c => c.Name.StartsWith(\"Smith\")"

An additional complexity is this: For ConstantExpressions, the ToString implementation simply delegates to the underlying wrapped object. We therefore need to be careful about what we allow to be wrapped in a ConstantExpression during partial evaluation. For example, the string representation of a LINQ to SQL IQueryable object is some version of the SQL that it would like to generate. This may not be enough to ensure uniqueness. Therefore we need to supply a slightly more sophisticated rule to PartialEval which determines whether a given node in the query is locally evaluable in order to prevent raw queries being locally evaluated and wrapped in ConstantExpressions by the partial evaluator.

This issue caused a few bug reports when I first released the source code, in particular for TVF functions in LINQ to SQL.

Local collections

Local collection values can be supplied as parameters to query operators such as Contains and Any, if the query provider supports them.

LINQ to SQL and now Entity Framework v4 both support local collection values. However, local collections (such as lists or arrays) are just constant expressions in a query, so special support is needed to ensure that a suitable cache key is created representing each of their elements.

This is implemented by a pass over the expression tree to make appropriate local collection values expand themselves during ToString invocation. Each method call in the expression is examined, and the argument to any parameters of type IEnumerable<> or List<> is wrapped in an object with an implementation of ToString which prints every element in the collection.

Please see this post for more info on LocalCollectionExpander.

Squashing the key

A final problem is that the cache key string could get very big, especially for complicated queries. Unless your query results are really super-sensitive, it’s fine to use an MD5 fingerprint of the key instead. MD5 fingerprints are not guaranteed to be be unique, but it should be computationally infeasible to find two identical fingerprints.

Gotchas

(1) Multiple data sources of the same type

While generating a cache key from the query expression in this manner is pretty elegant and very useful for LINQ-based applications and libraries, you should take care when using more than one query datasource of the same data type.

Constants in the query (including IQueryables) create the same key. Two different sources of type IQueryable<Customer> are not distinguished from each other – the same queries against them will generate identical cache keys. Usually this is what you want – for example, you want to be able to cache the results of a query regardless of which data context instance the query was issued against.

It (theoretically) may not be what you want in some scenarios. If in doubt, double-check that the cache key strings being generated don’t conflict.

(2) Caching and object-relational mapping

ORMs generally have their own internal object manager. You will need to make sure that your query results from any such provider (LINQ to SQL, Entity Framework, etc.) are released from their object manager.

  • For LINQ-to-SQL, set ObjectTrackingEnabled = false on your DataContext.
  • For Entity Framework, this can be enforced in the FromCache method itself.
  • For this, and other data sources, see the todo: in the source code.

(3) It’s a cache

Remember that the normal consequences of caching still apply. Any object reference put into an application-wide cache will be kept alive indeterminately. Once you put something into cache it can (and probably will) be accessed from arbitrary threads. Cached objects should probably be treated as read-only data.

Cache provider

This example implementation of FromCache uses the System.Web.Caching.Cache class. It’s worth noting that this useful class isn’t really specific to ASP.NET, and can be used by any .NET application or library. You’ll just need a reference to the System.Web assembly. (Note that its use outside web applications is not officially supported by Microsoft.)

Alternatively, you could just as easily use this technique with another cache implementation.

In a recent update to the source code I have extracted the public method IQueryable.GetCacheKey which could help emphasise that the meat of the idea is to automatically generate a cache key for a query. You can do whatever you like with the key, such as make a simple FromCache extension method with the ASP.NET cache, or doing something more complicated.

Source code

using System;
using System.Collections;
using System.Collections.Generic;
using System.Linq;
using System.Linq.Expressions;
using System.Security.Cryptography;
using System.Text;
using System.Web;
using System.Web.Caching;

namespace Monty.Linq
{
    /// <remarks>
    /// Copyright (c) 2010 Pete Montgomery.
    /// http://petemontgomery.wordpress.com
    /// Licenced under GNU LGPL v3.
    /// http://www.gnu.org/licenses/lgpl.html
    /// </remarks>
    public static class QueryResultCache
    {
        /// <summary>
        /// Returns the result of the query; if possible from the cache, otherwise
        /// the query is materialized and the result cached before being returned.
        /// The cache entry has a one minute sliding expiration with normal priority.
        /// </summary>
        public static IEnumerable<T> FromCache<T>(this IQueryable<T> query)
        {
            return query.FromCache(CacheItemPriority.Normal, TimeSpan.FromMinutes(1));
        }

        /// <summary>
        /// Returns the result of the query; if possible from the cache, otherwise
        /// the query is materialized and the result cached before being returned.
        /// </summary>
        public static IEnumerable<T> FromCache<T>(this IQueryable<T> query,
            CacheItemPriority priority,
            TimeSpan slidingExpiration)
        {
            string key = query.GetCacheKey();

            // try to get the query result from the cache
            var result = HttpRuntime.Cache.Get(key) as List<T>;

            if (result == null)
            {
                // todo: ... ensure that the query results do not
                // hold on to resources for your particular data source
                //
                //////// for entity framework queries, set to NoTracking
                //////var entityQuery = query as ObjectQuery<T>;
                //////if (entityQuery != null)
                //////{
                //////    entityQuery.MergeOption = MergeOption.NoTracking;
                //////}

                // materialize the query
                result = query.ToList();

                HttpRuntime.Cache.Insert(
                    key,
                    result,
                    null, // no cache dependency
                    Cache.NoAbsoluteExpiration,
                    slidingExpiration,
                    priority,
                    null); // no removal notification
            }

            return result;
        }

        /// <summary>
        /// Gets a cache key for a query.
        /// </summary>
        public static string GetCacheKey(this IQueryable query)
        {
            var expression = query.Expression;

            // locally evaluate as much of the query as possible
            expression = Evaluator.PartialEval(expression, QueryResultCache.CanBeEvaluatedLocally);

            // support local collections
            expression = LocalCollectionExpander.Rewrite(expression);

            // use the string representation of the expression for the cache key
            string key = expression.ToString();

            // the key is potentially very long, so use an md5 fingerprint
            // (fine if the query result data isn't critically sensitive)
            key = key.ToMd5Fingerprint();

            return key;
        }

        static Func<Expression, bool> CanBeEvaluatedLocally
        {
            get
            {
                return expression =>
                {
                    // don't evaluate parameters
                    if (expression.NodeType == ExpressionType.Parameter)
                        return false;

                    // can't evaluate queries
                    if (typeof(IQueryable).IsAssignableFrom(expression.Type))
                        return false;

                    return true;
                };
            }
        }
    }

    /// <summary>
    /// Enables the partial evaluation of queries.
    /// </summary>
    /// <remarks>
    /// From http://msdn.microsoft.com/en-us/library/bb546158.aspx
    /// Copyright notice http://msdn.microsoft.com/en-gb/cc300389.aspx#O
    /// </remarks>
    public static class Evaluator
    {
        /// <summary>
        /// Performs evaluation & replacement of independent sub-trees
        /// </summary>
        /// <param name="expression">The root of the expression tree.</param>
        /// <param name="fnCanBeEvaluated">A function that decides whether a given expression node can be part of the local function.</param>
        /// <returns>A new tree with sub-trees evaluated and replaced.</returns>
        public static Expression PartialEval(Expression expression, Func<Expression, bool> fnCanBeEvaluated)
        {
            return new SubtreeEvaluator(new Nominator(fnCanBeEvaluated).Nominate(expression)).Eval(expression);
        }

        /// <summary>
        /// Performs evaluation & replacement of independent sub-trees
        /// </summary>
        /// <param name="expression">The root of the expression tree.</param>
        /// <returns>A new tree with sub-trees evaluated and replaced.</returns>
        public static Expression PartialEval(Expression expression)
        {
            return PartialEval(expression, Evaluator.CanBeEvaluatedLocally);
        }

        private static bool CanBeEvaluatedLocally(Expression expression)
        {
            return expression.NodeType != ExpressionType.Parameter;
        }

        /// <summary>
        /// Evaluates & replaces sub-trees when first candidate is reached (top-down)
        /// </summary>
        class SubtreeEvaluator : ExpressionVisitor
        {
            HashSet<Expression> candidates;

            internal SubtreeEvaluator(HashSet<Expression> candidates)
            {
                this.candidates = candidates;
            }

            internal Expression Eval(Expression exp)
            {
                return this.Visit(exp);
            }

            public override Expression Visit(Expression exp)
            {
                if (exp == null)
                {
                    return null;
                }
                if (this.candidates.Contains(exp))
                {
                    return this.Evaluate(exp);
                }
                return base.Visit(exp);
            }

            private Expression Evaluate(Expression e)
            {
                if (e.NodeType == ExpressionType.Constant)
                {
                    return e;
                }
                LambdaExpression lambda = Expression.Lambda(e);
                Delegate fn = lambda.Compile();
                return Expression.Constant(fn.DynamicInvoke(null), e.Type);
            }

        }

        /// <summary>
        /// Performs bottom-up analysis to determine which nodes can possibly
        /// be part of an evaluated sub-tree.
        /// </summary>
        class Nominator : ExpressionVisitor
        {
            Func<Expression, bool> fnCanBeEvaluated;
            HashSet<Expression> candidates;
            bool cannotBeEvaluated;

            internal Nominator(Func<Expression, bool> fnCanBeEvaluated)
            {
                this.fnCanBeEvaluated = fnCanBeEvaluated;
            }

            internal HashSet<Expression> Nominate(Expression expression)
            {
                this.candidates = new HashSet<Expression>();
                this.Visit(expression);
                return this.candidates;
            }

            public override Expression Visit(Expression expression)
            {
                if (expression != null)
                {
                    bool saveCannotBeEvaluated = this.cannotBeEvaluated;
                    this.cannotBeEvaluated = false;
                    base.Visit(expression);
                    if (!this.cannotBeEvaluated)
                    {
                        if (this.fnCanBeEvaluated(expression))
                        {
                            this.candidates.Add(expression);
                        }
                        else
                        {
                            this.cannotBeEvaluated = true;
                        }
                    }
                    this.cannotBeEvaluated |= saveCannotBeEvaluated;
                }
                return expression;
            }
        }
    }

    /// <summary>
    /// Enables cache key support for local collection values.
    /// </summary>
    public class LocalCollectionExpander : ExpressionVisitor
    {
        public static Expression Rewrite(Expression expression)
        {
            return new LocalCollectionExpander().Visit(expression);
        }

        protected override Expression VisitMethodCall(MethodCallExpression node)
        {
            // pair the method's parameter types with its arguments
            var map = node.Method.GetParameters()
                .Zip(node.Arguments, (p, a) => new { Param = p.ParameterType, Arg = a })
                .ToLinkedList();

            // deal with instance methods
            var instanceType = node.Object == null ? null : node.Object.Type;
            map.AddFirst(new { Param = instanceType, Arg = node.Object });

            // for any local collection parameters in the method, make a
            // replacement argument which will print its elements
            var replacements = (from x in map
                                where x.Param != null && x.Param.IsGenericType
                                let g = x.Param.GetGenericTypeDefinition()
                                where g == typeof(IEnumerable<>) || g == typeof(List<>)
                                where x.Arg.NodeType == ExpressionType.Constant
                                let elementType = x.Param.GetGenericArguments().Single()
                                let printer = MakePrinter((ConstantExpression) x.Arg, elementType)
                                select new { x.Arg, Replacement = printer }).ToList();

            if (replacements.Any())
            {
                var args = map.Select(x => (from r in replacements
                                            where r.Arg == x.Arg
                                            select r.Replacement).SingleOrDefault() ?? x.Arg).ToList();

                node = node.Update(args.First(), args.Skip(1));
            }

            return base.VisitMethodCall(node);
        }

        ConstantExpression MakePrinter(ConstantExpression enumerable, Type elementType)
        {
            var value = (IEnumerable) enumerable.Value;
            var printerType = typeof(Printer<>).MakeGenericType(elementType);
            var printer = Activator.CreateInstance(printerType, value);

            return Expression.Constant(printer);
        }

        /// <summary>
        /// Overrides ToString to print each element of a collection.
        /// </summary>
        /// <remarks>
        /// Inherits List in order to support List.Contains instance method as well
        /// as standard Enumerable.Contains/Any extension methods.
        /// </remarks>
        class Printer<T> : List<T>
        {
            public Printer(IEnumerable collection)
            {
                this.AddRange(collection.Cast<T>());
            }

            public override string ToString()
            {
                return "{" + this.ToConcatenatedString(t => t.ToString(), "|") + "}";
            }
        }
    }

    public static class Utility
    {
        /// <summary>
        /// Creates an MD5 fingerprint of the string.
        /// </summary>
        public static string ToMd5Fingerprint(this string s)
        {
            var bytes = Encoding.Unicode.GetBytes(s.ToCharArray());
            var hash = new MD5CryptoServiceProvider().ComputeHash(bytes);

            // concat the hash bytes into one long string
            return hash.Aggregate(new StringBuilder(32),
                (sb, b) => sb.Append(b.ToString("X2")))
                .ToString();
        }

        public static string ToConcatenatedString<T>(this IEnumerable<T> source, Func<T, string> selector, string separator)
        {
            var b = new StringBuilder();
            bool needSeparator = false;

            foreach (var item in source)
            {
                if (needSeparator)
                    b.Append(separator);

                b.Append(selector(item));
                needSeparator = true;
            }

            return b.ToString();
        }

        public static LinkedList<T> ToLinkedList<T>(this IEnumerable<T> source)
        {
            return new LinkedList<T>(source);
        }
    }
}

The source code now assumes .NET 4 and above. If you need to run on .NET 3.5, you can use the MSDN ExpressionVisitor and the framework methods below.

    /// <summary>
    /// These methods are built-in to .NET 4 and above.
    /// </summary>
    public static class Framework35Utility
    {
        public static IEnumerable<R> Zip<T, U, R>(
            this IEnumerable<T> first, 
            IEnumerable<U> second, 
            Func<T, U, R> selector)
        {
            using (var e1 = first.GetEnumerator())
            using (var e2 = second.GetEnumerator())
            {
                while (e1.MoveNext() && e2.MoveNext())
                    yield return selector(e1.Current, e2.Current);                
            }
        }
        
        public static MethodCallExpression Update(
            this MethodCallExpression source,
            Expression @object,
            IEnumerable<Expression> arguments)
        {
            if (@object == source.Object && arguments.SequenceEqual(source.Arguments))
            {
                return source;
            }

            return Expression.Call(@object, source.Method, arguments);
        }
    }

kick it on DotNetKicks.com

Tags: ,

67 Responses to "Caching the results of LINQ queries"

Hi,
I’m having problems getting this to work. [....] it is throwing up errors regarding ObjectQuery and MergeOption. I gather that they are supposed to live in System.Data.Objects and System.Data.Services.Client respectively but I can’t find any evidence of these existing anywhere – am I missing something?

Also, I want to cache results from a stored procedure that return an ISingleResult, e.g.
currencyCode = dataContext.uspCurrencyById(currencyID)
Will your code work for this as well?
Thanks

Hi D Mann,

You are missing .NET 3.5 Service Pack 1. Actually you don’t need it, because the lines giving you trouble are only there to support Entity Framework queries.

This technique only works with IQueryables.

Pete.

Hi Pete.

Great job!

It works great to me in most cases. However is there a way to make it work with TVF’s?

Thanks

Hi Bartek,

What is a TVF?

Pete.

Table Valued Function – a function that returns table.

I.e.:

CREATE FUNCTION f_TVF_Test (@i int)
RETURNS TABLE
AS
RETURN
(
SELECT @i+2 colname
UNION ALL
SELECT @i*8 colname
)

now:

int param=2;
context.f_TVF_Test(param); // returns IQueryable

So i tried

var r1 = context.f_TVF_Test(1).FromCache();
var r2 = context.f_TVF_Test(2).FromCache();

…And found that it doesnt vary by param

Bartek.

Looks like Jeff Atwood from CodingHorror tried to use this on StackOverflow.com, but it apparently couldn’t handle the load:

Hi judahgabriel,

Since Jeff didn’t leave any feedback, I can’t really help…

The implementation simply uses the ASP.NET cache, so perhaps the usual advice about “load” that applies there applies here too…. ;-)

UPDATE: I’ve had a couple of questions about this, so I contacted Jeff. He couldn’t remember what the problem was, but conceded that it might have been at their end. I’ve fixed one issue since then, but this was a cache key bug – I’ve never seen anything that could account for the “errors” he reported, even under quite heavy load.

Pete

UPDATE: The following workaround is interesting, but no longer needed.

Bartek,

Interesting. The short answer is no – unfortunately this is an example of gotcha (1).

The parameter you pass to the auto-generated TVF method has no chance to get into the expression tree – it’s not “part of the query”, so to speak, so it can’t feature in the cache key.

The longer answer is that you could work around this in a number of ways.

(a) Create overloads of FromCache which accept an additional cache key string to prepend to the auto-generated key. This could be useful in general, and not just for dealing with LINQ to SQL’s TVF methods.

(b) Create a Bind function which inertly adds the parameters to the expression tree.

Usage:
db.MyFunction(3)

becomes
db.Bind<MyFunctionResult, int>(db.MyFunction, 3)

public IQueryable Bind(Func<T1, IQueryable> function, T1 arg1)
{
return function(arg1).Where(element => arg1.Equals(arg1));
}

// …create more overloads for additional arguments

The Bind function smuggles the parameter into the expression tree by adding a degenerate Where clause to the IQueryable. This clause will be optimised away by the query provider or database query engine.

Method (a) has the advantage of being more explicit but means you have to start writing your own cache keys; (b) solves this problem (at the expense of a little obscurity!) You could even implement both.

I’ve expanded the Gotchas section to make this limitation clearer. Thanks for the feedback!

Pete.

If you take a look at the expression tree’s ToString() for a call to the TVF you’ll see the parameter value included.

var query = db.f_TVF_Test(5);
Console.WriteLine(((IQueryable)query).Expression);

output:
value(ConsoleApplication3.NorthwindDataContext).f_TVF_Test(5)

So the key to the cache will be different each time. So it should be retrieving different data form the cache without any additional tricks to get the arguments represented in the query.

I suspect the MD5 fingerprint is not unique.

Thanks Matt!

I’m suitably pumped about having a comment from the creator of LINQ to SQL.

It’s not the fingerprint that’s wrong, though.

So the auto-generated TVF methods actually *do* put their parameters into the expression tree, as you point out. Curious!

Closer inspection reveals that the sqlmetal-generated TVF methods use reflection via MethodInfo.GetCurrentMethod to enable the returned query to literally represent the *calling of the TVF method itself*.

So there shouldn’t be any need for the workarounds I posted, as you rightly say.

Why then was Bartek having problems? Well it turns out I had a bug.

The SubtreeEvaluator (as you know!) works by evaluating the highest expression tree node(s) in the subtrees that have been nominated by the bottom-up Nominator visitor.

The problem happens when the query is simple enough that the entire query expression gets nominated. The SubtreeEvaluator dutifully evaluates the top node of the tree and wraps it in a ConstantExpression (of some IQueryable).

However, the ToString() value of such a constant expression is not what we want, as it will give us the ToString implementation of the concrete IQueryable!

EF: “value(System.Data.Objects.ObjectQuery`1[Product])”
DLinq: “SELECT [t0].ProductId….” // yes, in DLinq you produce the actual SQL – but without the SQL parameters to make it suitably unique for the cache key

This means, despite that I’ve been using the query cache without issue in a real product for months, it didn’t work for a query like this:

var q = db.Products.Take(1);

My solution is to look out for this special case of whole-query evaluation, ignore the ConstantExpression and pull out the real query [see fix to the source code].

So this, and LINQ to SQL’s TVF methods, now work as expected.

Any comments or advice massively appreciated!

Pete.

Hey Pete,

This is great work and we’ve been using it very sucessfully – until today :) We’ve got a query which is evaluated with the same expression (and hence MD5) even though the parameters are different. The expression is pretty huge but one thing I noticed is that it’s showing a @p0 parameter in the expression, rather than the actual value being used.

Any ideas why this might be?

Thanks

James

Sorry, seems to be the same issue as the TVF. I just implemented the (a) option and that fixed it

Thanks

Thanks James - if you can send me the source code of the query and the string representation of the expression, I’d like to look into it. You shouldn’t need the workaround I concocted for TVFs if you’re using the code as it is posted above – so this may be indicative of a deeper problem, which I’d like to know about. Can you mail me via the contact page?

Thanks,
Pete.

UPDATE: My earlier fix didn’t fully solve the TVF problem. I’ve added an additional rule to CanBeEvaluatedLocally to enable full support for them – if you are using TVFs please make sure you’re using the latest version of the code above.

Thanks James!

I don’t get it. Doesn’t FromCache gets executed after the query execution?

Hi Thiago,

FromCache takes advantage of the fact that LINQ queries are just that – queries, not results. FromCache accepts an IQueryable object (a query) and executes it (using ToList) if it can’t find the appropriate result already in the cache.

Is it any way to use your technique with CacheDependency, so if any element from query has changes, the cache is deleted?

We have implemented the FromCache feature in our PLINQO (http://www.plinqo.com) framework for anyone who is interested.

We are planning to put a page on the PLINQO site shortly that will appropriately give credit to incredibly smart people like Pete for LINQ to SQL improvements that we have scoured the internet for.

Maybe I’m missing something, but how does the FromCache() method get added to the IQueryable object (re: the first example in the post)?

ahh, extension methods. cool stuff. and great post, pete. i’m learning a lot from it.

http://msdn.microsoft.com/en-us/library/bb383977.aspx

Thanks for the post. This looks like it might just solve a problem I’ve been banging my head against for a while.

I implemented this and it compiled and looked like it was working properly. However, when I looked at my profiler to do a quick test it was going to the database everytime. Looking at my linq code I had a where date >= DateTime.Now which was the cluprit.
Using the DateTime.Now correctly create a different cache key for each run of the query. Another gotcha I guess!
thanks for the great code

[...] There are a different ways to approach caching with linq (e.g. caching the query, results of query, etc.) but in this simple case we get the cache key as the only parameter on the function so [...]

@Twisted, One of the early design mistakes of .NET was perhaps that DateTime.Now should have been a method, not a property. Then it would be clearer that the value is different every time you access it.

The query evaluator is behaving correctly – if the query is different, then it won’t be in the cache.

Pete.

How are people handling stale data with these methods?

Is there a way to add cache dependency?

I have some queries of the form
var elementalBlocksInNamedTrackSection = m_elementalBlockRepository.FindAll(eb => trackPieceIds.ToArray().Contains(eb.trackPieceId));

FindAll is just a wrapper for Where in my Repository class

Unfortunately my Contains is not being expanded by so I’m getting duplicate keys. Any idea on what I can do?

[...] for that strange-looking MD5Fingerprint method, “Monty” uses a similar method to convert unique IQueryable expressions into MD5 hashes. It’s a [...]

Hiya Paul – I may not have understood the question, but if I have then then the problem is that ToArray returns an array, not an IQueryable. Could you show me how/where you’re calling FromCache?

public IEnumerable FindAll(Expression<Func> exp)
{
IQueryable query = Table.Where(exp);

return query.FromCache();
}

I really appreciate you putting this source out there, but could you also please specify what libraries/references need to be included at the top of the file? It’s been a real headache trying to track them all down.

Have you tried this with .net 4.0 and EF? I’m getting this error.

{“This method supports the LINQ to Entities infrastructure and is not intended to be used directly from your code.”}

Can you send me the stack trace? Thanks.

stack trace for .net 4 and EF sent in prior email from the “contact us” page. Please let me know if you received or if I should send by another means or post as a comment to this blog.

Again, thanks for your help.

Brian

Thanks for the code. Like some of the folks above, I’m wondering how I can expire/ delete/ remove a cache item. Could I make the ToMd5Fingerprint method public and then delete that from the cache?

This is great! But when combined with Compiled Queries (see ) it seems to generate a new cache key for every invocation. I tried to debug it myself but the query/expression visitor stuff is way over my head. Any ideas, Pete or anybody else?

Sorry, meant to say see http://omaralzabir.com/solving_common_problems_with_compiled_queries_in_linq_to_sql_for_high_demand_asp_net_websites/ for background on compiled queries.

I realize that the advantage of compiled queries would be reduced when using this QueryResultCache technique, since the query only gets compiled to SQL once for each cache insertion. But compiled queries have become ingrained into Best Practices on our team, and we would like to keep it that way. For example, there are times when you loop through a batch of records and for each record, depending on some logic, you may need to load an associated record for processing. Well, without compiled queries, the query must be compiled to SQL each time. With a compiled query, you save that step, but you lose caching.

I suppose it comes down to choosing which approach is better based on what you’re doing in the code. In the example above, caching probably wouldn’t help much anyway, since each record is only processed once. So compiled queries would be better there.

Thanks for the information on Linq Caching. Just what I needed.

Nice! Exactly what i was looking for!

So if i understand right..

we use it that way :

var q = from c in context.Customers
where c.City == “London”
select new { c.Name, c.Phone };

var result = q.Take(10).FromCache();

because i think LINQ query arent executed until they bind, FromCache() will check if the result is already there.. if not it will lets the query being executed.

Does that invalidate the data in any way ?

Thanks.

This works great on scalar values, but the PartialEval function won’t evaluate collections, even local collections of something as simple as ints. What do you think the best way around this is?

Could you post a short sample of the problem you’re having?

I think it might be the same issue Paul was having. When I use the .Contains operator to check a collection for a match, it doesn’t get evaluated locally. For example:

List CustomerIDsToLoad = new List();
List.add(1);
List.Add(2);
List.Add(3);

var CustomerNames = from c in db.Customers where CustomerIDsToLoad.Contains(c.Id)
select c;

The CustomerIDsToLoad.Contains(c.Id) portion won’t be evaluated locally. Instead it will just look like this: System.Collections.Generic.List`1[System.Int32]

Your article helped me out a lot but I have one question.

I am using the specification pattern and wrapping LINQ statements in object such ForCustomerWithId(50) which returns a statement like candidate=>candidate.Id == 50. I can also chain them like this new ForCustomerWithId(50).And(new IsActive()) which creates and expression like this candidate=>candidate.Id == 50 && candidate.Active == true

However if I swap them like this new IsActive().And(new ForCustomerWithId(50)) the expression is different but it is looking for the same results. Is there anyway to take this into account?

Thanks,
Bill

I have updated the source code to support local collection values. Thanks to Matt S for his help testing the solution.

http://petemontgomery.wordpress.com/2011/01/03/fromcache-now-supports-local-collections/

Credit where credit is due please ;-)

check this post
April 13, 2010 at 4:48 am

Sorry for not getting what you were saying, Paul!

[...] spent the past week working with Pete Montgomery of Monty’s Gush fame to expand his brilliant FromCache() method to permit local collection [...]

This needs to go into GitHub or CodePlex or something!

Pete, this code is too important to keep on a blog! We should definitely add it to a source repository so that we can track changes.

Also, I’ve had to convert it to VB.NET for easy inclusion in an existing project (trickier than you’d think due to the extension use of lambda’s and yield’s.) I would be happy to volunteer to maintain the VB.NET version alongside your latest C# version in whatever source repository you would like to use.

[...] with Peter Montgomery’s “Caching the results of LINQ queries” source listed herewhich creates an extension method for IQueryable returning an IEnumerable from cached data if [...]

This is so elegant! What a nice solution. One question: How can we invalidate a query’s cache when one of the records it returns is changed.

e.g. you have 20 records and two queries. The first query returns the first 10 records, the second query returns the last 10 records. If one of the first 10 records is updated the first query should be invalidated while the second is still valid. Thoughts?

I did something completely different, when I came to this problem, I started to analyze the Expression<Func> and got a satisfying result , no matter how you write the expression I managed to make it into something like this:
“p.PostIdEqual1AndAlsop.StatusEqual1OrElsep.StatusEqual2″
I know that looks a bit weird but I got these results without compiling and avoiding ToString() until the very last moment. I have tried my code on x number of parameters and even if it has a compiler class baked in this still gets the value, all this with a fraction of the code here, I’m not saying it’s perfect but feels as a good alternative than using the IQueryable, I’m more than willing to share this piece of code as I’m sure it could be done better.

Excellent code, can someone please convert the following code to vb.net from the above, as all our other libraries are in vb.net so need the above to be of the same format:

var args = map.Select(x => (from r in replacements
where r.Arg == x.Arg
select r.Replacement).SingleOrDefault() ?? x.Arg).ToList();

Thanks

Z

Joakim I for one would love to see your code

Thanks Paul

I actually improved it a bit so it’s now readable with spaces,

private static string GetValueFromExpression(this Expression expression) {
var memberExpression = (ConstantExpression) expression;

return memberExpression.Value.ToString();
;
}

public static string GetCacheKey(this Expression<Func> expression)
where TEntity : class, IEntity {
// We get the name of the class so it gets more unique
string key = typeof (TEntity).Name + ” “;
//We get the binary expression from the expression body so we can get the values
var binaryExpression = (BinaryExpression) expression.Body;
key = GetKey(binaryExpression, key);
//We get rid of the trailing and double whitespace to make it look more clean
key = key.Replace(” “, ” “).TrimEnd();

return key;
}

private static string GetKey(BinaryExpression binaryExpression, string key) {
//if the nodetype on the right side of the expression not is a constant we will need to work on it in order to get the values
if (binaryExpression.Right.NodeType != ExpressionType.Constant) {
//we cast the left side to a binary expression and call this method again so we can dig down the expression tree and get what we want
var binaryExpressionNestedLeft = (BinaryExpression) binaryExpression.Left;
key = GetKey(binaryExpressionNestedLeft, key);
//binaryExpression.NodeType here would return for example AndAlso, OrElse and so on.
key += string.Format(” {0} “, binaryExpression.NodeType);

//we do the same for the right side and since the right side would always be the ending we won’t need to get the binaryExpression.NodeType again
var binaryExpressionNestedRight = (BinaryExpression) binaryExpression.Right;
key = GetKey(binaryExpressionNestedRight, key);
}
//if the nodetype is an ExpresisonType of constant we can get the values
else
{
//binaryExpression.Left returns for example “p.CommentId”.
//binaryExpression.NodeType returns for example “Equals”, “NotEquals” and so on.
//binaryExpression.Right contains the value for example “132″
key += string.Format(“{0} {1} {2} “, binaryExpression.Left, binaryExpression.NodeType, binaryExpression.Right.GetValueFromExpression());
}

return key;
}

Noticed that my post got parsed, the method takes expression of type Func TEntity,bool

Sorry for the spamming but the above code isn’t fully working, here is the working code http://pastebin.com/DhHi0Cs2 this has been fully tested and works great for getting a unique key from an expression func tentity, bool, after you get a key you can go with the CacheRepository pattern or something else that you would like.

This is really great, any thoughts on how to extend it to ISingleResult so stored procedure results can be cached?

After looking at ISingleResult the only way I can see to do it is to pass into FromCache the array of parameters used by ISingleResult, concatenate them with separators and run ToMd5Fingerprint on that. At least then it can be syntactically used like:

q.Take(10).FromCache(parameterArray);

Any thoughts on alternatives, this relies on ToString methods unfortunately.

Hi,
First of all, thanks for this great piece of code!

I’ve been using it but I have found a big problem when using Joins:
The table that is joined is wrongly identified as a local collection and a full select is performed to the table, every time I get the query from cache!

Does anybody have this problem or can confirm this?

Example query:
Dim query = From element1 In context.Table1
Join element2 In context.Table2 On element1.Key Equals element2.Key
Where
element2.SomeValue = “value”
Select New With {element1, element2}

Dim result = query.FromCache()

How would you cache the result of q.Count();

q.FromCache().Count(); causes all of the records to be read from the DB instead of running a COUNT(*) query. And of course q.Count().FromCache(); does not work.

Hi Pete – I was writing a caching layer for EF 4.1 code first over the weekend and as I was coming to a close and thought I’d google to see if anybody had done anything similar. Your post came up and we’ve both got a very similar approach – except yours is more mature so I’m going to park my code and move to yours.

Prior to materialising the query I’ve implemented:

var queryable = query as IQueryable;
if ( queryable != null )
{
queryable = queryable.AsNoTracking();
}

Does that look about right to you? I’ve also had to constraint the generics so that T : class. Do you know if this is the preferred route for EF 4.1?

Also in response to Todd’s question – any thoughts on the best way to cache aggregate functions? The solution I’ve come up with and have now integrated into your solution is has a declaration of

public static TResult FromAggregateCache( this IQueryable query, Func<IEnumerable, Func, TResult> func, Func selector )

So to use it you do:

var count = table.Where( m => m.condition).FromAggregateCache( System.Linq.Enumerable.Count );

or

var sum = table.Where( m => m.condition).FromAggregateCache( System.Linq.Enumerable.Sum, m => m.field );

If anyone is interested in the aggregate cache then I’m more than happy to release it independently or if Pete wishes to incorporate it then that’d be great. There’s a few gotcha’s in the code at the moment but with a few more eyes on it those should be solveable.

[...] 再搜索了一下,有个同学在08年还专门做了个”Caching the results of LINQ queries” [...]

I get next error
When called from ‘VisitMemberInit’, rewriting a node of type ‘System.Linq.Expressions.NewExpression’ must return a non-null value of the same type. Alternatively, override ‘VisitMemberInit’ and change it to not visit children of this type.
Anybody familiar with this type of error.

Hello,
Here is the implementation of the second level caching in EF Code first based on the above class + invaliding the cache automatically:

http://www.dotnettips.info/File/UserFile?name=EfSecondLevelCaching.zip

Any answer to Djordje’s error? I’m getting the same.

[...] operation won’t give you a key that is “uniqe enough” so a technique presented by Pete Montgomery is used to partially evaluate the expression tree of the [...]

Djordje [...] I get next error When called from ‘VisitMemberInit’, [...]
I am seeing the same error. Can be reproduced by running
Table data = context.GetTable();
string s = data.Select(z => new Class2 {PropC = z.PropA}).GetCacheKey();
I “solved” my problem by adding check to CanBeEvaluatedLocally()
if (expression.NodeType == ExpressionType.New)
return false;
I am still trying to understand the ramifications of my fix. With this change in place the cache key is now (before md5) “Table(Table1).Select(z => new Class2() {PropC = z.PropA})”
I would like to know if this is a good fix. How widely is this code used in production?

Thank you!

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Follow

Get every new post delivered to your Inbox.

%d bloggers like this: