PredicateBuilder nests OR clauses, causing nesting-too-deep issues for large predicates

Question

Summary: I'm using PredicateBuilder to Or() several expressions together, then sending that combined expression to OrmLite's Select() method. However, the generated SQL has a WHERE clause with so many nested parentheses that SQL Server throws an error. What can I do to work around this?

Details: I have a table Foo with two columns, Bar and Baz. If I have a collection of Bar/Baz values and I want to find all matching rows then I might (for example) issue the following SQL:

SELECT * FROM Foo WHERE (Bar=1 AND Baz=1) OR (Bar=2 AND Baz=3) OR ...

Since I'm using OrmLite, I'm using PredicateBuilder to generate a where clause for me:

var predicate = PredicateBuilder.False<Foo>();
foreach (var nextFoo in fooList)
    predicate = predicate.Or(foo => nextFoo.Bar == foo.Bar && 
                                    nextFoo.Baz == foo.Baz);
Db.Select(predicate);

If I execute this with 3 Foos in my list, the generated SQL looks like this (cleaned up for brevity, but intentionally left on one line to make a point):

SELECT Bar, Baz FROM Foo WHERE ((((1=0) OR ((1=Bar) AND (1=Baz))) OR ((2=Bar) AND (3=Baz))) OR ((2=Bar) AND (7=Baz)))

Notice the leading parentheses? The PredicateBuilder continually parenthesizes the existing expression before adding the next one, so that x -> (x) or y -> ((x) or y) or z, etc.

My problem: When I have dozens or hundreds of items to look up, the generated SQL has dozens or hundreds of nested parentheses, and SQL Server kicks it back with a SqlException:

Some part of your SQL statement is nested too deeply. Rewrite the query or break it up into smaller queries.

So what can I do about this? I need the generated SQL's WHERE clause to be flattened (like my example query above) if I want to avoid the nesting exception. I know I can generate my own SQL dynamically and send it to OrmLite's SqlList method, but being forced to do that defeats half of OrmLite's value.

Answer 1

Since SQL does not short-circuits ORs, you can convert an expression tree that looks like this

OR
 \
 OR
  \
  OR
   \
   OR

to an expression tree that looks like this:

        OR
      /    \
     /      \
    /        \
   OR        OR
 /   \     /    \
OR   OR   OR    OR

This is only a work-around: ideally, the framework should be able to deal with situations like that.

One way to construct a tree like this is to split your list recursively in halves, construct an "OR-tree" from each half recursively, and then combine the two "OR-tree"s with another OR:

Predicate ToOrTree(List<Foo> fooList) {
    if (fooList.Count > 2) {
        var firstHalf = fooList.Count / 2;
        var lhs = ToOrTree(fooList.Take(firstHalf).ToList());
        var rhs = ToOrTree(fooList.Skip(firstHalf).ToList());
        return lhs.Or(rhs);
    }
    Predicate res = PredicateBuilder.Create<Foo>(
        foo => fooList[0].Bar == foo.Bar &&  fooList[0].Baz == foo.Baz
    );
    if (fooList.Count == 2) {
        res = res.Or(
            foo => fooList[1].Bar == foo.Bar &&  fooList[1].Baz == foo.Baz
        );
    }
    return res;
}