Search results matching tags 't-sql' and 'Query Tuning'

Who's On First? Solving the Top per Group Problem (Part 1: Technique)

Adam Machanic — Fri, 08 Feb 2008 23:09:00 GMT

Relative comparison is a simple matter of human nature. From early childhood we compare and contrast what we see in the world around us, building a means by which to rate what we experience. And as it turns out, this desire to discover top and bottom, rightmost and leftmost, or best and worst happens to extend quite naturally into business scenarios. Which product is the top seller? How about the one that's simply not moving off the shelves? Which of our customers has placed the most expensive order? What are the most recent orders placed at each of our outlets?

In the world of common business questions, the edge cases are generally of most interest. What's in the middle is unimportant; it's often too difficult for the mind to compare and comprehend when there are hundreds, thousands, or even millions of items, transactions, or facts that are all within a similar range. Instead, we focus on those that stick out in some extraordinary way.

Those of us who work with SQL products on a regular basis are faced with solving this same problem time and again as we work through various business requirements. Over time, I have noticed four basic query patterns that can be used to solve the problem; each are logically equivalent (within certain restrictions -- more on that later), but can have surprisingly different performance characteristics depending on the data being queried. In this first post, I will outline the available patterns/methods. In the following posts, I will show the results of testing each pattern against a variety of scenarios in an attempt to discover where and when each should be used.

The four basic patterns are outlined below. Each of the methods is illustrated using a query to show all customers' names, plus their most recent order date, and the amount of that order. I've included notes that indicate where logic differences can arise among the various methods.

Method 1: Join to full group and use correlated subquery with a MIN/MAX aggregate to filter

In this method we use an inner join to get all required columns, then filter the resultant set using a correlated subquery in the WHERE clause.

SELECT
    c.FirstName,
    c.LastName,
    o.OrderDate,
    o.OrderAmount
FROM Customers c
JOIN Orders o ON o.CustomerId = c.CustomerId
WHERE
    o.OrderDate =
    (
        SELECT MAX(o1.OrderDate)
        FROM Orders o1
        WHERE
            o1.CustomerId = o.CustomerId
    )

Logic notes: With this method ties are automatically included in the output, unless a tiebreaker is specified (which can be tricky given that you only have one column to work with). This method does not allow you to pull back an arbitrary number of rows, such as top 10 per customer; you are limited to the edge and any ties that might exist.

Method 1a: Join to full group and use correlated subquery with TOP(n) and ORDER BY to filter

This method is almost identical to Method 1 (which is why it is classified here as 1a), but the TOP and ORDER BY allow for a bit more flexibility than the aggregates.

SELECT
    c.FirstName,
    c.LastName,
    o.OrderDate,
    o.OrderAmount
FROM Customers c
JOIN Orders o ON o.CustomerId = c.CustomerId
WHERE
    o.OrderDate =
    (
        SELECT TOP(1)
            o1.OrderDate
        FROM Orders o1
        WHERE
            o1.CustomerId = o.CustomerId
        ORDER BY
            o1.OrderDate DESC
    )

Logic notes: With this method you can more easily integrate a tiebreaker than with Method 1; the comparison column can be anything, including a primary key, and you can still order on whatever column makes most sense. In addition, you can take more rows than with Method 1 by using IN instead of = in the WHERE clause, and increasing the argument value to TOP.

Method 2: CROSS APPLY to ordered TOP(n)

In this method, SQL Server 2005's CROSS APPLY operator is used. This operator allows us to essentially create a table-valued correlated subquery -- something that impossible in previous versions of SQL Server. By using TOP in conjunction with ORDER BY we can get as many rows per group as needed.

SELECT
    c.FirstName,
    c.LastName,
    x.OrderDate,
    x.OrderAmount
FROM Customers c
CROSS APPLY
(
    SELECT TOP(1)
        o.OrderDate,
        o.OrderAmount
    FROM Orders o
    WHERE
        o.CustomerId = c.CustomerId
    ORDER BY
        o.OrderDate DESC
) x

Logic notes: This method is almost identical, from a logic point of view, with Method 1a modified to use IN on a primary key column. With both methods WITH TIES can be added to the TOP in order to get ties.

Method 3: Join to derived table that uses a partitioned, ordered windowing function, and filter in the outer query based on the row number

