Recent PostsRecent Posts Popular TopicsPopular Topics
 Home Search Members Calendar Who's On

 Filling Buckets Rate Topic Display Mode Topic Options
Author
 Message
 Posted Friday, September 12, 2008 7:42 AM
 SSC Eights! Group: General Forum Members Last Login: Monday, April 14, 2014 3:58 PM Points: 913, Visits: 1,734
 A customer had reported an issue with one of our stored procedures so I took a look and found that the developer had used a cursor to implement his solution. Taking the “all cursors are evil” view I thought that I had better rewrite it, however it wasn’t as easy as I hoped.The problem can be simplified to... You have a set of buckets, with varying sizes, so of which are already full/partly full. You are then given some more water which you are to use to fill the buckets on a first-come-first-served basis.This can be modelled with the following table`create table dbo.Buckets ( TotalSize int not null, Amount int not null, BucketID int not null,constraint pk_Buckets primary key (BucketID),constraint ck_Buckets_Amount check ( Amount between 0 and TotalSize))go`WhereTotalSize = the total amount the bucket can holdAmount = the amount currently in the bucketBucketID = unique id for the bucket, and is used to determine the order of the buckets ExampleSo if, we had the following 4 buckets`insert into dbo.Buckets (TotalSize,Amount,BucketID)select 10, 1, 1goinsert into dbo.Buckets (TotalSize,Amount,BucketID)select 5, 4, 2goinsert into dbo.Buckets (TotalSize,Amount,BucketID)select 10, 0, 3goinsert into dbo.Buckets (TotalSize,Amount,BucketID)select 10, 0, 4go`and we had to allocate 21 units of water we would end up withBucket 1=10Bucket 2 =5Bucket 3 =10Bucket 4 =1My SolutionThe solution I came up was to use two update statements, the first one to handle the buckets which would be completely filled, and the second one to partially fill the final bucket. This seemed to be working well, until I went to look at the issue reported by the customer - they also needed the ability to empty the buckets as well. My best solution so far (below), is to use another two update statements with an “if” statement to control which are to be used.So my questions are1. Is this a “standard” problem with a well known solution?2. Is there a better solution, as I have to use an ‘if’ statement and double-subselects.3. Is updating the @AmountToAllocate variable in an update statement a good idea?thanks in advanceDavidMy sql is...`-- The amount of water was have to allocatedeclare @AmountToAllocate intset @AmountToAllocate = 21-- 'Before'select * from dbo.Buckets-- If the amount is positive then we are filling the bucketsif @AmountToAllocate > 0 begin -- Fill these buckets completely, decrease our "amount to allocate" as we go. -- We update just the buckets then we can completely full. If we filled the following bucket then -- we would have exceed the amount of water we have been given to allocate. update dbo.Buckets set Amount = TotalSize, @AmountToAllocate = @AmountToAllocate - (TotalSize - Amount) where Amount != TotalSize and BucketID <= ( select max(B2.BucketID) from dbo.Buckets B2 where @AmountToAllocate >= ( select sum(TotalSize - Amount) from dbo.Buckets B3 where B3.BucketID <= B2.BucketID ) ) -- Part fill the remaining bucket update dbo.Buckets set Amount = Amount + @AmountToAllocate where BucketID = ( select min(B.BucketID) from dbo.Buckets B where B.Amount != B.TotalSize)endelsebegin--We have a negative amount so we are emptying the buckets -- Complete empty buckets update dbo.Buckets set Amount = 0, @AmountToAllocate = @AmountToAllocate + Amount where Amount != 0 and BucketID >= ( select min(B2.BucketID) from dbo.Buckets B2 where abs(@AmountToAllocate) >= ( select sum(Amount) from dbo.Buckets B3 where B3.BucketID >= B2.BucketID ) ) -- Part empty the remaining bucket update dbo.Buckets set Amount = Amount - abs(@AmountToAllocate) where BucketID = ( select max(B.BucketID) from dbo.Buckets B where B.Amount != 0)end--'After'select * from dbo.Buckets`
