# How can I write windowing query which sums a column to create discrete buckets?

I have a table which includes a column of decimal values, such as this:

``````id value size
-- ----- ----
1   100  .02
2    99  .38
3    98  .13
4    97  .35
5    96  .15
6    95  .57
7    94  .25
8    93  .15
``````

What I need to accomplish is a little difficult to describe, so please bear with me. What I am trying to do is create an aggregate value of the `size` column which increments by 1 each time the preceding rows sum up to 1, when in descending order according to `value`. The result would look something like this:

``````id value size bucket
-- ----- ---- ------
1   100  .02      1
2    99  .38      1
3    98  .13      1
4    97  .35      1
5    96  .15      2
6    95  .57      2
7    94  .25      2
8    93  .15      3
``````

My naive first attempt was to keep a running `SUM` and then `CEILING` that value, however it doesn't handle the case where some records' `size` end up contributing to the total of two separate buckets. The below example might clarify this:

``````id value size crude_sum crude_bucket distinct_sum bucket
-- ----- ---- --------- ------------ ------------ ------
1   100  .02       .02            1          .02      1
2    99  .38       .40            1          .40      1
3    98  .13       .53            1          .53      1
4    97  .35       .88            1          .88      1
5    96  .15      1.03            2          .15      2
6    95  .57      1.60            2          .72      2
7    94  .25      1.85            2          .97      2
8    93  .15      2.00            2          .15      3
``````

As you can see, if I were to simply use `CEILING` on `crude_sum` record #8 would be assigned to bucket 2. This is caused by the `size` of records #5 and #8 being split across two buckets. Instead, the ideal solution is to reset the sum each time it reaches 1, which then increments the `bucket` column and begins a new `SUM` operation starting at the `size` value of the current record. Because the order of the records is important to this operation, I've included the `value` column, which is intended to be sorted in descending order.

My initial attempts have involved making multiple passes over the data, once to perform the `SUM` operation, once more to `CEILING` that, etc. Here is an example of what I did to create the `crude_sum` column:

``````SELECT
id,
value,
size,
(SELECT TOP 1 SUM(size) FROM table t2 WHERE t2.value<=t1.value) as crude_sum
FROM
table t1
``````

Which was used in an `UPDATE` operation to insert the value into a table to work with later.

Edit: I'd like to take another stab at explaining this, so here goes. Imagine each record is a physical item. That item has a value associated with it, and a physical size less than one. I have a series of buckets with a volume capacity of exactly 1, and I need to determine how many of these buckets I will need and which bucket each item goes in according to the value of the item, sorted from highest to lowest.

A physical item cannot exist in two places at once, so it must be in one bucket or the other. This is why I can't do a running total + `CEILING` solution, because that would allow records to contribute their size to two buckets.

• You should add your SQL to make it clear what your initial attempt included. Jun 24, 2013 at 19:52
• Are you going to be aggregating data according to the bucket you're computing, or is the bucket number the final answer you're looking for? Jun 24, 2013 at 19:58
• Ack. I'd probably go with a client-side app since that will support better streaming-in of records as opposed to a cursor loop which fetches one row at a time. I think as long as all the updates are done in batches, it should perform reasonably well. Jun 24, 2013 at 20:39
• As the others have already mentioned, the requirement of bucketing on `distinct_count` complicates things. Aaron Bertrand has a great summary of your options on SQL Server for this kind of windowing work. I have used the "quirky update" method to calculate `distinct_sum`, which you can see here on SQL Fiddle, but this is unreliable. Jun 25, 2013 at 17:26
• @JonSeigel We should note that problem of placing X items in minimal number of buckets cannot be efficiently solved using a row by row algorithm of SQL language. Eg items of size 0.7;0.8;0.3 will need 2 buckets, but if sorted by id they'll need 3 buckets. Jun 25, 2013 at 19:51

I am not sure what type of performance you are looking for, but if CLR or external app is not an option, a cursor is all that is left. On my aged laptop I get through 1,000,000 rows in about 100 seconds using the following solution. The nice thing about it is that it scales linearly, so I would be looking at a little about 20 minutes to run through the entire thing. With a decent server you will be faster, but not an order of magnitude, so it would still take several minutes to complete this. If this is a one off process, you probably can afford the slowness. If you need to run this as a report or similar regularly, you might want to store the values in the same table un update them as new rows get added, e.g. in a trigger.

Anyway, here is the code:

``````IF OBJECT_ID('dbo.MyTable') IS NOT NULL DROP TABLE dbo.MyTable;