In this method a derived table or CTE is used, in conjunction with a windowing function partitioned based on the required grain of the final query. So for the "most recent order per customer" query, the row number is partitioned based on the customer. This gives us a count starting at 1 for each customer, which can be filtered in the outer query.

SELECT
    c.FirstName,
    c.LastName,
    x.OrderDate,
    x.OrderAmount
FROM Customers c
INNER JOIN
(
    SELECT
        o.OrderDate,
        o.OrderAmount,
        o.CustomerId,
        ROW_NUMBER() OVER
        (
            PARTITION BY o.CustomerId
            ORDER BY o.OrderDate DESC
        ) AS r
    FROM Orders o
) x ON
    x.CustomerId = c.CustomerId
    AND x.r = 1

Logic notes: If ties are important, use DENSE_RANK instead of ROW_NUMBER. ROW_NUMBER is good for arbitrary TOP(n), similar to Method 2. Unlike the previously described methods, in conjunction with DENSE_RANK this method can return an arbitrary TOP(n) rows, all of which can include ties. So if you would like to see the three most recent order dates and each happens to have multiple orders, this method will be able to return them all by simply filtering on x.r = 3. This would not be directly possible with any of the other methods described here.

Method 4: "Carry-along sort"

This is the only "tricky" method, and not one that I recommend using, except as a last resort. I'm including it here only for completeness and comparison because it happens to be a very high performance method in some cases. This method involves converting each of the required inner columns into a string, concatenating them, then applying an aggregate to the string as a whole. By putting the "sort" column first, the other data is "carried along" -- thus the name for the method. The concatenated data is then "unpacked" in the outer query. This can be surprisingly efficient from an I/O standpoint, but the resultant code is a maintenance nightmare and it is quite easy to introduce errors. In addition, this method can only return the top 1 per group -- no ties or multiple return items are supported.

SELECT
    c.FirstName,
    c.LastName,
    CONVERT(DATETIME, SUBSTRING(x.OrderInfo, 1, 8)) AS OrderDate,
    CONVERT(MONEY, SUBSTRING(x.OrderInfo, 9, 15)) AS OrderAmount
FROM Customers c
INNER JOIN
(
    SELECT
        o.CustomerId,
        MAX
        (
            CONVERT(CHAR(8), OrderDate, 112) +
            CONVERT(CHAR(15), SubTotal)
        ) OrderInfo
    FROM Orders o
    GROUP BY
        o.CustomerId
) x ON
    x.CustomerId = c.CustomerId

This post is just the beginning; watch this space in the coming days for a series of performance tests and analysis of these methods, and some results that I personally found to be quite surprising.

Medians, ROW_NUMBERs, and performance

Adam Machanic — Mon, 18 Dec 2006 19:52:00 GMT

A couple of days ago, Aaron Bertrand posted about a method for calculating medians in SQL Server 2005 using the ROW_NUMBER function in conjunction with the COUNT aggregate. This method (credited to Itzik Ben-Gan) is interesting, but I discovered an even better way to attack the problem in Joe Celko's Analytics and OLAP in SQL.

Rather than using a COUNT aggregate in conjunction with the ROW_NUMBER function, Celko's method uses ROW_NUMBER twice: Once with an ascending sort, and again with a descending sort. The output rows can then be matched based on the ascending row number being within +/- 1 of the descending row number. This becomes clearer with a couple of small examples:

A	1	4
B	2	3
C	3	2
D	4	1

A	1	5
B	2	4
C	3	3
D	4	2
E	5	1

In the first table (even number of rows), the median rows are B and C. These can be matched based on [Ascending Column] IN ([Descending Column] + 1, [Descending Column] - 1). In the second table (odd number of rows), the median row is C, which is matched where [Ascending Column] = [Descending Column]. Note that in the second table, the match criteria for the first table does not apply -- so the generic expression to match either case is the combination of the two: [Ascending Column] IN ([Descending Column], [Descending Column] + 1, [Descending Column] - 1).

We can apply this logic within the AdventureWorks database to find the median of the "TotalDue" amount in the Sales.SalesOrderHeader table, for each customer:

SELECT
   CustomerId,
   AVG(TotalDue)
FROM
(
   SELECT
      CustomerId,
      TotalDue,
      ROW_NUMBER() OVER (
         PARTITION BY CustomerId
         ORDER BY TotalDue ASC, SalesOrderId ASC) AS RowAsc,
      ROW_NUMBER() OVER (
         PARTITION BY CustomerId
         ORDER BY TotalDue DESC, SalesOrderId DESC) AS RowDesc
   FROM Sales.SalesOrderHeader SOH
) x
WHERE
   RowAsc IN (RowDesc, RowDesc - 1, RowDesc + 1)
