Nesting Linq-to-Objects query within Linq-to-Entities query –what is happening under the covers?

Question

        var numbers = new int[] { 1, 2, 3, 4, 5 };

        var contacts = from c in context.Contacts
                       where c.ContactID == numbers.Max() | c.ContactID == numbers.FirstOrDefault()
                       select c;

        foreach (var item in contacts) Console.WriteLine(item.ContactID); ;

Linq-to-Entities query is first translated into Linq expression tree, which is then converted by Object Services into command tree. And if Linq-to-Entities query nests Linq-to-Objects query, then this nested query also gets translated into an expression tree.

a) I assume none of the operators of the nested Linq-to-Objects query actually get executed, but instead data provider for particular DB (or perhaps Object Services) knows how to transform the logic of Linq-to-Objects operators into appropriate SQL statements?

b) Data provider knows how to create equivalent SQL statements only for some of the Linq-to-Objects operators?

c) Similarly, data provider knows how to create equivalent SQL statements only for some of the non-Linq methods in the Net Framework class library?

REPLYING TO ADAM MILLS:

1) I'm a bit confused by your reply. In reply to b) you agreed that if say Linq2Entities Data Provider for SQL Server supports particular Linq-to-Objects operator, then it will try to convert it into an equivalent SQL statement, and in reply to c) you also agreed that if this provider supports particular non-Linq method, it will convert it into an equivalent SQL statement ( and if it doesn't support it, it will throw an exception ). But for a) you replied just the opposite of what you said for c), thus that this provider won't try to convert Max into equivalent Sql statement, but will instead execute it and used the returned value in a query?

2) Anyways, I know only some Sql so I can't be completely sure, but reading Sql query generated for the above code it seems data provider didn't actually execute numbers.Max method, but instead just somehow figured out that numbers.Max should return the maximum value and then proceed to include in generated Sql query a call to TSQL's build-in MAX function. It also put all the values held by numbers array into a Sql query.

 SELECT CASE
         WHEN (([Project1].[C1] = 1)
               AND ([Project1].[C1] IS NOT NULL)) THEN '0X0X'
         ELSE '0X1X'
       END                      AS [C1],
       [Extent1].[ContactID]    AS [ContactID],
       [Extent1].[FirstName]    AS [FirstName],
       [Extent1].[LastName]     AS [LastName],
       [Extent1].[Title]        AS [Title],
       [Extent1].[AddDate]      AS [AddDate],
       [Extent1].[ModifiedDate] AS [ModifiedDate],
       [Extent1].[RowVersion]   AS [RowVersion],
       CASE
         WHEN (([Project1].[C1] = 1)
               AND ([Project1].[C1] IS NOT NULL)) THEN [Project1].[CustomerTypeID]
       END                      AS [C2],
       CASE
         WHEN (([Project1].[C1] = 1)
               AND ([Project1].[C1] IS NOT NULL)) THEN [Project1].[InitialDate]
       END                      AS [C3],
       CASE
         WHEN (([Project1].[C1] = 1)
               AND ([Project1].[C1] IS NOT NULL)) THEN [Project1].[PrimaryDesintation]
       END                      AS [C4],
       CASE
         WHEN (([Project1].[C1] = 1)
               AND ([Project1].[C1] IS NOT NULL)) THEN [Project1].[SecondaryDestination]
       END                      AS [C5],
       CASE
         WHEN (([Project1].[C1] = 1)
               AND ([Project1].[C1] IS NOT NULL)) THEN [Project1].[PrimaryActivity]
       END                      AS [C6],
       CASE
         WHEN (([Project1].[C1] = 1)
               AND ([Project1].[C1] IS NOT NULL)) THEN [Project1].[SecondaryActivity]
       END                      AS [C7],
       CASE
         WHEN (([Project1].[C1] = 1)
               AND ([Project1].[C1] IS NOT NULL)) THEN [Project1].[Notes]
       END                      AS [C8],
       CASE
         WHEN (([Project1].[C1] = 1)
               AND ([Project1].[C1] IS NOT NULL)) THEN [Project1].[RowVersion]
       END                      AS [C9],
       CASE
         WHEN (([Project1].[C1] = 1)
               AND ([Project1].[C1] IS NOT NULL)) THEN [Project1].[BirthDate]
       END                      AS [C10],
       CASE
         WHEN (([Project1].[C1] = 1)
               AND ([Project1].[C1] IS NOT NULL)) THEN [Project1].[HeightInches]
       END                      AS [C11],
       CASE
         WHEN (([Project1].[C1] = 1)
               AND ([Project1].[C1] IS NOT NULL)) THEN [Project1].[WeightPounds]
       END                      AS [C12],
       CASE
         WHEN (([Project1].[C1] = 1)
               AND ([Project1].[C1] IS NOT NULL)) THEN [Project1].[DietaryRestrictions]
       END                      AS [C13]
