ROW_NUMBER(): An Efficient Alternative to Subqueries

Question

ROW_NUMBER(): An Efficient Alternative to Subqueries

Viewing 15 posts - 46 through 60 (of 60 total)

You must be logged in to reply to this topic. Login to reply

Mike C SSC-Insane Points: 23224 More actions · Answer 1

Paul White (1/29/2010)
Mike C (1/29/2010)
What Tony is referring to is the fact that the CTE regenerates the GUID every time the "rn" column is referenced from the CTE. This is a bug. The GUID should be generated every time NEWID is referenced. NEWID is only directly referenced once (in the CTE, by the ROW_NUMBER function). Run Tony's example and look at the two "rn" columns. They should match up with one another in every row.
Yes I know - and I disagree, and previously explained why. Read Microsoft's replies to the Connect item entered by Itzik Ben-Gan for a fuller explanation of why this is not a bug - it's a sensible design decision.

I'm familiar with that bug. The way I read it, even MS agrees it's a bug - it was simply a bug closed as "won't fix". Basically no one wants to open up the "once-per-row behavior" can of worms and put strict definition to it.

Matt Arpidone SSC Veteran Points: 275 More actions · Answer 2

What I meant was that in a peer reviewed public forum, criticism should be welcome, even encouraged as long as it is well structured, helpful, and avoids personal attacks. I don't understand the tone of your posts towards me because they seem full of angry sarcastic remarks. And I don't even see anything particularly wrong with that, except that I can't seem to pinpoint exactly what the arguments you're trying to make are.

Here is a brief outline of the points I was making in my argument (before I realized that I may have missed the true purpose of the article):

The example used in the article was a bad example
The first query provided was very poorly written
The "solution" query provided was not "efficient" as claimed in the title
An alternate could be written, using APPLY (which may be considered by some to be a type of subquery) that is shorter, clearer, and more efficient

Stating these points alone wouldn't be very helpful, so I supported the "clearer and shorter" claim by writing an example, and I supported the "more efficient" claim by doing some simple tests, explaining my test procedure, and posting the exact results I got from SSMS.

Now apparently, this doesn't seem like a structured, constructive, and supported argument to you. So please help me out here, what exactly is your argument?

I'm going to guess that your main concern is this snippet:

First off, the first query provided was a joke. If anyone wrote a monster like that I would be giving them that look. You know what look I'm talking about, the "Seriously? Who hired you?" look. In fact, I can't believe the author took the time to write something like that for the article.

Reading this over a couple times I'm starting to agree that this does look like a personal attack. I honestly didn't mean it that way. My gut reaction to the query in the article was honestly, "oh god, that's awful", and if I came across something like that in a production environment at work that I had to maintain, I would be upset. I tried to make some mild humor out of this and obviously failed. But my point still stands, I believe that query to be very poorly written and a bad example to use in a "before and after" comparison, and I'm not trying to say anything derogatory about the author in general by these statements.

And then finally, and I feel like I'm pulling teeth here, can you please post the details about your testing. Not some generic statements and sarcastic remarks, but an actual description of your testing procedures and the exact results that you got. I would like to reproduce them on my end because I'm seriously interested in how the results could be that different.

Mike C SSC-Insane Points: 23224 More actions · Answer 3

