Dave Ballantyne - Phil Factor Challenge Entry 3.d

Peso had adding some index hints and shuffled a calculation to my initial 3.a. So this is 3.a(+) with comments

with 3.d doing the TotalStock sum in one operation shaves some more time off

“A problem well stated is a problem half solved” - Charles F. Kettering

Let us think about what has been asked within the challenge.

We have a warehouse which starts empty , the data contains the stock movements in (including returns) and out. The stock movements ALWAYS happen in a first in first out basis. With this we know that if the present stock level (sum(in's) - sum(out's) is 50 that will be the last 50 that have entered the warehouse. The key to this query is to efficiently find the cost of those 50 items.

    CREATE NONCLUSTERED INDEX [IX_Dave_General] ON [dbo].[Stock]
    (
            [ArticleID] ASC,
        	  [TranDate] DESC,
            [TranCode] ASC
    )
    INCLUDE ( [Items],
    [Price]) WITH (PAD_INDEX  = OFF, STATISTICS_NORECOMPUTE  = OFF, SORT_IN_TEMPDB = OFF, IGNORE_DUP_KEY = OFF, DROP_EXISTING = OFF, ONLINE = OFF, ALLOW_ROW_LOCKS  = ON, ALLOW_PAGE_LOCKS  = ON) ON [PRIMARY]

    GO
    CREATE NONCLUSTERED INDEX [IX_Dave_Items] ON [dbo].[Stock]
    (
            [ArticleID] ASC,
            [TranDate] ASC
    )
    INCLUDE ( [Items])
    WHERE ([TranCode] IN ('IN', 'RET'))
    WITH (PAD_INDEX  = OFF, STATISTICS_NORECOMPUTE  = OFF, SORT_IN_TEMPDB = OFF, IGNORE_DUP_KEY = OFF, DROP_EXISTING = OFF, ONLINE = OFF, ALLOW_ROW_LOCKS  = ON, ALLOW_PAGE_LOCKS  = ON) ON [PRIMARY]

    GO

    CREATE NONCLUSTERED INDEX [IX_Dave_Price] ON [dbo].[Stock]
    (
            [ArticleID] ASC,
            [TranDate] ASC
    )
    INCLUDE ( [Price])
    WHERE ([TranCode]='IN')
    WITH (PAD_INDEX  = OFF, STATISTICS_NORECOMPUTE  = OFF, SORT_IN_TEMPDB = OFF, IGNORE_DUP_KEY = OFF, DROP_EXISTING = OFF, ONLINE = OFF, ALLOW_ROW_LOCKS  = ON, ALLOW_PAGE_LOCKS  = ON, FILLFACTOR = 100) ON [PRIMARY]

    GO

   /* Sum up the ins and outs to calculate the remaining stock level */
;WITH cteStockSum 
AS      (

      SELECT  ArticleID,
            SUM(CASE  WHEN TranCode = 'OUT' THEN 0-Items
                      ELSE Items END) AS TotalStock
            FROM  dbo.Stock
      GROUP BY  ArticleID
), 
/* Perform a rolling balance ( in reverse order ) through the stock movements in */
cteReverseInSum
AS      (
   SELECT  s.ArticleID,
           s.TranDate,
           (
               SELECT SUM(i.Items)
                 FROM dbo.Stock AS i WITH (INDEX (IX_Dave_Items))
                WHERE i.ArticleID = s.ArticleID
                  AND i.TranCode IN ('IN', 'RET')
                  AND i.TranDate >= s.TranDate
           /*   SELECT SUM(i.Items)
                 FROM dbo.vwStockIn as i with (index (idxStockInArtTrans))
                WHERE i.ArticleID = s.ArticleID
                  AND i.TranDate >= s.TranDate*/

           ) AS RollingStock,
           s.Items AS ThisStock
     FROM  dbo.Stock AS s
    WHERE  s.TranCode IN ('IN', 'RET')

), 
/* Using the rolling balance above find the first stock movement in that meets (or exceeds) our required stock level */
/* and calculate how much stock is required from the earliest stock in */
cteWithLastTranDate
AS      (
  SELECT   w.ArticleID,
           w.TotalStock,
           LastPartialStock.TranDate,
           LastPartialStock.StockToUse,
           LastPartialStock.RunningTotal,
           w.TotalStock - LastPartialStock.RunningTotal + LastPartialStock.StockToUse AS UseThisStock

      FROM cteStockSum AS w
           CROSS APPLY  ( SELECT TOP(1)  
                                 z.TranDate,
                                 z.ThisStock AS StockToUse,
                                 z.RollingStock AS RunningTotal
                            FROM cteReverseInSum AS z
                           WHERE z.ArticleID = w.ArticleID
                             AND z.RollingStock >= w.TotalStock
                        ORDER BY z.TranDate DESC ) AS LastPartialStock

)
/*  Sum up the cost of 100% of the stock movements in after the returned stockid and
    for that stockid we need 'UseThisStock' items' */
SELECT y.ArticleID,
       y.TotalStock as CurrentItems ,
       SUM(CASE WHEN e.TranDate = y.TranDate THEN y.UseThisStock
                ELSE e.Items
                END * Price.Price) AS CurrentValue
  FROM cteWithLastTranDate AS y
 INNER JOIN  dbo.Stock AS e  WITH (INDEX (IX_Dave_Items)) 
    ON e.ArticleID = y.ArticleID
   AND e.TranDate >= y.TranDate
   AND e.TranCode IN ('IN', 'RET')
 CROSS APPLY  (
       /* Find the Price of the item in */
       SELECT TOP(1)        
              p.Price
         FROM dbo.Stock AS p WITH (INDEX (IX_Dave_Price))
        WHERE p.ArticleID = e.ArticleID
          AND p.TranDate <= e.TranDate
          AND p.TranCode = 'IN'
        ORDER BY p.TranDate DESC
      ) AS Price
GROUP BY  y.ArticleID,
          y.TotalStock
ORDER BY   y.ArticleID
go

Great job Dave! I was able to get mine down to 2900ms with a couple index hints but still not fast enough.

Cheers Scot

Here's an alternative solution, based on a tally table triangular join. I would have expected it to be quicker than my previous entry, but it's not. I'm posting just for the fun of it and for those interested in taking a look at a different approach. The cost is 92% in the aggregate after the triangular join and I wasn't able to get rid of it. Maybe some of you can squeeze something more out of this query.

-- Gianluca Sartori 3a
-- Tally triangular join

SELECT ArticleId, 
        CurrentItems = SUM(CASE Number WHEN 1 THEN Items - ISNULL(OutItems,0) ELSE 0 END),
        CurrentValue = SUM(CASE RN4 WHEN 1 THEN Items - ISNULL(OutItems,0) ELSE LastItem END * LastPrice)
FROM (
        SELECT *, RN4 = ROW_NUMBER() OVER (PARTITION BY ArticleId ORDER BY Number DESC)
        FROM (
                SELECT ArticleId, Number, SUM(Items) AS Items, 
                                SUM(CASE WHEN RN3 = Number THEN Items ELSE 0 END) AS LastItem,
                                SUM(CASE WHEN RN3 = Number THEN Price ELSE 0 END) AS LastPrice
                FROM (
                        SELECT ArticleId, 
                                RN3 = ROW_NUMBER() OVER (PARTITION BY ArticleId ORDER BY MIN(StockId) DESC), 
                                SUM(Items) Items,
                                Price = SUM(Price)
                        FROM (
                                SELECT *, RN = ROW_NUMBER() OVER (PARTITION BY ArticleId ORDER BY StockId)
                                FROM (
                                        SELECT StockId, ArticleId, TranCode, Items, Price, RN2 = ROW_NUMBER() OVER (PARTITION BY ArticleId ORDER BY StockId)
                                        FROM Stock
                                        WHERE TranCode = 'IN'
                                        UNION ALL 
                                        SELECT StockId, ArticleId, TranCode, Items, Price, RN2 = ROW_NUMBER() OVER (PARTITION BY ArticleId ORDER BY StockId)
                                        FROM Stock
                                        WHERE TranCode = 'RET'
                                ) AS S 
                        ) AS A
                        GROUP BY ArticleId, CASE TranCode WHEN 'IN' THEN RN2 ELSE RN - RN2 END
                ) AS B
                INNER JOIN TallyNumbers AS T
                        ON RN3 >= T.Number
                GROUP BY ArticleId, Number
        ) AS C
        CROSS APPLY (
                SELECT SUM(Items) AS OutItems
                FROM Stock
                WHERE ArticleId = C.ArticleId
                        AND TranCode = 'OUT'
        ) AS D 
        WHERE Items >= ISNULL(OutItems,0)
) AS E 
GROUP BY ArticleId
ORDER BY ArticleId

Ok, well I would post a pure set based solution, except that the site is refusing to let me post the whole thing!! Lame.

Anyway, the SQL is just

EXEC [dbo].[FIFOStock]

It runs in about 6.3 seconds on my box.

There are two source files, one for the support class (mostly the same guts as the CLR type version, except for the fact that IBinarySerialize support is removed, and it is now class, rather than struct based).

FIFOStock Procedure:

using System;
using System.Data;
using System.Data.SqlClient;
using System.Data.SqlTypes;
using Microsoft.SqlServer.Server;

public partial class StoredProcedures
{
    [Microsoft.SqlServer.Server.SqlProcedure]
    public static void FIFOStock()
    {
        using (SqlConnection connection = new SqlConnection("context connection=true"))
        {
            connection.Open();
            using (SqlCommand command = new SqlCommand("SELECT [ArticleID], CASE [TranCode] WHEN 'IN' THEN 1 WHEN 'OUT' THEN 2 ELSE 3 END, [Items], [Price] FROM [dbo].[Stock] ORDER BY [ArticleID], [TranDate]", connection))
            {
                short lastArticleID = -1;
                StockStack ss = new StockStack();

                // Create a record object that represents an individual row, including it's metadata.
                SqlDataRecord record =
                    new SqlDataRecord(new SqlMetaData[] {
                    new SqlMetaData("ArticleID", SqlDbType.Int),
                    new SqlMetaData("CurrentItems", SqlDbType.Int),
                    new SqlMetaData("CurrentValue", SqlDbType.Money),
                });

                SqlContext.Pipe.SendResultsStart(record);

                using (SqlDataReader reader = command.ExecuteReader())
                {
                    while (reader.Read())
                    {
                        short articleID = reader.GetInt16(0);
                        if (articleID != lastArticleID)
                        {
                            if (lastArticleID != -1)
                            {
                                // Populate the record.
                                record.SetInt32(0, lastArticleID);
                                record.SetInt32(1, ss.TotalCount);
                                record.SetSqlMoney(2, ss.TotalPrice);

                                SqlContext.Pipe.SendResultsRow(record);
                            }
                            ss = new StockStack();
                            lastArticleID = articleID;
                        }
                        int opCode = reader.GetInt32(1);
                        switch (opCode)
                        {
                            case 1:
                            {
                                ss.AddStock(reader.GetSqlMoney(3), reader.GetInt32(2));
                            } break;
                            case 2:
                            {
                                ss.RemoveStock(reader.GetInt32(2));
                            } break;
                            case 3:
                            {
                                ss.ReturnStock(reader.GetInt32(2));
                            } break;
                        }
                    }

                    // populate and emit the final record
                    record.SetInt32(0, lastArticleID);
                    record.SetInt32(1, ss.TotalCount);
                    record.SetSqlMoney(2, ss.TotalPrice);
                    SqlContext.Pipe.SendResultsRow(record);
                }
                SqlContext.Pipe.SendResultsEnd();
            }
        }
    }
}

StockStack class:

using System;
using System.Data;
using System.Data.SqlClient;
using System.Data.SqlTypes;
using Microsoft.SqlServer.Server;
using System.Collections.Generic;
using System.Text;

internal class StockStack
{
    public override string ToString()
    {
        StringBuilder sb = new StringBuilder(1024);
        foreach (StockStackItem ssi in _stackItems)
        {
            sb.Append(ssi.Value);
            sb.Append(" x ");
            sb.AppendLine(ssi.Count.ToString());
        }
        sb.Append("---");
        sb.Append(TotalPrice.ToString());
        sb.Append(" - ");
        sb.Append(TotalCount.ToString());
        return sb.ToString();
    }

    public void ReturnStock(int Count)
    {
        _stackItems[_stackItems.Count - 1].ReturnStock(Count);
    }

    public void AddStock(SqlMoney Price, int Count)
    {
        _stackItems.Add(new StockStackItem((Decimal)Price, Count));
    }

    public void RemoveStock(int Count)
    {
        int itemsLeft = 0;
        bool itemEmpty = false;
        while (true)
        {
            _stackItems[0].RemoveStock(Count, out itemsLeft, out itemEmpty);

            if (itemEmpty)
            {
                _stackItems.RemoveAt(0);
            }
            if (itemsLeft == 0)
            {
                return;
            }
            Count = itemsLeft;
        }
    }

    public int TotalCount
    {
        get
        {
            int totalCount = 0;
            foreach (StockStackItem ssi in _stackItems)
            {
                totalCount += ssi.Count;
            }
            return totalCount;
        }
    }


    public SqlMoney TotalPrice
    {
        get
        {
            Decimal totalValue = 0;
            foreach (StockStackItem ssi in _stackItems)
            {
                totalValue += ssi.TotalValue;
            }
            return totalValue;
        }
    }

    public static StockStack GetInitialisedStack(SqlMoney Price, int Count)
    {
        StockStack ss = new StockStack();
        ss._stackItems.Add(new StockStackItem((Decimal)Price, Count));
        return ss;
    }

    public static StockStack Empty
    {
        get
        {
            return new StockStack();
        }
    }

    public static StockStack Parse(SqlString s)
    {
        // no implementation of from-string for this type
        return StockStack.Empty;
    }

    // List of items in the stock stack
    private List<StockStackItem> _stackItems = new List<StockStackItem>(4);

    private class StockStackItem
    {
        Decimal _stackItemValue;
        int _stackItemCount;

        public void ReturnStock(int Count)
        {
            _stackItemCount += Count;
        }

        public int Count
        {
            get
            {
                return _stackItemCount;
            }
        }

        public Decimal Value
        {
            get
            {
                return _stackItemValue;
            }
        }

        public Decimal TotalValue
        {
            get
            {
                return _stackItemValue * _stackItemCount;
            }
        }

        public void RemoveStock(int Count, out int RemainingItems, out bool IsEmpty)
        {
            if (_stackItemCount > Count)
            {
                RemainingItems = 0;
                IsEmpty = false;
                _stackItemCount -= Count;
            }
            else 
            {
                RemainingItems = Count - _stackItemCount;
                IsEmpty = true;
                _stackItemCount = 0;
            }
        }

        public StockStackItem(Decimal StackItemValue, int StackItemCount)
        {
            _stackItemValue = StackItemValue;
            _stackItemCount = StackItemCount;
        }
    }
}

Here is my cursor solution as counterweight to all set-based solutions :-)

