Concatenating an IQueryable with an IEnumerable into an IQueryable

Question

I have searched the internet for the last couple days for a solution to this, and haven't found what I've wanted. Basically, here is my problem:

1. I have an interface I need to implement that has a method that returns an IQueryable (I don't have access to the interface, so I cannot change this)
2. I would like the method to return the concatenation of (a) an IQueryable that points to a very large database table, and (b) a large IEnumerable that has been computed in memory of the same Entity type
3. I cannot do queryableA.Concat(enumerableB).Where(condition) because it will try to send the entire array to the server (and, aside from that, I get an exception that it only supports primitive types)
4. I cannot do enumerableB.Concat(queryableA).Where(condition) because it will pull the entirety of the table into memory and treat it as an IEnumerable

So, after some searching, I think I've decided a good way to approach this problem is to write my own ConcatenatingQueryable implementation of IQueryable that takes two IQueryable's and executes the Expression tree on each independently, and then concatenations the results. However, I seem to be having issues as it returns a stack overflow. Based on http://blogs.msdn.com/b/mattwar/archive/2007/07/30/linq-building-an-iqueryable-provider-part-i.aspx, this is what I've implemented so far:

class Program
{
    static void Main(string[] args)
    {
        var source1 = new[] {  1, 2 }.AsQueryable();
        var source2 = new[] { -1, 1 }.AsQueryable();
        var matches = new ConcatenatingQueryable<int>(source1, source2).Where(x => x <= 1).ToArray();
        Console.WriteLine(string.Join(",", matches));
        Console.ReadKey();
    }

    public class ConcatenatingQueryable<T> : IQueryable<T>
    {
        private readonly ConcatenatingQueryableProvider<T> provider;
        private readonly Expression expression;

        public ConcatenatingQueryable(IQueryable<T> source1, IQueryable<T> source2)
            : this(new ConcatenatingQueryableProvider<T>(source1, source2))
        {}

        public ConcatenatingQueryable(ConcatenatingQueryableProvider<T> provider)
        {
            this.provider = provider;
            this.expression = Expression.Constant(this);
        }

        public ConcatenatingQueryable(ConcatenatingQueryableProvider<T> provider, Expression expression)
        {
            this.provider = provider;
            this.expression = expression;
        }

        Expression IQueryable.Expression
        {
            get { return expression; }
        }

        Type IQueryable.ElementType
        {
            get { return typeof(T); }
        }

        IQueryProvider IQueryable.Provider
        {
            get { return provider; }
        }

        public IEnumerator<T> GetEnumerator()
        {
            // This line is calling Execute below
            return ((IEnumerable<T>)provider.Execute(expression)).GetEnumerator();
        }

        IEnumerator IEnumerable.GetEnumerator()
        {
            return ((IEnumerable)provider.Execute(expression)).GetEnumerator();
        }
    }

    public class ConcatenatingQueryableProvider<T> : IQueryProvider
    {
        private readonly IQueryable<T> source1;
        private readonly IQueryable<T> source2;

        public ConcatenatingQueryableProvider(IQueryable<T> source1, IQueryable<T> source2)
        {
            this.source1 = source1;
            this.source2 = source2;
        }

        IQueryable<TS> IQueryProvider.CreateQuery<TS>(Expression expression)
        {
            var elementType = TypeSystem.GetElementType(expression.Type);
            try
            {
                return (IQueryable<TS>)Activator.CreateInstance(typeof(ConcatenatingQueryable<>).MakeGenericType(elementType), new object[] { this, expression });
            }
            catch (TargetInvocationException tie)
            {
                throw tie.InnerException;
            }
        }

        IQueryable IQueryProvider.CreateQuery(Expression expression)
        {
            var elementType = TypeSystem.GetElementType(expression.Type);
            try
            {
                return (IQueryable)Activator.CreateInstance(typeof(ConcatenatingQueryable<>).MakeGenericType(elementType), new object[] { this, expression });
            }
            catch (TargetInvocationException tie)
            {
                throw tie.InnerException;
            }
        }

        TS IQueryProvider.Execute<TS>(Expression expression)
        {
            return (TS)Execute(expression);
        }

        object IQueryProvider.Execute(Expression expression)
        {
            return Execute(expression);
        }

        public object Execute(Expression expression)
        {
            // This is where I suspect the problem lies, as executing the 
            // Expression.Constant from above here will call Enumerate again,
            // which then calls this, and... you get the point
            dynamic results1 = source1.Provider.Execute(expression);
            dynamic results2 = source2.Provider.Execute(expression);
            return results1.Concat(results2);
        }
    }

    internal static class TypeSystem
    {
        internal static Type GetElementType(Type seqType)
        {
            var ienum = FindIEnumerable(seqType);
            if (ienum == null)
                return seqType;
            return ienum.GetGenericArguments()[0];
        }

        private static Type FindIEnumerable(Type seqType)
        {
            if (seqType == null || seqType == typeof(string))
                return null;
            if (seqType.IsArray)
                return typeof(IEnumerable<>).MakeGenericType(seqType.GetElementType());
            if (seqType.IsGenericType)
            {
                foreach (var arg in seqType.GetGenericArguments())
                {
                    var ienum = typeof(IEnumerable<>).MakeGenericType(arg);
                    if (ienum.IsAssignableFrom(seqType))
                    {
                        return ienum;
                    }
                }
            }
            var ifaces = seqType.GetInterfaces();
            if (ifaces.Length > 0)
            {
                foreach (var iface in ifaces)
                {
                    var ienum = FindIEnumerable(iface);
                    if (ienum != null)
                        return ienum;
                }
            }
            if (seqType.BaseType != null && seqType.BaseType != typeof(object))
            {
                return FindIEnumerable(seqType.BaseType);
            }
            return null;
        }
    }
}

I don't have much experience with this interface, and am a bit lost as to what to do from here. Does anyone have any suggestions on how to do this? I'm also open to abandoning this approach entirely if need be.

Just to reiterate, I'm getting a StackOverflowException, and the stacktrace is simply a bunch of calls between the two commented lines above, with "[External Code]" in between each pair of calls. I have added an example Main method that uses two tiny enumerables, but you can imagine these were larger data sources that take a very long time to enumerate.

Thank you very much in advance for your help!

Answer 1

When you break down the expression tree that gets passed into the IQueryProvider, you will see the call chain of LINQ methods. Remember that generally LINQ works by chaining extension methods, where the return value of the previous method is passed into the next method as the first argument.

If we follow that logically, that means the very first LINQ method in the chain must have a source argument, and it's plain from the code that its source is, in fact, the very same IQueryable that kicked the whole thing off in the first place (your ConcatenatingQueryable).

You pretty much got the idea right when you built this - you just need to go one small step further. What we need to do is re-point that first LINQ method to use the actual source, then allow the execution to follow its natural path.

Here is some example code that does this:

    public object Execute(Expression expression)
    {
        var query1 = ChangeQuerySource(expression, Expression.Constant(source1));
        var query2 = ChangeQuerySource(expression, Expression.Constant(source2));
        dynamic results1 = source1.Provider.Execute(query1);
        dynamic results2 = source2.Provider.Execute(query2);
        return Enumerable.Concat(results1, results2);
    }

    private static Expression ChangeQuerySource(Expression query, Expression newSource)
    {
        // step 1: cast the Expression as a MethodCallExpression.
        // This will usually work, since a chain of LINQ statements
        // is generally a chain of method calls, but I would not
        // make such a blind assumption in production code.
        var methodCallExpression = (MethodCallExpression)query;

        // step 2: Create a new MethodCallExpression, passing in
        // the existing one's MethodInfo so we're calling the same
        // method, but just changing the parameters. Remember LINQ
        // methods are extension methods, so the first argument is
        // always the source. We carry over any additional arguments.
        query = Expression.Call(
            methodCallExpression.Method,
            new Expression[] { newSource }.Concat(methodCallExpression.Arguments.Skip(1)));

        // step 3: We call .AsEnumerable() at the end, to get an
        // ultimate return type of IEnumerable<T> instead of
        // IQueryable<T>, so we can safely use this new expression
        // tree in any IEnumerable statement.
        query = Expression.Call(
            typeof(Enumerable).GetMethod("AsEnumerable", BindingFlags.Static | BindingFlags.Public)
            .MakeGenericMethod(
                TypeSystem.GetElementType(methodCallExpression.Arguments[0].Type)
            ),
            query);
        return query;
    }