Filling Buckets

  • David Betteridge

    SSCrazy

    Points: 2999

    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

    Where

    TotalSize = the total amount the bucket can hold

    Amount = the amount currently in the bucket

    BucketID = unique id for the bucket, and is used to determine the order of the buckets

    Example

    So if, we had the following 4 buckets

    insert into dbo.Buckets (TotalSize,Amount,BucketID)

    select 10, 1, 1

    go

    insert into dbo.Buckets (TotalSize,Amount,BucketID)

    select 5, 4, 2

    go

    insert into dbo.Buckets (TotalSize,Amount,BucketID)

    select 10, 0, 3

    go

    insert into dbo.Buckets (TotalSize,Amount,BucketID)

    select 10, 0, 4

    go

    and we had to allocate 21 units of water we would end up with

    Bucket 1=10

    Bucket 2 =5

    Bucket 3 =10

    Bucket 4 =1

    My Solution

    The 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 are

    1. 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 advance

    David

    My sql is...

    -- The amount of water was have to allocate

    declare @AmountToAllocate int

    set @AmountToAllocate = 21

    -- 'Before'

    select * from dbo.Buckets

    -- If the amount is positive then we are filling the buckets

    if @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)

    end

    else

    begin

    --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

  • faiselj

    SSC Veteran

    Points: 229

    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: 100

    Month 4: 120

    I have to remove 450 from the month buckets, starting at M1.

    So the update forecast would be:

    M1: 0

    M2: 0

    M3: 0

    M4: 70

    There 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.

  • Mark Cowne

    One Orange Chip

    Points: 26687

    I think this is a running totals problem, have a look here

    http://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_RunningTotal

    FROM dbo.Buckets)

    SELECT TotalSize,

    Amount,

    BucketID,

    CASE WHEN Remaining_RunningTotal <= @ToAllocate

    THEN Remaining

    ELSE @ToAllocate - Remaining_RunningTotal + Remaining

    END AS AmountToAdd

    FROM CTE

    WHERE Remaining_RunningTotal - Remaining < @ToAllocate

    ORDER BY BucketID;

    ____________________________________________________

    Deja View - The strange feeling that somewhere, sometime you've optimised this query before

    How to get the best help on a forum

    http://www.sqlservercentral.com/articles/Best+Practices/61537
  • Dwain Camps

    SSC Guru

    Points: 86873

    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.aspx

    There'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![/I]

    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?[/url]
    Since random numbers are too important to be left to chance, let's generate some![/url]
    Learn to understand recursive CTEs by example.[/url]
    [url url=http://www.sqlservercentral.com/articles/St

  • faiselj

    SSC Veteran

    Points: 229

    Thanks for the links guys. Obviously wasn't looking hard enough.

    🙂

  • ChrisM@Work

    SSC Guru

    Points: 186043

    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.Buckets

    WHERE BucketID = 1

    UNION ALL

    SELECT

    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 tr

    INNER JOIN Calculator lr ON lr.BucketID + 1 = tr.BucketID

    )

    SELECT

    BucketID,

    TotalSize,

    Amount = NewAmount,

    OldAmount = Amount

    FROM Calculator

    [font="Arial"]“Write the query the simplest way. If through testing it becomes clear that the performance is inadequate, consider alternative query forms.” - Gail Shaw[/font]


    For fast, accurate and documented assistance in answering your questions, please read this article[/url].
    Understanding and using APPLY, (I)[/url] and (II)[/url] Paul White[/url]
    Hidden RBAR: Triangular Joins[/url] / The "Numbers" or "Tally" Table: What it is and how it replaces a loop[/url] Jeff Moden[/url]
    [url

  • Dwain Camps

    SSC Guru

    Points: 86873

    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.Buckets

    WHERE BucketID = 1

    UNION ALL

    SELECT

    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 tr

    INNER 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![/I]

    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?[/url]
    Since random numbers are too important to be left to chance, let's generate some![/url]
    Learn to understand recursive CTEs by example.[/url]
    [url url=http://www.sqlservercentral.com/articles/St

  • ChrisM@Work

    SSC Guru

    Points: 186043

    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.Buckets

    WHERE BucketID = 1

    UNION ALL

    SELECT

    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 tr

    INNER 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 😀

    [font="Arial"]“Write the query the simplest way. If through testing it becomes clear that the performance is inadequate, consider alternative query forms.” - Gail Shaw[/font]


    For fast, accurate and documented assistance in answering your questions, please read this article[/url].
    Understanding and using APPLY, (I)[/url] and (II)[/url] Paul White[/url]
    Hidden RBAR: Triangular Joins[/url] / The "Numbers" or "Tally" Table: What it is and how it replaces a loop[/url] Jeff Moden[/url]
    [url

  • ashishkumarrai

    SSC-Addicted

    Points: 439

    Hi

    Thanks for the post, really useful. I am working on similar stuff. My problem is the value the above query is using is static. What will be the solution if the value is also a table.

    If the Variable above @AmountToAllocate is a table of values to be filled in this bucket. Any help is appreciated. I want to show all the records recursively till the bucket gets filled.

  • ChrisM@Work

    SSC Guru

    Points: 186043

    ashishkumarrai (9/6/2016)


    Hi

    Thanks for the post, really useful. I am working on similar stuff. My problem is the value the above query is using is static. What will be the solution if the value is also a table.

    If the Variable above @AmountToAllocate is a table of values to be filled in this bucket. Any help is appreciated. I want to show all the records recursively till the bucket gets filled.

    You've come along at a good time, quite a few folks have recently worked on similar problems.

    Before doing anything else, have a quick scan through this article[/url]. We'll need sample data scripts and a script to generate your expected result set from the sample data. The article shows you how to do this.

    Also, start a new thread - your scenario is different to the one covered by this thread.

    Cheers

    [font="Arial"]“Write the query the simplest way. If through testing it becomes clear that the performance is inadequate, consider alternative query forms.” - Gail Shaw[/font]


    For fast, accurate and documented assistance in answering your questions, please read this article[/url].
    Understanding and using APPLY, (I)[/url] and (II)[/url] Paul White[/url]
    Hidden RBAR: Triangular Joins[/url] / The "Numbers" or "Tally" Table: What it is and how it replaces a loop[/url] Jeff Moden[/url]
    [url

  • ashishkumarrai

    SSC-Addicted

    Points: 439

    Posted my problem with all the details and sample data over here. https://ask.sqlservercentral.com/questions/140089/sql-server-2008-cte-bucket-filling.html

  • ChrisM@Work

    SSC Guru

    Points: 186043

    This should be a step in the right direction:

    DROP TABLE #Buckets

    CREATE TABLE #Buckets (bucketID INT, FullCapacity INT, CurrentAmount INT);

    INSERT INTO #Buckets

    VALUES ( '1', 85, 0 ) ,

    ( '2', 80, 0 ) ,

    ( '3', 75, 0 ) ,

    ( '4', 70, 0 ) ,

    ( '5', 50, 0 ) ,

    ( '6', 40, 0 );

    DROP TABLE #Filler

    CREATE TABLE #Filler (FillerID INT, Filler INT);

    INSERT INTO #Filler

    VALUES ( '1', 90 ) ,

    ( '2', 40 ) ,

    ( '3', 70 ) ,

    ( '4', 50 ) ,

    ( '5', 40 ) ,

    ( '6', 30 ) ,

    ( '7', 35 );

    WITH ProcessedDebits AS (

    SELECT bucketID, FullCapacity, [from] = ([to] - FullCapacity), [to]

    FROM (SELECT *, [to] = SUM(FullCapacity) OVER (PARTITION BY 1 ORDER BY bucketID

    ROWS BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW) FROM #Buckets) d

    ),

    ProcessedCredits AS (

    SELECT FillerID, Filler, [from] = ([to] - Filler), [to]

    FROM (SELECT *, [to] = SUM(Filler) OVER (PARTITION BY 1 ORDER BY FillerID

    ROWS BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW) FROM #Filler) d

    )

    SELECT

    bucketID, FullCapacity,

    DebitBalance = CASE

    WHEN dr.[to] >= cr.[to] THEN (dr.[to] - cr.[to])

    WHEN dr.[to] < cr.[to] THEN 0

    ELSE dr.[to] - MAX(cr.[to]) OVER(PARTITION BY 1 ORDER BY dr.bucketID

    ROWS BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW)

    END,

    FillerID, Filler,

    CreditBalance = CASE

    WHEN cr.[to] >= dr.[to] THEN (cr.[to] - dr.[to])

    WHEN cr.[to] < dr.[to] THEN 0

    ELSE cr.[to] - MAX(dr.[to]) OVER(PARTITION BY 1 ORDER BY cr.FillerID

    ROWS BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW)

    END

    FROM ProcessedDebits dr

    FULL OUTER JOIN ProcessedCredits cr

    ON cr.[from] < dr.[to]

    AND cr.[to] > dr.[from]

    ORDER BY bucketID, FillerID

    OPTION (MAXDOP 1);

    [font="Arial"]“Write the query the simplest way. If through testing it becomes clear that the performance is inadequate, consider alternative query forms.” - Gail Shaw[/font]


    For fast, accurate and documented assistance in answering your questions, please read this article[/url].
    Understanding and using APPLY, (I)[/url] and (II)[/url] Paul White[/url]
    Hidden RBAR: Triangular Joins[/url] / The "Numbers" or "Tally" Table: What it is and how it replaces a loop[/url] Jeff Moden[/url]
    [url

  • J Livingston SQL

    SSC Guru

    Points: 51272

    ashishkumarrai (9/9/2016)


    Posted my problem with all the details and sample data over here. https://ask.sqlservercentral.com/questions/140089/sql-server-2008-cte-bucket-filling.html

    can you please provide your expected results from the sample data?

    edit >>>

    is this the result you are looking for?

    +---------------------------------------------+

    ¦ BucketId ¦ Fullcapacity ¦ RemainingCapacity ¦

    ¦----------+--------------+-------------------¦

    ¦ 1 ¦ 85 ¦ 0 ¦

    ¦----------+--------------+-------------------¦

    ¦ 2 ¦ 80 ¦ 0 ¦

    ¦----------+--------------+-------------------¦

    ¦ 3 ¦ 75 ¦ 0 ¦

    ¦----------+--------------+-------------------¦

    ¦ 4 ¦ 70 ¦ 0 ¦

    ¦----------+--------------+-------------------¦

    ¦ 5 ¦ 50 ¦ 5 ¦

    ¦----------+--------------+-------------------¦

    ¦ 6 ¦ 40 ¦ 40 ¦

    +---------------------------------------------+

    ________________________________________________________________
    you can lead a user to data....but you cannot make them think
    and remember....every day is a school day

  • Joe Celko

    SSCertifiable

    Points: 5553

    CREATE TABLE Buckets

    (bucket_nbr INTEGER NOT NULL PRIMARY KEY,

    bucket_size INTEGER NOT NULL

    CHECK (bucket_size > 0,

    bucket_content INTEGER NOT NULL

    CHECK (bucket_content BETWEEN 0 AND bucket_size)

    );

    INSERT INTO Buckets (bucket_size, bucket_content, bucket_nbr)

    (1, 10, 0), (2, 5, 0), (3, 10, 0), (4, 10, 0);

    There are actually several different ways of doing this. Using a "greedy algorithm", we fill the biggest buckets first. But you could just as easily start filling the smallest buckets.

    In general there is no perfect way of doing it. Google "martello toth bin packing" and look at all the free PDF files which you can download on the topic. Try playing with this query:

    SELECT bucket_nbr, bucket_size, bucket_content,

    SUM(bucket_content)

    OVER (ORDER BY bucket_size DESC

    ROWS BETWEEN UNBOUNDED PRECEDING AND CURENT ROW)

    AS greedy_running_total,

    SUM(bucket_size)

    ROWS BETWEEN UNBOUNDED PRECEDING AND CURENT ROW)

    AS capacity_running_total

    FROM Buckets;

    (1, 10, 10, NULL)

    (3, 10, 20, NULL)

    (4, 10, 30, NULL)

    (2, 5, 35, NULL)

    Without going into the code, you can see that your 21 liters will overflow bucket #1, then bucket #2, but not bucket #4. We never get to bucket #2, because we ran out of water. This means we need some logic (hint: it can be done with case expressions in the UPDATE statement) to classify each of the buckets as {'full', 'empty', 'partial'}

    (1, 10, 10, 10) -- full

    (3, 10, 20, 10) -- full

    (4, 10, 30, 1) -- partial, and needs math

    (2, 5, 35, 0) -- empty = 0

    In the body the procedure, it is probably a good idea to have a test for (SUM(bucket_size) >= @input_amount) so that you know your task is impossible due to lack of capacity.

    Books in Celko Series for Morgan-Kaufmann Publishing
    Analytics and OLAP in SQL
    Data and Databases: Concepts in Practice
    Data, Measurements and Standards in SQL
    SQL for Smarties
    SQL Programming Style
    SQL Puzzles and Answers
    Thinking in Sets
    Trees and Hierarchies in SQL

  • J Livingston SQL

    SSC Guru

    Points: 51272

    CELKO (9/10/2016)


    CREATE TABLE Buckets

    (bucket_nbr INTEGER NOT NULL PRIMARY KEY,

    bucket_size INTEGER NOT NULL

    CHECK (bucket_size > 0,

    bucket_content INTEGER NOT NULL

    CHECK (bucket_content BETWEEN 0 AND bucket_size)

    );

    INSERT INTO Buckets (bucket_size, bucket_content, bucket_nbr)

    (1, 10, 0), (2, 5, 0), (3, 10, 0), (4, 10, 0);

    There are actually several different ways of doing this. Using a "greedy algorithm", we fill the biggest buckets first. But you could just as easily start filling the smallest buckets.

    In general there is no perfect way of doing it. Google "martello toth bin packing" and look at all the free PDF files which you can download on the topic. Try playing with this query:

    SELECT bucket_nbr, bucket_size, bucket_content,

    SUM(bucket_content)

    OVER (ORDER BY bucket_size DESC

    ROWS BETWEEN UNBOUNDED PRECEDING AND CURENT ROW)

    AS greedy_running_total,

    SUM(bucket_size)

    ROWS BETWEEN UNBOUNDED PRECEDING AND CURENT ROW)

    AS capacity_running_total

    FROM Buckets;

    (1, 10, 10, NULL)

    (3, 10, 20, NULL)

    (4, 10, 30, NULL)

    (2, 5, 35, NULL)

    Without going into the code, you can see that your 21 liters will overflow bucket #1, then bucket #2, but not bucket #4. We never get to bucket #2, because we ran out of water. This means we need some logic (hint: it can be done with case expressions in the UPDATE statement) to classify each of the buckets as {'full', 'empty', 'partial'}

    (1, 10, 10, 10) -- full

    (3, 10, 20, 10) -- full

    (4, 10, 30, 1) -- partial, and needs math

    (2, 5, 35, 0) -- empty = 0

    In the body the procedure, it is probably a good idea to have a test for (SUM(bucket_size) >= @input_amount) so that you know your task is impossible due to lack of capacity.

    bit confused on this....

    there are two tables....(Buckets/Filler)...which you only include "Buckets"

    your code that you provide doesnt parse and throws errors...?

    can you please review and advise....will be appreciated

    edit>>>

    for clarification I refer to the latest question on this post....probably better if it was a new thread

    http://www.sqlservercentral.com/Forums/FindPost1816384.aspx

    Posted my problem with all the details and sample data over here. https://ask.sqlservercentral.com/questions/140089/sql-server-2008-cte-bucket-filling.html

    ________________________________________________________________
    you can lead a user to data....but you cannot make them think
    and remember....every day is a school day

Viewing 15 posts - 1 through 15 (of 26 total)

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