Matt Arpidone (1/30/2010)
What I meant was that in a peer reviewed public forum, criticism should be welcome, even encouraged as long as it is well structured, helpful, and avoids personal attacks. I don't understand the tone of your posts towards me because they seem full of angry sarcastic remarks. And I don't even see anything particularly wrong with that, except that I can't seem to pinpoint exactly what the arguments you're trying to make are.
Here is a brief outline of the points I was making in my argument (before I realized that I may have missed the true purpose of the article):
The example used in the article was a bad example
The first query provided was very poorly written
The "solution" query provided was not "efficient" as claimed in the title
An alternate could be written, using APPLY (which may be considered by some to be a type of subquery) that is shorter, clearer, and more efficient
Stating these points alone wouldn't be very helpful, so I supported the "clearer and shorter" claim by writing an example, and I supported the "more efficient" claim by doing some simple tests, explaining my test procedure, and posting the exact results I got from SSMS.
Now apparently, this doesn't seem like a structured, constructive, and supported argument to you. So please help me out here, what exactly is your argument?
I'm going to guess that your main concern is this snippet:
First off, the first query provided was a joke. If anyone wrote a monster like that I would be giving them that look. You know what look I'm talking about, the "Seriously? Who hired you?" look. In fact, I can't believe the author took the time to write something like that for the article.
Reading this over a couple times I'm starting to agree that this does look like a personal attack. I honestly didn't mean it that way. My gut reaction to the query in the article was honestly, "oh god, that's awful", and if I came across something like that in a production environment at work that I had to maintain, I would be upset. I tried to make some mild humor out of this and obviously failed. But my point still stands, I believe that query to be very poorly written and a bad example to use in a "before and after" comparison, and I'm not trying to say anything derogatory about the author in general by these statements.
And then finally, and I feel like I'm pulling teeth here, can you please post the details about your testing. Not some generic statements and sarcastic remarks, but an actual description of your testing procedures and the exact results that you got. I would like to reproduce them on my end because I'm seriously interested in how the results could be that different.

I'm not trying to be sarcastic at all, and I'm sorry you took it that way. Let me tell you a short story to explain my point of view. I saw an article once that I thought was not so great. I found several assertions by the author that were not only a little off or on the edge between possibly correct/possibly incorrect -- they were completely and totally wrong. That's when I decided to write my own article which corrected the information being put out. You worded your response to this article very strongly so I recommended that if you really felt so strongly about it, submit an article; then wait for the next clever guy to come up with an even better solution 🙂

Now in this article the author began with nested subqueries that unfortunately are all too common! I've seen that exact same query used by many people in many places (granted they were different source tables, but the exact same concept!) I agree it is a rough way to go, but I can only assume the author probably ran into something like this in his work--and that he decided to change it. Believe it or not, that's where 90% of these articles come from--people run across a real-world problem, find a solution, and write it up. The author then went on to demonstrate one method (the key words here being "one method") of simplifying the code and getting a more efficient query plan versus the nested subqueries. Note that I said he demonstrated "one method", not "all methods" or "every method".

So the question you raised is "are there more efficient ways to get the same results"? And the answer, as you have shown, is yes. Your solution is clever, which is why I recommended you take it off the back page and submit an article describing it in more detail for the front page. However, a new solution does not automatically make another solution "garbage" or "horrible". Remember there are many ways to accomplish the same thing in SQL/T-SQL--it's one of the major strengths of SQL/T-SQL.

However, when you do your actual testing you'll want to (1) make sure you're reporting the statistics that are relevant; (2) make sure you clear buffers and cache to ensure consistent, accurate results.

So here's some details (from Books Online) about the statistics you're looking at:

Client processing time - The cumulative amount of time that the client spent executing code while the query was executed.

Total execution time - The cumulative amount of time (in milliseconds) that the client spent processing while the query was executed, including the time that the client spent waiting for replies from the server as well as the time spent executing code.

Wait time on server replies - The cumulative amount of time (in milliseconds) that the client spent while it waited for the server to reply.

Notice all time is in milliseconds. Now, for our purposes since I'm running it on a client local to my server I'll focus in on "wait time on server replies". This may not be valid if you're doing it over the network since network communication time is going to be rolled up in there also.

CROSS APPLY version:

-----------------------

8296 ms

7577 ms

7889 ms

7920.7 ms (Avg.)

ROW_NUMBER() version:

--------------------------

10232 ms

9809 ms

10832 ms

10291 ms (Avg.)

7920.7 ms / 10291 ms = 0.77 = 77%

Perhaps even more telling and to the point is the actual query plan, which shows a cost of 14.2601 for your method and a cost of 214.487 for the ROW_NUMBER version. 93% of the cost of the ROW_NUMBER version is in one Sort operation. Just for snorts and giggles, try your query versus the author's query on a table like the following (you can change your existing table structure to match):

CREATE TABLE [Production].[ProductVersion]

(

[ID] [int] IDENTITY(1,1) NOT NULL,

[ProductID] [int] NOT NULL,

[Version] [int] NOT NULL,

[MinorVersion] [int] NOT NULL,

[ReleaseVersion] [int] NOT NULL,

[StandardCost] [numeric](30, 4) NOT NULL,

CONSTRAINT [PK_ProductVersion] PRIMARY KEY NONCLUSTERED

(

[ID] ASC

)

);

