LINQ extension for optimising Skip() Take()

Question

I have been applying the optimization from this blog: RimDev.io

context.Cars
.Where(x => context.Cars
.OrderBy(y => y.Id)
.Select(y => y.Id)
.Skip(50000)
.Take(1000)
.Contains(x.Id)).ToList();

I want to convert this into a general LINQ extension, however, I am not sure how to refer to x.Id in Contains. It does not seem like something that you could pass as an expression but it does not then specifically reference an instance of x.

Update here goes in progress code:

public static class LinqExtension {
    public static IQueryable<TSource> SkipTake<TSource, TKey>(this IQueryable<TSource> source, Expression<Func<TSource, TKey>> selector, int skip, int take)
    where TSource: class {
      return source.Where(x=> source.OrderBy<TSource,TKey(selector)
               .Select(selector)
               .Skip(skip)
               .Take(take)
               .Contains( ??? ));
     }
}

Answer 1

I think you have stepped into the world of Expression tree building. Your question inspired me to create some new helpers to make this easier in certain cases.

Here are some extension methods that help with Expression tree manipulation and building:

public static class ExpressionExt {
    public static Expression Contains(this Expression src, Expression item) => src.Call("Contains", item);

    public static Expression Call(this Expression p1, string methodName, params Expression[] px) {
        var tKey = p1.Type.GetGenericArguments()[0];
        var containsMI = typeof(Queryable).MakeGenericMethod(methodName, px.Length + 1, tKey);
        return Expression.Call(null, containsMI, px.Prepend(p1));
    }

    /// <summary>
    /// Replaces an Expression (reference Equals) with another Expression
    /// </summary>
    /// <param name="orig">The original Expression.</param>
    /// <param name="from">The from Expression.</param>
    /// <param name="to">The to Expression.</param>
    /// <returns>Expression with all occurrences of from replaced with to</returns>
    public static T Replace<T>(this T orig, Expression from, Expression to) where T : Expression => (T)new ReplaceVisitor(from, to).Visit(orig);

    /// <summary>
    /// ExpressionVisitor to replace an Expression (that is Equals) with another Expression.
    /// </summary>
    public class ReplaceVisitor : ExpressionVisitor {
        readonly Expression from;
        readonly Expression to;

        public ReplaceVisitor(Expression from, Expression to) {
            this.from = from;
            this.to = to;
        }

        public override Expression Visit(Expression node) => node == from ? to : base.Visit(node);
    }
}

public static class TypeExt {
    public static MethodInfo GetGenericMethod(this Type t, string methodName, int paramCount) =>
        t.GetMethods().Where(mi => mi.Name == methodName && mi.IsGenericMethodDefinition && mi.GetParameters().Length == paramCount).Single();

    public static MethodInfo MakeGenericMethod(this Type t, string methodName, int paramCount, params Type[] genericParameters) =>
        t.GetGenericMethod(methodName, paramCount).MakeGenericMethod(genericParameters);
}

Now you can create your SkipTake method - I am assuming the Contains member selector parameter is always the same member as the selector parameter.

public static class LinqExtension {
    public static IQueryable<TSource> SkipTake<TSource, TKey>(this IQueryable<TSource> source, Expression<Func<TSource, TKey>> selector, int skip, int take)
        where TSource : class {
        // x
        var xParm = Expression.Parameter(typeof(TSource), "x");
        var qBase = source.OrderBy(selector)
                          .Select(selector)
                          .Skip(skip)
                          .Take(take);
        // selector(x)
        var outerSelector = selector.Body.Replace(selector.Parameters[0], xParm);
        // source.OrderBy(selector).Select(selector).Skip(skip).Take(take).Contains(selector(x))
        var whereBody = qBase.Expression.Contains(outerSelector);
        // x => whereBody
        var whereLambda = Expression.Lambda<Func<TSource,bool>>(whereBody, xParm);
        return source.Where(whereLambda);
    }
}

To create the method, you need to build the lambda for the Where method manually. Rather than build the qBase Expression tree manually, I let the compiler do that for me, then use the resulting Expression. My Call helper makes it easy to create extension methods that correspond to the Queryable extension methods but work on Expression trees though, of course, you could just use Call directly for any Queryable methods you need (but then a Constant helper would be useful).

Once you've built the whereLambda, you just pass it to Where for the original source.