Solving the Running Total and Ordinal Rank Problems (Rewritten)

  • Hi Jeff

    Thanks for the very well written article. I had tried something very similar myself some time ago but could never get it to work accurately. The logic always looked like it should work but I could never get consistent results. Now thanks to your article I realise it down to the clustered key I have on the table I was using. My key was equivalent to the TransactionDetailID whereas i needed AccountID,TransactionDetailID. Not sure I want to change the table in production though as it has about 50 million rows.

    Did it with a backup and your method was way faster than the optimised triangular join I am using.

  • Hey Jeff,

    Top-tier article, rated 5 stars because that's all there are 🙂

    I just hope those handrails are welded on.

    The only thing I dislike about this method is the name. It's the RBAR-avoiding Ordered Update Technique (ROUT) as far as I'm concerned...also nice because its performance ROUTs the competition!

    So...on to my comments:

    1. How much do you regret retiring the INDEX(0) specification present in your original article? That simple hint does away with Hugo's attempt to break it using a WHERE clause or an IN statement. In addition to that, this method has always been about persisting a running total for all records in the set. If you want to do a small subset (enough to invoke an unordered update) you'd probably use another method. That said, adding the INDEX(0) back in solves all those worries.

    2. Alex's objections are valid, but not new. This method is not for everyone. If you don't feel comfortable putting it into production code, that's totally fine. Some will, some won't. I accept that testing is required before every new Cumulative Update, Service Pack, and Version - but I do that anyway!

    3. CLR solutions add little value to this class of problem. Since every row needs to be retrieved and updated, with relatively little computation, T-SQL is the natural solution. And you know what a fan of .NET extensions I am.

    4. Calculating running totals as a batch of records is added is obviously optimal. But that's missing the point too. This method doesn't target that need - it targets persisting a running total when the records already exist, or when new records require an unrestricted update. The two (and other methods) can co-exist quite happily.

    5. It's absolutely true that this method depends on the Clustered Index Update operator processing rows in clustered index order. That's never been a secret. Re-instating the INDEX(0) hint eliminates the only way to defeat that assertion.

    6. The 'optimized cursor' contains a hidden cheat. The STATIC cursor creates a full copy of the needed data in tempdb. This side-steps the horrible fragmentation you set up deliberately on the base table. The RBAR update also side-steps the fragmentation issue by only doing singleton index seeks and updating that single row. If you remove the fragmentation from the base table I think you'll find the performance gap widens again.

    7. The three-part update issue is a bit of a red herring. Very interesting, but I kinda wish you had resisted the temptation to include it in this article. As far as I can see, it should never affect this ordered update method.

    8. The TABLOCK hint potentially allows the Storage Engine to choose an IAM-ordered scan. I have the greatest confidence that the optimizer will in fact always stipulate Ordered:True in the tree it produces if we use INDEX(0). This prevents the IAM-ordered scan. To elaborate: If we have enough rows to that the Storage Engine might consider an IAM scan (64 pages/extents?) the QO is bound to add Ordered:True or an intermediate sort to optimize the update operation. We all know how keen the QO is to avoid random I/O whenever it makes any sort of sense (and occasionally when it doesn't!)

    9. Hugo's RANK method (no slight intended!) also cheats. It sorts the horribly fragmented data into a (non-logged) table variable, before using the RBAR singleton selects and update to avoid the fragmentation when writing the results. (I wonder in passing why RANK() and not ROW_NUMBER(), which is marginally faster...but no matter).

    10. Let's not forget that this method is all about big datasets. One million rows is good enough for a quick repro in an article, but in the real world, with 500M rows to process, the performance difference would be utterly decisive. Especially if you do yourself a favour and remove that artificial fragmentation.

    11. As you may recall, I dislike logical I/O as a performance metric. Worker time (and probably elapsed time) are much more reliable. Ask Joe Chang.

    So Jeff, a huge round of applause for this article. I'm impressed, and that doesn't come easily. I'm not going to throw superlatives at you, but you get the idea. Particularly in light of the handrail situation!

    Paul

  • Peso-284236 (11/11/2009)


    Table variables are bad when comes to parallellism. It seems that parallellism is not used at all when modifying (insert, update or delete) the content of a table variable in any kind. However, using a table variable in a JOIN makes it possible to use parallellism.

    See http://weblogs.sqlteam.com/peterl/archive/2009/10/15/Performance-consideration-when-using-a-Table-Variable.aspx

    Good points...

    To add to that, it's not possible for table variables to use any statistics. Just an FYI... my machine is a single CPU machine so none of the performance increases I got by shifting Hugo's code from a Table Variable to a Temp Table are due to any parallelism.

    --Jeff Moden


    RBAR is pronounced "ree-bar" and is a "Modenism" for Row-By-Agonizing-Row.
    First step towards the paradigm shift of writing Set Based code:
    ________Stop thinking about what you want to do to a ROW... think, instead, of what you want to do to a COLUMN.

    Change is inevitable... Change for the better is not.


    Helpful Links:
    How to post code problems
    How to Post Performance Problems
    Create a Tally Function (fnTally)

  • Martin Butcher-415798 (11/11/2009)


    Hi Jeff

    Thanks for the very well written article. I had tried something very similar myself some time ago but could never get it to work accurately. The logic always looked like it should work but I could never get consistent results. Now thanks to your article I realise it down to the clustered key I have on the table I was using. My key was equivalent to the TransactionDetailID whereas i needed AccountID,TransactionDetailID. Not sure I want to change the table in production though as it has about 50 million rows.

    Did it with a backup and your method was way faster than the optimised triangular join I am using.

    Very cool... Thanks for the feedback Martin.

    On such a large table, the UPDATE may be running into the "Tipping Point" (system sudden slows down due to many factors... mostly memory usage). If there's a logic break in the rows such as an AccountID, you may want to divide you UPDATEs into logical groups of updates. Even if you need to bring a temp table into play, it will still be very, very fast. My recommendation for simple running total/running counts would be try to limit to logical groups of somewhere between 1 and 4 million rows depending on some performance testing on your part.

    Thanks again for the feedback, Martin. I always like to hear about real-life scenarios using the "Quirky Update".

    --Jeff Moden


    RBAR is pronounced "ree-bar" and is a "Modenism" for Row-By-Agonizing-Row.
    First step towards the paradigm shift of writing Set Based code:
    ________Stop thinking about what you want to do to a ROW... think, instead, of what you want to do to a COLUMN.

    Change is inevitable... Change for the better is not.


    Helpful Links:
    How to post code problems
    How to Post Performance Problems
    Create a Tally Function (fnTally)

  • Paul, lets not use words such as "cheat" here.

    The sole purpose of the deliberate fragmentation is to make a point about the order in which the updates take place regardless the level of fragmentation. It is a core argument to make in order to prove the method works as advertised.

    In real life any decent DBA will keep tables at low fragmentation levels and performance comparisons should reflect this reality. Once code has been proven to work reliable on the highly fragmented table, it is therefore much more interesting to acquire the performance numbers from another run on a table with a more realistic (fairly low) level of fragmentation.

  • Paul White (11/11/2009)


    Hey Jeff,

    Top-tier article, rated 5 stars because that's all there are 🙂

    I just hope those handrails are welded on.

    Thanks for stopping by, Paul. It's always a pleasure to see what your thoughts are. They're usually pretty close to what mine are but you write them down one heck of a lot better than I do. 😉

    I'm getting ready for work so just a quick answer for now...

    Great feedback, particullarly on the use of the INDEX(0) hint...The INDEX(0) hint will do as you say and prevent certain bits of code from causing out of order updates. It can certainly be used if you ever need to do odd WHERE clause content like Hugo did and I thank you for that reminder. It does come at a huge price, though. Use of that hint will make a 5-7 second "Quirky Update" suddenly take 30-40 seconds. That's probably well within the tolerance of pain for most folks on a million rows but as you properly pointed out, some of us would be lucky to have tables of only a million rows.

    Heh... on the issue with the 3 part update... I had to be fair with a problem that was found and I wanted to quell folks fears about that non-problem. At the base level of adding 1+2 to make 3 instead of using a constant, it all looks rather silly because people just wouldn't do that and, even at a higher level, most people simply wouldn't run into that type of problem doing simple running calculations. But, it is something to be aware of while initially creating the formula's for the SET clauses. Just to (again) set everyone's mind at ease, once you have a set of formulas that do the job correctly, it won't break... folks just need to be aware of why things might go wrong while you're trying to write the formulas initially.

    And, just so you know, I had extra heavy duty handrails installed. I'm now considering lubing them up with some pork chop grease.

    Thansk for the feedback and the awesome compliment, Paul.

    --Jeff Moden


    RBAR is pronounced "ree-bar" and is a "Modenism" for Row-By-Agonizing-Row.
    First step towards the paradigm shift of writing Set Based code:
    ________Stop thinking about what you want to do to a ROW... think, instead, of what you want to do to a COLUMN.

    Change is inevitable... Change for the better is not.


    Helpful Links:
    How to post code problems
    How to Post Performance Problems
    Create a Tally Function (fnTally)

  • Jeff Moden (11/11/2009)


    Martin Butcher-415798 (11/11/2009)


    Hi Jeff

    Thanks for the very well written article. I had tried something very similar myself some time ago but could never get it to work accurately. The logic always looked like it should work but I could never get consistent results. Now thanks to your article I realise it down to the clustered key I have on the table I was using. My key was equivalent to the TransactionDetailID whereas i needed AccountID,TransactionDetailID. Not sure I want to change the table in production though as it has about 50 million rows.

    Did it with a backup and your method was way faster than the optimised triangular join I am using.

    Very cool... Thanks for the feedback Martin.

    On such a large table, the UPDATE may be running into the "Tipping Point" (system sudden slows down due to many factors... mostly memory usage). If there's a logic break in the rows such as an AccountID, you may want to divide you UPDATEs into logical groups of updates. Even if you need to bring a temp table into play, it will still be very, very fast. My recommendation for simple running total/running counts would be try to limit to logical groups of somewhere between 1 and 4 million rows depending on some performance testing on your part.

    Thanks again for the feedback, Martin. I always like to hear about real-life scenarios using the "Quirky Update".

    Jeff

    Something odd goes on when you apply this on large tables, maybe the tipping point you mention above but I havent had time to investigate fully.

    I ran the code to update the running balance in a table with 35 million rows and it took about 17 mins on my PC which is excellent. BUT it did not produce accurate results. I had about 185 thousand rows with descrepancies. When I re-ran the update on just those accounts where it had gone wrong the first time around I got the correct results so its not the actual code that seems to be faulty. I will try spitting it up into chuncks of around 4 million rows and let you know the results

    Cheers

    PS have re-run it on the same database splitting it into chunks of accounts and it all works OK

    That kind of behaviour is a little bit too disconcerting to use this in a production environment, you could never rely on it not having a funny moment and updating the totals incorrectly so I will have a play with the other solutions.

    Martin

  • Martin,

    Understood. Could you post the original code you used that created the bad updates?

    --Jeff Moden


    RBAR is pronounced "ree-bar" and is a "Modenism" for Row-By-Agonizing-Row.
    First step towards the paradigm shift of writing Set Based code:
    ________Stop thinking about what you want to do to a ROW... think, instead, of what you want to do to a COLUMN.

    Change is inevitable... Change for the better is not.


    Helpful Links:
    How to post code problems
    How to Post Performance Problems
    Create a Tally Function (fnTally)

  • peter-757102 (11/11/2009)


    Paul, lets not use words such as "cheat" here.

    Why not? I think you're reading something into that which isn't there!

    peter-757102 (11/11/2009)


    The sole purpose of the deliberate fragmentation is to make a point about the order in which the updates take place regardless the level of fragmentation. It is a core argument to make in order to prove the method works as advertised.

    That's fine.

    peter-757102 (11/11/2009)


    In real life any decent DBA will keep tables at low fragmentation levels and performance comparisons should reflect this reality. Once code has been proven to work reliable on the highly fragmented table, it is therefore much more interesting to acquire the performance numbers from another run on a table with a more realistic (fairly low) level of fragmentation.

    I think that was broadly my point. When comparing performance, we should be fair.

    Paul

  • Jeff Moden (11/11/2009)


    Martin,

    Understood. Could you post the original code you used that created the bad updates?

    Hi Jeff as requested here is the code used and the output from my database with about 35 million rows, I have also included the code that I used to split it up into smaller transactions where it updated OK.

    Sorry the formatting is so bad but it was Ok when I posted it in!

    SET NOCOUNT ON

    --===== Declare the working variables

    DECLARE @PrevAccountID INT

    DECLARE @AccountRunningTotal DECIMAL(14, 3)

    --

    --===== Update the running total for this row using the "Quirky Update" -- and a "Pseudo-cursor"

    UPDATE

    dbo.Ledger

    SET

    @AccountRunningTotal = RunningTotal =

    CASE WHEN AccountID = @PrevAccountID THEN CASE WHEN @AccountRunningTotal > 0

    THEN @AccountRunningTotal + (Credit - Debit)

    ELSE @AccountRunningTotal - (Debit - Credit)END

    ELSE (Credit - Debit)

    END,

    @PrevAccountID = AccountID

    FROM

    dbo.Ledger WITH (TABLOCKX)

    WHERE

    LedgerType = 'Account'

    OPTION

    (MAXDOP 1)

    Below are the results. Basically I have a table that holds monetary transactions for accounts where they get billed periodically. This is held in the credit and debit columns which are both positive. The running balance can be positive or negative depending on whether there is any money owing. The RunningBallance is the existing balance column that already exists on the table I have been playing with and the RunningTotal is the new column I have added to examine the Quirky Update.

    For most accounts this works OK, but occasionally it seems to lose track of the AccountID so it falls through to the final else statement that sets RunningTotal = (Credit - Debit). See the results below for one account where it works for the first 27 rows then is wrong

    Which account this happens to is not consistent across multiple times of running the code so it is not the data.

    I re-ran the the update splitting it into blocks of 1000 accounts and it all ran OK

    SET NOCOUNT ON

    --===== Declare the working variables

    DECLARE @PrevAccountID INT

    DECLARE @AccountRunningTotal DECIMAL(14, 3)

    DECLARE @ic INT

    Declare @oc int

    SET @ic = 0

    SET @oc = 0

    WHILE @oc < 560000

    BEGIN

    BEGIN TRAN

    WHILE @ic < = 10000

    BEGIN

    UPDATE

    dbo.Ledger

    SET

    @AccountRunningTotal = RunningTotal =

    CASE WHEN AccountID = @PrevAccountID

    THEN CASE WHEN @AccountRunningTotal > 0

    THEN @AccountRunningTotal

    + (Credit - debit)

    ELSE @AccountRunningTotal –

    (Debit - Credit)

    END

    ELSE (Credit - debit)

    END,

    @PrevAccountID = AccountID

    FROM

    dbo.Ledger WITH (TABLOCKX)

    WHERE

    LedgerType = 'Account'

    AND AccountID = @oc

    OPTION

    (MAXDOP 1)

    SET @ic = @ic + 1

    SET @oc = @oc + 1

    END

    SET @ic = 0

    COMMIT TRAN

    End

    Results from one bad account

    Where the 2 final columns are equal it is OK but after line 27 the columns are no longer equal

    CreditDebitRunningBalanceRunningtotal

    0.0025.90-25.90-25.90

    0.0069.95-95.85-95.85

    25.900.00-69.95-69.95

    69.950.000.000.00

    0.0025.90-25.90-25.90

    25.900.000.000.00

    0.0025.90-25.90-25.90

    25.900.000.000.00

    0.0025.90-25.90-25.90

    25.900.000.000.00

    0.0025.90-25.90-25.90

    25.900.000.000.00

    0.0025.90-25.90-25.90

    25.900.000.000.00

    0.0025.90-25.90-25.90

    25.900.000.000.00

    0.0025.90-25.90-25.90

    25.900.000.000.00

    0.0025.90-25.90-25.90

    25.900.000.000.00

    0.0025.90-25.90-25.90

    25.900.000.000.00

    0.0025.90-25.90-25.90

    25.900.000.000.00

    0.0025.90-25.90-25.90

    25.900.000.000.00

    0.0025.90-25.90-25.90

    25.900.000.0025.90

    0.0025.90-25.900.00

    25.900.000.0025.90

    0.0025.90-25.900.00

    25.900.000.0025.90

    0.0025.90-25.900.00

    25.900.000.0025.90

    0.0025.90-25.900.00

    25.900.000.0025.90

    0.0025.90-25.900.00

    25.900.000.0025.90

    0.0025.90-25.900.00

    25.900.000.0025.90

    0.0025.90-25.900.00

    25.900.000.0025.90

    0.0025.90-25.900.00

    25.900.000.0025.90

    0.0025.90-25.900.00

    25.900.000.0025.90

    0.0025.90-25.900.00

    25.900.000.0025.90

    0.0025.90-25.900.00

    25.900.000.0025.90

  • I've got a solution to the 'undocumented' aspect:

    (1) write two SQL solutions to solve the problem, one using 'quirky update' and the other using <insert documented method preference here>. Test them side by side, the only difference should be performance.

    (2) write a switch into the program to choose one or the other methods based on a bit value in a singleton config table

    (3) (optional) write some 'canary code' which runs a reasonably complex test case (like Jeff's). Run this automatically on your test server every time you apply a new SP or update. Alternatively, run it once a day in a test environment. Have it email you if the test ever fails.

    (4) (optional) create a process to automatically 'flick the switch' on your production server(s) if the canary code test ever fails. You can do the investigation while the production server runs in safe go-slow mode.

    (5) (personally, I would code it like this, and you're probably very glad by now that I'm not coding your systems) store some metadata on the user who is viewing the config switch, and depending which side of the floor they're on in this debate, display options as either 'Use Undocumented Hack' vs 'Proper Functioning', or 'Go Fast' vs 'Go Slow'.

    🙂

    ... (6) maybe we could also use a test like this for some of the documented functions of SQL Server too ...

  • Martin Butcher-415798 (11/12/2009)


    Hi Jeff as requested here is the code used and the output from my database with about 35 million rows, I have also included the code that I used to split it up into smaller transactions where it updated OK.

    Thanks Martin, I'll check it out tonight after work.

    --Jeff Moden


    RBAR is pronounced "ree-bar" and is a "Modenism" for Row-By-Agonizing-Row.
    First step towards the paradigm shift of writing Set Based code:
    ________Stop thinking about what you want to do to a ROW... think, instead, of what you want to do to a COLUMN.

    Change is inevitable... Change for the better is not.


    Helpful Links:
    How to post code problems
    How to Post Performance Problems
    Create a Tally Function (fnTally)

  • Jeff Moden (11/12/2009)


    Martin Butcher-415798 (11/12/2009)


    Hi Jeff as requested here is the code used and the output from my database with about 35 million rows, I have also included the code that I used to split it up into smaller transactions where it updated OK.

    Thanks Martin, I'll check it out tonight after work.

    Martin, before I can check it out, I need some additional information... I need you to generate the CREATE TABLE statement and the code for all the indexes, please.

    --Jeff Moden


    RBAR is pronounced "ree-bar" and is a "Modenism" for Row-By-Agonizing-Row.
    First step towards the paradigm shift of writing Set Based code:
    ________Stop thinking about what you want to do to a ROW... think, instead, of what you want to do to a COLUMN.

    Change is inevitable... Change for the better is not.


    Helpful Links:
    How to post code problems
    How to Post Performance Problems
    Create a Tally Function (fnTally)

  • [/quote]

    Martin, before I can check it out, I need some additional information... I need you to generate the CREATE TABLE statement and the code for all the indexes, please.[/quote]

    Jeff

    Here is the create table statement, in real life it has more colums and foreign keys but there is no way I can paste the real life table on a public forum

    You will notice the Ledgertype column where in real life this is used to define several types of accounts within the table. The vast majority of which are of type 'Account' which is what I was playing with in my tests.

    I am running 2005 service pack 3 Developer Edition

    Cheers

    Martin

    SET ANSI_NULLS ON

    GO

    SET QUOTED_IDENTIFIER ON

    SET ANSI_PADDING ON

    GO

    CREATE TABLE [dbo].[Ledger](

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

    [LedgerType] [varchar](50) NOT NULL,

    [AccountID] [int] NOT NULL,

    [Debit] [decimal](14, 3) NULL CONSTRAINT [DF_LedDebit_0] DEFAULT ((0)),

    [Credit] [decimal](14, 3) NULL CONSTRAINT [DF_LedCredit_0] DEFAULT ((0)),

    [RunningBalance] [decimal](14, 3) NOT NULL CONSTRAINT [DF_LedgerRunningBalance] DEFAULT ((0)),

    [runningtotal] [decimal](14, 3) NULL,

    CONSTRAINT [PK_Ledger] PRIMARY KEY CLUSTERED

    (

    [AccountID] ASC,

    [LedgerId] ASC

    )WITH (PAD_INDEX = OFF, STATISTICS_NORECOMPUTE = OFF, IGNORE_DUP_KEY = OFF, ALLOW_ROW_LOCKS = ON, ALLOW_PAGE_LOCKS = ON) ON [PRIMARY]

    ) ON [PRIMARY]

    GO

    SET ANSI_PADDING OFF

    GO

    CREATE NONCLUSTERED INDEX [Ledger_AccountID] ON [dbo].[Ledger]

    (

    [AccountID] ASC

    )

    INCLUDE ( [LedgerId]) WITH (PAD_INDEX = OFF, STATISTICS_NORECOMPUTE = OFF, SORT_IN_TEMPDB = OFF, IGNORE_DUP_KEY = OFF, DROP_EXISTING = OFF, ONLINE = OFF, ALLOW_ROW_LOCKS = ON, ALLOW_PAGE_LOCKS = ON) ON [PRIMARY]

    GO

    CREATE NONCLUSTERED INDEX [Account_LedgerID_LedgerType] ON [dbo].[Ledger]

    (

    [AccountID] ASC,

    [LedgerId] ASC,

    [LedgerType] ASC

    )

    INCLUDE ( [Debit],[Credit]) WITH (PAD_INDEX = OFF, STATISTICS_NORECOMPUTE = OFF, SORT_IN_TEMPDB = OFF, IGNORE_DUP_KEY = OFF, DROP_EXISTING = OFF, ONLINE = OFF, ALLOW_ROW_LOCKS = ON, ALLOW_PAGE_LOCKS = ON, FILLFACTOR = 80) ON [PRIMARY]

    GO

    CREATE NONCLUSTERED INDEX [LedgerID_AccountID] ON [dbo].[Ledger]

    (

    [LedgerId] ASC,

    [AccountID] ASC

    )

    INCLUDE ( [RunningBalance]) WITH (PAD_INDEX = OFF, STATISTICS_NORECOMPUTE = OFF, SORT_IN_TEMPDB = OFF, IGNORE_DUP_KEY = OFF, DROP_EXISTING = OFF, ONLINE = OFF, ALLOW_ROW_LOCKS = ON, ALLOW_PAGE_LOCKS = ON) ON [PRIMARY]

    GO

  • Ok, Martin... I'm confused... I see that all of your code examples update the "RunningBalance" column... none of the code updates the "RunningTotal" column yet your complaint is that the "RunningTotal" column goes astray according to your thoughts. What is it that updates the "RunningTotal" column?

    And, by the way, it's the "RunningTotal" column that went astray... not the "RunningBalance" column that (according to your code), that the "Quirky Update" correctly calculated. 😉

    --Jeff Moden


    RBAR is pronounced "ree-bar" and is a "Modenism" for Row-By-Agonizing-Row.
    First step towards the paradigm shift of writing Set Based code:
    ________Stop thinking about what you want to do to a ROW... think, instead, of what you want to do to a COLUMN.

    Change is inevitable... Change for the better is not.


    Helpful Links:
    How to post code problems
    How to Post Performance Problems
    Create a Tally Function (fnTally)

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

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