FROM   [dbo].[Contact] AS [Extent1]
       LEFT OUTER JOIN (SELECT [Extent2].[ContactID]            AS [ContactID],
                               [Extent2].[BirthDate]            AS [BirthDate],
                               [Extent2].[HeightInches]         AS [HeightInches],
                               [Extent2].[WeightPounds]         AS [WeightPounds],
                               [Extent2].[DietaryRestrictions]  AS [DietaryRestrictions],
                               [Extent3].[CustomerTypeID]       AS [CustomerTypeID],
                               [Extent3].[InitialDate]          AS [InitialDate],
                               [Extent3].[PrimaryDesintation]   AS [PrimaryDesintation],
                               [Extent3].[SecondaryDestination] AS [SecondaryDestination],
                               [Extent3].[PrimaryActivity]      AS [PrimaryActivity],
                               [Extent3].[SecondaryActivity]    AS [SecondaryActivity],
                               [Extent3].[Notes]                AS [Notes],
                               [Extent3].[RowVersion]           AS [RowVersion],
                               cast(1 as bit)                   AS [C1]
                        FROM   [dbo].[ContactPersonalInfo] AS [Extent2]
                               INNER JOIN [dbo].[Customers] AS [Extent3]
                                 ON [Extent2].[ContactID] = [Extent3].[ContactID]) AS [Project1]
         ON [Extent1].[ContactID] = [Project1].[ContactID]
       LEFT OUTER JOIN (SELECT TOP (1) [c].[C1] AS [C1]
                        FROM   (SELECT [UnionAll3].[C1] AS [C1]
                                FROM   (SELECT [UnionAll2].[C1] AS [C1]
                                        FROM   (SELECT [UnionAll1].[C1] AS [C1]
                                                FROM   (SELECT 1 AS [C1]
                                                        FROM   (SELECT 1 AS X) AS [SingleRowTable1]
                                                        UNION ALL


                                                        SELECT 2 AS [C1]
                                                        FROM   (SELECT 1 AS X) AS [SingleRowTable2]) AS [UnionAll1]
                                                UNION ALL


                                                SELECT 3 AS [C1]
                                                FROM   (SELECT 1 AS X) AS [SingleRowTable3]) AS [UnionAll2]
                                        UNION ALL


                                        SELECT 4 AS [C1]
                                        FROM   (SELECT 1 AS X) AS [SingleRowTable4]) AS [UnionAll3]
                                UNION ALL


                                SELECT 5 AS [C1]
                                FROM   (SELECT 1 AS X) AS [SingleRowTable5]) AS [c]) AS [Limit1]
         ON 1 = 1
       LEFT OUTER JOIN (SELECT TOP (1) [c].[C1] AS [C1]
                        FROM   (SELECT [UnionAll7].[C1] AS [C1]
                                FROM   (SELECT [UnionAll6].[C1] AS [C1]
                                        FROM   (SELECT [UnionAll5].[C1] AS [C1]
                                                FROM   (SELECT 1 AS [C1]
                                                        FROM   (SELECT 1 AS X) AS [SingleRowTable6]
                                                        UNION ALL


                                                        SELECT 2 AS [C1]
                                                        FROM   (SELECT 1 AS X) AS [SingleRowTable7]) AS [UnionAll5]
                                                UNION ALL


                                                SELECT 3 AS [C1]
                                                FROM   (SELECT 1 AS X) AS [SingleRowTable8]) AS [UnionAll6]
                                        UNION ALL


                                        SELECT 4 AS [C1]
                                        FROM   (SELECT 1 AS X) AS [SingleRowTable9]) AS [UnionAll7]
                                UNION ALL


                                SELECT 5 AS [C1]
                                FROM   (SELECT 1 AS X) AS [SingleRowTable10]) AS [c]) AS [Limit2]
         ON 1 = 1
       CROSS JOIN (SELECT MAX([UnionAll12].[C1]) AS [A1]
                   FROM   (SELECT [UnionAll11].[C1] AS [C1]
                           FROM   (SELECT [UnionAll10].[C1] AS [C1]
                                   FROM   (SELECT [UnionAll9].[C1] AS [C1]
                                           FROM   (SELECT 1 AS [C1]
                                                   FROM   (SELECT 1 AS X) AS [SingleRowTable11]
                                                   UNION ALL


                                                   SELECT 2 AS [C1]
                                                   FROM   (SELECT 1 AS X) AS [SingleRowTable12]) AS [UnionAll9]
                                           UNION ALL


                                           SELECT 3 AS [C1]
                                           FROM   (SELECT 1 AS X) AS [SingleRowTable13]) AS [UnionAll10]
                                   UNION ALL


                                   SELECT 4 AS [C1]
                                   FROM   (SELECT 1 AS X) AS [SingleRowTable14]) AS [UnionAll11]
                           UNION ALL


                           SELECT 5 AS [C1]
                           FROM   (SELECT 1 AS X) AS [SingleRowTable15]) AS [UnionAll12]) AS [GroupBy1]