GROUP BY CustomerId
ORDER BY CustomerId;

The equivalent logic using Itzik Ben-Gan's method follows:

SELECT
   CustomerId,
   AVG(TotalDue)
FROM
(
   SELECT
      CustomerId,
      TotalDue,
      ROW_NUMBER() OVER (
         PARTITION BY CustomerId
         ORDER BY TotalDue) AS RowNum,
       COUNT(*) OVER (
          PARTITION BY CustomerId) AS RowCnt
   FROM Sales.SalesOrderHeader
) x
WHERE
   RowNum IN ((RowCnt + 1) / 2, (RowCnt + 2) / 2)
GROUP BY CustomerId
ORDER BY CustomerId;

Taking a look at the estimated execution plans for these two queries, we might believe that Ben-Gan's method is superior: Celko's algorithm requires an expensive intermediate sort operation and has an estimated cost of 4.96, compared to 3.96 for Ben-Gan's.

Remember that these are merely estimates. And as it turns out, this is one of those times that the Query Optimizer's cost estimates are are totally out of line with the reality of what happens when you actually run the queries. Although the performance difference is not especially noticeable on a set of data as small as that in Sales.SalesOrderHeader, check out the STATISTICS IO output. Celko's version does 703 logical reads; Ben-Gan's does an astonishing 140110!

There is a good lesson to be learned from this: Cost-based optimization is far from perfect! Never completely trust what estimates tell you; they've come a long way, but clearly there is still some work to do in this area. The only way to actually determine that one query is better than another is to run it against a realistic set of data and look at how much IO and CPU time is actually used.

In this case, Ben-Gan's query probably should perform better than Celko's. It seems odd that the Query Processor can't collect the row counts at the same time it processes the row numbers. Regardless, as of today this is the best way to solve this problem... Not that I've ever needed a median in any production application I've worked on. But I suppose that's beside the point!

Scalar functions, inlining, and performance: An entertaining title for a boring post

Adam Machanic — Fri, 04 Aug 2006 03:07:00 GMT

Scalar. Function.

Wow.

Could any other combination of words evoke the same feeling of encapsulation, information hiding, and simplification of client code? After years spent developing software in the procedural and OO worlds, it can be difficult--perhaps, even impossible--to migrate over to working with SQL Server and not consider how to architect your data access logic using some of the same techniques you'd use in the application tier.

In short: Why would you ever write the same piece of logic more than once? Answer: You wouldn't (damn it!). And so Microsoft bestowed upon the SQL Server community, in SQL Server 2000, the ability to write scalar user-defined functions. And they could have been such beautiful things...

But alas, reality can be painful, and as developers tried these new tools they were struck with a strange feeling of sadness as their applications buckled under the weight of what otherwise would have been a wonderful idea. As it turned out, putting all but the simplest of logic into these scalar functions was a recipe for disaster. Why? Because they're essentially cursors waiting to happen (but they don't look like cursors, so you may not know... until it's too late.)

The central problem is that when you wrap logic in a multistatement UDF, the query optimizer just can't unwrap it too easily. And so there's really only one way to evaluate a scalar UDF: call it once per row. And that is really nothing more than a cursor.

Seeing this behavior in action is easy enough; consider the following scalar function that some poor sap DBA working for AdventureWorks might be compelled to create:

CREATE FUNCTION GetMaxProductQty_Scalar
(
    @ProductId INT
)
RETURNS INT
AS
BEGIN
    DECLARE @maxQty INT

    SELECT @maxQty = MAX(sod.OrderQty)
    FROM Sales.SalesOrderDetail sod
    WHERE sod.ProductId = @ProductId

    RETURN (@maxQty)
END

Simple enough, right? Let's pretend that AdventureWorks has a bunch of reports, each of which requires maximum quantity sold per product. So the DBA, thinking he can save himself some time and keep everything centralized (and that is a good idea), puts all of the logic into a scalar UDF. Now, when he needs this logic, he can just call the UDF. And if the logic has a bug, or needs to be changed, he can change it in exactly one place. And so life is great... Or is it?

Let's take a look at a sample query:

SELECT
    ProductId,
    dbo.GetMaxProductQty_Scalar(ProductId)
