SQL Linq .Take() latest 20 rows from HUGE database, performance-wise

Question

I'm using EntityFramework 6 and I make Linq queries from Asp.NET server to a azure sql database.

I need to retrieve the latest 20 rows that satisfy a certain condition

Here's a rough example of my query

using (PostHubDbContext postHubDbContext = new PostHubDbContext())
{
    DbGeography location = DbGeography.FromText(string.Format("POINT({1} {0})", latitude, longitude));

    IQueryable<Post> postQueryable =
        from postDbEntry in postHubDbContext.PostDbEntries
        orderby postDbEntry.Id descending
        where postDbEntry.OriginDbGeography.Distance(location) < (DistanceConstant)
        select new Post(postDbEntry);

    postQueryable = postQueryable.Take(20);
    IOrderedQueryable<Post> postOrderedQueryable = postQueryable.OrderBy(Post => Post.DatePosted);

    return postOrderedQueryable.ToList();
}

The question is, what if I literally have a billion rows in my database. Will that query brutally select millions of rows which meet the condition then get 20 of them ? Or will it be smart and realise that I only want 20 rows hence it will only select 20 rows ?

Basically how do I make this query work efficiently with a database that has a billion rows ?

Answer 1

According to http://msdn.microsoft.com/en-us/library/bb882641.aspx Take() function has deferred streaming execution as well as select statement. This means that it should be equivalent to TOP 20 in SQL and SQL will get only 20 rows from the database.

This link: http://msdn.microsoft.com/en-us/library/bb399342(v=vs.110).aspx shows that Take has a direct translation in Linq-to-SQL.

So the only performance you can make is in database. Like @usr suggested you can use indexes to increase performance. Also storing the table in sorted order helps a lot (which is likely your case as you sort by id).

Answer 2

Why not try it? :) You can inspect the sql and see what it generates, and then look at the execution plan for that sql and see if it scans the entire table

Check out this question for more details How do I view the SQL generated by the Entity Framework?

Answer 3

This will be hard to get really fast. You want an index to give you the sort order on Id but you want a different (spatial) index to provide you with efficient filtering. It is not possible to create an index that fulfills both goals efficiently.

Assume both indexes exist:

If the filter is very selective expect SQL Server to "select" all rows where this filter is true, then sorting them, then giving you the top 20. Imagine there are only 21 rows that pass the filter - then this strategy is clearly very efficient.

If the filter is not at all selective SQL Server will rather traverse the table ordered by Id, test each row it comes by and outputs the first 20. Imagine that the filter applies to all rows - then SQL Server can just output the first 20 rows it sees. Very fast.

So for 100% or 0% selectivity the query will be fast. In between there are nasty mixtures. If you have that this question requires further thought. You probably need more than a clever indexing strategy. You need app changes.

Btw, we don't need an index on DatePosted. The sorting by DatePosted is only done after limiting the set to 20 rows. We don't need an index to sort 20 rows.