Part 1  |  Part 2

The first article in this series started with a very simple inventory of one kind of item, to which you add stock once a day. It gave a few queries by which you can assign a value to the Widget inventory using various methods (average cost per unit, replacement costs, FIFO and LIFO). The first two methods were very simple to program, but FIFO (First In, First Out) and LIFO (Last In, First Out) required a bit more work and some VIEWs.

Here is the DDL for the table:

CREATE TABLE WidgetInventory
(bin_nbr INTEGER NOT NULL PRIMARY KEY,
 purchase_date DATETIME DEFAULT CURRENT_TIMESTAMP NOT NULL,
 qty_on_hand INTEGER NOT NULL
   CHECK (qty_on_hand >= 0),
 unit_price DECIMAL (12,4) NOT NULL);

with the following data:

 WidgetInventory
 bin_nbr purchase_date qty_on_hand unit_price
 ============================================
  1       '2005-08-01'   15         10.00
  2       '2005-08-02'   25         12.00
  3       '2005-08-03'   40         13.00
  4       '2005-08-04'   35         12.00
  5       '2005-08-05'   45         10.00 

What we did not do in part 1 was to actually update the inventory when the Widgets were shipped out. Let’s build another view that will make life easier.

CREATE VIEW StockLevels (purchase_date, previous_qty, current_qty)
AS
SELECT W1.purchase_date, 
       SUM(CASE WHEN W2.purchase_date < W1.purchase_date 
                THEN W2.qty_on_hand ELSE 0 END),
       SUM(CASE WHEN W2.purchase_date <= W1.purchase_date 
                THEN W2.qty_on_hand ELSE 0 END) 
  FROM WidgetInventory AS W1,
       WidgetInventory AS W2
 WHERE W2.purchase_date <= W1.purchase_date
 GROUP BY W1.purchase_date, W1.unit_price; 

StockLevels 
purchase_date previous_qty current_qty
======================================
'2005-08-01'       0    15
'2005-08-02'      15    40
'2005-08-03'      40    80
'2005-08-04'      80   115
'2005-08-05'     115   160 

Using CASE expressions will save you a self-join.

CREATE PROCEDURE RemoveQty (IN my_order_qty INTEGER)
LANGUAGE SQL
BEGIN 
IF my_order_qty > 0
THEN 
UPDATE WidgetInventory
  SET qty_on_hand 
      = CASE
        WHEN my_order_qty 
             >= (SELECT current_qty 
                   FROM StockLevels AS L 
                  WHERE L.purchase_date 
                        = WidgetInventory.purchase_date)
        THEN 0
        WHEN my_order_qty 
             < (SELECT previous_qty 
                  FROM StockLevels AS L 
                 WHERE L.purchase_date 
                       = WidgetInventory.purchase_date)
        THEN WidgetInventory.qty_on_hand 
        ELSE (SELECT current_qty 
                FROM StockLevels AS L 
               WHERE L.purchase_date = WidgetInventory.purchase_date)
              - my_order_qty END;
END IF;

-- remove empty bins
DELETE FROM WidgetInventory 
 WHERE qty_on_hand = 0;
END;

Another inventory problem is how to fill an order with the smallest or greatest number of bins. This assumes that the bins are not in order, so you are free to fill the order as you wish. Using the fewest bins would make less work for the order pickers. Using the greatest number of bins would clean out more storage in the warehouse.

For example, with this data, you could fill an order for 80 widgets by shipping out bins (1, 2, 3) or bins (4, 5). These bins happen to be in date and bin number order in the sample data, but that is not required.

Mathematicians call it (logically enough) a bin-packing problem, and it belongs to the NP-complete family of problems. This kind of problem is too hard to solve for the general case because the work requires trying all the combinations, and this increases too fast for a computer to do it. 

However, there are “greedy algorithms” that are often nearly optimal. The idea is to begin by taking the “biggest bite” you can until you have met or passed your goal. In procedural languages, you can back-track when you go over the target amount and try to find an exact match or apply a rule that dictates from which bin to take a partial pick.

This is not easy in SQL, because it is a declarative, set-oriented language. A procedural language can stop when it has a solution that is “good enough,” while an SQL query tends to find all of the correct answers no matter how long it takes. If you can put a limit on the number of bins you are willing to visit, you can fake an array in a table:

CREATE TABLE Picklists
(order_nbr INTEGER NOT NULL PRIMARY KEY,
 goal_qty INTEGER NOT NULL
   CHECK (goal_qty > 0),
 bin_nbr_1 INTEGER NOT NULL UNIQUE,
 qty_on_hand_1 INTEGER DEFAULT 0 NOT NULL
  CHECK (qty_on_hand_1 >= 0),
 bin_nbr_2 INTEGER NOT NULL UNIQUE,
 qty_on_hand_2 INTEGER DEFAULT 0 NOT NULL
  CHECK (qty_on_hand_2 >= 0),
 bin_nbr_3 INTEGER NOT NULL UNIQUE, 
 qty_on_hand_3 INTEGER DEFAULT 0 NOT NULL
  CHECK (qty_on_hand_3 >= 0),
 CONSTRAINT not_over_goal
  CHECK (qty_on_hand_1 + qty_on_hand_2 + qty_on_hand_3
          <= goal_qty)
CONSTRAINT bins_sorted
  CHECK (qty_on_hand_1 >= qty_on_hand_2
         AND qty_on_hand_2 >= qty_on_hand_3));

Now you can start stuffing bins into the table. This query will give you the ways to fill or almost fill an order with three or fewer bins. The first trick is to load some empty dummy bins into the table. If you want at most (n) picks, then add (n-1) dummy bins:

INSERT INTO WidgetInventory VALUES (-1, '1990-01-01', 0 ,0.00);
INSERT INTO WidgetInventory VALUES (-2, '1990-01-02', 0 ,0.00);

The following code shows how to build a CTE or VIEW with the possible pick lists:

CREATE VIEW PickCombos(total_pick, bin_1, qty_on_hand_1,
                  bin_2, qty_on_hand_2,
                  bin_3, qty_on_hand_3)
AS 
SELECT DISTINCT 
       (W1.qty_on_hand + W2.qty_on_hand + W3.qty_on_hand) AS total_pick,
       CASE WHEN W1.receipt_nbr < 0 
            THEN 0 ELSE W1.receipt_nbr END AS bin_1, W1.qty_on_hand,
       CASE WHEN W2.receipt_nbr < 0 
            THEN 0 ELSE W2.receipt_nbr END AS bin_2, W2.qty_on_hand,
       CASE WHEN W3.receipt_nbr < 0 
            THEN 0 ELSE W3.receipt_nbr END AS bin_3, W3.qty_on_hand
 FROM WidgetInventory AS W1, 
      WidgetInventory AS W2, 
      WidgetInventory AS W3
WHERE W1.receipt_nbr NOT IN (W2.receipt_nbr, W3.receipt_nbr)
  AND W2.receipt_nbr NOT IN (W1.receipt_nbr, W3.receipt_nbr)
  AND W1.qty_on_hand >= W2.qty_on_hand
  AND W2.qty_on_hand >= W3.qty_on_hand;

Now you need a procedure to find the pick combination that meet or come closest to a certain quantity.

CREATE PROCEDURE OverPick (IN goal_qty INTEGER)
LANGUAGE SQL
BEGIN 
IF goal_qty > 0
THEN 
SELECT goal_qty, total_pick, bin_1, qty_on_hand_1,
      bin_2, qty_on_hand_2,
      bin_3, qty_on_hand_3
  FROM PickCombos 
 WHERE total_pick
        = (SELECT MIN (total_pick)
             FROM PickCombos 
            WHERE total_pick >= goal_qty) 
END IF;
END;

With the SQL-99 syntax, the VIEW could be put into a Common Table Expression (CTE) and produce a query without a VIEW. With the current data and goal of 73 Widgets, you can find two picks that together equal 75, namely {3, 4} and {4, 2, 1}.

I will leave it as an exercise for the reader to find a query that under-picks a target quantity.

--

Joe Celko was a member of the ANSI X3H2 Database Standards Committee and helped write the SQL-92 standards. He is the author of over 750 magazine columns and seven books, the best known of which is SQL for Smarties, now in its third edition. For more articles, puzzles, resources, and more, go to www.celko.com.