Introduction
This is absolutely nothing new, but well worth revisiting for those who've never seen it before...
In a previous article called "Hidden RBAR: Triangular Joins", I explained the problem of the massive numbers of internal rows that are generated by the use of "Triangular Joins". Many people have solved the Running Total problem using Triangular Joins only to be frustrated by huge performance problems as the source row-counts inched toward as little as 10,000 rows to be totaled.
In one of the responses to my article, someone mentioned that there was a very well written article athttp://sqlblog.com/blogs/adam_machanic/archive/2006/07/12/running-sums-redux.aspx (written by Adam Machanic) where the author discovered that same crippling performance problem. He then explained that he did some testing only to find that cursors where much, much faster at solving the Running Total problem. He found that the cursor would solve the problem on 113,443 rows in only 14 seconds. Since it's a linear/procedural solution, that means it would process a Million rows in just over 2 minutes. Not bad, I say... but it did have to put the output of the cursor into a temp table in order to return the result as a single result set. Between the cursor and the temp table, that's a lot of resources used.
Others chimed in with various methods, some good, some not so good, but many of them required either a cursor or a temp table and While loop. Both the author and others also suggested that the use of CLR's may effectively solve the problem, but no one volunteered any code.
One person correctly identified a very high speed method, but didn't identify the potential reliability problems associated with using SQL Server's proprietary update method of SET @variable = columnname = formula. Other responses to my Triangular Join article included that very same high speed method and, as expected, many folks rightfully pointed out the problem with that method which can make it unreliable. Good friend and frequent poster Gail Shaw (affectionately known as "Gila Monster" on SQLServerCentral.com) appropriately called that problem the "Merry-go-round" index because of the way an index can "wrap around". (By the way, Gail has an interesting SQL blog at http://sqlinthewild.co.za/)
However, you can make the "update method" for solving Running Totals absolutely rock solid reliable and it will resolve a Million rows in less than 7 seconds. This article explains how.
The "Other" Methods
I was actually working on showing how and why the "Triangular Join" methods for solving the Running Total problem where extremely performance challenged and how the Cursor method just beat the pants off of them. Then, I was going to do the obligatory ragging on the Cursor and While loop methods, but the article I cited in the introduction is very well written and I just don't think I could do any better at explaining the problem. Adam even included the formula to calculate the number of internal rows generated for the Triangular Join
If you haven't done so already, take the time to go read that article. The author, Adam Machanic, did a great job... (heh) right up to the point where he thought he needed a Cursor.
Just a little side-bar... Adam Machanic is the good fellow who introduced me to the idea of using Tally (Numbers) tables many years ago... I have a huge respect for the man. Anytime you can find one of his articles or blogs, it's well worth the read.
Test Table
As always, extraordinary claims require extraordinary proof. In SQL Server, that means you have to prove things with code running against some known data... lots of data. The following code builds the test table I used... we'll fill in the data in a minute or two...
--===== Create and populate a 1,000,000 row test table 100 rows at a time to
-- simulate inserting multiple sets of rows.
-- Column "RowNum" is an IDENTITY and has a range of 1 to 1,000,000 unique numbers
-- Column "AccountID" has a range of 1 to 50,000 non-unique numbers
-- Column "Amount has a range of 0.0000 to +/- 99.9900 non-unique numbers
-- Column "Date" has a range of >=01/01/2000 and <01/01/2010 non-unique date/times
--===== If the test table already exists, drop it
SET NOCOUNT ON
IF OBJECT_ID('dbo.JBMTest','U') IS NOT NULL
DROP TABLE dbo.JBMTest
GO
--===== Create the test table
CREATE TABLE dbo.JBMTest
(
RowNum INT IDENTITY (1,1) NOT NULL,
AccountID INT NULL,
Amount MONEY NULL,
Date DATETIME NULL,
RunBal MONEY NULL,
GrpBal MONEY NULL,
RunCnt INT NULL,
GrpCnt INT NULL
)
Notice that we have a couple of "extra" columns for two types of balances (running totals) and two types of running counts. I'll explain each of those as we solve them.
Gail's "Merry-go-Round" Index
Indexes are powerful tools and some think standard indexes can also "sort". But, as Gail pointed out, when you insert data using multiple inserts (the norm for any table over it's life time), you can end up with what she calls a "Merry-go-Round" index that will cause the data to be out of order when you use just the index to drive the sorted return. Just to prove her point, I used the following code to populate the test table with multiple inserts... sorry folks, in order to do the multiple inserts, I had to use a loop...
--===== Add the primary key
ALTER TABLE dbo.JBMTest
ADD PRIMARY KEY CLUSTERED (RowNum) --clustered for "Merry-go-Round" test
--===== Add the "sorting index" to the table
CREATE NONCLUSTERED INDEX IX_JBMTest_AccountID_Date --not clustered for "Merry-go-Round" test
ON dbo.JBMTest (AccountID, Date)
--===== Build the table 100 rows at a time to "mix things up"
DECLARE @Counter INT
SET @Counter = 0
WHILE @Counter < 1000000
BEGIN
--===== Add 1000 rows to the test table
INSERT INTO dbo.JBMTest
(AccountID, Amount, Date)
SELECT TOP 100
AccountID = ABS(CHECKSUM(NEWID()))%50000+1,
Amount = CAST(CHECKSUM(NEWID())%10000 /100.0 AS MONEY),
Date = CAST(RAND(CHECKSUM(NEWID()))*3653.0+36524.0 AS DATETIME)
FROM Master.dbo.SysColumns t1
CROSS JOIN Master.dbo.SysColumns t2
--===== Increment the counter
SET @Counter = @Counter + 100
END
Notice the configuration of the indexes... the "oh-so-typical" Clustered Primary Key on an IDENTITY column and a NON-Clustered Index across the columns we'll use to create the running total. Notice also that I added the indexes BEFORE we added data so they had the opportunity to frag just like in a real table.
If you run the following code in the Grid Mode, you see that things start out nicely sorted by AccountID and Date, but the end of the result set "wraps" (Merry-go-Round) as witnessed by the lower AccountID's that suddenly appear...
SELECT *
FROM dbo.JBMTest WITH (INDEX(IX_JBMTest_AccountID_Date)) --Index causes "Merry-go-Round" data
THAT's the problem that so many folks warn about... you simply cannot rely on a standard index to control the order of returned data. That also means that you cannot use a standard index to control procedural code like we will in a minute.
The "ORDER BY" Solution
You absolutely must (not really, you'll see) use an ORDER BY as in the following code which uses SQL Server's proprietary update method instead of a cursor or a loop. And, since ORDER BY doesn't work in an UPDATE, you've gotta use a "Derived Table" to control the order...
--===== Declare the required variables
DECLARE @PrevBal MONEY
SET @PrevBal = 0
DECLARE @AccountID INT
SET @AccountID = 0
--===== Calculate the running total using SQL Server's proprietary update
-- and force the order of the update with and ORDER BY
UPDATE t1
SET @PrevBal = RunBal = t1.Amount + @PrevBal,
@AccountID = t1.AccountID --This does nothing but provide an "anchor"
FROM dbo.JBMTest t1
INNER JOIN
(--==== Derived table "d" provides the sort order for the update
SELECT TOP 100 PERCENT RowNum
FROM dbo.JBMTest
ORDER BY AccountID, Date
)d
ON t1.RowNum = d.RowNum
--===== Display the results in the correct order
SELECT *
FROM dbo.JBMTest
ORDER BY AccountID, Date
Not including the section of code to display the results, that bit of code only took 56 seconds to solve the running total problem on a million rows of highly randomized data and it did it correctly despite the "Merry-go-Round" index. It takes longer than that to do just 10,000 rows using a Triangular Join (Hidden RBAR on steroids!).
Of course, it's difficult to check a million rows of data for accuracy just using the ol' mil-spec Mark 1 Mod 1 "eyeball"... so, part of the extraordinary proof is some verification code... here that is...
Verification Code
--===== If the test table already exists, drop it
IF OBJECT_ID('TempDB..#CheckResults','U') IS NOT NULL
DROP TABLE #CheckResults
GO
--===== Create a table to check the running balance with
CREATE TABLE #CheckResults
(
RowNum INT IDENTITY (1,1) NOT NULL,
AccountID INT NULL,
Amount MONEY NULL,
Date DATETIME NULL,
RunBal MONEY NULL,
GrpBal MONEY NULL,
RunCnt INT NULL,
GrpCnt INT NULL
)
--===== Populate the table so we can check the results
INSERT INTO #CheckResults
SELECT AccountID,
Amount,
Date,
RunBal,
GrpBal,
RunCnt,
GrpCnt
FROM dbo.JBMTest
ORDER BY AccountID, Date
--===== Do the check by subtracting the amount from the running balance
-- and check against the previous record's running balance. THEY SHOULD MATCH!!!
-- In other words, if it worked, this should not return any rows.
SELECT cr1.RunBal,cr2.RunBal - cr2.Amount AS CheckBal
FROM #CheckResults cr1,
#CheckResults cr2
WHERE cr2.RowNum = cr1.RowNum + 1
AND cr2.RunBal - cr2.Amount <> cr1.RunBal
--===== Same kind of check except this is the postive test and should return
-- all rows except one because there is no previous balance after the
-- second to the last row
SELECT cr1.RowNum,cr1.RunBal,cr2.RunBal - cr2.Amount AS CheckBal,cr2.RowNum
FROM #CheckResults cr1,
#CheckResults cr2
WHERE cr2.RowNum = cr1.RowNum + 1
AND cr2.RunBal - cr2.Amount = cr1.RunBal
Now, if you're an SQL purest, you'll probably take some pretty severe exception to using an ORDER BY in a sub-query. Still, it works every time in SQL Server 2k so you might just give it up this one time and use it to solve running total problems because it's twice as fast as the Cursor and While Loop methods...
... heh... but not me... it's way too slow ;-)
Stop the Merry-go-Round, I wanna get off! (Final Test Data)
Absolutely the highest performance method of resolving the Running Total problem is to use a combination of the proprietary Update that SQL Server offers in conjunction with an Index that is capable of guaranteeing the order of the update. In order to do that, we need a CLUSTERED index on the columns that the update code will force using the WITH INDEX hint. Again, extraordinary claims require proof... the following code recreates the table, the required indexes, and the data. This is the "Final" test data that we'll use to solve the Running Total problem from here on in this article...
FINAL Test Data Configuration
--===== Create and populate a 1,000,000 row test table 100 rows at a time to
-- simulate inserting multiple sets of rows.
-- Column "RowNum" is an IDENTITY and has a range of 1 to 1,000,000 unique numbers
-- Column "AccountID" has a range of 1 to 50,000 non-unique numbers
-- Column "Amount has a range of 0.0000 to +/- 99.9900 non-unique numbers
-- Column "Date" has a range of >=01/01/2000 and <01/01/2010 non-unique date/times
--===== If the test table already exists, drop it
SET NOCOUNT ON
IF OBJECT_ID('dbo.JBMTest','U') IS NOT NULL
DROP TABLE dbo.JBMTest
GO
--===== Create the test table
CREATE TABLE dbo.JBMTest
(
RowNum INT IDENTITY (1,1) NOT NULL,
AccountID INT NULL,
Amount MONEY NULL,
Date DATETIME NULL,
RunBal MONEY NULL,
GrpBal MONEY NULL,
RunCnt INT NULL,
GrpCnt INT NULL
)
--===== Add the primary key
ALTER TABLE dbo.JBMTest
ADD PRIMARY KEY NONCLUSTERED (RowNum) --nonclustered to resolve "Merry-go-Round"
--===== Add the "sorting index" to the table
CREATE CLUSTERED INDEX IX_JBMTest_AccountID_Date --clustered to resolve "Merry-go-Round"
ON dbo.JBMTest (AccountID, Date)
--===== Build the table 100 rows at a time to "mix things up"
DECLARE @Counter INT
SET @Counter = 0
WHILE @Counter < 1000000
BEGIN
--===== Add 1000 rows to the test table
INSERT INTO dbo.JBMTest
(AccountID, Amount, Date)
SELECT TOP 100
AccountID = ABS(CHECKSUM(NEWID()))%50000+1,
Amount = CAST(CHECKSUM(NEWID())%10000 /100.0 AS MONEY),
Date = CAST(RAND(CHECKSUM(NEWID()))*3653.0+36524.0 AS DATETIME)
FROM Master.dbo.SysColumns t1
CROSS JOIN Master.dbo.SysColumns t2
--===== Increment the counter
SET @Counter = @Counter + 100
END
GO
--===== Demonstrate that the "Merry-go-Round" symptoms don't apply to the CLUSTERED index
SELECT *
FROM dbo.JBMTest WITH (INDEX(IX_JBMTest_AccountID_Date)) --CLUSTERED Index resolves "Merry-go-Round"
Run the code as often as you like (Grid mode, folks). A quick visual scan through the results will show that they're correctly sorted by AccountID and Date. If you can make it fail in SQL Server 2k, I'd sure like to see the code where it fails. The Clustered Index stops the "Merry-go-Round".
Again, the code above produces the final table/index configuration and data that will be used from here forward in this article.
Code Basis for ALL Such Calculations
The code basis of all the updates that will be demonstrated, whether they be for Running Totals or Running Counts (teaser: Running Counts are also know as "Ranking"), is as follows...
UPDATE SomeTable
SET @Accumulator = ColumnBeingUpdated = @Accumulator + SomeColumnOrValue,
@Reference = SomeColumnInClusteredIndex --an "anchor" whether used or not
FROM SomeTable WITH (INDEX(NameOfClusteredIndex), TABLOCKX)
Trust me, the @Reference column variable is absolutely necessary. Without it, the update may go a bit hay-wire and produce incorrect Running Totals, etc. Good friend and frequent poster Matt Miller noticed that this is especially important in SQL Server 2k5 solutions. On simple Running Total problems, he'll frequently give the @Reference variable the name @Dummy. I think he named it very appropriately because, heh, you're a "Dummy" if you don't include it ;-)
"SomeColumnInClusteredIndex" should usually be something like CustID or, as in our test data, AccountID. It MUST be part of the Clustered index. I usually use a column I want to detect a change in so I can restart the running totals or running counts from 0 if needed.
"@Accumulator" is the "running result" that will contain things like the total accumulated total/balance or total count for the rows processed so far.
"ColumnBeingUpdated" is the column where the running balance or running count will stored.
"SomeColumnOrValue" should be an "amount" column for running totals or the number "1" for running counts (Ranks).
"@Accumulator + SomeColumnOrValue" can actually be quite a lengthy formula including a CASE statement depending on whether or not you're "restarting" the accumulation based on when the "reference" changes, or not.
The "TABLOCKX" just guarantees that no one is going to sneak a row in while our code is at work. It also makes it so SQL Server doesn't have to escalate locks. We know we're going to end up locking the whole table, so why not make it that way right from the "git".
Let's start with solving the Running Total problem...
Solving the Running Total Problem
Let's define the problem and then apply the problem definition to the "Code Basis". We want to calculate a Running Total (without breaks, we'll store it in the "RunBal" column) of the Amount in the test data and we want the results to be displayed in order by AccountID and Date. The Running Total column in the result must contain the sum of all previous rows amounts (also know as the previous row's balance for sake of discussion and we'll call it "@PrevRunBal") + the Amount of the current row (adding a negative amount is the same as subtracting). Our "reference" will be the AccountID so we'll need an @PrevAcctID variable, as well.
If we apply that definition to the Code Basis along with the variable declarations, we end up with the following code to resolve the Running Total (Running Balance) problem...
--===== Declare the variables for the "Code Basis"
DECLARE @PrevRunBal MONEY
SET @PrevRunBal = 0
DECLARE @PrevAcctID INT
SET @PrevAcctID = 0
--===== Apply what we know to the "Code Basis"
UPDATE dbo.JBMTest
SET @PrevRunBal = RunBal = @PrevRunBal + Amount,
@PrevAcctID = AccountID
FROM dbo.JBMTest WITH (INDEX(IX_JBMTest_AccountID_Date),TABLOCKX)
--===== Display the results in the correct order
SELECT *
FROM dbo.JBMTest
ORDER BY AccountID, Date
Not including the code to display the results, the code solves the Running Total problem in less than 7 seconds! It also solves it correctly, every time. But, don't take my word for it... run the "Verification Code" we ran before to prove it!
Solving the "Grouped" Running Total Problem
Ok, what's a "Grouped Running Total". Think of it this way... you have a table with thousands of accounts and amounts... you want a running total for each account much like you would for a single checkbook. Every time the account number changes, you want the running total to start over at zero.
Our test data of a million rows has 50,000 accounts and an average of 20 entries (amounts) for each account. All we have to do is change the running total code from above so that when a change is detected, we reset the running total to zero. We'll do that by changing the formula to a CASE statement (I also changed some variable names for clarity in the code)... like this...
--===== Declare the variables for the "Code Basis"
DECLARE @PrevGrpBal MONEY
SET @PrevGrpBal = 0
DECLARE @PrevAcctID INT
SET @PrevAcctID = 0
--===== Changed the formula to "reset" when the account changes
UPDATE dbo.JBMTest
SET @PrevGrpBal = GrpBal = CASE
WHEN AccountID = @PrevAcctID
THEN @PrevGrpBal + Amount
ELSE Amount -- Restarts total at "0 + current amount"
END,
@PrevAcctID = AccountID
FROM dbo.JBMTest WITH (INDEX(IX_JBMTest_AccountID_Date),TABLOCKX)
--===== Display the results in the correct order
SELECT *
FROM dbo.JBMTest
ORDER BY AccountID, Date
Notice, again... if you don't include the display code, the "Grouped Running Total" is solved on a million rows in less than 7 seconds!. Check it out... scroll through the result set... every time the account changes, the Running Total (GrpBal column) is reset to be "0 + the current Amount".
Solving the Running Count (Ordinal Rank) Problems
The ONLY difference between a Running Total and a Running Count (also known as "Ordinal Rank") is that Running Totals sum up amounts from a column... Running Counts (Ordinal Ranks) sum up "1's". If you replace "Amount" with "1" in the Running Total code, you'll have the Running Count code. Other than that little nuance, the code is absolutely identical. (Note that there are several different types of "Ranks" and those may be covered a future article. The code demonstrated in this article only demonstrates "Ordinal Ranks" where there are no "ties" and no "gaps" in the count).
Because of that, I'm not going to make this already long article any longer by posting the code for each type of Running Count (Ordinal Rank) separately... instead, let's put the two types of Running Totals and Running Counts together in a single documented update and see how fast it runs...
Putting It All Together
The title of this section says it all... we're going to solve the Running Total, Grouped Running Total, Running Count, and Grouped Running Count problems all in 1 Update statement. While it's true that just copying correctly ordered data into a Temp Table that has an IDENTITY column will solve the Running Count problem, that wouldn't be quite as much fun :-), but do keep that in mind... it can be useful in other batch code that doesn't require Running Totals and the like.
--===== Declare the variables for the "Code Basis"
DECLARE @PrevRunBal MONEY --Overall running total
SET @PrevRunBal = 0
DECLARE @PrevGrpBal MONEY --Running total resets when account changes
SET @PrevGrpBal = 0
DECLARE @PrevRunCnt INT --Overall running count (ordinal rank)
SET @PrevRunCnt = 0
DECLARE @PrevGrpCnt INT --Running count resets when account changes
SET @PrevGrpCnt = 0
DECLARE @PrevAcctID INT --The "anchor" and "account change detector"
SET @PrevAcctID = 0
--===== Solve 2 types of Running Total and 2 types of Running Count problems
-- using a single update based on a Clustered Index at VERY high speeds.
UPDATE dbo.JBMTest
SET --===== Running Total
@PrevRunBal = RunBal = @PrevRunBal + Amount,
--===== Grouped Running Total (Reset when account changes)
@PrevGrpBal = GrpBal = CASE
WHEN AccountID = @PrevAcctID
THEN @PrevGrpBal + Amount
ELSE Amount -- Restarts total at "0 + current amount"
END,
--===== Running Count (Ordinal Rank)
@PrevRunCnt = RunCnt = @PrevRunCnt + 1,
--===== Grouped Running Total (Ordinal Rank, Reset when account changes)
@PrevGrpCnt = GrpCnt = CASE
WHEN AccountID = @PrevAcctID
THEN @PrevGrpCnt + 1
ELSE 1 -- Restarts count at "1"
END,
--===== "Anchor" and provides for "account change detection"
@PrevAcctID = AccountID
FROM dbo.JBMTest WITH (INDEX(IX_JBMTest_AccountID_Date),TABLOCKX)
--===== Display the results in the correct order
SELECT *
FROM dbo.JBMTest
ORDER BY AccountID, Date
What's really amazing about this code is it's speed... all 4 "problems" are solved in about 10 seconds or less (not including the display code, of course).
Can't Modify the Base Table
Heh... how many times have I heard that? "Your solution is fine but I can't make changes to my tables so I can't add the Running Total and Running Count columns." Ok, fine... copy the data from the source table to a Temp Table and correctly index the Temp Table and run the code against that.
Another possible problem might be that your DBA is stingy with disk space and won't allow for large Temp Tables or you have many more than a million rows to work with. In that case, you can still do the same thing but using a "semi-permanent working table".
Last, but not least, if you have more than just a couple of million rows to work with, you may need to break the updates into pieces that contain just 1 or two million rows. In that case, the use of Temp or Semi-permanent working tables along with some code to pick the "pages" of a million rows at a time would probably be necessary.
Or, you can use a Cursor method or While Loop method. After all, it does take only a couple of minutes to do a million rows... ;-)
2k5
I've just recently had the [dis] pleasure of installing SQL Server 2005. I ran the attached test code (includes the final test table, indexes, data, and the single update for all 4 running columns) in 2k5 and was delighted to see that it works just like it does in 2k and with nearly identical performance. Not including the data build or display codes, the million row test resolves in about 10 seconds.
I also found one "new" method for Running Totals that uses CROSS APPLY... it turns out that CROSS APPLY nothing more than a correlated subquery in the FROM clause and, for Running Totals and the like, creates a huge Triangular Join and it's performance is just as bad. You can just bet that I'll be testing the RANKing functions for performance to solve the Running Count problems.
Conclusion
In SQL Server 2000, solving Running Total and Running Count (Ordinal Ranking) problems are an absolute bear. Many folks have written slick "set based looking" code that has the hidden RBAR of Triangular Joins that absolutely crushes performance in the face of any significant scalability. Because of that problem, many have made the realization that Running Totals and Running Counts require some sort of procedural code and have given in to the highly accurate yet somewhat slothful Cursor and While Loop methods. Others have made the mistake of trusting standard indexes to sort the data for use with SQL Server's proprietary and very high-speed Update statement.
Hopefully, the proofs and the methods/code demonstrated in this article will give you the confidence that those problems simply melt away when using a Clustered index to control the sort order of the combination "set based/procedural" Update method in SQL Server 2000.
Admittedly, I've not tested this method in SQL Server 7 or 6.5 because I don't have access to those versions anymore, but now you have the tools, methods, and data to conduct such tests on your own. If you find any problems and/or solutions for those problems in any of those versions of SQL Server, I'm sure we'd all appreciate it if you'd take the time to post your findings in the discussions that I'm sure will follow.
I've not completed all of my research on the 2k5 side, but it's starting to look like the methods used in this article , also work nicely in 2k5. Based on the miserable performance of the hidden RBAR of the CROSS APPLY method I found for Running Totals, I'm starting to think that the Update method is going to be faster than any other method in 2k5, as well.
Remember, code is where the performance is at.
--Jeff Moden
"Your lack of planning DOES constitute an emergency on my part... SO PLAN BETTER! "
"RBAR is pronounced "ree-bar" and is a "Modenism" for "Row-By-Agonizing-Row"