FROM Production.Product
ORDER BY ProductId

This query does nothing more than get the max quantity sold for each product in the Productin.Product table. And a look at the execution plan or the STATISTICS IO output might indicate that there's nothing too interesting going on here: The execution plan shows an index scan (to be expected, with no WHERE clause), followed by a compute scalar operation (the call to the UDF). And STATISTICS IO shows a mere 16 reads.

So why is this query so problematic? Because the real issue is hiding just beneath the surface. The execution plan and STATISTICS IO didn't consider any of the code evaluated within the UDF! To see what's really going on, fire up SQL Server Profiler, turn on the SQL:BatchCompleted event, and make sure you're showing the Reads column. Now run the query again and you'll see that this seemingly-innocent block of T-SQL is, in fact, using 365,247 logical reads. Quite a difference!

Each of those "compute scalar" operations is really a call to the UDF, and each of the calls to the UDF is really a new query. And all of those queries (all 504 of them -- the number of products in the Product table) add up to massive I/O. Clearly not a good idea in a production environment.

But luckily, we're not done here yet (or this would be a very boring post). Because while the performance penalty is a major turnoff, I really do love the encapsulation afforded by scalar UDFs. I want them (or a similar tool) in my toolbox... And so I got to thinking.

The answer to my dilemma, as it turns out, is to not use scalar UDFs at all, but rather to use inline table-valued UDFs and treat them like scalars. This means that queries get slightly more complex than with scalar UDFs, but because the funtions are inlined (treated like macros) they're optimized along with the rest of the query. Which means, no more under-the-cover cursors.

Following is a modified version of the scalar UDF posted above:

CREATE FUNCTION GetMaxProductQty_Inline
(
    @ProductId INT
)
RETURNS TABLE
AS
    RETURN
    (
        SELECT MAX(sod.OrderQty) AS maxqty
        FROM Sales.SalesOrderDetail sod
        WHERE sod.ProductId = @ProductId
    )

This function is no longer actually scalar--in fact, it now returns a table. It just so happens that the table has exactly one column and exactly one row, and uses the same logic as the scalar UDF shown above. So it's still scalar enough for my purposes.

The query shown above, used to retrieve the maximum quantity sold for each product, will not quite work with this UDF as-is. Trying to substitute in the new UDF will result in nothing more than a variant on an "object not found" error. Instead, you need actually treat this function like it returns a table (due to the fact that it does). And that means, in this case, a subquery:

SELECT
    ProductId,
    (
        SELECT MaxQty
        FROM dbo.GetMaxProductQty_Inline(ProductId)
    ) MaxQty
FROM Production.Product
ORDER BY ProductId

So there it is. We're now treating the table-valued UDF more or less just like a scalar UDF. And the difference in I/O results is really quite astounding: 1267 logical reads in this case. Meaning that the scalar UDF solution is around 288 times more I/O intensive!

The question being, of course, was it worth it? The whole thing could have been written as one query, without the need for any UDFs at all. And the final query in this case is quite a bit more complex than the previous version, in addition to the fact that the encapsulation breaks down to some degree by forcing the caller to have some knowledge of how the UDF actually works. But I do feel that this sacrifice is warranted in some cases. Although the "greatest quantity sold" example shown here is simplistic, imagine other situations in which the same code fragments or logic are used over and over, due to lack of a good way of standardizing and centralizing them. I know I've seen that a lot in my work, and some examples I can think of have included complex logic that might very well have been easier to maintain in a UDF.

This technique may not be perfect for every case, and it certainly has its tradeoffs. But it may be a useful trick to keep in the back of your mind for a rainy day in the data center when someone's scalar UDF solution starts breaking down and you need a fix that doesn't require a massive code rewrite.

Paging in SQL Server 2005

Adam Machanic — Thu, 13 Jul 2006 01:12:00 GMT

I keep seeing questions on newsgroups about paging in stored procedures, and whether there will be a better way in SQL Server 2005. However, aside from a few answers in newsgroups, I haven't seen any content on how to do it. So I'd like to spend a few minutes and share with you the new features that will make paging stored procedures both easier to build and a lot more performant...

But first, since this is a performance-related blog, let's generate a bunch of big test data!

Since I don't have AdventureWorks installed on my test SQL Server 2005 server at the moment and am too lazy to track it down, the data is somewhat ugly... Anyway, start this up and let it run for a while (takes around 35 minutes on my test box):

