Take the 2-minute tour ×
Database Administrators Stack Exchange is a question and answer site for database professionals who wish to improve their database skills and learn from others in the community. It's 100% free, no registration required.

I have a persisted computed column on a table which is simply made up concatenated columns, e.g.

CREATE TABLE dbo.T 
(   
    ID INT IDENTITY(1, 1) NOT NULL CONSTRAINT PK_T_ID PRIMARY KEY,
    A VARCHAR(20) NOT NULL,
    B VARCHAR(20) NOT NULL,
    C VARCHAR(20) NOT NULL,
    D DATE NULL,
    E VARCHAR(20) NULL,
    Comp AS A + '-' + B + '-' + C PERSISTED NOT NULL 
);

In this Comp is not unique, and D is the valid from date of each combination of A, B, C, therefore I use the following query to get the end date for each A, B, C (basically the next start date for the same value of Comp):

SELECT  t1.ID,
        t1.Comp,
        t1.D,
        D2 = (  SELECT  TOP 1 t2.D
                FROM    dbo.T t2
                WHERE   t2.Comp = t1.Comp
                AND     t2.D > t1.D
                ORDER BY t2.D
            )
FROM    dbo.T t1
WHERE   t1.D IS NOT NULL -- DON'T CARE ABOUT INACTIVE RECORDS
ORDER BY t1.Comp;

I then added an index to the computed column to assist in this query (and also others):

CREATE NONCLUSTERED INDEX IX_T_Comp_D ON dbo.T (Comp, D) WHERE D IS NOT NULL;

The query plan however surprised me. I would have thought that since I have a where clause stating that D IS NOT NULL and I am sorting by Comp, and not referencing any column outside of the index that the index on the computed column could be used to scan t1 and t2, but I saw a clustered index scan.

enter image description here

So I forced the use of this index to see if it yielded a better plan:

SELECT  t1.ID,
        t1.Comp,
        t1.D,
        D2 = (  SELECT  TOP 1 t2.D
                FROM    dbo.T t2
                WHERE   t2.Comp = t1.Comp
                AND     t2.D > t1.D
                ORDER BY t2.D
            )
FROM    dbo.T t1 WITH (INDEX (IX_T_Comp_D))
WHERE   t1.D IS NOT NULL
ORDER BY t1.Comp;

Which gave this plan

enter image description here

This shows that a Key lookup is being used, the details of which are:

enter image description here

Now, according to the SQL-Server documentation:

You can create an index on a computed column that is defined with a deterministic, but imprecise, expression if the column is marked PERSISTED in the CREATE TABLE or ALTER TABLE statement. This means that the Database Engine stores the computed values in the table, and updates them when any other columns on which the computed column depends are updated. The Database Engine uses these persisted values when it creates an index on the column, and when the index is referenced in a query. This option enables you to create an index on a computed column when Database Engine cannot prove with accuracy whether a function that returns computed column expressions, particularly a CLR function that is created in the .NET Framework, is both deterministic and precise.

So if, as the docs say "the Database Engine stores the computed values in the table", and the value is also being stored in my index, why is a Key Lookup required to get A, B and C when they are not referenced in the query at all? I assume they are being used to calculate Comp, but why? Also, why can the query use the index on t2, but not on t1?

Queries and DDL on SQL Fiddle

N.B. I have tagged SQL Server 2008 because this is the version that my main problem is on, but I also get the same behaviour in 2012.

share|improve this question

migrated from stackoverflow.com Oct 24 '13 at 14:13

This question came from our site for professional and enthusiast programmers.

1  
I'm not sure at the moment what quirk of computed column matching causes this behaviour but I wouldn't bother persisting this anyway. It's not a very expensive calculation and if you just index the constituent parts it all works fine. SQL Fiddle –  Martin Smith Oct 24 '13 at 11:26
    