WHERE  [Extent1].[ContactID] IN ([GroupBy1].[A1], (CASE
                                                     WHEN ([Limit1].[C1] IS NULL) THEN 0
                                                     ELSE [Limit2].[C1]
                                                   END))

Based on this, is it possible that Linq2Entities provider indeed doesn't execute non-Linq and Linq-to-Object methods, but instead creates equivalent SQL statements for some of them ( and for others it throws an exception )?

SECOND EDIT:

Ok, I did what you told me:

For b) I created Linq-to-Objects extension method:

public static class TEST_CLASS
{
    public static int Testing<TSource>(this IEnumerable<TSource> source)
    {
        Console.WriteLine("Testing Called"); // here I've put a breakpoint
        return source.Count();
    }
}

        List<int> list = new List<int>() {1,2,3,4,5,6 };

        var contact = (from c in context.Contacts
                       where c.ContactID == list.Testing()
                       select c).First();

When I run the code in debug mode, I immediatelly get the following exception (thus debugger doesn't step into Testing method before throwing an exception):

System.NotSupportedException:LINQ to Entities does not recognize the method 'Int32 TestingInt32' method, and this method cannot be translated into a store expression.

For c) I created non-Linq method:

public class Another_TEST_CLASS
{
    public static int Testing_Again()
    {
        Console.WriteLine("Testing_Again called");// here I've put a breakpoint
        return 1000;
    }
}


        var contact = (from c in context.Contacts
                       where c.ContactID == Another_TEST_CLASS.Testing_Again()
                       select c).First();

When I run the code in debug mode, I immediatelly get the following exception (thus debugger doesn't step into Testing_Again method before throwing an exception):

System.NotSupportedException: LINQ to Entities does not recognize the method 'Int32 Testing_Again()' method, and this method cannot be translated into a store expression. at System.Data.Objects.ELinq.ExpressionConverter.MethodCallTranslator.Default

Thank you in advance

Answer 1

EDIT: My apologies, this answer is for Linq-To-SQL which has a different data provider to Linq-To-Entities and different semantics.

It is the responsibility of the Data Provider to translate the expression tree into a format the underlying store understands, in your case SQL, and it will define its own rules.

See here for a simple implementation of a Linq-To-LDAP provider

In the case of the Linq-Sql Data Provider it knows it needs a value for the where clause. Based on the expression it knows which part of the predicate is to come from the queried table via the use of the predicates parameter (in your example c). The other side of the equality expression must either be a value to pass as a parameter or an SQL (function, query).

If the value expressions result type is a known sql type and it is derived from an Object Reference expression (or a method call on an object reference) the expression is expanded (executed) and the value is passed to the query as a parameter.

If the expression is a direct method reference it will attempt to match it to an SQL function or throw (i.e. this would throw).

 where c.ContactID == Test()

If the expressions result is IQueryable it will continue converting it to Sql.

a) In your case the method numbers.Max() IS executed and the returned value is used for the query, test this by using a custom extension method and put a debug break in it.

b) This is correct, if instead of a locally declared list of numbers you did the following

cts = from c in context.Contacts
                   where c.ContactID == context.Numbers.Max()
                   select c;

It would convert that to a sub-query of the Numbers table (because the return type was IQueryable). If you used a method that was unsupported by the provider in this case you will get an expcetion. Again to test this use a custom extension method.

c) Correct, such as strings StartsWith method which is converted to SQL like

Answer 2

I've just tried this in LinqPad, and the generated SQL looks like:

-- Region Parameters
DECLARE @p0 Int = 5
DECLARE @p1 Int = 1
-- EndRegion
SELECT [t0].[ContactID], [t0].[Name]
FROM [Contacts] AS [t0]
WHERE ([t0].[ContactID] = @p0) OR ([t0].[ContactID] = @p1)

This is using Linq-to-Sql, but I don't think that Linq-to-Entities would do anything different; the provider will execute the Linq-to-Objects queries and insert the results into the expression tree.

---

Edit

It looks like Linq-to-Entities is generating a query to evaluate the numbers.Max() and numbers.FirstOrDefault() on the server. It seems extremely inefficient to do it that way, and it feels like a bug. I can't think of any scenario where the L2E behaviour would be preferable to the L2S behaviour.

You can force the L2S behaviour by extracting the relevant values outside of your query:

var numbers = new int[] { 1, 2, 3, 4, 5 };

int max = numbers.Max();
int first = numbers.FirstOrDefault();

var contacts = from c in context.Contacts
   where c.ContactID == max !| c.ContactID == first
   select c;