SQL to choose a price between two points in time

Question

Given a time-series of datetime price changes and another disparate time-series of N events, how do I query the last known price at the time of each event without running N queries? Essentially, I need to write some kind of CROSS-JOIN BETWEEN query that matches the most recent known price.

For example, price change history:

Changed At (time) | Price (money)
                1 |    10
                5 |    20
               10 |    30
               20 |    40

Events:

Event Time | Nearest Matched Price (from above)
         0 | n/a
         3 | 10
         6 | 20
        10 | 30
        15 | 30

The real-world use-case is that I tracked a time series of stock movements with costs and prices, but neglected to store costs alongside my invoice lines. My stock movements usually occurred right before the time of invoice.

I have a similar calendaring report query that reports sales across calendar days/weeks/months, but only works because the CROSS JOIN condition (> now && < next-day) will only ever return one row. Pardon the noisy query (will clean it up):

SELECT [t3].[FirstDateOfWeek] AS [Date], [t3].[value] AS [Total], [t3].[value2] AS [Count]
FROM (
    SELECT SUM([t0].[Total]) AS [value], COUNT(*) AS [value2], [t2].[FirstDateOfWeek]
    FROM [dbo].[vw_Invoices] AS [t0]
    LEFT OUTER JOIN [dbo].[Cases] AS [t1] ON ([t1].[CaseId]) = [t0].[CaseId]
    CROSS JOIN [dbo].[Calendar] AS [t2]
    WHERE ([t0].[Date] >= [t2].[CalendarDate]) AND ([t0].[Date] < [t2].[NextDayDateTime]) AND ([t0].[Date] >= @p0) AND ([t0].[Date] < @p1) AND (NOT ([t0].[IsVoided] = 1))
    GROUP BY [t2].[FirstDateOfWeek]
    ) AS [t3]
ORDER BY [t3].[FirstDateOfWeek]  

Is this even possible in SQL, perhaps with a "running total" query grouped by extracted hour?

Answer 1

Quick-and-dirty, not tested on a live instance.

For each row of Event data we need one row from Price - the one which happened most recently, but before the Event's timestamp. TSQL supports the top 1 .. order by notation. By embedding the Price lookup as a sub-query in a SELECT list it will be executed once per row in Event. Predicating Price on Event's values will ensure the most recent is returned. Something like this:

select
    e.event_id,
    e.event_time,
    ( select top 1     -- return one value
        p.price
      from Prices as p
      where p.price_time <= e.event_time -- ensure the price change happened at or before the event
      order by p.price_time desc  -- top ensure "top 1" picks the price with the gretest i.e. most recent, timestamp
    ) as price
from Events as e;

The sub-query will run once per row in Events, so performance may be compromised for very large sets. Make sure there are indexes on Price.price_time.

Answer 2

If you combine your price data with your event data in a UNION ALL query then the problem reduces to finding the last non NULL value. Itzik Ben-Gan writes about that problem here:

Given a table T1, with a key column called id and a NULLable value column called col1, return the last non NULL col1 value based on id order.

Going back to your problem, below is data prep that I did to cover your example data (I used INT columns for simplicity but you should be able to easily switch to columns that store a datetime):

CREATE TABLE #X_PRICE_CHANGE (CHANGED_TIME INT, PRICE INT);

INSERT INTO #X_PRICE_CHANGE
VALUES (1, 10), (5, 20), (10, 30), (20, 40);

CREATE TABLE #X_EVENT (EVENT_TIME INT);

INSERT INTO #X_EVENT
VALUES (0), (3), (6), (10), (15);

Here's one way to solve your problem with window functions:

SELECT 
  CHANGED_TIME AS EVENT_TIME
, CURRENT_PRICE
FROM
(
    SELECT
      CHANGED_TIME
    , SRC
    , MAX(PRICE) OVER (PARTITION BY CHANGED_TIME_OF_LAST_PRICE) CURRENT_PRICE
    FROM 
    (
        SELECT 
          CHANGED_TIME
        , PRICE
        , SRC
        , MAX(CASE WHEN SRC = 'PRICE' THEN CHANGED_TIME ELSE NULL END) 
            OVER (ORDER BY CHANGED_TIME ASC, SRC DESC 
            ) CHANGED_TIME_OF_LAST_PRICE
        FROM
        (
            SELECT 
            CHANGED_TIME, PRICE, 'PRICE' AS SRC
            FROM #X_PRICE_CHANGE

            UNION ALL

            SELECT 
            EVENT_TIME, NULL, 'EVENT' AS SRC
            FROM #X_EVENT
        ) t
    ) tt
) ttt
WHERE ttt.SRC = 'EVENT';

Let's go through the code step by step. The t derived table just combines the price and event data together with UNION ALL. Nothing exciting here:

