7

I have a parent table that contains a foreign key to a lookup table (simplified example):

CREATE TABLE [dbo].[Parent] (
    [Id] [uniqueidentifier] NOT NULL,
    [LookupId] [uniqueidentifier] NULL
)

CREATE TABLE [dbo].[Lookup] (
    [Id] [uniqueidentifier] NOT NULL,
    [Name] [nvarchar](64) NOT NULL
)

In this case, the Parent table has over 10 million rows and the Lookup table has around 5,000. The real Parent implementation has several such foreign key references to other tables and each of those columns may contain NULLs.

Both example tables have unique clustered indexes for their Id columns, Parent has a non-clustered index for LookupId and Lookup has a non-clustered index for Name.

I'm running a paged query where I want to include the lookup value in the results:-

SELECT
    P.Id,
    L.Name
FROM Parent P
LEFT JOIN Lookup L ON P.LookupId = L.Id 
ORDER BY P.Id
OFFSET 500000 ROWS FETCH NEXT 50 ROWS ONLY

This runs quickly, as does ordering by P.LookupId.

If, however, I try to order by Name (or even L.Id), the query runs considerably slower:

SELECT
    P.Id,
    L.Name
FROM Parent P
LEFT JOIN Lookup L ON P.LookupId = L.Id 
ORDER BY L.Name
OFFSET 500000 ROWS FETCH NEXT 50 ROWS ONLY

The query plan for the second query is here: https://www.brentozar.com/pastetheplan/?id=Sk3SIOvMD

Other seemingly related questions seem to involve ordering by columns in the first table which could be resolved using an appropriate index.

I tried creating an indexed view for this query, however, SQL Server won't allow me to index the view because it contains a LEFT JOIN which I require because LookupId may be NULL and if I use an INNER JOIN those records would be excluded.

Is there a way to optimise this situation?

EDIT

Rob Farley's answer (thanks!) is great and works perfectly for the question as I originally asked it, in which I implied I was joining a single table.

As it is, I have multiple such tables and I was unable to reconcile all using INNER JOINs in order to use that solution.

For the moment I have worked around this by adding a "NULL" row to the lookup tables so I can use an INNER JOIN without losing any rows on the left.

In my case I use uniqueidentifier identities, so I create an indexed view like this:

CREATE VIEW [dbo].[ParentView]
WITH SCHEMABINDING
AS
SELECT
    P.Id,
    L.Name
FROM [dbo].Parent P
INNER JOIN [dbo].Lookup L ON ISNULL(P.LookupId, '00000000-0000-0000-0000-000000000000') = L.Id

I then add a row to the Lookup table with a value of 00000000-0000-0000-0000-000000000000 for Id so there is always a match on the right of the join.

I can then create indexes on that view as needed.

Also, as I'm not using Enterprise, I found I needed to use the NOEXPAND hint to ensure those indexes are used:

SELECT *
FROM [ParentView]
WITH (NOEXPAND)
ORDER BY Name
OFFSET 0 ROWS FETCH NEXT 50 ROWS ONLY
4
  • If the Lookup-Tables seldomly change you could create virtual columns on the parent table, which contain the looked-up values and create an index on them? If sql-Server allows the creation of a virtual index, you wouldn't even need virtual columns and could create an index on the lookup-values directly (maybe using a function, which looks up the value?) – Falco Aug 17 '20 at 12:02
  • 1
    @Falco, as far as I can see, there is no way to create "virtual columns", the closest is computed columns, which don't support this kind of thing as far as I can tell. I tried with a UDF, however, as it's non-deteministic you cannot add an index to a column that uses it. The way to do as you have suggested is to create an indexed view, but this doesn't work in my case for the reasons above. – Aleks Aug 18 '20 at 1:14
  • If an index on a persistent computed column on a non-deterministic UDF is not possible, you could try a materialized view, or maybe even create a real column and fill it with a DB-Trigger? This would copy the data from the lookup table into columns in the main table, which would need to be updated on changes in the lookup table. – Falco Aug 18 '20 at 9:27
  • @Falco, SQL Server doesn't have materialized views... indexed views are (more or less) the same thing. As you have said, I could pre-resolve the values during insert/update, however, that creates other performance issues and before I go down that path I'd like to see if there is a way to optimise the query. – Aleks Aug 19 '20 at 1:40
10

Let's start by thinking about that first query.

You're joining between Parent and Lookup, but it's an outer join, so Parents are never removed from the results. I'm going to guess that Lookup.Id is unique, so therefore, no Parent is going to have multiple Lookups that it joins to.

Therefore, the 50000th row in Parent (ordered by Parent.Id) is going to be the 50000th row in the results if we don't have the OFFSET clause.

Therefore, the query can move past the 50000 rows for the offset, look at the next 50 rows, and use this to join to the Lookup table. It doesn't matter if the join doesn't find anything, it's a left outer join and it'll just return NULL.

If you order by a different column in Parent, and that's indexed, it can move past those 50000 rows just as quickly.

Now let's consider the second query.

You want the 50000 rows that you ignore (by the offset) to be the first 50000 based on the results of the join. Those 50000 rows may include some that are NULL, where the Parent.LookupId value doesn't exist in the Lookup table. Even if you have a nice index on Parent.LookupId, you'll probably need to involve most of the rows, because unless you find 50050 rows that don't join successfully, you'll need to keep going. Even 50050 is way more than the 50 rows you join on in the first query.

Now, if you have a foreign key in place then things might be a little different. Then, the SQL engine ought to know that if it has a value at all, then Lookup.Name isn't going to be null. So it could theoretically start by finding the ones that are null, to see if there are 50000 of them. But that's still a bit of a stretch, and the SQL engine is unlikely to produce a plan like this.

But you could.

So to solve the performance of the second query, I would do a few things.

Start by considering the ones that aren't null. That means the rows which are part of an inner join. You can make an indexed view on this, so that you can have an index which is in the order you want.

But you will also need the ones where Parent.LookupID is null - except that for these ones, you don't need the join at all.

If you do a UNION ALL across these two sets (and maybe include a constant column in both, to make sure that the NULL rows appear before the NOT NULL ones in your order by), you should be able to see some improvement.

Something like this:

SELECT ID, Name
FROM 
(
  SELECT i.ID, i.Name, 2 as SetNumber
  FROM dbo.MyIndexedView i
  UNION ALL
  SELECT p.ID, NULL, 1 as SetNumber
  FROM dbo.Parent p
  WHERE p.LookupID IS NULL
) u
ORDER BY u.SetNumber, u.Name
OFFSET 50000 ROWS FETCH NEXT 50 ROWS ONLY;

Hopefully your plan will include a Merge Join (Concatenation) operator, so that it only pulls the rows that it needs from an Index Scan on the indexed view (in Name order) and an Index Seek on Parent (for the LookupIDs).

1
  • 1
    That is considerably faster and does indeed end up using a Merge Join (Concatenation). In the real implementation, Parent has multiple such foreign key columns which may be NULL so I just need to work out a way to handle that scenario. I'll only ever need to sort by a single column at a time, so I think I can get away with a separate view and query depending on which column I need to sort by. I'll leave this up while I work that out and in case there is some other magical solution that negates the need, but will otherwise mark this as accepted. Many thanks for your assistance! – Aleks Aug 17 '20 at 4:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.