I hit this problem -- which I consider to be a bug -- when writing this post on my blog. IIRC, I was able to hint my way out of the particular scenario when playing around with it (I didn't include that in the post because I thought it was too far aside from the point I was trying to make), but that really shouldn't be necessary. –  Jon Seigel Oct 24 '13 at 15:26
    
Thanks GarethD, I just ran into this exact same bug on 2008 R2 and am desperate for a good solution. Possibly useful tidbit: for me if I query only the table with the persisted column directly it does an index seek without a key lookup. When I join to another table it starts doing the key lookup even though I'm using the same columns. –  influent Oct 24 '13 at 17:17
    
Looking into this a bit further the issue seems particularly to happen with scalar correlated sub queries. Rewriting with an OUTER APPLY gives a nicer plan –  Martin Smith Oct 25 '13 at 23:17
    
@influent - Are you using an actual JOIN or a correlated sub query? If a join can you set up a simple repro on SQL Fiddle? –  Martin Smith Oct 26 '13 at 12:05

3 Answers 3

up vote 14 down vote accepted
+250

Why is a Key Lookup required to get A, B and C when they are not referenced in the query at all? I assume they are being used to calculate Comp, but why?

Columns A, B, and C are referenced in the query plan - they are used by the seek on T2.

Also, why can the query use the index on t2, but not on t1?

The optimizer decided that scanning the clustered index was cheaper than scanning the filtered nonclustered index and then performing a lookup to retrieve the values for columns A, B, and C.

Explanation

The real question is why the optimizer felt the need to retrieve A, B, and C for the index seek at all. We would expect it to read the Comp column using a nonclustered index scan, and then perform a seek on the same index (alias T2) to locate the Top 1 record.

The query optimizer expands computed column references before optimization begins, to give it a chance to assess the costs of various query plans. For some queries, expanding the definition of a computed column allows the optimizer to find more efficient plans.

When the optimizer encounters a correlated subquery, it attempts to 'unroll it' to a form it finds easier to reason about. If it cannot find a more effective simplification, it resorts to rewriting the correlated subquery as an apply (a correlated join):

Apply rewrite

It just so happens that this apply unrolling puts the logical query tree into a form that does not work well with project normalization (a later stage that looks to match general expressions to computed columns, among other things).

In your case, the way the query is written interacts with internal details of the optimizer such that the expanded expression definition is not matched back to the computed column, and you end up with a seek that references columns A, B, and C instead of the computed column, Comp. This is the root cause.

Workaround

One idea to workaround this side-effect is to write the query as an apply manually:

SELECT
    T1.ID,
    T1.Comp,
    T1.D,
    CA.D2
FROM dbo.T AS T1
CROSS APPLY
(  
    SELECT TOP (1)
        D2 = T2.D
    FROM dbo.T AS T2
    WHERE
        T2.Comp = T1.Comp
        AND T2.D > T1.D
    ORDER BY
        T2.D ASC
) AS CA
WHERE
    T1.D IS NOT NULL -- DON'T CARE ABOUT INACTIVE RECORDS
ORDER BY
    T1.Comp;

Unfortunately, this query will not use the filtered index as we would hope either. The inequality test on column D inside the apply rejects NULLs, so the apparently redundant predicate WHERE T1.D IS NOT NULL is optimized away.

Without that explicit predicate, the filtered index matching logic decides it cannot use the filtered index. There are a number of ways to work around this second side-effect, but the easiest is probably to change the cross apply to an outer apply (mirroring the logic of the rewrite the optimizer performed earlier on the correlated subquery):

SELECT
    T1.ID,
    T1.Comp,
    T1.D,
    CA.D2
FROM dbo.T AS T1
OUTER APPLY
(  
    SELECT TOP (1)
        D2 = T2.D
    FROM dbo.T AS T2
    WHERE
        T2.Comp = T1.Comp
        AND T2.D > T1.D
    ORDER BY
        T2.D ASC
) AS CA
WHERE
    T1.D IS NOT NULL -- DON'T CARE ABOUT INACTIVE RECORDS
ORDER BY
    T1.Comp;

Now the optimizer does not need to use the apply rewrite itself (so the computed column matching works as expected) and the predicate is not optimized away either, so the filtered index can be used for both data access operations, and the seek uses the Comp column on both sides:

Outer Apply Plan

This would generally be preferred over adding A, B, and C as INCLUDEd columns in the filtered index, because it addresses the root cause of the problem, and does not require widening the index unnecessarily.

Persisted computed columns

As a side note, it is not necessary to mark the computed column as PERSISTED, if you don't mind repeating its definition in a CHECK constraint:

CREATE TABLE dbo.T 
(   
    ID integer IDENTITY(1, 1) NOT NULL,
    A varchar(20) NOT NULL,
    B varchar(20) NOT NULL,
    C varchar(20) NOT NULL,
    D date NULL,
    E varchar(20) NULL,
    Comp AS A + '-' + B + '-' + C,

    CONSTRAINT CK_T_Comp_NotNull
        CHECK (A + '-' + B + '-' + C IS NOT NULL),

    CONSTRAINT PK_T_ID 
        PRIMARY KEY (ID)
);

CREATE NONCLUSTERED INDEX IX_T_Comp_D
ON dbo.T (Comp, D) 
WHERE D IS NOT NULL;

The computed column is only required to be PERSISTED in this case if you want to use a NOT NULL constraint or to reference the Comp column directly (instead of repeating its definition) in a CHECK constraint.

share|improve this answer
2  
+1 BTW I came across another case of superfluous lookup whilst looking at this that you may (or may not) find of interest. SQL Fiddle. –  Martin Smith Oct 28 '13 at 12:19
    
@MartinSmith Yes that is interesting. Another generic rule rewrite (FOJNtoLSJNandLASJN) that results in things not working as we would hope, and leaving junk (BaseRow/Checksums) that is useful in some types of plans (e.g. cursors) but not needed here. –  Paul White Oct 28 '13 at 22:31
    
Ah Chk is checksum! Thanks I wasn't sure about that. Originally I was thinking it might be something to do with check constraints. –  Martin Smith Oct 29 '13 at 10:17

Although this might be a bit of a co-incidence due to the artificial nature of your test data, being as you mentioned SQL 2012 I tried a rewrite:

SELECT  ID,
        Comp,
        D,
        D2 = LEAD(D) OVER(PARTITION BY COMP ORDER BY D)
FROM    dbo.T 
WHERE   D IS NOT NULL
ORDER BY Comp;

This yielded a nice low-cost plan using your index and with significantly lower reads than the other options (and the same results for your test data).

Plan Explorer costs for four options: Original; original with hint; outer apply and Lead

I suspect your real data is more complicated so there might be some scenarios where this query behaves semantically different to yours, but it does show sometimes the new features can make a real difference.

I did experiment with some more varied data and found some scenarios to match and some not:

--Example 1: results matched
TRUNCATE TABLE dbo.t

-- Generate some more interesting test data
;WITH cte AS
(
SELECT TOP 1000 ROW_NUMBER() OVER ( ORDER BY ( SELECT 1 ) ) rn
FROM master.sys.columns c1
    CROSS JOIN master.sys.columns c2
    CROSS JOIN master.sys.columns c3
)
INSERT T (A, B, C, D)
SELECT  'A' + CAST( a.rn AS VARCHAR(5) ),
        'B' + CAST( a.rn AS VARCHAR(5) ),
        'C' + CAST( a.rn AS VARCHAR(5) ),
        DATEADD(DAY, a.rn + b.rn, '1 Jan 2013')
FROM cte a
    CROSS JOIN cte b
WHERE a.rn % 3 = 0
 AND b.rn % 5 = 0
ORDER BY 1, 2, 3
GO


-- Original query
SELECT  t1.ID,
        t1.Comp,
        t1.D,
        D2 = (  SELECT  TOP 1 D
                FROM    dbo.T t2
                WHERE   t2.Comp = t1.Comp
                AND     t2.D > t1.D
                ORDER BY D
            )
INTO #tmp1
FROM    dbo.T t1 
WHERE   t1.D IS NOT NULL
ORDER BY t1.Comp;
GO

SELECT  ID,
        Comp,
        D,
        D2 = LEAD(D) OVER(PARTITION BY COMP ORDER BY D)
INTO #tmp2
FROM    dbo.T 
WHERE   D IS NOT NULL
ORDER BY Comp;
GO


-- Checks ...
SELECT * FROM #tmp1
EXCEPT
SELECT * FROM #tmp2

SELECT * FROM #tmp2
EXCEPT
SELECT * FROM #tmp1


Example 2: results did not match
TRUNCATE TABLE dbo.t

-- Generate some more interesting test data
;WITH cte AS
(
SELECT TOP 1000 ROW_NUMBER() OVER ( ORDER BY ( SELECT 1 ) ) rn
FROM master.sys.columns c1
    CROSS JOIN master.sys.columns c2
    CROSS JOIN master.sys.columns c3
)
INSERT T (A, B, C, D)
SELECT  'A' + CAST( a.rn AS VARCHAR(5) ),
        'B' + CAST( a.rn AS VARCHAR(5) ),
        'C' + CAST( a.rn AS VARCHAR(5) ),
        DATEADD(DAY, a.rn, '1 Jan 2013')
FROM cte a

-- Add some more data
INSERT dbo.T (A, B, C, D)
SELECT A, B, C, D 
FROM dbo.T
WHERE DAY(D) In ( 3, 7, 9 )


INSERT dbo.T (A, B, C, D)
SELECT A, B, C, DATEADD( day, 1, D )
FROM dbo.T
WHERE DAY(D) In ( 12, 13, 17 )


SELECT * FROM #tmp1
EXCEPT
SELECT * FROM #tmp2

SELECT * FROM #tmp2
EXCEPT
SELECT * FROM #tmp1

SELECT * FROM #tmp2
INTERSECT
SELECT * FROM #tmp1


select * from #tmp1
where comp = 'A2-B2-C2'

select * from #tmp2
where comp = 'A2-B2-C2'
share|improve this answer
1  
Well it uses the index but only up to a point. If comp is not a computed column you don't see the sort. –  Martin Smith Oct 28 '13 at 13:31
    
+1 For creative thinking (though the semantics are indeed different). –  Paul White Oct 28 '13 at 22:32
    
Thanks @PaulWhite! : ) –  wBob Oct 29 '13 at 0:29
    
Thanks. My actual scenario is not a lot more complicated and the LEAD function worked exactly as I would like on my local instance of 2012 express. Unfortunately, this minor inconvenience to me was not deemed a good enough reason to upgrade the production servers yet... –  GarethD Oct 29 '13 at 16:14
    
lol @GarethD, maybe next year : ) –  wBob Oct 29 '13 at 20:07

When I tried to perform the same actions, a got the another results. Firstly, my execution plan for table without indexes looks as following:enter image description here

As we can see from the Clustered Index Scan (t2), the predicate is used for determine the needed rows to be returned (because of condition):

enter image description here

When the index was added, not a matter if it was defined by WITH operator or no, the execution plan became as following:

enter image description here

As we can see, the Clustered Index Scan is replaced by Index Scan. As we saw above, the SQL Server use the source columns of the computed column to perform the matching of the nested query. During the clustered index scan all this values can be acquired in the same time (no additional operations needed). When the index was added, the filtering of the necessary rows from the table (in the main select) is performing according to the index, but the values of the source columns for the computed column comp still need to be gotten (last operation Nested Loop).

enter image description here

Because of this the Key Lookup operation is used - to get the data of the source columns of the computed one.

P.S. Looks like a bug in SQL Server.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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