Post #568498
 Posted Tuesday, September 11, 2012 3:17 AM
 Forum Newbie Group: General Forum Members Last Login: Tuesday, July 02, 2013 7:12 AM Points: 3, Visits: 58
 Interesting. I have been working on a similar task. This is to take away sales figures (already sold items) from a set of monthly sales forecast figures.eg. Sales Forecast for an item:Month 1: 200, Sales 450 (already sold items in Month 1)Month 2: 100 (no Sales beyond current month, only future orders)Month 3: 100Month 4: 120I have to remove 450 from the month buckets, starting at M1.So the update forecast would be:M1: 0M2: 0M3: 0M4: 70There is an added constraint, which is to only only make adjustments up to a certain number of months in the future. eg. If Months to Consider = 4 then the result would be as above.But if Months to Consider = 3 then the result for Month 4 would remain at the original 120. The extra 70 from the Sales would become part of the original Sales forecast.Orders (not shown) as opposed to Sales also affect the forecast.Got no code to show, but it is similar to what you have shown.But I ended up using a cursor around the procedure because I have 6,000 item forecasts to process. (I couldn't work out how to do the sub-selects without the cursor, and was running out of time).I have not found anything much better than what you have shown. If I had some more time I would investigate, as I can't help feeling there may be some "Tally table" solution to this.
Post #1357223
 Posted Tuesday, September 11, 2012 3:53 AM
 SSCommitted Group: General Forum Members Last Login: Tuesday, April 08, 2014 6:13 AM Points: 1,694, Visits: 19,550
 I think this is a running totals problem, have a look herehttp://www.sqlservercentral.com/articles/T-SQL/68467/If you are using SQL Server 2012, you can use the built-in windowing functions`DECLARE @ToAllocate INT = 21;WITH CTE AS (SELECT TotalSize, Amount, BucketID, TotalSize - Amount AS Remaining, SUM(TotalSize - Amount) OVER (ORDER BY BucketID ROWS UNBOUNDED PRECEDING) AS Remaining_RunningTotalFROM dbo.Buckets)SELECT TotalSize, Amount, BucketID, CASE WHEN Remaining_RunningTotal <= @ToAllocate THEN Remaining ELSE @ToAllocate - Remaining_RunningTotal + Remaining END AS AmountToAddFROM CTEWHERE Remaining_RunningTotal - Remaining < @ToAllocateORDER BY BucketID;` ____________________________________________________How to get the best help on a forumhttp://www.sqlservercentral.com/articles/Best+Practices/61537Never approach a goat from the front, a horse from the rear, or a fool from any direction.
Post #1357250
 Posted Tuesday, September 11, 2012 4:03 AM
 Hall of Fame Group: General Forum Members Last Login: Yesterday @ 5:42 PM Points: 3,596, Visits: 5,112
 The first looks more like a bin packing problem to me:http://sqlblog.com/blogs/hugo_kornelis/archive/2007/11/30/bin-packing-part-1-setting-a-baseline.aspxThere's a series of 5 articles by Hugo Kornelis at this link (to the first). Very complicated, but the fastest solutions typically involve a set-based loop of some sort.You didn't mention if speed is an issue for you. The CURSOR will work OK as long as you don't have too many buckets to fill.PM me if you would like more information. My mantra: No loops! No CURSORs! No RBAR! Hoo-uh!My thought question: Have you ever been told that your query runs too fast?My advice:INDEXing a poor-performing query is like putting sugar on cat food. Yeah, it probably tastes better but are you sure you want to eat it?The path of least resistance can be a slippery slope. Take care that fixing your fixes of fixes doesn't snowball and end up costing you more than fixing the root cause would have in the first place.Need to UNPIVOT? Why not CROSS APPLY VALUES instead?Since random numbers are too important to be left to chance, let's generate some!Learn to understand recursive CTEs by example.Splitting strings based on patterns can be fast!
Post #1357261
 Posted Tuesday, September 11, 2012 5:08 AM
 Forum Newbie Group: General Forum Members Last Login: Tuesday, July 02, 2013 7:12 AM Points: 3, Visits: 58
 Thanks for the links guys. Obviously wasn't looking hard enough.
Post #1357317
 Posted Tuesday, September 11, 2012 7:24 AM
 SSCertifiable Group: General Forum Members Last Login: Today @ 9:12 AM Points: 6,783, Visits: 12,893
 Using the sample data provided, a simple calculation rCTE works fine with both positive and negative numbers.`DECLARE @AmountToAllocate INT = 21 ;WITH Calculator AS (SELECT BucketID, TotalSize, Amount, AmountLeftToAllocate = CASE WHEN @AmountToAllocate > (TotalSize - Amount) THEN @AmountToAllocate - (TotalSize - Amount) WHEN @AmountToAllocate < 0 AND ABS(@AmountToAllocate) > Amount THEN Amount + @AmountToAllocate ELSE 0 END, NewAmount = CASE WHEN @AmountToAllocate > (TotalSize - Amount) THEN TotalSize WHEN @AmountToAllocate < 0 AND ABS(@AmountToAllocate) > Amount THEN 0 ELSE Amount + @AmountToAllocate END FROM dbo.BucketsWHERE BucketID = 1UNION ALLSELECT tr.BucketID, tr.TotalSize, tr.Amount, AmountLeftToAllocate = CASE WHEN lr.AmountLeftToAllocate > (tr.TotalSize - tr.Amount) THEN lr.AmountLeftToAllocate - (tr.TotalSize - tr.Amount) WHEN lr.AmountLeftToAllocate < 0 AND ABS(lr.AmountLeftToAllocate) > tr.Amount THEN tr.Amount + lr.AmountLeftToAllocate ELSE 0 END, NewAmount = CASE WHEN lr.AmountLeftToAllocate > (tr.TotalSize - tr.Amount) THEN tr.TotalSize WHEN lr.AmountLeftToAllocate < 0 AND ABS(lr.AmountLeftToAllocate) > tr.Amount THEN 0 ELSE tr.Amount + lr.AmountLeftToAllocate END FROM dbo.Buckets trINNER JOIN Calculator lr ON lr.BucketID + 1 = tr.BucketID )SELECT BucketID, TotalSize, Amount = NewAmount, OldAmount = Amount FROM Calculator` “Write the query the simplest way. If through testing it becomes clear that the performance is inadequate, consider alternative query forms.” - Gail ShawFor fast, accurate and documented assistance in answering your questions, please read this article.Understanding and using APPLY, (I) and (II) Paul White Hidden RBAR: Triangular Joins / The "Numbers" or "Tally" Table: What it is and how it replaces a loop Jeff ModenExploring Recursive CTEs by Example Dwain Camps
Post #1357390
 Posted Tuesday, September 11, 2012 6:10 PM
 Hall of Fame Group: General Forum Members Last Login: Yesterday @ 5:42 PM Points: 3,596, Visits: 5,112
 ChrisM@Work (9/11/2012)Using the sample data provided, a simple calculation rCTE works fine with both positive and negative numbers.`DECLARE @AmountToAllocate INT = 21 ;WITH Calculator AS (SELECT BucketID, TotalSize, Amount, AmountLeftToAllocate = CASE WHEN @AmountToAllocate > (TotalSize - Amount) THEN @AmountToAllocate - (TotalSize - Amount) WHEN @AmountToAllocate < 0 AND ABS(@AmountToAllocate) > Amount THEN Amount + @AmountToAllocate ELSE 0 END, NewAmount = CASE WHEN @AmountToAllocate > (TotalSize - Amount) THEN TotalSize WHEN @AmountToAllocate < 0 AND ABS(@AmountToAllocate) > Amount THEN 0 ELSE Amount + @AmountToAllocate END FROM dbo.BucketsWHERE BucketID = 1UNION ALLSELECT tr.BucketID, tr.TotalSize, tr.Amount, AmountLeftToAllocate = CASE WHEN lr.AmountLeftToAllocate > (tr.TotalSize - tr.Amount) THEN lr.AmountLeftToAllocate - (tr.TotalSize - tr.Amount) WHEN lr.AmountLeftToAllocate < 0 AND ABS(lr.AmountLeftToAllocate) > tr.Amount THEN tr.Amount + lr.AmountLeftToAllocate ELSE 0 END, NewAmount = CASE WHEN lr.AmountLeftToAllocate > (tr.TotalSize - tr.Amount) THEN tr.TotalSize WHEN lr.AmountLeftToAllocate < 0 AND ABS(lr.AmountLeftToAllocate) > tr.Amount THEN 0 ELSE tr.Amount + lr.AmountLeftToAllocate END FROM dbo.Buckets trINNER JOIN Calculator lr ON lr.BucketID + 1 = tr.BucketID )SELECT BucketID, TotalSize, Amount = NewAmount, OldAmount = Amount FROM Calculator`Nice one Chris! For some reason I just couldn't wrap my head around solving it that way. My mantra: No loops! No CURSORs! No RBAR! Hoo-uh!My thought question: Have you ever been told that your query runs too fast?My advice:INDEXing a poor-performing query is like putting sugar on cat food. Yeah, it probably tastes better but are you sure you want to eat it?The path of least resistance can be a slippery slope. Take care that fixing your fixes of fixes doesn't snowball and end up costing you more than fixing the root cause would have in the first place.Need to UNPIVOT? Why not CROSS APPLY VALUES instead?Since random numbers are too important to be left to chance, let's generate some!Learn to understand recursive CTEs by example.Splitting strings based on patterns can be fast!
Post #1357749
 Posted Thursday, September 13, 2012 2:41 AM
 SSCertifiable Group: General Forum Members Last Login: Today @ 9:12 AM Points: 6,783, Visits: 12,893
 dwain.c (9/11/2012)ChrisM@Work (9/11/2012)Using the sample data provided, a simple calculation rCTE works fine with both positive and negative numbers.`DECLARE @AmountToAllocate INT = 21 ;WITH Calculator AS (SELECT BucketID, TotalSize, Amount, AmountLeftToAllocate = CASE WHEN @AmountToAllocate > (TotalSize - Amount) THEN @AmountToAllocate - (TotalSize - Amount) WHEN @AmountToAllocate < 0 AND ABS(@AmountToAllocate) > Amount THEN Amount + @AmountToAllocate ELSE 0 END, NewAmount = CASE WHEN @AmountToAllocate > (TotalSize - Amount) THEN TotalSize WHEN @AmountToAllocate < 0 AND ABS(@AmountToAllocate) > Amount THEN 0 ELSE Amount + @AmountToAllocate END FROM dbo.BucketsWHERE BucketID = 1UNION ALLSELECT tr.BucketID, tr.TotalSize, tr.Amount, AmountLeftToAllocate = CASE WHEN lr.AmountLeftToAllocate > (tr.TotalSize - tr.Amount) THEN lr.AmountLeftToAllocate - (tr.TotalSize - tr.Amount) WHEN lr.AmountLeftToAllocate < 0 AND ABS(lr.AmountLeftToAllocate) > tr.Amount THEN tr.Amount + lr.AmountLeftToAllocate ELSE 0 END, NewAmount = CASE WHEN lr.AmountLeftToAllocate > (tr.TotalSize - tr.Amount) THEN tr.TotalSize WHEN lr.AmountLeftToAllocate < 0 AND ABS(lr.AmountLeftToAllocate) > tr.Amount THEN 0 ELSE tr.Amount + lr.AmountLeftToAllocate END FROM dbo.Buckets trINNER JOIN Calculator lr ON lr.BucketID + 1 = tr.BucketID )SELECT BucketID, TotalSize, Amount = NewAmount, OldAmount = Amount FROM Calculator`Nice one Chris! For some reason I just couldn't wrap my head around solving it that way.Cheers buddy. It took two goes, the first was rubbish “Write the query the simplest way. If through testing it becomes clear that the performance is inadequate, consider alternative query forms.” - Gail ShawFor fast, accurate and documented assistance in answering your questions, please read this article.Understanding and using APPLY, (I) and (II) Paul White Hidden RBAR: Triangular Joins / The "Numbers" or "Tally" Table: What it is and how it replaces a loop Jeff ModenExploring Recursive CTEs by Example Dwain Camps
Post #1358401
 Posted Friday, September 14, 2012 9:44 AM
 SSCommitted Group: General Forum Members Last Login: Tuesday, January 15, 2013 11:11 AM Points: 1,945, Visits: 2,782
 This is called the Bin Packing problem and there is a lot of literature on it. Now the bad news; it is known to be an NP-Complete, so any solution we find will be sub-optimal. Books in Celko Series for Morgan-Kaufmann PublishingAnalytics and OLAP in SQL Data and Databases: Concepts in Practice Data, Measurements and Standards in SQLSQL for SmartiesSQL Programming Style SQL Puzzles and Answers Thinking in SetsTrees and Hierarchies in SQL
Post #1359446
 Posted Friday, September 14, 2012 10:21 AM
 SSCommitted Group: General Forum Members Last Login: Tuesday, January 15, 2013 11:11 AM Points: 1,945, Visits: 2,782
 This is called the Bin Packing problem and there is a lot of literature on it. Now the bad news; it is known to be an NP-Complete, so any solution we find will be sub-optimal. CREATE TABLE Buckets (bucket_nbr INTEGER NOT NULL PRIMARY KEY, bucket_capacity INTEGER NOT NULL, bucket_contents INTEGER NOT NULL, CHECK (bucket_contents BETWEEN 0 AND bucket_capacity));INSERT INTO Buckets (bucket_nbr, bucket_capacity, bucket_contents)VALUES (1, 10, 1), (2, 5, 4), (3, 10, 0), (4, 10, 0);Want to make a rule that we fill from left to right? So we can find the available capacity at any point in the sequence of buckets.CREATE VIEW Running_Total (bucket_nbr, available_capacity_tot)ASSELECT bucket_nbr, SUM (bucket_capacity – bucket_contents) OVER (ORDER BY bucket_nbr ROWS BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW) FROM Buckets; Now we can find the bucket range, (1 to n) <= 21 and fill them. But the better way is to look for the "best fit" bucket and use it; we often get lucky and can do it with one bucket. The better solutions are (ugh!) procedural and hueristic. Books in Celko Series for Morgan-Kaufmann PublishingAnalytics and OLAP in SQL Data and Databases: Concepts in Practice Data, Measurements and Standards in SQLSQL for SmartiesSQL Programming Style SQL Puzzles and Answers Thinking in SetsTrees and Hierarchies in SQL
Post #1359489

 Permissions