CREATE TABLE dbo.MyTable(
Id INT IDENTITY(1,1) PRIMARY KEY CLUSTERED,
v NUMERIC(5,3) DEFAULT ABS(CHECKSUM(NEWID())%100)/100.0
);

MERGE dbo.MyTable T
USING (SELECT TOP(1000000) 1 X FROM sys.system_internals_partition_columns A,sys.system_internals_partition_columns B,sys.system_internals_partition_columns C,sys.system_internals_partition_columns D)X
ON(1=0)
WHEN NOT MATCHED THEN
INSERT DEFAULT VALUES;

--SELECT * FROM dbo.MyTable

DECLARE @st DATETIME2 = SYSUTCDATETIME();
DECLARE cur CURSOR FAST_FORWARD FOR
SELECT Id,v FROM dbo.MyTable
ORDER BY Id;

DECLARE @id INT;
DECLARE @v NUMERIC(5,3);
DECLARE @running_total NUMERIC(6,3) = 0;
DECLARE @bucket INT = 1;

CREATE TABLE #t(
id INT PRIMARY KEY CLUSTERED,
v NUMERIC(5,3),
bucket INT,
running_total NUMERIC(6,3)
);

OPEN cur;
WHILE(1=1)
BEGIN
FETCH NEXT FROM cur INTO @id,@v;
IF(@@FETCH_STATUS <> 0) BREAK;
IF(@running_total + @v > 1)
BEGIN
SET @running_total = 0;
SET @bucket += 1;
END;
SET @running_total += @v;
INSERT INTO #t(id,v,bucket,running_total)
VALUES(@id,@v,@bucket, @running_total);
END;
CLOSE cur;
DEALLOCATE cur;
SELECT DATEDIFF(SECOND,@st,SYSUTCDATETIME());
SELECT * FROM #t;

GO
DROP TABLE #t;
``````

It drops and recreates the table MyTable, fills it with 1000000 rows and then goes to work.

The cursor copies each row into a temp table while running the calculations. At the end the select returns the calculated results. You might be a little faster if you don't copy the data around but do an in-place update instead.

If you have an option to upgrade to SQL 2012 you can look at the new window-spool supported moving window aggregates, that should give you better performance.

On a side note, if you have an assembly installed with permission_set=safe, you can do more bad stuff to a server with standard T-SQL than with the assembly, so I would keep working on removing that barrier - You have a good use case here where CLR really would help you.

• I accepted this one due to how easy it was to implement, and how easily I can change and debug it later as the need arises. @NickChammas's answer is also correct and probably runs more efficiently, so I guess it's a matter of preference for anyone else coming up against a similar issue. Jun 25, 2013 at 21:08

Absent the new windowing functions in SQL Server 2012, complex windowing can be accomplished with the use of recursive CTEs. I wonder how well this will perform against millions of rows.

The following solution covers all the cases you described. You can see it in action here on SQL Fiddle.

``````-- schema setup
CREATE TABLE raw_data (
id    INT PRIMARY KEY
, value INT NOT NULL
, size  DECIMAL(8,2) NOT NULL
);

INSERT INTO raw_data
(id, value, size)
VALUES
( 1,   100,  .02) -- new bucket here
, ( 2,    99,  .99) -- and here
, ( 3,    98,  .99) -- and here
, ( 4,    97,  .03)
, ( 5,    97,  .04)
, ( 6,    97,  .05)
, ( 7,    97,  .40)
, ( 8,    96,  .70) -- and here
;
``````

Now take a deep breath. There are two key CTEs here, each preceded by a brief comment. The rest are just "cleanup" CTEs, for example, to pull the right rows after we've ranked them.

``````-- calculate the distinct sizes recursively
WITH distinct_size AS (
SELECT
id
, size
, 0 as level
FROM raw_data

UNION ALL

SELECT
base.id
, CAST(base.size + tower.size AS DECIMAL(8,2)) AS distinct_size
, tower.level + 1 as level
FROM
raw_data AS base
INNER JOIN  distinct_size AS tower
ON base.id = tower.id + 1
WHERE base.size + tower.size <= 1
)
, ranked_sum AS (
SELECT
id
, size AS distinct_size
, level
, RANK() OVER (PARTITION BY id ORDER BY level DESC) as rank
FROM distinct_size
)
, top_level_sum AS (
SELECT
id
, distinct_size
, level
, rank
FROM ranked_sum
WHERE rank = 1
)
-- every level reset to 0 means we started a new bucket
, bucket AS (
SELECT
base.id
, COUNT(base.id) AS bucket
FROM
top_level_sum base
INNER JOIN top_level_sum tower
ON base.id >= tower.id
WHERE tower.level = 0
GROUP BY base.id
)
-- join the bucket info back to the original data set
SELECT
rd.id
, rd.value
, rd.size
, tls.distinct_size
, b.bucket
FROM
raw_data rd
INNER JOIN top_level_sum tls
ON rd.id = tls.id
INNER JOIN bucket   b
ON rd.id = b.id
ORDER BY
rd.id
;
``````

