Query challenge: Creating even sized buckets, based on a measure not row count I'll describe the problem in terms of loading a fixed number of trucks with orders, as evenly as possible.

Inputs:

@TruckCount - the number of empty trucks to fill


A set:

OrderId, 
OrderDetailId, 
OrderDetailSize, 
TruckId (initially null)


Orders are composed of one or more OrderDetails.

The challenge here is to assign a TruckId to each record.

A single order cannot be split across trucks.

Trucks should be as evenly* loaded as possible, measured by sum(OrderDetailSize).

* Evenly: The smallest achievable delta between the least loaded truck and most loaded truck. By this definition, 1,2,3 is more evenly distributed than 1,1,4. If it helps, pretend you are stats algorithm, creating even height histograms.

There is no consideration for maximum truck load. These are magic elastic trucks. The number of trucks however is fixed.

There’s an obviously solution which is iterative - round robin allocate orders.

But can it be done as set based logic?

My main interest is for SQL Server 2014 or later. But set based solutions for other platforms could also be interesting.

This feels like Itzik Ben-Gan territory :)

My real world application is distributing a processing workload into a number of buckets to match the number of logical CPUs. Hence each bucket has no maximum size. Stats updates, specifically. I just thought it was more fun to abstract the problem into trucks as a way of framing the challenge.

CREATE TABLE #OrderDetail (
OrderId int NOT NULL,
OrderDetailId int NOT NULL PRIMARY KEY,
OrderDetailSize tinyint NOT NULL,
TruckId tinyint NULL)

-- Sample Data

INSERT #OrderDetail (OrderId, OrderDetailId, OrderDetailSize)
VALUES
(1  ,100    ,75 ),
(2  ,101    ,5  ),
(2  ,102    ,5  ),
(2  ,103    ,5  ),
(2  ,104    ,5  ),
(2  ,105    ,5  ),
(3  ,106    ,100),
(4  ,107    ,1  ),
(5  ,108    ,11 ),
(6  ,109    ,21 ),
(7  ,110    ,49 ),
(8  ,111    ,25 ),
(8  ,112    ,25 ),
(9  ,113    ,40 ),
(10 ,114    ,49 ),
(11 ,115    ,10 ),
(11 ,116    ,10 ),
(12 ,117    ,15 ),
(13 ,118    ,18 ),
(14 ,119    ,26 )




--&gt; YOUR SOLUTION HERE

-- After assigning Trucks, Measure delta between most and least loaded trucks.
-- Zero is perfect score, however the challenge is a set based solution that will scale, and produce good results, rather
-- than iterative solution that will produce perfect results by exploring every possibility.