-- Peso CURSOR    
CREATE TABLE    #Stage
    	(
    		ArticleID INT,
    		CurrentItems INT,
    		CurrentValue MONEY
    	)

DECLARE 	@ArticleID INT,
    	@PrevID INT = 0,
    	@Items INT,
    	@CurrItems INT,
    	@Price MONEY,
    	@LatestPrice MONEY,
    	@Away INT,
    	@Diff INT

DECLARE 	curYak CURSOR LOCAL FORWARD_ONLY FOR
    		SELECT		s.ArticleID,
    				s.Items,
    				s.Price,
    				COALESCE(w.Items, 0) AS Away
    		FROM		(
    					SELECT	ArticleID,
    						TranDate,
    						Items,
    						Price
    					FROM	dbo.Stock
    					WHERE	TranCode IN ('IN', 'RET')
    				) AS s
    		LEFT JOIN	(
    					SELECT		ArticleID,
    							SUM(Items) AS Items
    					FROM		dbo.Stock
    					WHERE		TranCode = 'OUT'
    					GROUP BY	ArticleID
    				) AS w ON w.ArticleID = s.ArticleID
    		ORDER BY	s.ArticleID,
    				s.TranDate

OPEN    curYak

FETCH   NEXT
FROM    curYak
INTO    @ArticleID,
    @Items,
    @Price,
    @Away

