Converting a lambda expression into a unique key for caching

Question

I've had a look at other questions similar to this one but I couldn't find any workable answers.

I've been using the following code to generate unique keys for storing the results of my linq queries to the cache.

    string key = ((LambdaExpression)expression).Body.ToString();

    foreach (ParameterExpression param in expression.Parameters)
    {
        string name = param.Name;
        string typeName = param.Type.Name;

        key = key.Replace(name + ".", typeName + ".");
    }

    return key;

It seems to work fine for simple queries containing integers or booleans but when my query contains nested constant expressions e.g.

// Get all the crops on a farm where the slug matches the given slug.
(x => x.Crops.Any(y => slug == y.Slug) && x.Deleted == false)

The key returned is thus:

(True AndAlso (Farm.Crops.Any(y => (value(OzFarmGuide.Controllers.FarmController+<>c__DisplayClassd).slug == y.Slug)) AndAlso (Farm.Deleted == False)))

As you can see any crop name I pass will give the same key result. Is there a way I can extract the value of the given parameter so that I can differentiate between my queries?

Also converting the y to say the correct type name would be nice.....

Etalon

whats wrong with using the GetHashCode() method and a HashSet<LambdaExpression>? It's not unique but a HashSet is in most cases able to receive and add items in O(1). – Mayflower

@CommuSoft, that wouldn't work, because even two expressions that look exactly the same wouldn't be considered equal (unless you provided your own equality comparer). – Conjugation

@CommuSoft - Besides, a hashcode is not guaranteed unique and therefore a potential bug in your code – Intelligent

this link: petemontgomery.wordpress.com/2008/08/07/… explains exactly the problem and how to deal with it. – Intelligent

I suspect to solve this you could use ExpressionVisitor to detect and flatten any sequence of MemberExpression (*n) on a ConstantExpression, evaluating this and replacing with a straight ConstantExpression; not trivial, but not too crazy either. Which, reading Polity's comment, is exactly what PartialEval does. – Godgiven

+1 just for the slug example :) – Whited

Expressions are recreated from scratch when invoked. Hence they will never share the same instance. Unlike delegates. – Kyne

Answer 1

As Polity and Marc said in their comments, what you need is a partial evaluator of the LINQ expression. You can read how to do that using ExpressionVisitor in Matt Warren's LINQ: Building an IQueryable Provider - Part III. The article Caching the results of LINQ queries by Pete Montgomery (linked to by Polity) describes some more specifics regarding this kind of caching, e.g. how to represent collections in the query.

Also, I'm not sure I would rely on ToString() like this. I think it's meant mostly for debugging purposes and it might change in the future. The alternative would be creating your own IEqualityComparer<Expression> that can create a hash code for any expression and can compare two expressions for equality. I would probably do that using ExpressionVisitor too, but doing so would be quite tedious.

Conjugation

Here is a link to Matt Warren's blog post that works web.archive.org/web/20160122054419/http://blogs.msdn.com/b/… The whole blog series has been moved to Github as well: github.com/mattwar/iqtoolkit/tree/master/docs/blog – Ostracod

These other sections for Matt Warren's blog post can also be useful. web.archive.org/web/20160122054419/http://blogs.msdn.com/b/… web.archive.org/web/20190118145231/https://… And if you are really interested in the code behind it. it has all been moved to github github.com/mattwar/iqtoolkit – Ostracod

Answer 2

I've been trying to figure out a scenario where this kind of approach could be useful without leading to bloated cache that is insanely hard to maintain.

I know this isn't directly answering your question, but I want to raise a few questions about this approach that, at first, may sound tempting:

• How did you plan to manage parameter ordering? Ie. (x => x.blah == "slug" && !x.Deleted) cache key should equal (x => !x.Deleted && x.blah == "slug") cache key.
• How did you plan to avoid duplicate objects in cache? Ie. Same farm from multiple queries would by design be cached separately with each query. Say, for each slug that appears in the farm, we have a separate copy of the farm.
• Extending the above with more parameters, such as parcel, farmer etc. would lead to more matching queries with each having a separate copy of the farm cached. The same applies to each type you might query plus the parameters might not be in the same order
• Now, what happens if you update the farm? Without knowing which cached queries would contain your farm, you'd be forced to kill your whole cache. Which kind of is counterproductive to what you're trying to achieve.

