In one of our production servers, something was knocking IIS down, logs had nothing (well almost nothing - they had records about application pool failing - but no reason why). Usually that means stackoverflow exception, question was only where and why, could not get any pattern when that was happening.
So to catch the problem, we've installed DebugDiag - tool that helps to catch hard to catch exceptions on production servers. We have quite a lot requests coming in, so we had to tune DebugDiag a bit to reduce performance hit, but in result it gave us line, that was causing problems:

var items = dataContext.Items()
      .InAnsiStringRange(x => x.Sku, 2000, skus)
      .ToDictionary(x => x.Sku, x => x);

Having that, we could reproduce that on development machines, but reason still wasn't obvious - it was failing somewhere inside Linq lib. If you've noticed, in that line there's specific method - InAnsiStringRange. We use it to workaround two problems:

  1. Sql server does not support more than 2100 parameters and Contains method generates in sequence with as many parameters, as there are in searched collection, so if you're searching for more than 2100 Skus for example, query will fail. So we execute query in chunks to avoid this problem.
  2. Linq2Sql has a bug when Contains is used on ANSI strings, it converts everything to Nvarchar - and that is a big performance issue. To avoid that we generate large condition from joined ORs (that may be solved better with rewriting IN condition parameters that were generated by Contains, but we didn't wanted to mess with DbCommand)

So we had this code:

 IEnumerable<Expression> expressions = collection.Select(value => (Expression)Expression.Equal(selector.Body, Expression.Constant(value, typeof(TValue))));
 Expression expression = expressions.Aggregate(Expression.Or);

Debugging it gave idea what is wrong. Thing is, that expression tree is tree-like data structure, where each node is an expression - a method call or a binary operation such as x = y. So it was constructing tree like this: Or aggregated tree

As you can see - tree is unbalanced - one branch is from single element, and another is going deep down. Looks like .NET is recognizing that as recursion and gives stackoverflow exception.

So tree needs to be constructed like this to prevent behavior mentioned above:
Or balanced tree

As you can see it is not as deep as first one.

Problem will still be here, just it will handle much more search items (in my test first type of tree handled ~750 search items, second type of tree handled 200000 search items and I think it is able to handle even more).

To form tree as in second picture, following code was used:

public Expression GenerateTree(List<Expression> expressions, int start, int end) {
    if (start == end) return expressions[start];

    var middle = start + ((end - start) / 2);
    var left = GenerateTree(expressions, start, middle);
    var right = GenerateTree(expressions, middle + 1, end);

    return Expression.Or(left, right);
Comments c#  linq