WHILE @@FETCH_STATUS = 0
    BEGIN
    	SELECT	@Diff =	CASE
    				WHEN @ArticleID > @PrevID THEN 0
    				WHEN @CurrItems > @Away THEN @CurrItems - @Away
    				ELSE @Diff
    			END,
    		@CurrItems =	CASE
    					WHEN @ArticleID > @PrevID THEN @Items
    					ELSE @CurrItems + @Items - @Diff
    				END,
    		@PrevID = @ArticleID,
    		@LatestPrice = COALESCE(@Price, @LatestPrice)

    	IF @CurrItems >= @Away
    		INSERT	#Stage
    			(
    				ArticleID,
    				CurrentItems,
    				CurrentValue
    			)
    		VALUES	(
    				@ArticleID,
    				@CurrItems - @Away,
    				(@CurrItems - @Away) * @LatestPrice
    			)

    	FETCH	NEXT
    	FROM	curYak
    	INTO	@ArticleID,
    		@Items,
    		@Price,
    		@Away
    END

CLOSE curYak
DEALLOCATE curYak

SELECT  	ArticleID,
    	SUM(CurrentItems) AS CurrentItems,
    	SUM(CurrentValue) AS CurrentValue
FROM    	#Stage
GROUP BY    ArticleID
ORDER BY    ArticleID

DROP TABLE  #Stage