GO

A simple change. The 4 columns in the table are no longer declared as the PK; instead there is a surrogate key represented by the IDENTITY column. I'd be interested to know if your test results are the same as mine in this situation. My tests show that the ROW_NUMBER method is around 3X faster (8518 ms avg. vs. 23094 ms avg.) I'll let you decide if, with no index on the columns you're sorting on (and yes, I've seen this as well!), whether or not you believe the ROW_NUMBER method is "crappy" compared to your CROSS APPLY method. CROSS APPLY is not what's speeding up your code, as you'll see once you get rid of the index. What is speeding up your code is simply the fact that the subquery can take advantage of the covering index on all three columns in this particular scenario.

Now, my point is simply this: I believe you missed the whole point of the article -- the author simply showed one method of simplifying and speeding up a convoluted mess of nested correlated subqueries. Whether you believe anyone alive would have the intestinal fortitude to put queries like that in production, it does happen (I've made a decent living fixing queries like that). Also, if optimizing queries is part of your day to day activities, you should invest in learning the tools that are available to help you do that job -- you may find that sometimes a big number is not a bad thing.

jbuttery Ten Centuries Points: 1226 More actions · Answer 4

"The following figure shows the estimated query costs for the Production.ProductVersion2. The subquery implementation took 43 seconds to complete where as the ROW_NUMBER() implementation took 5 seconds to complete for 1,000,000 rows."

It appears those results are for 100,000 rows, but still 7 times faster.

Paul White SSC Guru Points: 150467 More actions · Answer 5

Mike C (1/30/2010)
Hope that helps with the search for the UDF 🙂

Oh right - well thanks for that.

Paul White
SQLPerformance.com
SQLkiwi blog
@SQL_Kiwi

Ted Manasa Default port Points: 1461 More actions · Answer 6

Matt Arpidone (1/30/2010)
Thanks Mike, I'll keep in mind that any criticism of articles or disagreement will be met with animosity. I guess my opinion isn't welcome unless I agree with the author, which, as I can clearly see now, makes total sense on a site that welcomes "peer review".
I do not know the author at all, nor have I read any of his other work, and I was very careful in my post not to resort to empty ad hominem attacks. I did express concern about the content of the article, and if you would like to disagree with me on a particular point, feel free.
Regarding the testing, I completely understand your concerns, although I find the aggravated tone of your post a little disturbing (maybe I'm reading it wrong, if so I apologize).
The reason I did not look up the unit of measure is because units are irrelevant when discussing relative speed differences. I would rather you not point out my deficiencies as a developer (of which there are many) unless they actually have relevance to my argument. Certainly, my lack of knowledge about "client statistics" doesn't discredit anything I've posted (unless I've missed something), and furthermore doesn't impair my ability to do my job at all - which makes me curious why you insist that every one of your developers know about them.
I am a little worried that I seemed harsh in my post. I had previously typed up another post (in response to the author's post after mine) about how I thought his title was misleading and that caused me to misjudge the article - along with some additional disagreements - but then I decided to just drop it. I do still stand by what I've already presented, but I recognize that I seem to have missed the true purpose of the article.
Also I find it distasteful that you point out weaknesses in my testing and indicate that you have done your own improved testing, and then you fail to post any details about what you have done. What do you mean when you say 25-30% faster when tested correctly? Faster than what? What do you mean "correctly"? Personally, I feel that my tests were adequate to get my point across. If you have numbers that disagree with mine, why don't you post them instead of giving nonconstructive retorts?
In your article you might wish to discuss the internals of how CROSS APPLY works. It might surprise you, and just might change your mind about using a UDF. I'll leave it for you to research CROSS APPLY, as I don't want to pre-empt publication of what I expect to be an excellent article with your name on it in the near future.
What did you mean here exactly? As I understand it, APPLY is similar to joining on a correlated subquery. Actually, I confess that my love of APPLY comes from it being so similar to a foreach loop in a typical programming language. I don't see what kind of crazy internal things could be going on that make it behave differently. I did try doing some research on how it works internally, and while I didn't find much helpful material, I did come across this article: http://explainextended.com/2009/07/16/inner-join-vs-cross-apply/. It explains a specific scenario where APPLY is more efficient than a query using ROW_NUMBER(), and it explains the minor pitfall with ROW_NUMBER(). I suspect something similar is happening with the product version query.
Anyway, I'm not asking you to spoonfeed me a lecture all about how APPLY works, but a link to an article describing this surprising internal behavior would be appreciated since most of the stuff I'm finding gives basic overviews and is pretty much consistent with what I expected.

Matt, I thought that your response was very enlightening. I would not have thought to use a CROSS APPLY to perform this operation. I have been using RANK(), but will now look into using CROSS APPLY instead. Thanks.

---------------------------
|Ted Pin >>

Quassnoi Valued Member Points: 51 More actions · Answer 7

And now, most importantly, here are the execution results I got running these queries on my 50 million row table.

Hi Matt, I just found this discussion in the referrers to my blog.

Both CROSS APPLY and ROW_NUMBER (or DENSE_RANK if you want ties) can be more efficient, depending on the cardinality of the field you're grouping (or partitioning) by.

For high cardinality fields, analytic functions (ROW_NUMBER or DENSE_RANK) are more efficient due to the overhead of building a DISTINCT list of the values of this field.

For low cardinality fields, CROSS APPLY is a more efficient solution, and that's what your test case shows.

You may want to read another article in my blog, which compares both solutions performance-wise, depending on the cardinality of the field in question: SQL Server: Selecting records holding group-wise maximum (with ties)[/url]

Matt Arpidone SSC Veteran Points: 275 More actions · Answer 8

Thanks Quassnoi, after considering it for a while that's the conclusion I came to, although I didn't realize that the CROSS APPLY would actually perform worse for high-cardinality groupings. I thought it would gradually worsen as the cardinality got higher until it eventually ended up about the same as the ranking functions performance wise. I guess I was wrong.

Your articles are great. I read the one you put in your reply here and I was pretty amazed at some of those queries. I thought SQL Server would be smart enough that you wouldn't have to use tricky recursive CTEs and double-APPLYs to explicitly force efficient usage of the index. When I have some time, I'm going to try testing some of the queries in your articles to see the results firsthand.

Here's a question related to the ProductVersion queries in this discussion:

... analytic functions (ROW_NUMBER or DENSE_RANK) are more efficient due to the overhead of building a DISTINCT list ...

You're saying that the CROSS APPLY query takes a performance hit for high-cardinality data because of the overhead of building a list of DISTINCT ProductIds right? If that's the case, what if there was a separate table that stored each product (lets say dbo.Products) and instead of querying DISTINCT values from the ProductVersions table, we used all the ProductIds from the Products table.

SELECT version.*

FROM dbo.Products product

CROSS APPLY (

SELECT TOP(1) *

FROM dbo.ProductVersions

WHERE ProductId = product.Id

ORDER BY Version DESC, MinorVersion DESC, ReleaseVersion DESC

) version

This shouldn't change the resultset at all since products without versions will be eliminated by the CROSS APPLY, but lets assume anyway that every Product has at least one associated ProductVersions record. If I'm understanding things correctly, this should perform equivalent to the ranking function query for high-cardinality ProductVersions(ProductId), and much better with low-cardinality, since we're avoiding having to build a list of DISTINCT ProductIds. Is this correct?

-- Edit --

Also, in this article:

http://explainextended.com/2009/11/30/sql-server-selecting-records-holding-group-wise-maximum/

at the bottom it says:

To select records holding group-wise maximums in SQL Server, the following approaches can be used:
* Analytic functions
* Using DISTINCT / CROSS APPLY / TOP
* Using recursive CTE’s / CROSS APPLY / TOP
These methods are arranged in order of increasing complexity and decreasing efficiency (for low-cardinality groupers).

Didn't you mean increasing efficiency or maybe decreasing cost? As the queries became more complex they also executed a lot faster.

Quassnoi Valued Member Points: 51 More actions · Answer 9

This shouldn't change the resultset at all since products without versions will be eliminated by the CROSS APPLY, but lets assume anyway that every Product has at least one associated ProductVersions record. If I'm understanding things correctly, this should perform equivalent to the ranking function query for high-cardinality ProductVersions(ProductId), and much better with low-cardinality, since we're avoiding having to build a list of DISTINCT ProductIds. Is this correct?

This will be much faster than doing DISTINCT, of course. Actually, that's the reason why the CTE version of the query is faster: instead of grouping all records to build the distinct list it just jumps over the index keys. (This access method is called loose index scan and MySQL supports it natively, but in SQL Server and other systems you need to resort to the dirty tricks like that to emulate it)

The dedicated table with the products will of course speed it up yet a little more.

However, CROSS APPLY with a TOP implies nested loops and within each loop, it will have to do an index seek for the top-rated record for the current product.

An index seek is fast but not instant, it takes O(log n), where n is the number or records in the table. If you have m distinct groupers, the whole query will take O(m × log(n)), or O(n × log(n) × c), where ? is the cardinality of the column. (By definition, cardinality is m / n)

The analytic function, on the other hand, will just need to do a single index scan, which takes O(n), or O(n × const).

This means that for high cardinality columns, where log(n) × ? > const, the analytic functions will be faster. The actual value of the constant depends on many factors, like the index key size, cache hit ratio etc. However, the cost of a record fetch in a sequential index scan is always less than that of an index seek, that's why const will be always less than 1.

Hence, starting from a certain level or cardinality, the analytic functions solution will be more efficient, even with a dedicated product table.

For instance, if the products are unique within the ProductVersion, the ROW_NUMBER query will just return all records, while the CROSS APPLY query will do the same, but the the overhead of a join an an index seek for each record.

In general, for the tables that do not fit completely into the cache, sequential scan over the index becomes even more efficient than random seeks, and the cost of the index seek grows, so the larger are the tables with the same cardinality of the groupers (products), the more beneficial are the analytic functions.

Didn't you mean increasing efficiency or maybe decreasing cost? As the queries became more complex they also executed a lot faster.

Oh, you're right, I should have been more careful. Thanks for noticing!

Paul White SSC Guru Points: 150467 More actions · Answer 10

Quassnoi,

At the risk of interrupting your flow here, are you aware that you are missing something very important from your 'group-wise min/max (with ties) discussion?

There is a QO transformation, available in both 2005 and 2008, which produces a plan which performs as well as the best methods you show, regardless of cardinality or distribution. No recursive CTEs and no analytic functions required. Excellent performance, without unnecessary complexity.

Please consider the following code, using the sample data from your blog:

WITH RowIDs

AS (

SELECT DD.id

FROM [20091201_ties].t_distinct DD

WHERE DD.lorderer =

(

SELECT MIN(DI.lorderer)

FROM [20091201_ties].t_distinct DI

WHERE DI.glow = DD.glow

)

SELECT COUNT(*),

SUM(LEN(LookUp.stuffing))

FROM RowIDs

CROSS

APPLY (

SELECT stuffing

FROM [20091201_ties].t_distinct TD

WHERE TD.id = RowIDs.id

) LookUp;

That code uses the 'lorderer' column. Just change 'lorderer' to 'orderer' in the CTE for the second run.

Here are the actual execution plans for both:

One other thing. I notice that the index definitions given in your blog effectively INCLUDE the id column since that is the clustering key for the table. The id therefore only exists at the leaf level of the index, which makes it unavailable at higher levels. (As an aside, the name of the index seems to imply that id is a key column, rather than an include.)

For the amount of extra space required to store the id at non-leaf levels, you might consider adding the id column explicitly to the index. Not only can you then mark the index as UNIQUE (which may help the optimizer), you allow the QO more options when considering transformations.

The 'segment top' method I demonstrate above requires all referenced columns (in the CTE section) to be explicit keys in the index (and textually referenced in key order). So, if you wanted to change the query do a MIN or MAX ordered on the *id* column at any stage, it would need to be part of the key, not just an include.

Cheers

Paul

(edit to fix graphical plans)

Paul White
SQLPerformance.com
SQLkiwi blog
@SQL_Kiwi

Quassnoi Valued Member Points: 51 More actions · Answer 11

Hi Paul.

Please consider the following code, using the sample data from your blog:
WITH RowIDs
AS (
SELECT DD.id
FROM [20091201_ties].t_distinct DD
WHERE DD.lorderer =
(
SELECT MIN(DI.lorderer)
FROM [20091201_ties].t_distinct DI
WHERE DI.glow = DD.glow
)
)
SELECT COUNT(*),
SUM(LEN(LookUp.stuffing))
FROM RowIDs
CROSS
APPLY (
SELECT stuffing
FROM [20091201_ties].t_distinct TD
WHERE TD.id = RowIDs.id
) LookUp;

On my 2005 installation, this runs slower than DISTINCT:

SQL Server parse and compile time:

CPU time = 0 ms, elapsed time = 1 ms.

(????? ??????????: 1)

Table 't_distinct'. Scan count 11, logical reads 2250, physical reads 0, read-ahead reads 0, lob logical reads 0, lob physical reads 0, lob read-ahead reads 0.

SQL Server Execution Times:

CPU time = 250 ms, elapsed time = 241 ms.

for DISTINCT,

SQL Server parse and compile time:

CPU time = 0 ms, elapsed time = 1 ms.

(????? ??????????: 1)

Table 't_distinct'. Scan count 1, logical reads 2188, physical reads 0, read-ahead reads 0, lob logical reads 0, lob physical reads 0, lob read-ahead reads 0.

SQL Server Execution Times:

CPU time = 359 ms, elapsed time = 356 ms.

for your query.

I created the index with id explicitly added, and it's used in both queries. The optimizer built the same plan as shown in your post.

Segment operator still requires a full index scan which is costly. The sample table contains only a million records and the whole index fits into the cache, so the performance difference it not so obvious, but as the index size grows, the extra physical reads make the query perform much worse.

CTE query was intended to get rid of the full index scans. It completes in only IndexDepth page reads per distinct record. Even for billion rows, the index depth will be around 6, and with 100 groupers, the same query would compete in 600 page reads from the index. Even if all these reads are physical reads, this is not that much.

Of course, having a dedicated table instead of the CTE, as Matt suggested, will improve the query yet a little more.

One other thing. I notice that the index definitions given in your blog effectively INCLUDE the id column since that is the clustering key for the table. The id therefore only exists at the leaf level of the index, which makes it unavailable at higher levels. (As an aside, the name of the index seems to imply that id is a key column, rather than an include.)

I've heard this before, but my googlefu was not enough for me to be able to find any reference which proves or disproves it 🙂

But let us conduct a little experiment:

SET NOCOUNT OFF

CREATE TABLE t_clustered (

id INT NOT NULL,

val INT NOT NULL,

lid INT NOT NULL,

CONSTRAINT PK_clustered_id PRIMARY KEY (id),

CONSTRAINT UX_clustered_lid UNIQUE (lid)

)

CREATE INDEX ix_clustered_val ON t_clustered (val)

CREATE INDEX ix_clustered_val__lid ON t_clustered (val) INCLUDE (lid)

GO

WITH q (id) AS

(

SELECT 1

UNION ALL

SELECT id + 1

FROM q

WHERE id < 1000000

)

INSERT

INTO t_clustered (id, val, lid)

SELECT id, 1, id

FROM q

OPTION (MAXRECURSION 0)

This table has 1,000,000 records, clustered PK on id and two indexes: one on val only, another one on val covering lid.

lid holds the same values as id, and is marked UNIQUE

Val is the only declared key column in both indexes, and the only value of val is 1.

Let us issue the following query which searches both for val and lid:

SELECT val, lid

FROM t_clustered WITH (INDEX (ix_clustered_val__lid))

WHERE val = 1

AND lid = 987654

, which forces use of the index, with the following plan:

|--Index Seek(OBJECT:([test].[dbo].[t_clustered].[ix_clustered_val__lid]), SEEK:([test].[dbo].[t_clustered].[val]=(1)), WHERE:([test].[dbo].[t_clustered].[lid]=(987654)) ORDERED FORWARD)

Formally, it's an index seek, but since val = 1 holds for every record in the table and lid is not included in the key, the engine had to do the full index scan which required reading of all index pages:

SQL Server parse and compile time:

CPU time = 2 ms, elapsed time = 2 ms.

(????? ??????????: 1)

Table 't_clustered'. Scan count 1, logical reads 1862, physical reads 0, read-ahead reads 0, lob logical reads 0, lob physical reads 0, lob read-ahead reads 0.

SQL Server Execution Times:

CPU time = 62 ms, elapsed time = 75 ms.

But if we issue a similar query against (val, id)

SELECT val, id

FROM t_clustered WITH (INDEX (ix_clustered_val))

WHERE val = 1

AND id = 987654

, we get this plan:

|--Index Seek(OBJECT:([test].[dbo].[t_clustered].[ix_clustered_val]), SEEK:([test].[dbo].[t_clustered].[val]=(1) AND [test].[dbo].[t_clustered].[id]=(987654)) ORDERED FORWARD)

, and the query completes in 3 page reads (which is the index depth):

SQL Server parse and compile time:

CPU time = 2 ms, elapsed time = 2 ms.

(????? ??????????: 1)

Table 't_clustered'. Scan count 0, logical reads 3, physical reads 0, read-ahead reads 0, lob logical reads 0, lob physical reads 0, lob read-ahead reads 0.

SQL Server Execution Times:

CPU time = 0 ms, elapsed time = 1 ms.

id, I remind, is not declared a part of the index, but we see that it is used by the Seek operator against the index, and the query does not have to fetch all index pages. Somehow, 3 page reads is enough for the engine to locate the required record.

I cannot figure out how would this be possible if id were not a part of the key.

Could you please provide any reference that would show the key layout of a secondary index in a clustered table?

Paul White SSC Guru Points: 150467 More actions · Answer 12

Quassnoi,

I don't have time this morning for a full reply, and I'm off around the island for the next few days, so this will be just a quick one. I promise a fuller reply when I get back.

The reference you need is http://sqlblog.com/blogs/kalen_delaney/archive/2008/03/16/nonclustered-index-keys.aspx - a blog entry by Kalen Delaney.

The point about the Segement Top is that it is very fast on all scenarios, and doesn't require any special tricks or coding to just work well. It also works for the other cases in your blog entry too (without ties etc).

The problem with the other methods in your blog entry is that they depend on data distribution, and perform poorly if the distribution is 'wrong'.

Naturally, if one knows something about the data distribution, and can guarantee that it will never change, it might be worthwhile considering a hand-coded 'trick' like the recursive CTE for extremely large data sets, though I think this is very much an edge case to be honest, and might be too fragile for production use.

I think a general method with very good and predictable performance that uses the statistics available to the optimizer to produce an appropriate plan over a wide set of circumstances should be preferred in the general case. Segment Top provides such a method for this class of query, and you really should include it in your blog and tests.

I have many other things to say on the specifics of your last reply, but they will have to wait.

Cheers

Paul

Paul White
SQLPerformance.com
SQLkiwi blog
@SQL_Kiwi

Quassnoi Valued Member Points: 51 More actions · Answer 13

Paul,

The reference you mentioned explicitly states that when a secondary index is not declared UNIQUE, it contains the values of the clustered key in the key-level pages:

Now you should see something different. The first index, nonunique, still has all three columns in the upper level page: the nonclustered key SalesOrderDetailID, and the two columns of the clustered key: SalesOrderID and the uniqueifier.

Paul White SSC Guru Points: 150467 More actions · Answer 14

Quassnoi (2/7/2010)
The reference you mentioned explicitly states that when a secondary index is not declared UNIQUE, it contains the values of the clustered key in the key-level pages:

:laugh: Typical. Oh well, my mistake there then - sorry about that. I should have checked which way round it was.

It's an interesting blog entry though isn't it? Makes you think.

Paul White
SQLPerformance.com
SQLkiwi blog
@SQL_Kiwi

Quassnoi Valued Member Points: 51 More actions · Answer 15

It's an interesting blog entry though isn't it? Makes you think.

You bet it is!

However, common sense has always told me that an index should provide a fast way of locating a record it points to (or otherwise it would become unmaintainable), and storing the record's pointer along with the index keys (be it RID or a clustered key) is the best way to achieve this.

I know for certain that InnoDB does it, but InnoDB tables, being B-Trees rather than B+Trees, do not maintain direct links between leaf-level pages (and do not even distinguish between key-level and leaf-level pages).

I was just seeking for a proof that SQL Server does the same, and, thanks to you, I got it now 🙂