Select sum of a column without cursor

Question

I have data as:

ID   LENGTH_IN_CM
1        1.0
2        1.0
3        9.0
4        5.0
5        15.0
6        3.0
7        5.0

I know that a page is 20cm long and would like to calculate which pages each item will be on.

So for example items with id 1, 2, 3, and 4 will be on the first page (1.0 + 1.0 + 9.0 + 5.0 < 20.0) but 5 and 6 will be on the second and 7 on the third.

Is it possible to calculate the page numbers without using a cursor?

Answer 1

Okay, I did this more for the challenge than because I necessarily think it's a good idea. I'm inclined to believe Aaron that a cursor may be more appropriate. Anyhow:

declare @Items table (ID int not null,LENGTH_IN_CM decimal(5,1) not null)
insert into @Items(ID,LENGTH_IN_CM) values
(1,1.0),
(2,1.0),
(3,9.0),
(4,5.0),
(5,15.0),
(6,3.0),
(7,6.0)

;With PossiblePages as (
    select ID as MinID,ID as MaxID,LENGTH_IN_CM as TotalLength from @Items
    union all
    select MinID,MaxID + 1,CONVERT(decimal(5,1),TotalLength + LENGTH_IN_CM)
    from
        PossiblePages pp
            inner join
        @Items it
            on
                pp.MaxID + 1 = it.ID
    where
        TotalLength + LENGTH_IN_CM <= 20.0
), LongPages as (
    select MinID,MAX(MaxID) as MaxID,MAX(TotalLength) as TotalLength from PossiblePages group by MinID
), FinalPages as (
    select MinID,MaxID,TotalLength from LongPages where MinID = 1
    union all
    select lp.MinID,lp.MaxID,lp.TotalLength
    from
        LongPages lp
            inner join
        FinalPages fp
            on
                lp.MinID = fp.MaxID + 1
), PageNumbers as (
    select MinID,MaxID,ROW_NUMBER() OVER (ORDER BY MinID) as PageNo
    from FinalPages
)
select * from PageNumbers

Result:

MinID       MaxID       PageNo
----------- ----------- --------------------
1           4           1
5           6           2
7           7           3

Which should be easy enough to join back to the original table, if you want to assign a page number to each row.

PossiblePages calculates every possible page - for every row, it acts as if that row is the first one on that page, and then works out how many additional rows can be appended to that, and the total length that that range of rows represents (there may be cleaner ways to calculate this expression, not sure at the moment).

LongPages then finds the longest value that PossiblePages calculated, for each starting row number.

Finally, FinalPages starts with the first page (that must, logically, be the one started with ID 1 - you can always introduce another calculation if you're not guaranteed to start at 1, and need to find the earliest). Then, the next page is the one that starts from the row ID one higher than the previous row.

You don't need PageNumbers, but as I said, I was thinking of joining back to the original table.

---

And as predicted by the commenters, I don't think this is going to perform well - just on the sample, I'm seeing at least 4 table scans to compute this.

---

Bonus insanity. This one only scans the table 3 times:

;With PageRows as (
    select ID as MinID,ID as MaxID,LENGTH_IN_CM as TotalLength from @Items where ID=1
    union all
    select MinID,MaxID + 1,CONVERT(decimal(5,1),TotalLength + LENGTH_IN_CM)
    from
        PageRows pr
            inner join
        @Items ir
            on
                pr.MaxID = ir.ID-1
    where
        TotalLength + LENGTH_IN_CM <= 20.0
    union all
    select ir.ID as MinID,ir.ID as MaxID,ir.LENGTH_IN_CM as TotalLength
    from
        PageRows pr
            inner join
        @Items ir
            on
                pr.MaxID = ir.ID-1
    where
        TotalLength + LENGTH_IN_CM > 20.0
), PageNumbers as (
    select MinID,MAX(MaxID) as MaxID,ROW_NUMBER() OVER (ORDER BY MinID) as PageNo
    from PageRows
    group by MinID
)
select * from PageNumbers