╔══════════════╦═══════╦═══════╗
║ CHANGED_TIME ║ PRICE ║  SRC  ║
╠══════════════╬═══════╬═══════╣
║            1 ║ 10    ║ PRICE ║
║            5 ║ 20    ║ PRICE ║
║           10 ║ 30    ║ PRICE ║
║           20 ║ 40    ║ PRICE ║
║            0 ║ NULL  ║ EVENT ║
║            3 ║ NULL  ║ EVENT ║
║            6 ║ NULL  ║ EVENT ║
║           10 ║ NULL  ║ EVENT ║
║           15 ║ NULL  ║ EVENT ║
╚══════════════╩═══════╩═══════╝

The tt derived table applies the MAX window function to t. The purpose of the window function is to find the changed_time for each "EVENT" row that contains the latest price.

╔══════════════╦═══════╦═══════╦════════════════════════════╗
║ CHANGED_TIME ║ PRICE ║  SRC  ║ CHANGED_TIME_OF_LAST_PRICE ║
╠══════════════╬═══════╬═══════╬════════════════════════════╣
║            0 ║ NULL  ║ EVENT ║ NULL                       ║
║            1 ║ 10    ║ PRICE ║ 1                          ║
║            3 ║ NULL  ║ EVENT ║ 1                          ║
║            5 ║ 20    ║ PRICE ║ 5                          ║
║            6 ║ NULL  ║ EVENT ║ 5                          ║
║           10 ║ 30    ║ PRICE ║ 10                         ║
║           10 ║ NULL  ║ EVENT ║ 10                         ║
║           15 ║ NULL  ║ EVENT ║ 10                         ║
║           20 ║ 40    ║ PRICE ║ 20                         ║
╚══════════════╩═══════╩═══════╩════════════════════════════╝

Consider the row with a CHANGED_TIME of 15. CHANGED_TIME_OF_LAST_PRICE has a value of 10, so if we could go back and grab the price value for the "PRICE" row with CHANGED_TIME_OF_LAST_PRICE = 10 we would have the right price for the row with a CHANGED_TIME of 15. That is what happens in the third derived table ttt:

╔══════════════╦═══════╦═══════════════╗
║ CHANGED_TIME ║  SRC  ║ CURRENT_PRICE ║
╠══════════════╬═══════╬═══════════════╣
║            0 ║ EVENT ║ NULL          ║
║            1 ║ PRICE ║ 10            ║
║            3 ║ EVENT ║ 10            ║
║            5 ║ PRICE ║ 20            ║
║            6 ║ EVENT ║ 20            ║
║           10 ║ PRICE ║ 30            ║
║           10 ║ EVENT ║ 30            ║
║           15 ║ EVENT ║ 30            ║
║           20 ║ PRICE ║ 40            ║
╚══════════════╩═══════╩═══════════════╝

The MAX() window function will only ever find a single non NULL value in each partition. MAX() is used here to effectively smear the PRICE value from the "PRICE" row to all "EVENT" rows with the same value for CHANGED_TIME_OF_LAST_PRICE.

Finally, we remove unnecessary rows that had a source of "PRICE" from the results. We needed those rows to get the right results from the window functions but we don't want them in the final result set. Here is the result from ttt after filtering:

╔════════════╦═══════════════╗
║ EVENT_TIME ║ CURRENT_PRICE ║
╠════════════╬═══════════════╣
║          0 ║ NULL          ║
║          3 ║ 10            ║
║          6 ║ 20            ║
║         10 ║ 30            ║
║         15 ║ 30            ║
╚════════════╩═══════════════╝

From a performance point of view one important thing to note is that if your time columns are unique in each table then you can use ROWS for the ROW or RANGE clause to possibly improve performance.

If you want to get really fancy you can eliminate one of the window functions by casting your data as BINARY. You may need to adjust your code for this to work with a non-INT column. Here's one implementation:

SELECT
  CHANGED_TIME
, CURRENT_PRICE
FROM
(
    SELECT 
      CHANGED_TIME
    , PRICE
    , SRC
    , CAST(SUBSTRING(MAX(binval) OVER (ORDER BY CHANGED_TIME ASC, SRC DESC 
        ), 5, 4) AS INT) CURRENT_PRICE
    FROM
    (
        SELECT 
        CHANGED_TIME, PRICE, 'PRICE' AS SRC
        , CAST(CHANGED_TIME AS BINARY(4)) + CAST(PRICE AS BINARY(4)) AS binval
        FROM #X_PRICE_CHANGE

        UNION ALL

        SELECT 
        EVENT_TIME, NULL, 'EVENT' AS SRC
        , CAST(EVENT_TIME AS BINARY(4)) + CAST(NULL AS BINARY(4)) AS binval
        FROM #X_EVENT
    ) t
) tt
WHERE tt.SRC = 'EVENT';

I recommend reading the sqlmag article if you want to learn more about that technique.