"Order By" in LINQ-to-SQL Causes performance issues

Question

I've set out to write a method in my C# application which can return an ordered subset of names from a table containing about 2000 names starting at the 100th name and returning the next 20 names.

I'm doing this so I can populate a WPF DataGrid in my UI and do some custom paging. I've been using LINQ to SQL but hit a snag with this long executing query so I'm examining the SQL the LINQ query is using (Query B below).

Query A runs well:

SELECT TOP (20) 
[t0].[subject_id] AS [Subject_id],
[t0].[session_id] AS [Session_id], 
[t0].[name] AS [Name]

FROM [Subjects] AS [t0]
WHERE (NOT (EXISTS(
    SELECT NULL AS [EMPTY]
    FROM (
        SELECT TOP (100) [t1].[subject_id]
        FROM [Subjects] AS [t1]
        WHERE [t1].[session_id] = 1
        ORDER BY [t1].[name]
        ) AS [t2]
    WHERE [t0].[subject_id] = [t2].[subject_id]
    ))) AND ([t0].[session_id] = 1)

Query B takes 40 seconds:

SELECT TOP (20) 
[t0].[subject_id] AS [Subject_id],
[t0].[session_id] AS [Session_id], 
[t0].[name] AS [Name]

FROM [Subjects] AS [t0]
WHERE (NOT (EXISTS(
    SELECT NULL AS [EMPTY]
    FROM (
        SELECT TOP (100) [t1].[subject_id]
        FROM [Subjects] AS [t1]
        WHERE [t1].[session_id] = 1
        ORDER BY [t1].[name]
        ) AS [t2]
    WHERE [t0].[subject_id] = [t2].[subject_id]
    ))) AND ([t0].[session_id] = 1)
ORDER BY [t0].[name]

When I add the ORDER BY [t0].[name] to the outer query it slows down the query.

How can I improve the second query?

---

This was my LINQ stuff Nick

int sessionId = 1;
int start = 100;
int count = 20;

//  Query subjects with the shoot's session id
var subjects = cldb.Subjects.Where<Subject>(s => s.Session_id == sessionId);

//  Filter as per params
var orderedSubjects = subjects
        .OrderBy<Subject, string>(
                    s => s.Col_zero 
                    );                

var filteredSubjects = orderedSubjects
        .Skip<Subject>(start)
        .Take<Subject>(count);

Answer 1

Missing index on [Subjects].[name]?

Answer 2

If you could change the sequence of the .OrderBy in the LINQ Query, you might gain some performance. i.e. you query paged data (unordered), and then do the OrderBy. This will inject your Query A, to do the sorting for in-memory-data.

Answer 3

Your query selects the TOP 20, but when you add ORDER BY to the TOP query, it means it must sort the entire table by Name and then execute this subquery row-by-row. So although the change may seem innocuous, the second query is actually very different, as it now has a lot more than 20 rows to process. It's bad in terms of performance, and even worse if you don't have an index on the Name column.

If you're trying to do paging, you might want to look at this question. Although this is something you'd never do in a multi-user database, SQL Server CE is single-user and for paging queries it's often (almost always) going to be faster to just use either table-direct access for this type of thing or a static cursor (SqlCeResultSet) that can seek backward.