Generating Cache Keys from IQueryable For Caching Results of EF Code First Queries

Question

I'm trying to implement a caching scheme for my EF Repository similar to the one blogged here. As the author and commenters have reported the limitation is that the key generation method cannot produce cache keys that vary with a given query's parameters. Here is the cache key generation method:

private static string GetKey<T>(IQueryable<T> query)
{
    string key = string.Concat(query.ToString(), "\n\r",
        typeof(T).AssemblyQualifiedName);
    return key;
}

So the following queries will yield the same cache key:

var isActive = true;
var query = context.Products
.OrderBy(one => one.ProductNumber)
.Where(one => one.IsActive == isActive).AsCacheable();

and

var isActive = false;
var query = context.Products
.OrderBy(one => one.ProductNumber)
.Where(one => one.IsActive == isActive).AsCacheable();

Notice that the only difference is that isActive = true in the first query and isActive = false in the second.

Any suggestions/insight to efficiently generating cache keys which vary by IQueryable parameters would be truly appreciated.

Kudos to Sergey Barskiy for sharing the EF CodeFirst caching scheme.

Update

I took the approach of traversing the IQueryable's expression tree myself with the goal of resolving the values of the parameters used in the query. With maxlego's suggestion, I extended the System.Linq.Expressions.ExpressionVisitor class to visit the expression nodes that we're interested in - in this case, the MemberExpression. The updated GetKey method looks something like this:

public static string GetKey<T>(IQueryable<T> query)
{
    var keyBuilder = new StringBuilder(query.ToString());
    var queryParamVisitor = new QueryParameterVisitor(keyBuilder);
    queryParamVisitor.GetQueryParameters(query.Expression);
    keyBuilder.Append("\n\r");
    keyBuilder.Append(typeof (T).AssemblyQualifiedName);

    return keyBuilder.ToString();
}

And the QueryParameterVisitor class, which was inspired by the answers of Bryan Watts and Marc Gravell to this question, looks like this:

/// <summary>
/// <see cref="ExpressionVisitor"/> subclass which encapsulates logic to 
/// traverse an expression tree and resolve all the query parameter values
/// </summary>
internal class QueryParameterVisitor : ExpressionVisitor
{
    public QueryParameterVisitor(StringBuilder sb)
    {
        QueryParamBuilder = sb;
        Visited = new Dictionary<int, bool>();
    }

    protected StringBuilder QueryParamBuilder { get; set; }
    protected Dictionary<int, bool> Visited { get; set; }

    public StringBuilder GetQueryParameters(Expression expression)
    {
        Visit(expression);
        return QueryParamBuilder;
    }

    private static object GetMemberValue(MemberExpression memberExpression, Dictionary<int, bool> visited)
    {
        object value;
        if (!TryGetMemberValue(memberExpression, out value, visited))
        {
            UnaryExpression objectMember = Expression.Convert(memberExpression, typeof (object));
            Expression<Func<object>> getterLambda = Expression.Lambda<Func<object>>(objectMember);
            Func<object> getter = null;
            try
            {
                getter = getterLambda.Compile();
            }
            catch (InvalidOperationException)
            {
            }
            if (getter != null) value = getter();
        }
        return value;
    }

    private static bool TryGetMemberValue(Expression expression, out object value, Dictionary<int, bool> visited)
    {
        if (expression == null)
        {
            // used for static fields, etc
            value = null;
            return true;
        }
        // Mark this node as visited (processed)
        int expressionHash = expression.GetHashCode();
        if (!visited.ContainsKey(expressionHash))
        {
            visited.Add(expressionHash, true);
        }
        // Get Member Value, recurse if necessary
        switch (expression.NodeType)
        {
            case ExpressionType.Constant:
                value = ((ConstantExpression) expression).Value;
                return true;
            case ExpressionType.MemberAccess:
                var me = (MemberExpression) expression;
                object target;
                if (TryGetMemberValue(me.Expression, out target, visited))
                {
                    // instance target
                    switch (me.Member.MemberType)
                    {
                        case MemberTypes.Field:
                            value = ((FieldInfo) me.Member).GetValue(target);
                            return true;
                        case MemberTypes.Property:
                            value = ((PropertyInfo) me.Member).GetValue(target, null);
                            return true;
                    }
                }
                break;
        }
        // Could not retrieve value
        value = null;
        return false;
    }

    protected override Expression VisitMember(MemberExpression node)
    {
        // Only process nodes that haven't been processed before, this could happen because our traversal
        // is depth-first and will "visit" the nodes in the subtree before this method (VisitMember) does
        if (!Visited.ContainsKey(node.GetHashCode()))
        {
            object value = GetMemberValue(node, Visited);
            if (value != null)
            {
                QueryParamBuilder.Append("\n\r");
                QueryParamBuilder.Append(value.ToString());
            }
        }

        return base.VisitMember(node);
    }
}

I'm still doing some performance profiling on the cache key generation and hoping that it isn't too expensive (I'll update the question with the results once I have them). I'll leave the question open, in case anyone has suggestions on how to optimize this process or has a recommendation for a more efficient method for generating cache keys with vary with the query parameters. Although this method produces the desired output, it is by no means optimal.

Ousley

Answer 1

i suggest to use ExpressionVisitor http://msdn.microsoft.com/en-us/library/bb882521(v=vs.90).aspx

Nonparticipation

Answer 2

Just for the record, "Caching the results of LINQ queries" works well with the EF and it's able to work with parameters correctly, so it can be considered as a good second level cache implementation for EF.

Transvalue

Could you modify your answer to be a comment instead? To clarify, this question is intended to solve the problem of creating cache keys for out of process caching clusters, so results from identical queries can be shared across multiple servers. – Ousley

I won't. Please refer to the GetCacheKey(this IQueryable query) of the mentioned article for more info about creating the cache key or just spend some time and read it once. – Transvalue

Answer 3

While the solution of the OP works quite well, I found that the performance of the solution is a little bit poor.

The duration of the key generation varied between 300ms and 1200ms for my queries.

However, I've found another solution that has quite better performance (<10ms).

    public static string ToTraceString<T>(DbQuery<T> query)
    {
        var internalQueryField = query.GetType().GetFields(BindingFlags.NonPublic | BindingFlags.Instance).Where(f => f.Name.Equals("_internalQuery")).FirstOrDefault();

        var internalQuery = internalQueryField.GetValue(query);

        var objectQueryField = internalQuery.GetType().GetFields(BindingFlags.NonPublic | BindingFlags.Instance).Where(f => f.Name.Equals("_objectQuery")).FirstOrDefault();

        var objectQuery = objectQueryField.GetValue(internalQuery) as ObjectQuery<T>;

        return ToTraceStringWithParameters(objectQuery);
    }

    private static string ToTraceStringWithParameters<T>(ObjectQuery<T> query)
    {
        string traceString = query.ToTraceString() + "\n";

        foreach (var parameter in query.Parameters)
        {
            traceString += parameter.Name + " [" + parameter.ParameterType.FullName + "] = " + parameter.Value + "\n";
        }

        return traceString;
    }

Amphi

That may be so, but this solution will only work with EF, so you trade performance for flexibility. The OP solution will work with any other ORM, as long as they conform to the IQueryable interface. – Endomorphism

Answer 4

I serialized the IQueryable using this library which looks to use the vistor pattern to materialize the IQueryable.

https://github.com/esskar/Serialize.Linq/

Grafton