This is a long answer, so I decided to add a summary here.
- At first I present a solution that produces exactly the same result in the same order as in the question. It scans the main table 3 times: to get a list of
ProductIDs with the range of dates for each Product, to sum up costs for each day (because there are several transactions with the same dates), to join result with original rows.
- Next I compare two approaches that simplify the task and avoid one last scan of the main table. Their result is a daily summary, i.e. if several transactions on a Product have the same date they are rolled into single row. My approach from previous step scans the table twice. Approach by Geoff Patterson scans the table once, because he uses external knowledge about the range of dates and list of Products.
- At last I present a single pass solution that again returns a daily summary, but it doesn't require external knowledge about range of dates or list of
ProductIDs.
I will use AdventureWorks2014 database and SQL Server Express 2014.
Changes to the original database:
- Changed type of
[Production].[TransactionHistory].[TransactionDate] from datetime to date. The time component was zero anyway.
- Added calendar table
[dbo].[Calendar]
- Added index to
[Production].[TransactionHistory]
.
CREATE TABLE [dbo].[Calendar]
(
[dt] [date] NOT NULL,
CONSTRAINT [PK_Calendar] PRIMARY KEY CLUSTERED
(
[dt] ASC
))
CREATE UNIQUE NONCLUSTERED INDEX [i] ON [Production].[TransactionHistory]
(
[ProductID] ASC,
[TransactionDate] ASC,
[ReferenceOrderID] ASC
)
INCLUDE ([ActualCost])
-- Init calendar table
INSERT INTO dbo.Calendar (dt)
SELECT TOP (50000)
DATEADD(day, ROW_NUMBER() OVER (ORDER BY s1.[object_id])-1, '2000-01-01') AS dt
FROM sys.all_objects AS s1 CROSS JOIN sys.all_objects AS s2
OPTION (MAXDOP 1);
MSDN article about OVER clause has a link to an excellent blog post about window functions by Itzik Ben-Gan. In that post he explains how OVER works, the difference between ROWS and RANGE options and mentions this very problem of calculating a rolling sum over a date range. He mentions that current version of SQL Server doesn't implement RANGE in full and doesn't implement temporal interval data types. His explanation of the difference between ROWS and RANGE gave me an idea.
Dates without gaps and duplicates
If TransactionHistory table contained dates without gaps and without duplicates, then the following query would produce correct results:
SELECT
TH.ProductID,
TH.TransactionDate,
TH.ActualCost,
RollingSum45 = SUM(TH.ActualCost) OVER (
PARTITION BY TH.ProductID
ORDER BY TH.TransactionDate
ROWS BETWEEN
45 PRECEDING
AND CURRENT ROW)
FROM Production.TransactionHistory AS TH
ORDER BY
TH.ProductID,
TH.TransactionDate,
TH.ReferenceOrderID;
Indeed, a window of 45 rows would cover exactly 45 days.
Dates with gaps without duplicates
Unfortunately, our data has gaps in dates. To solve this problem we can use a Calendar table to generate a set of dates without gaps, then LEFT JOIN original data to this set and use the same query with ROWS BETWEEN 45 PRECEDING AND CURRENT ROW. This would produce correct results only if dates do not repeat (within the same ProductID).
Dates with gaps with duplicates
Unfortunately, our data has both gaps in dates and dates can repeat within the same ProductID. To solve this problem we can GROUP original data by ProductID, TransactionDate to generate a set of dates without duplicates. Then use Calendar table to generate a set of dates without gaps. Then we can use the query with ROWS BETWEEN 45 PRECEDING AND CURRENT ROW to calculate rolling SUM. This would produce correct results. See comments in the query below.
WITH
-- calculate Start/End dates for each product
CTE_Products
AS
(
SELECT TH.ProductID
,MIN(TH.TransactionDate) AS MinDate
,MAX(TH.TransactionDate) AS MaxDate
FROM [Production].[TransactionHistory] AS TH
GROUP BY TH.ProductID
)
-- generate set of dates without gaps for each product
,CTE_ProductsWithDates
AS
(
SELECT CTE_Products.ProductID, C.dt
FROM
CTE_Products
INNER JOIN dbo.Calendar AS C ON
C.dt >= CTE_Products.MinDate AND
C.dt <= CTE_Products.MaxDate
)
-- generate set of dates without duplicates for each product
-- calculate daily cost as well
,CTE_DailyCosts
AS
(
SELECT TH.ProductID, TH.TransactionDate, SUM(ActualCost) AS DailyActualCost
FROM [Production].[TransactionHistory] AS TH
GROUP BY TH.ProductID, TH.TransactionDate
)
-- calculate rolling sum over 45 days
,CTE_Sum
AS
(
SELECT
CTE_ProductsWithDates.ProductID
,CTE_ProductsWithDates.dt
,CTE_DailyCosts.DailyActualCost
,SUM(CTE_DailyCosts.DailyActualCost) OVER (
PARTITION BY CTE_ProductsWithDates.ProductID
ORDER BY CTE_ProductsWithDates.dt
ROWS BETWEEN 45 PRECEDING AND CURRENT ROW) AS RollingSum45
FROM
CTE_ProductsWithDates
LEFT JOIN CTE_DailyCosts ON
CTE_DailyCosts.ProductID = CTE_ProductsWithDates.ProductID AND
CTE_DailyCosts.TransactionDate = CTE_ProductsWithDates.dt
)
-- remove rows that were added by Calendar, which fill the gaps in dates
-- add back duplicate dates that were removed by GROUP BY
SELECT
TH.ProductID
,TH.TransactionDate
,TH.ActualCost
,CTE_Sum.RollingSum45
FROM
[Production].[TransactionHistory] AS TH
INNER JOIN CTE_Sum ON
CTE_Sum.ProductID = TH.ProductID AND
CTE_Sum.dt = TH.TransactionDate
ORDER BY
TH.ProductID
,TH.TransactionDate
,TH.ReferenceOrderID
;
I confirmed that this query produces same results as the approach from the question that uses subquery.
Execution plans
First query uses subquery, second - this approach. You can see that duration and number of reads is much less in this approach. Majority of estimated cost in this approach is the final ORDER BY, see below.
Subquery approach has a simple plan with nested loops and O(n*n) complexity.
Plan for this approach scans TransactionHistory several times, but there are no loops. As you can see more than 70% of estimated cost is the Sort for the final ORDER BY.
Top result - subquery, bottom - OVER.
Avoiding extra scans
The last Index Scan, Merge Join and Sort in the plan above is caused by the final INNER JOIN with the original table to make the final result exactly the same as a slow approach with subquery. The number of returned rows is the same as in TransactionHistory table. There are rows in TransactionHistory when several transactions occurred on the same day for the same product. If it is OK to show only daily summary in the result, then this final JOIN can be removed and the query becomes a bit simpler and a bit faster. The last Index Scan, Merge Join and Sort from the previous plan are replaced with Filter, which removes rows added by Calendar.
WITH
-- two scans
-- calculate Start/End dates for each product
CTE_Products
AS
(
SELECT TH.ProductID
,MIN(TH.TransactionDate) AS MinDate
,MAX(TH.TransactionDate) AS MaxDate
FROM [Production].[TransactionHistory] AS TH
GROUP BY TH.ProductID
)
-- generate set of dates without gaps for each product
,CTE_ProductsWithDates
AS
(
SELECT CTE_Products.ProductID, C.dt
FROM
CTE_Products
INNER JOIN dbo.Calendar AS C ON
C.dt >= CTE_Products.MinDate AND
C.dt <= CTE_Products.MaxDate
)
-- generate set of dates without duplicates for each product
-- calculate daily cost as well
,CTE_DailyCosts
AS
(
SELECT TH.ProductID, TH.TransactionDate, SUM(ActualCost) AS DailyActualCost
FROM [Production].[TransactionHistory] AS TH
GROUP BY TH.ProductID, TH.TransactionDate
)
-- calculate rolling sum over 45 days
,CTE_Sum
AS
(
SELECT
CTE_ProductsWithDates.ProductID
,CTE_ProductsWithDates.dt
,CTE_DailyCosts.DailyActualCost
,SUM(CTE_DailyCosts.DailyActualCost) OVER (
PARTITION BY CTE_ProductsWithDates.ProductID
ORDER BY CTE_ProductsWithDates.dt
ROWS BETWEEN 45 PRECEDING AND CURRENT ROW) AS RollingSum45
FROM
CTE_ProductsWithDates
LEFT JOIN CTE_DailyCosts ON
CTE_DailyCosts.ProductID = CTE_ProductsWithDates.ProductID AND
CTE_DailyCosts.TransactionDate = CTE_ProductsWithDates.dt
)
-- remove rows that were added by Calendar, which fill the gaps in dates
SELECT
CTE_Sum.ProductID
,CTE_Sum.dt AS TransactionDate
,CTE_Sum.DailyActualCost
,CTE_Sum.RollingSum45
FROM CTE_Sum
WHERE CTE_Sum.DailyActualCost IS NOT NULL
ORDER BY
CTE_Sum.ProductID
,CTE_Sum.dt
;
Still, TransactionHistory is scanned twice. One extra scan is needed to get the range of dates for each product. I was interested to see how it compares with another approach, where we use external knowledge about the global range of dates in TransactionHistory, plus extra table Product that has all ProductIDs to avoid that extra scan. I removed calculation of number of transactions per day from this query to make comparison valid. It can be added in both queries, but I'd like to keep it simple for comparison. I also had to use other dates, because I use 2014 version of the database.
DECLARE @minAnalysisDate DATE = '2013-07-31',
-- Customizable start date depending on business needs
@maxAnalysisDate DATE = '2014-08-03'
-- Customizable end date depending on business needs
SELECT
-- one scan
ProductID, TransactionDate, ActualCost, RollingSum45
--, NumOrders
FROM (
SELECT ProductID, TransactionDate,
--NumOrders,
ActualCost,
SUM(ActualCost) OVER (
PARTITION BY ProductId ORDER BY TransactionDate
ROWS BETWEEN 45 PRECEDING AND CURRENT ROW
) AS RollingSum45
FROM (
-- The full cross-product of products and dates,
-- combined with actual cost information for that product/date
SELECT p.ProductID, c.dt AS TransactionDate,
--COUNT(TH.ProductId) AS NumOrders,
SUM(TH.ActualCost) AS ActualCost
FROM Production.Product p
JOIN dbo.calendar c
ON c.dt BETWEEN @minAnalysisDate AND @maxAnalysisDate
LEFT OUTER JOIN Production.TransactionHistory TH
ON TH.ProductId = p.productId
AND TH.TransactionDate = c.dt
GROUP BY P.ProductID, c.dt
) aggsByDay
) rollingSums
--WHERE NumOrders > 0
WHERE ActualCost IS NOT NULL
ORDER BY ProductID, TransactionDate
-- MAXDOP 1 to avoid parallel scan inflating the scan count
OPTION (MAXDOP 1);
Both queries return the same result in the same order.
Comparison
Here are time and IO stats.
The two-scan variant is a bit faster and has fewer reads, because one-scan variant has to use Worktable a lot. Besides, one-scan variant generates more rows than needed as you can see in the plans. It generates dates for each ProductID that is in the Product table, even if a ProductID doesn't have any transactions. There are 504 rows in Product table, but only 441 products have transactions in TransactionHistory. Also, it generates the same range of dates for each product, which is more than needed. If TransactionHistory had a longer overall history, with each individual product having relatively short history, the number of extra unneeded rows would be even higher.
On the other hand, it is possible to optimize two-scan variant a bit further by creating another, more narrow index on just (ProductID, TransactionDate). This index would be used to
calculate Start/End dates for each product (CTE_Products) and it would have less pages than covering index and as a result cause less reads.
So, we can choose, either have an extra explicit simple scan, or have an implicit Worktable.
BTW, if it is OK to have a result with only daily summaries, then it is better to create an index that doesn't include ReferenceOrderID. It would use less pages => less IO.
CREATE NONCLUSTERED INDEX [i2] ON [Production].[TransactionHistory]
(
[ProductID] ASC,
[TransactionDate] ASC
)
INCLUDE ([ActualCost])
Single pass solution using CROSS APPLY
It becomes a really long answer, but here is one more variant that returns only daily summary again, but it does only one scan of the data and it doesn't require external knowledge about range of dates or list of ProductIDs. It doesn't do intermediate Sorts as well. Overall performance is similar to previous variants, though seems to be a bit worse.
The main idea is to use a table of numbers to generate rows that would fill the gaps in dates. For each existing date use LEAD to calculate the size of the gap in days and then use CROSS APPLY to add required number of rows into the result set. At first I tried it with a permanent table of numbers. The plan showed large number of reads in this table, though actual duration was pretty much the same, as when I generated numbers on the fly using CTE.
WITH
e1(n) AS
(
SELECT 1 UNION ALL SELECT 1 UNION ALL SELECT 1 UNION ALL
SELECT 1 UNION ALL SELECT 1 UNION ALL SELECT 1 UNION ALL
SELECT 1 UNION ALL SELECT 1 UNION ALL SELECT 1 UNION ALL SELECT 1
) -- 10
,e2(n) AS (SELECT 1 FROM e1 CROSS JOIN e1 AS b) -- 10*10
,e3(n) AS (SELECT 1 FROM e1 CROSS JOIN e2) -- 10*100
,CTE_Numbers
AS
(
SELECT ROW_NUMBER() OVER (ORDER BY n) AS Number
FROM e3
)
,CTE_DailyCosts
AS
(
SELECT
TH.ProductID
,TH.TransactionDate
,SUM(ActualCost) AS DailyActualCost
,ISNULL(DATEDIFF(day,
TH.TransactionDate,
LEAD(TH.TransactionDate)
OVER(PARTITION BY TH.ProductID ORDER BY TH.TransactionDate)), 1) AS DiffDays
FROM [Production].[TransactionHistory] AS TH
GROUP BY TH.ProductID, TH.TransactionDate
)
,CTE_NoGaps
AS
(
SELECT
CTE_DailyCosts.ProductID
,CTE_DailyCosts.TransactionDate
,CASE WHEN CA.Number = 1
THEN CTE_DailyCosts.DailyActualCost
ELSE NULL END AS DailyCost
FROM
CTE_DailyCosts
CROSS APPLY
(
SELECT TOP(CTE_DailyCosts.DiffDays) CTE_Numbers.Number
FROM CTE_Numbers
ORDER BY CTE_Numbers.Number
) AS CA
)
,CTE_Sum
AS
(
SELECT
ProductID
,TransactionDate
,DailyCost
,SUM(DailyCost) OVER (
PARTITION BY ProductID
ORDER BY TransactionDate
ROWS BETWEEN 45 PRECEDING AND CURRENT ROW) AS RollingSum45
FROM CTE_NoGaps
)
SELECT
ProductID
,TransactionDate
,DailyCost
,RollingSum45
FROM CTE_Sum
WHERE DailyCost IS NOT NULL
ORDER BY
ProductID
,TransactionDate
;
This plan is "longer", because query uses two window functions (LEAD and SUM).
