In our prior story about allocating people with the power of window aggregation, we saw our valiant hero and heroine trying to sort people into elevators to ensure that each elevator ride was not over capacity. All was good in the world until someone named Frank came along and spoiled the party. Frank rightfully pointed out that our algorithm was flawed because should Charlie double his weight, then we could have one elevator ride over capacity. We have a plan.

What was wrong with our first try? Well we failed to realize that while the number of rides you need at each increment of weight has to be at least the ceiling of the sum divided by the capacity of the car, it can exceed that number. This approach we think works fine if you are simply counting people. If we had normally weighted people instead of some dwarfs and giants that may work fine. So if we wanted to fit at most 5 people per car we would do this. Note we also changed our window to something that is a bit shorter but equivalent in meaning.

To test this idea out lets recreate our table of characters (Charlie being a little fatter now). We want at most 5 people per car run.

CREATE TABLE passengers(passenger_name varchar(20) PRIMARY KEY, weight_kg integer);
INSERT INTO passengers(passenger_name, weight_kg)
VALUES ('Johnny', 60),
		('Jimmy', 120),
		('Jenny', 50),
		('Namy', 20),
		('Grendel', 500),
		('Charlie', 400),
		('Gongadin', 400),
		('Tin Tin', 10),
		('Thumb Twins', 10),
		('Titan', 600),
		('Titania', 550),
		('Titan''s Groupie', 55) ;

SELECT carriage,COUNT(passenger_name) As cnt_pass,
	array_agg(passenger_name) As passengers
FROM (SELECT passenger_name, weight_kg,
  ceiling(COUNT(passenger_name)
	OVER(ROWS UNBOUNDED PRECEDING)/5.0) As carriage
FROM passengers) As congregation
GROUP BY carriage
ORDER BY carriage;

The result looks like

  carriage | cnt_pass |                    passengers
----------+----------+--------------------------------------------------
		1 |        5 | {Johnny,Jimmy,Jenny,Namy,Grendel}
		2 |        5 | {Charlie,Gongadin,"Tin Tin","Thumb Twins",Titan}
		3 |        2 | {Titania,"Titan's Groupie"}

Of course this is not the problem we were trying to solve. We want to ensure that our car weights are at most 750 kg with giants in mind. So what to do. Sadly the power of window aggregates in PostgreSQL appears to fail us here but we can write a recursive query AKA (Recursive common table expression (CTE) with PostgreSQL 8.4. Sorry it looks kind of convoluted. The translation to this into spoken tongue is actually closer to what we said we were doing in the first place. If anyone can come up with a simpler way of achieving this, we'd like to know. I think there is a way to do this with a self-join, but haven't thought that far into it.

WITH RECURSIVE p1 As
(SELECT 1 As carriage, passenger_name, weight_kg, weight_kg As car_weight
FROM passengers
	ORDER BY passenger_name LIMIT 1
),
congregation AS
(
	SELECT carriage, passenger_name, weight_kg, car_weight
FROM  p1
UNION ALL
SELECT np.carriage, np.passenger_name, np.weight_kg,  np.car_weight
 FROM
(SELECT CASE WHEN c.car_weight + p2.weight_kg <= 750
			THEN c.carriage ELSE c.carriage + 1 END As carriage,
	p2.passenger_name, p2.weight_kg,
		CASE WHEN c.car_weight + p2.weight_kg <= 750
			THEN c.car_weight + p2.weight_kg
				ELSE p2.weight_kg END As car_weight
FROM passengers As p2 INNER JOIN
	(SELECT carriage, passenger_name, weight_kg, car_weight
		FROM congregation ORDER BY passenger_name DESC LIMIT 1)
			As c ON (p2.passenger_name > c.passenger_name)
ORDER BY p2.passenger_name LIMIT 1) As np
)
SELECT carriage, COUNT(passenger_name) As cnt_pass,
	array_agg(passenger_name) As passengers, SUM(weight_kg) As car_kg
 FROM congregation
GROUP BY carriage;

 Result
carriage | cnt_pass |                    passengers                     | car_kg
----------+----------+---------------------------------------------------+------
		1 |        1 | {Charlie}                                         |    400
		2 |        1 | {Gongadin}                                        |    400
		3 |        5 | {Grendel,Jenny,Jimmy,Johnny,Namy}                 |    750
		4 |        4 | {"Thumb Twins","Tin Tin",Titan,"Titan's Groupie"} |    675
		5 |        1 | {Titania}                                         |    550