Solving the Running Total and Ordinal Rank Problems (Rewritten)

  • These are incredibly smart techniques, but after playing with such approaches I decided that I don't want to put it into production - they are just a little bit too complex and they do not look robust to me. In my book this is one of those cases where denormalization allows for much faster and significantly simpler solutions:

    BTW, Adam Machanic recommends CLR cursors in such cases...

  • Alexander Kuznetsov-291390 (11/10/2009)


    I decided that I don't want to put it into production - they are just a little bit too complex and they do not look robust to me. In my book this is one of those cases where denormalization allows for much faster and significantly simpler solutions

    Probably a very smart decision in the long run Alex. I have been in that situation many times before where I discover something really kind of neat in SQl Server, but after some serious deliberation and some serious testing as well, I finally realized that discretion is the better part of valor and decided to just leave it out of my production environment. 😛

    "Technology is a weird thing. It brings you great gifts with one hand, and it stabs you in the back with the other. ...:-D"

  • Alexander Kuznetsov-291390 (11/10/2009)


    These are incredibly smart techniques, but after playing with such approaches I decided that I don't want to put it into production - they are just a little bit too complex and they do not look robust to me. In my book this is one of those cases where denormalization allows for much faster and significantly simpler solutions:

    BTW, Adam Machanic recommends CLR cursors in such cases...

    First, thanks for taking the time to stop by and post your thoughts, Alexander. I really appreciate it.

    I'm not sure why you find the "Quirky Update" a bit too complex nor why you don't think they look robust, but that's OK. Your good method will nicely support ongoing running balance updates on insertion of new data, albeit, in a RBAR manner. I'll add some performance testing using your good method to my list of things to do.

    To be sure, your method is very clever... I like it. I just think it will be a bit slow because of it's RBAR nature.

    And, yes, I know Adam recommends using a cursor for this... so do a lot of other good folks. If you don't trust the "Quirky Update" you can do as I suggested in the article... use verification code to verify it worked correctly or do like Adam and others suggest.... use a cursor and tolerate the performance and resource usage hit on large batches. 😉

    --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)
    Intro to Tally Tables and Functions

  • talltop-969015 (11/10/2009)


    Alexander Kuznetsov-291390 (11/10/2009)


    I decided that I don't want to put it into production - they are just a little bit too complex and they do not look robust to me. In my book this is one of those cases where denormalization allows for much faster and significantly simpler solutions

    Probably a very smart decision in the long run Alex. I have been in that situation many times before where I discover something really kind of neat in SQl Server, but after some serious deliberation and some serious testing as well, I finally realized that discretion is the better part of valor and decided to just leave it out of my production environment. 😛

    Yep... that's why I included the Cursor code. If you don't trust in the "Quirky Update" (even though no one has been able to break a properly written one since the first article came out), then do as I said in the article.... use a Cursor, CLR, or some other method you deem satisfactory. I do, however, believe that you're missing out on a very powerful tool. Running totals aren't the only thing this method can be used for.

    Either way, thanks for stopping by and taking the time to write a bit of feedback. I appreciate it.

    --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)
    Intro to Tally Tables and Functions

  • Jeff Moden (11/10/2009)


    Alexander Kuznetsov-291390 (11/10/2009)


    These are incredibly smart techniques, but after playing with such approaches I decided that I don't want to put it into production - they are just a little bit too complex and they do not look robust to me. In my book this is one of those cases where denormalization allows for much faster and significantly simpler solutions:

    BTW, Adam Machanic recommends CLR cursors in such cases...

    First, thanks for taking the time to stop by and post your thoughts, Alexander. I really appreciate it.

    I'm not sure why you find the "Quirky Update" a bit too complex nor why you don't think the look robust, but that's OK. Your good method will nicely support ongoing running balance updates on insertion of new data, albeit, in a RBAR manner. I'll add some performance testing using your good method to my list of things to do.

    To be sure, your method is very clever... I like it. I just think it will be a bit slow because of it's RBAR nature.

    Jeff, I am not sure how RBAR is relevant to denormalization, yet when the running totals are stored right in your row, you don't need any joins, any cursors, anything - selects are as fast as it goes. For inserts, you retrieve only one previous row, so your inserts do not slow down as your table grows...

  • I have found the "quirky update" useful when helping others who needed to capture and update intermediate results along with the final results of a calculation.

    It helps break down the complexity of some problems.

  • Great article Jeff!

    Forget about the undocumented argument for a minute... This is a wonderfully creative solution that gets around the RBAR mess and doesn't leave that bad after-taste I tend to get after I use a cursor 😛 .

    I am interested in how the recursive approach holds up.

  • Thanxalot for the effort in (re-)writing this great article Jeff!

    Adding cross-references to several other great articles and the amount of code to support/prove your point makes it not "only" an article but a "need to know when arguing Quirky Updates" - regardless if for or against it.



    Lutz
    A pessimist is an optimist with experience.

    How to get fast answers to your question[/url]
    How to post performance related questions[/url]
    Links for Tally Table [/url] , Cross Tabs [/url] and Dynamic Cross Tabs [/url], Delimited Split Function[/url]

  • Alexander Kuznetsov-291390 (11/10/2009)


    Jeff, I am not sure how RBAR is relevant to denormalization, yet when the running totals are stored right in your row, you don't need any joins, any cursors, anything - selects are as fast as it goes. For inserts, you retrieve only one previous row, so your inserts do not slow down as your table grows...

    I'm sorry... I should have explained more. It's not the denormalization that makes it RBAR... it's that you can only insert 1 row at a time that makes it RBAR. That notwithstanding, for systems that typically only insert one row at a time, it's a great solution for keeping the in-row running total up to date. On systems that use batches of inserts, it would still have about the same performance as a very well written cursor but would have the advantage of only having to update (calculate) the running total for the new rows added. In other words, it's a great solution when the RBAR inherent in most GUI's is heaped upon the required task.

    --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)
    Intro to Tally Tables and Functions

  • Jeff,

    In my experience, if we need running totals, then we have some unique order of rows to calculate those totals with respect to. Because we know the running totals before we insert a batch, we can insert the whole batch just as easily as we insert a single row - precalculating running totals for every row being inserted is simple, and our constraints definitely support multi-row operations. Does it make sense to you?

  • Hi Jeff,

    Still reading the article. Slowly, though, as I had to do the shopping - cooking - eating - taking kids to bed routine in between. But here are two more comments.

    In the part about the cursor solution, you write:

    It's a very tight loop and pretty fast if I do say so myself. It successfully and correctly updates the AccountRunningTotal column in the table in about 7 minutes and 40 seconds on my humble desktop PC. Not bad for a million rows (heh... yeah... right. Wait and see.).

    I believe that if you compare performance of a cursor to a different solution, the least you can do is to give the cursor a fair chance by choosing the best options. I tested your code on my desktop and it ran in 6:35. I then changed the cursor to a READ_ONLY cursor (which required me to add the primary key to the column list, as this now becomes the way to update the data) and running time dropped to 4:24. I then changed the options from LOCAL FORWARD_ONLY READ_ONLY to LOCAL STATIC READ_ONLY and shaved off another half a mintue - 3:58. I also tried LOCAL FAST_FORWARD READ_ONLY; this took 4:21 for this data (but based on other tests, I expect FAST_FORWARD to outperform STATIC as soon as the amount of data exceeds the available cache memory). I included the bits of code I had to change below.

    --===== Declare the working variables

    DECLARE @PrevAccountID INT

    DECLARE @AccountRunningTotal MONEY

    DECLARE @TransactionDetailID INT

    --===== Create the cursor with rows sorted in the correct

    -- order to do the running balance by account

    DECLARE curRunningTotal CURSOR LOCAL STATIC READ_ONLY

    FOR

    SELECT AccountID, Amount, TransactionDetailID

    FROM dbo.TransactionDetail

    -- WHERE AccountID <= 10 --Uncomment for "short" testing

    ORDER BY AccountID, Date, TransactionDetailID

    OPEN curRunningTotal

    --===== Read the information from the first row of the cursor

    FETCH NEXT FROM curRunningTotal

    INTO @CurAccountID, @Amount, @TransactionDetailID

    (...)

    --===== Update the running total for this row

    UPDATE dbo.TransactionDetail

    SET AccountRunningTotal = @AccountRunningTotal

    WHERE TransactionDetailID = @TransactionDetailID

    --===== Read the information from the next row of the cursor

    FETCH NEXT FROM curRunningTotal

    INTO @CurAccountID, @Amount, @TransactionDetailID

    END --End of the cursor

    If you want to know more details about optimizing cursor performance, read my blog post about this subject.

    On a completely unrelated note, a lot further down in the article you write:

    As we'll see later on in the "ORDER BY" proofs, it's not the scan that matters, it's the actual update that matters. If it has a "Clustered Index Update" as the last step (on the left), then the UPDATE will be done in the same order as the Clustered Index.

    I don't know where you read that a "Clustered Index Update" implies anything about the order in which the update is being done. As far as I know, this operator only means that data in the clustered index pages will be changed. A simple experiment supports this: add a nonclustered index on the AccountRunningCount column before running the UPDATE in figure 14. The "Clustered Index Update" now no longer is the last step (on the left), but the result is still the same - at least on my system (running SQL Server 2005); no idea what this will do on your box since this is indeed undocumented.

    If you have any source that indicates that a "Clustered Index Update" operator in an execution plan implies some ordering of rows instead of only doing what the name sais and nothing more, then please post a reference, as this would be new to me.

    More comments will probably follow as I read further, but I have other things to do as well so it will probably take some time.


    Hugo Kornelis, SQL Server/Data Platform MVP (2006-2016)
    Visit my SQL Server blog: https://sqlserverfast.com/blog/
    SQL Server Execution Plan Reference: https://sqlserverfast.com/epr/

  • Hugo Kornelis (11/10/2009)


    ... and shaved off another half a mintue - 3:58.

    Heh... very cool optimization of the cursor, Hugo. You've managed to upgrade it to only being 33 times slower than the "Quirky Update".

    So far as the source of information about the clustered index, there isn't one... it's undocumented, remember? 😉

    --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)
    Intro to Tally Tables and Functions

  • Alexander Kuznetsov-291390 (11/10/2009)


    Jeff,

    In my experience, if we need running totals, then we have some unique order of rows to calculate those totals with respect to. Because we know the running totals before we insert a batch, we can insert the whole batch just as easily as we insert a single row - precalculating running totals for every row being inserted is simple, and our constraints definitely support multi-row operations. Does it make sense to you?

    The constraints you have in your code certainly support multi-row inserts but, correct me if I'm wrong... the code you use to calculate running totals is still done only one row at a time. Correct?

    --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)
    Intro to Tally Tables and Functions

  • Hi again!

    I've now finished the article, and I just want to post two more comments before I start trying to adapt my set-based iteration method for this specific problem.

    First: In the section 'Introducing the "Quirky Update"', you write that the syntax is documented and even quote the relevant part of Books Online. Unfortunately, you forgot to also quote this very relevant remark in the "Remarks" section of the same Books Online page (highlight added by me):

    Variable names can be used in UPDATE statements to show the old and new values affected, but this should be used only when the UPDATE statement affects a single record. If the UPDATE statement affects multiple records, to return the old and new values for each record, use the OUTPUT clause.

    So your use of this syntax is indeed documented - but as not intended for this purpose!

    Second: In the section 'OMG! I broke it!', you have this code snippet:

    UPDATE @OMG

    SET @N = @N + 1, --Adds 1 to N

    @N = SomeInt = @N + 2, --"Forgets" to do @N + 2 after first row

    @Anchor = RowNum

    FROM @OMG --WITH (TABLOCKX) --Can't be used on a table variable

    OPTION (MAXDOP 1)

    The comment suggests that SQL Server "forgets" something, for all but one of the rows. That is in fact not the case.

    The real problem here is not the 3 part SET statement, but the fact that the SET clause attempts to set a single variable to two different expressions. I was unable to find any official documentation to describe how SQL Server should handle this. I would have expected an error message (just as you do get when you include two column = expression clauses for a single column), but apparently you don't.

    I tried to figure out the rules used in this case by running countless variations of your code and studying the detailed execution plan. The only thing I can say at this point is that I have been unable to find a generic rule, but that (of course, on THIS PARTICULAR hardware, and in THIS PARTICULAR version and build of SQL Server) in this specific case, SQL Server apparently "solves" this by removing the first part of the 3-part assignment. So the query that is executed is actually this one:

    UPDATE @OMG

    SET @N = @N + 1, --Adds 1 to N

    SomeInt = @N + 2, --Sets SomeInt to the current value of @N + 2 but leaves @N unchanged

    @Anchor = RowNum

    FROM @OMG --WITH (TABLOCKX) --Can't be used on a table variable

    OPTION (MAXDOP 1)

    You can easily verify this by checking the value of @N after executing the code - both your version and my guess of the actuallly executed version will leave @N at 4, since it has been increased by 1 for each of the rows.


    Hugo Kornelis, SQL Server/Data Platform MVP (2006-2016)
    Visit my SQL Server blog: https://sqlserverfast.com/blog/
    SQL Server Execution Plan Reference: https://sqlserverfast.com/epr/

  • Jeff Moden (11/10/2009)


    Hugo Kornelis (11/10/2009)


    ... and shaved off another half a mintue - 3:58.

    Heh... very cool optimization of the cursor, Hugo. You've managed to upgrade it to only being 33 times slower than the "Quirky Update".

    I agree that it's still quite slow. I'm working on something better without using undocumented features. Patience, my friend!:-)

    So far as the source of information about the clustered index, there isn't one... it's undocumented, remember? 😉

    So just because you saw a few cases where the clustered index update was on the left and the order in which updates were done happened to coincide with the clustered index, you jumped to the conclusion that this is a reliable rule?

    Okay, you never explicitly state this as being a reliable rule, but you do write:

    If it [the execution plan -HK] has a "Clustered Index Update" as the last step (on the left), then the UPDATE will be done in the same order as the Clustered Index.

    and further down in the article:

    Remember that I said that "Quirky Updates" on a single table will always update in order by the Clustered Index if a "Clustered Index Update" occurred?

    (emphasis in both quotes added by me)

    Well, I already showed you some code where the Clustered Index Update is not the last step and yet the update is done in the clustered index order. If that is not enough to prove that the last index update operator does not dictate update order, how about this one:

    DECLARE @Counter INT

    SELECT @Counter = 0

    UPDATE dbo.TransactionDetail

    SET @Counter = AccountRunningCount = @Counter + 1

    FROM dbo.TransactionDetail WITH (TABLOCKX)--(INDEX=IX_Transaction_NCID)

    WHERE TransactionDetailID IN (12,123,1234,23,234,2345,34,345,3456)

    OPTION (MAXDOP 1)

    GO

    --===== Select all the rows in order by the clustered index

    SELECT *

    FROM dbo.TransactionDetail

    WHERE TransactionDetailID IN (12,123,1234,23,234,2345,34,345,3456)

    ORDER BY AccountID, Date, TransactionDetailID

    I agree that it's a bit silly to try to get a running count for only these 9 rows, but it does prove my point. If you run the code, you'll see that the execution plan for the UPDATE has an "Update Clustered Index" operator as the last step (on the left). And yet, results prove that the updates were not processed in clustered index order, but rather in ascending TransactionDetailID order.

    Note also that if you change the WHERE clause to, for instance,

    WHERE TransactionDetailID % 12345 = 1

    the rows will be updated in clustered index order again.

    The true answer is that the rows will be updated in clustered index order if (and only if)

    a) the rows are read from the clustered index, using an ordered scan (an unordered scan MIGHT be ordered but this is not guaranteed), *AND* there is no sort or other order-affecting step between the read operator and the Compute Scalar / Update Clustered Index operators, or

    b) the rows are read from any (combination of indexes) *AND* there is a sort operator that explicitly sorts the rows in clustered index order before the Compute Scalar / Update Clustered Index operators.

    The only thing that the Clustered Index Update operator does, is writing new values to data pages of the clustered index (which is in fact the table)


    Hugo Kornelis, SQL Server/Data Platform MVP (2006-2016)
    Visit my SQL Server blog: https://sqlserverfast.com/blog/
    SQL Server Execution Plan Reference: https://sqlserverfast.com/epr/

Viewing 15 posts - 16 through 30 (of 308 total)

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