SELECT DISTINCT A.Name + B.Name + C.Name AS SomewhatLargeString
INTO #BigTableOfStrings
FROM	master..spt_values A,
	master..spt_values B,
	master..spt_values C
WHERE	a.TYPE NOT IN ('P', 'R', 'F', 'F_U')
	AND b.TYPE NOT IN  ('P', 'R', 'F', 'F_U')

CREATE CLUSTERED INDEX CI_LargeString ON #BigTableOfStrings(SomewhatLargeString)

Coffee (or preferably, beer) time! See you in 35 minutes.

... All set?

Okay, now let's pretend we're in a web app with a SQL Server 2000 backend and we want the second page of data... Rows 11-20, ordered by SomewhatLarge. How might we do this in SQL Server 2000..? Here's one way:

SELECT A.SomewhatLargeString
FROM #BigTableOfStrings A
JOIN #BigTableOfStrings B ON B.SomewhatLargeString <= A.SomewhatLargeString
GROUP BY A.SomewhatLargeString
HAVING COUNT(*) BETWEEN 11 AND 20

... Still waiting for that to return? Keep waiting. Maybe get another coffee, or go home for the night. On my system, that query has quite possibly the biggest estimated cost I've ever seen, a staggering 1,523,110,700. Yeah, that sucks. So let's change it around a bit:

SELECT x.SomewhatLargeString
FROM (
	SELECT TOP 20 A.SomewhatLargeString, COUNT(*) AS TheCount
	FROM #BigTableOfStrings A
	JOIN #BigTableOfStrings B ON B.SomewhatLargeString <= A.SomewhatLargeString
	GROUP BY A.SomewhatLargeString
	ORDER BY A.SomewhatLargeString ) x
WHERE x.TheCount BETWEEN 11 AND 20

Much nicer than before, with an estimated cost on my system of 23.1, and a virtually instant return time. But wait, we have an over-zealous user who wants rows 20,001 - 20,010!

SELECT x.SomewhatLargeString
FROM (
	SELECT TOP 20010 A.SomewhatLargeString, COUNT(*) AS TheCount
	FROM #BigTableOfStrings A
	JOIN #BigTableOfStrings B ON B.SomewhatLargeString <= A.SomewhatLargeString
	GROUP BY A.SomewhatLargeString
	ORDER BY A.SomewhatLargeString ) x
WHERE x.TheCount BETWEEN 20001 AND 20010

Oops, cost skyrocketed to 50516, with a return time of 1:30... Can you feel your users abandoning your sinking ship of an app and heading towards the competitors? Probably not, since they won't actually click through 20,000 rows, but it makes a really good contrived example, so let's roll with it!

So how to solve this problem? In SQL Server 2000, the answer is, find some other paging mechanism, probably using a middle tier. But in SQL Server 2005, we have new and better toys to play with. Allow me to introduce your new paging best friend, the ROW_NUMBER() function. For those readers who are slow on the uptake, this function does exactly what its name implies; it creates a surrogate row number for each row in a result set. So now, instead of the very painfully inefficient COUNT(*) methods, we can let SQL Server do all the work as it builds the result set we actually want...

SELECT x.SomewhatLargeString
FROM (
	SELECT TOP 20010 A.SomewhatLargeString, ROW_NUMBER() OVER(ORDER BY A.SomewhatLargeString) AS TheCount
	FROM #BigTableOfStrings A
	ORDER BY A.SomewhatLargeString) x
WHERE x.TheCount BETWEEN 20000 AND 20010

I guess we can call that a tiny improvement. Total estimated cost: 0.202. That's only about a 25 MILLION PERCENT difference.

So why is ROW_NUMBER so much more efficient? It's a combination of the COUNT(*) method itself being inefficient and the query optimizer probably not handling it as well as it should. The COUNT(*) method requires an ordered-forward clustered index scan of the table, followed by correlation of each of the top 20010 rows that we asked for to all of the rows less than or equal to that row in the same table, for the count. Alas, the optimizer chooses a nested loop for that, which causes the cost to shoot up as the operation is repeated over and over.

The ROW_NUMBER method, on the other hand, requires only the scan of the TOP 20010 rows, followed by computation of the row number itself, which is nothing more than a scalar calculation. Then, just filter the rows. Simple, easy on the optimizer, easy for the system, and good for your customers. Definitely a great feature that I'm looking forward to using!