I can see the reasoning behind this approach. A 0-maintenance performance layer. However, if the above points are not taken into consideration, the approach will first kill the performance, then lead to a lot of attempts to maintain it, then prove to be completely unmaintainable.

I've been down that road. Eventually wasted a lot of time and gave up.

I found a much better approach by caching each resulting entity separately when the results come from the backend with an extension method for each type separately or through a common interface.

Then you can build extension method for your lambda expressions to first try the cache before hitting the db.

var query = (x => x.Crops.Any(y => slug == y.Slug) && x.Deleted == false);
var results = query.FromCache();
if (!results.Any()) {
    results = query.FromDatabase();
    results.ForEach(x = x.ToCache());
}

Of course, you will still need to track which queries have actually hit the database to avoid query A returning 3 farms from DB satisfying query B with one matching farm from cache while the database would actually have 20 matching farms available. So, each query stll need to hit DB at least once.

And you need to track queries returning 0 results to avoid them consequently hitting the DB for nothing.

But all in all, you get away with a lot less code and as a bonus, when you update a farm, you can

var farm = (f => f.farmId == farmId).FromCache().First();
farm.Name = "My Test Farm";
var updatedFarm = farm.ToDatabase();
updatedFarm.ToCache();

Delois

I actually knocked up something [here] The cache keys are created from partially evaluating the lambda expression so only the return from the IQueryable is cached. On update the cache will clear out all objects cached with a specific key. It's still a work in progress but seems very promising. I need to do some tidy up re objectcontext vs dbcontext. (github.com/JimBobSquarePants/EFBootstrap) – Etalon

Answer 3

What about this?

public class KeyGeneratorVisitor : ExpressionVisitor
{
    protected override Expression VisitParameter(ParameterExpression node)
    {
        return Expression.Parameter(node.Type, node.Type.Name);
    }

    protected override Expression VisitMember(MemberExpression node)
    {
        if (CanBeEvaluated(node))
        {
            return Expression.Constant(Evaluate(node));
        }
        else
        {
            return base.VisitMember(node);
        }
    }

    private static bool CanBeEvaluated(MemberExpression exp)
    {
        while (exp.Expression.NodeType == ExpressionType.MemberAccess)
        {
            exp = (MemberExpression) exp.Expression;
        }

        return (exp.Expression.NodeType == ExpressionType.Constant);
    }

    private static object Evaluate(Expression exp)
    {
        if (exp.NodeType == ExpressionType.Constant)
        {
            return ((ConstantExpression) exp).Value;
        }
        else
        {
            MemberExpression mexp = (MemberExpression) exp;
            object value = Evaluate(mexp.Expression);

            FieldInfo field = mexp.Member as FieldInfo;
            if (field != null)
            {
                return field.GetValue(value);
            }
            else
            {
                PropertyInfo property = (PropertyInfo) mexp.Member;
                return property.GetValue(value, null);
            }
        }
    }
}

This will replace the complex constant expressions to their original values as well as the parameter names to their type names. So just have to create a new KeyGeneratorVisitor instance and call its Visit or VisitAndConvert method with your expression.

Please note that the Expression.ToString method will be also invoked on your complex types, so either override their ToString methods or write a custom logic for them in the Evaluate method.

Interinsurance

I found this very helpful. I had to add an overload for VisitBinary to handle conversion of constant value, but otherwise it worked like a charm. – Miso

Answer 4

How about:

var call = expression.Body as MethodCallExpression;

if (call != null)
{

    List<object> list = new List<object>();

    foreach (Expression argument in call.Arguments)
    {

        object o = Expression.Lambda(argument, expression.Parameters).Compile().DynamicInvoke();

        list.Add(o);

    }

    StringBuilder keyValue = new StringBuilder();

    keyValue.Append(expression.Body.ToString());

    list.ForEach(e => keyValue.Append(String.Format("_{0}", e.ToString())));

    string key = keyValue.ToString();

}

Ballman