SELECT max(TruckOrderDetailSize) - MIN(TruckOrderDetailSize) AS TruckMinMaxDelta
FROM 
(SELECT SUM(OrderDetailSize) AS TruckOrderDetailSize FROM #OrderDetail GROUP BY TruckId) AS Truck


DROP TABLE #OrderDetail
My first thought was 

select
    &lt;best solution&gt;
from
    &lt;all possible combinations&gt;


The "best solution" part is defined in the question - the smallest difference between the most loaded and least loaded trucks. The other bit - all combinations - caused me pause for thought.

Consider a situation where we have three orders A, B and C and three trucks. The possibilities are

Truck 1 Truck 2 Truck 3
------- ------- -------
A       B       C
A       C       B
B       A       C
B       C       A
C       A       B
C       B       A
AB      C       -
AB      -       C
C       AB      -
-       AB      C
C       -       AB
-       C       AB
AC      B       -
AC      -       B
B       AC      -
-       AC      B
B       -       AC
-       B       AC
BC      A       -
BC      -       A
A       BC      -
-       BC      A
A       -       BC
-       A       BC
ABC     -       -
-       ABC     -
-       -       ABC

Table A: all permutations.


Many of these are symmetric. The first six rows, for example, differ only in which truck each order is placed. Since the trucks are fungible these arrangemets will produce the same outcome. I shall ignore this for now.

There are known queries for producing permutations and combinations. However, these will produce arrangements within a single bucket. For this problem I need arrangements across multiple buckets.

Looking at the output from the standard "all combinations" query

;with Numbers as
(
    select n = 1
    union
    select 2
    union
    select 3
)
select
    a.n,
    b.n,
    c.n
from Numbers as a
cross join Numbers as b
cross join Numbers as c
order by 1, 2, 3;


  n   n   n
--- --- ---
  1   1   1
  1   1   2
  1   1   3
  1   2   1
 &lt;snip&gt;
  3   2   3
  3   3   1
  3   3   2
  3   3   3

Table B: cross join of three values.


I noted the results formed the same pattern as Table A. By making the congnitive leap of considering each column to be an Order1, the values to say which truck will hold that Order, and a row to be an arrangement of Orders within trucks. The query then becomes

select
    Arrangement             = ROW_NUMBER() over(order by (select null)),
    First_order_goes_in     = a.TruckNumber,
    Second_order_goes_in    = b.TruckNumber,
    Third_order_goes_in     = c.TruckNumber
from Trucks a   -- aka Numbers in Table B
cross join Trucks b
cross join Trucks c

Arrangement First_order_goes_in Second_order_goes_in Third_order_goes_in
----------- ------------------- -------------------- -------------------
          1                   1                    1                   1
          2                   1                    1                   2
          3                   1                    1                   3
          4                   1                    2                   1
  &lt;snip&gt;

Query C: Orders in trucks.


Expaning this to cover the fourteen Orders in the example data, and simplifying the names we get this:

;with Trucks as
(
    select * 
    from (values (1), (2), (3)) as T(TruckNumber)
)
select
    arrangement = ROW_NUMBER() over(order by (select null)),
    First       = a.TruckNumber,
    Second      = b.TruckNumber,
    Third       = c.TruckNumber,
    Fourth      = d.TruckNumber,
    Fifth       = e.TruckNumber,
    Sixth       = f.TruckNumber,
    Seventh     = g.TruckNumber,
    Eigth       = h.TruckNumber,
    Ninth       = i.TruckNumber,
    Tenth       = j.TruckNumber,
    Eleventh    = k.TruckNumber,
    Twelth      = l.TruckNumber,
    Thirteenth  = m.TruckNumber,
    Fourteenth  = n.TruckNumber
into #Arrangements
from Trucks a
cross join Trucks b
cross join Trucks c
cross join Trucks d
cross join Trucks e
cross join Trucks f
cross join Trucks g
cross join Trucks h
cross join Trucks i
cross join Trucks j
cross join Trucks k
cross join Trucks l
cross join Trucks m
cross join Trucks n;

Query D: Orders spread over trucks.


I choose to hold the intermediate results in temporary tables for convenience.

Subsequent steps will be much easier if the data is first UNPIVOTED.

select
    Arrangement,
    TruckNumber,
    ItemNumber  = case NewColumn
                    when 'First'        then 1
                    when 'Second'       then 2
                    when 'Third'        then 3
                    when 'Fourth'       then 4
                    when 'Fifth'        then 5
                    when 'Sixth'        then 6
                    when 'Seventh'      then 7
                    when 'Eigth'        then 8
                    when 'Ninth'        then 9
                    when 'Tenth'        then 10
                    when 'Eleventh'     then 11
                    when 'Twelth'       then 12
                    when 'Thirteenth'   then 13
                    when 'Fourteenth'   then 14
                    else -1
                end
into #FilledTrucks
from #Arrangements
unpivot
(
    TruckNumber
    for NewColumn IN 
    (
        First,
        Second,
        Third,
        Fourth,
        Fifth,
        Sixth,
        Seventh,
        Eigth,
        Ninth,
        Tenth,
        Eleventh,
        Twelth,
        Thirteenth,
        Fourteenth
    )
) as q;

Query E: Filled trucks, unpivoted.


Weights can be introduced by joining to the Orders table.

select
    ft.arrangement,
    ft.TruckNumber,
    TruckWeight = sum(i.Size)
into #TruckWeights
from #FilledTrucks as ft
inner join #Order as i
    on i.OrderId = ft.ItemNumber
group by
    ft.arrangement,
    ft.TruckNumber;

Query F: truck weights


The question can now be answered by finding the arrangement(s) which have the smallest difference between most-loaded and least-loaded trucks

select
    Arrangement,
    LightestTruck   = MIN(TruckWeight),
    HeaviestTruck   = MAX(TruckWeight),
    Delta           = MAX(TruckWeight) - MIN(TruckWeight)
from #TruckWeights
group by
    arrangement
order by
    4 ASC;

Query G: most balanced arrangements


Discussion

There are a great many problems with this. First it is a brute-force algorithm. The number of rows in the working tables is exponential in the number of trucks and orders. The number of rows in #Arrangements is (number of trucks)^(number of orders). This will not scale well.

Second is that the SQL queries have the number of Orders embedded in them. The only way around this is to use dynamic SQL, which has problems of its own. If the number of orders is in the thousands there may come a time when the generated SQL becomes too long.

Third is the redundancy in the arrangements. This bloats the intermediate tables increasing runtime hugely.

Fourth, many rows in #Arrangements leave one or more trucks empty. This cannot possibly be the optimum configuration. It would be easy to filter out these rows upon creation. I've chosen not to do so to keep the code simpler and focused.

On the up side this handles negative weights, should your enterprise ever start shipping filled helium baloons!

Thoughts

If there were a way to populate #FilledTrucks directly from the list of trucks and Orders I think the worst of these concerns would be managable. Sadly my immagination stumbled on that hurdle. My hope is some future contributor may be able to supply that which eluded me.



1 You say all items for an order must be on the same truck. This means the atom of assignment is the Order, not the OrderDetail. I have generated these from your test data thus:

select
    OrderId,
    Size = sum(OrderDetailSize)
into #Order
from #OrderDetail
group by OrderId;


It makes no difference, though, whether we label the items in question 'Order' or 'OrderDetail', the solution remains the same.