Click here to monitor SSC
SQLServerCentral is supported by Red Gate Software Ltd.
 
Log in  ::  Register  ::  Not logged in
 
 
 
        
Home       Members    Calendar    Who's On


Add to briefcase «««34567»»

ROW_NUMBER(): An Efficient Alternative to Subqueries Expand / Collapse
Author
Message
Posted Monday, February 1, 2010 8:19 AM
SSC Journeyman

SSC JourneymanSSC JourneymanSSC JourneymanSSC JourneymanSSC JourneymanSSC JourneymanSSC JourneymanSSC Journeyman

Group: General Forum Members
Last Login: Wednesday, May 11, 2011 1:33 PM
Points: 85, Visits: 299
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 >>
Post #857218
Posted Friday, February 5, 2010 6:45 AM
Forum Newbie

Forum NewbieForum NewbieForum NewbieForum NewbieForum NewbieForum NewbieForum NewbieForum Newbie

Group: General Forum Members
Last Login: Sunday, June 20, 2010 12:51 AM
Points: 5, Visits: 37

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)
Post #860403
Posted Saturday, February 6, 2010 1:34 AM
Grasshopper

GrasshopperGrasshopperGrasshopperGrasshopperGrasshopperGrasshopperGrasshopperGrasshopper

Group: General Forum Members
Last Login: Monday, April 11, 2011 12:11 AM
Points: 11, Visits: 59
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.
Post #861031
Posted Saturday, February 6, 2010 5:12 AM
Forum Newbie

Forum NewbieForum NewbieForum NewbieForum NewbieForum NewbieForum NewbieForum NewbieForum Newbie

Group: General Forum Members
Last Login: Sunday, June 20, 2010 12:51 AM
Points: 5, Visits: 37

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!
Post #861073
Posted Saturday, February 6, 2010 6:54 AM


SSCrazy Eights

SSCrazy EightsSSCrazy EightsSSCrazy EightsSSCrazy EightsSSCrazy EightsSSCrazy EightsSSCrazy EightsSSCrazy EightsSSCrazy EightsSSCrazy Eights

Group: General Forum Members
Last Login: Today @ 5:25 AM
Points: 9,928, Visits: 11,204
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
SQL Server MVP
SQLblog.com
@SQL_Kiwi


  Post Attachments 
Q1.jpg (179 views, 21.21 KB)
Q2.jpg (178 views, 22.17 KB)
Post #861085
Posted Saturday, February 6, 2010 12:46 PM
Forum Newbie

Forum NewbieForum NewbieForum NewbieForum NewbieForum NewbieForum NewbieForum NewbieForum Newbie

Group: General Forum Members
Last Login: Sunday, June 20, 2010 12:51 AM
Points: 5, Visits: 37
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?
Post #861167
Posted Saturday, February 6, 2010 4:06 PM


SSCrazy Eights

SSCrazy EightsSSCrazy EightsSSCrazy EightsSSCrazy EightsSSCrazy EightsSSCrazy EightsSSCrazy EightsSSCrazy EightsSSCrazy EightsSSCrazy Eights

Group: General Forum Members
Last Login: Today @ 5:25 AM
Points: 9,928, Visits: 11,204
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
SQL Server MVP
SQLblog.com
@SQL_Kiwi
Post #861206
Posted Sunday, February 7, 2010 4:05 AM
Forum Newbie

Forum NewbieForum NewbieForum NewbieForum NewbieForum NewbieForum NewbieForum NewbieForum Newbie

Group: General Forum Members
Last Login: Sunday, June 20, 2010 12:51 AM
Points: 5, Visits: 37
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.

Post #861286
Posted Sunday, February 7, 2010 1:58 PM


SSCrazy Eights

SSCrazy EightsSSCrazy EightsSSCrazy EightsSSCrazy EightsSSCrazy EightsSSCrazy EightsSSCrazy EightsSSCrazy EightsSSCrazy EightsSSCrazy Eights

Group: General Forum Members
Last Login: Today @ 5:25 AM
Points: 9,928, Visits: 11,204
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:

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
SQL Server MVP
SQLblog.com
@SQL_Kiwi
Post #861373
Posted Sunday, February 7, 2010 3:37 PM
Forum Newbie

Forum NewbieForum NewbieForum NewbieForum NewbieForum NewbieForum NewbieForum NewbieForum Newbie

Group: General Forum Members
Last Login: Sunday, June 20, 2010 12:51 AM
Points: 5, Visits: 37

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 :)
Post #861399
« Prev Topic | Next Topic »

Add to briefcase «««34567»»

Permissions Expand / Collapse