This solution assumes that `id` is a gapless sequence. If not, you will need to generate your own gapless sequence by adding an additional CTE at the beginning that numbers the rows with `ROW_NUMBER()` according to the desired order (e.g. `ROW_NUMBER() OVER (ORDER BY value DESC)`).

Fankly, this is quite verbose.

• This solution does not seem to address the case where a row might contribute its size to multiple buckets. A rolling sum is easy enough, but I need that sum to reset each time it reaches 1. See the last example table in my question and compare `crude_sum` with `distinct_sum` and their associated `bucket` columns to see what I mean. Jun 25, 2013 at 15:48
• @Zikes - I have addressed this case with my updated solution. Jun 25, 2013 at 18:37
• That looks like it should work now. I'll work on integrating it into my database to test it out. Jun 25, 2013 at 20:36
• @Zikes - Just curious, how do the various solutions posted here perform against your large data set? I'm guessing Andriy's is the fastest. Jun 26, 2013 at 5:34

This feels like a silly solution, and it probably won't scale well, so test carefully if you use it. Since the main problem comes from the "space" left in the bucket, I first had to create a filler record to union into the data.

``````with bar as (
select
id
,value
,size
from foo
union all
select
f.id
,value = null
,size = 1 - sum(f2.size) % 1
from foo f
inner join foo f2
on f2.id < f.id
group by f.id
,f.value
,f.size
having cast(sum(f2.size) as int) <> cast(sum(f2.size) + f.size as int)
)
select
f.id
,f.value
,f.size
,bucket = cast(sum(b.size) as int) + 1
from foo f
inner join bar b
on b.id <= f.id
group by f.id
,f.value
,f.size
``````

• +1 I think this has potential if appropriate indexes are there. Jun 24, 2013 at 21:02

The following is another recursive CTE solution, although I'd say it's more straightforward than @Nick's suggestion. It is actually closer to @Sebastian's cursor, only I used running differences instead of running totals. (At first I even thought that @Nick's answer was going to be along the lines of what I am suggesting here, and it is after learning that his was in fact a very different query that I decided to offer mine.)

``````WITH rec AS (
SELECT TOP 1
id,
value,
size,
bucket        = 1,
room_left     = CAST(1.0 - size AS decimal(5,2))
FROM atable
ORDER BY value DESC
UNION ALL
SELECT
t.id,
t.value,
t.size,
bucket        = r.bucket + x.is_new_bucket,
room_left     = CAST(CASE x.is_new_bucket WHEN 1 THEN 1.0 ELSE r.room_left END - t.size AS decimal(5,2))
FROM atable t
INNER JOIN rec r ON r.value = t.value + 1
CROSS APPLY (
SELECT CAST(CASE WHEN t.size > r.room_left THEN 1 ELSE 0 END AS bit)
) x (is_new_bucket)
)
SELECT
id,
value,
size,
bucket
FROM rec
ORDER BY value DESC
;
``````

Note: this query assumes that the `value` column consists of unique values with no gaps. If that is not the case, you'll need to introduce a calculated ranking column based on the descending order of `value` and use it in the recursive CTE instead of `value` to join the recursive part with the anchor.

A SQL Fiddle demo for this query can be found here.

• This is much shorter than what I wrote. Nice work. Is there any reason you count down the room left in the bucket rather than count up? Jun 26, 2013 at 5:55
• Yes, there is, not sure if it makes much sense for the version I ended up posting here, though. Anyway, the reason was that it seemed easier/more natural to compare a single value with a single value (`size` with `room_left`) as opposed to comparing a single value with an expression (`1` with `running_size` + `size`). I didn't use an `is_new_bucket` flag at first but several `CASE WHEN t.size > r.room_left ...` instead ("several" because I also was calculating (and returning) the total size, but then thought against it for the sake of simplicity), so I thought it'd be more elegant that way. Jun 26, 2013 at 6:43