Sql-server – Optimal way to record and retrieve a time-dependent value

database-designsql serversql server 2014

I have a table that has transactions for a bus (boarding riders). Given the route ID and the date, I need to look up in another table what service type it was doing that day. Bus schedules change at most every 6 months or so, with most going years unchanged.

Currently the schedule table is defined like so:

CREATE TABLE [dbo].[Routes](
    [ID] [int] NOT NULL,
    [RouteID] [int] NOT NULL,
    [Type] [varchar](50) NOT NULL,
    [StartDate] [datetime] NOT NULL,
PRIMARY KEY CLUSTERED 
(
    [ID] ASC
));

An example might look like:

ID  RouteID  Type          StartDate
--  -------  ------------  ----------
 1      301  Standard      2015-01-01
 2      301  Discontinued  2016-06-01
 3      302  Standard      2015-01-01
 4      302  ParaTrans     2017-01-01

So, if I have a transaction from 2015-04-20 for RouteID 301, I want to get back "Standard", but if the transaction is from 2018-01-20, it should return "Discontinued". For transactions prior to 2015-01-01, it should return NULL (or "", or anything other than a result that might conflict with a valid answer, i.e., "Standard", "Paratrans", or "Discontinued").

Basically, the table represents that route 301 was a standard route between 2015-01-01 and 2016-05-31 (and thus any transactions during that period should be categorized as "Standard"), then it was Discontinued on 2016-06-01 (through current day, implicitly as there is no later schedule change noted), while 302 was a Standard route from 2015-01-01 through 2016-12-31, then a ParaTrans(it) route after.

Route   Type          Start       End
-----   ----          -----       ---
301
        Standard      2015-01-01  2016-05-31
        Discontinued  2016-06-01  Present
302
        Standard      2015-01-01  2016-12-31
        ParaTrans     2017-01-01  Present

Currently, the query to do this looks like this:

SELECT
    TRANSIT_DAY, 
    ROUTE_ID, 
    (SELECT TOP (1) Type FROM Routes
     WHERE (RouteID = dbo.DAILY_SALES_DETAIL.ROUTE_ID) 
     AND (StartDate <= dbo.DAILY_SALES_DETAIL.TRANSIT_DAY)
     ORDER BY StartDate DESC) AS NCTD_MODE 
FROM dbo.DAILY_SALES_DETAIL

Questions

What I'd like to know is: Is this the most effective combination of (a) structure of the Routes table and (b) query to achieve this result? In other words, could a more efficient query be used with the existing structure? Could a change to the route table allow for a more efficient query?

Considerations

The table of transactions is imported from a vendor on a daily basis, and so changing the schema of that table is not trivial and it is preferred to be avoided. More importantly, this lookup is used across a number of tables and databases using transactions or other bus related data sourced form multiple vendors; this is just a single example. We have one vendor (and thus one database) for monetary transactions, another for rider count, and still another for performance, and so on, with the route number and date being the only reliably consistent identifier across them all.

The route table has an index of (RouteID, StartDate). Currently there are 56 rows in the Route table and 26M rows in the transaction table. The route table is comprised of 45 routes, and currently there are no routes with more than 2 rows, or one change. There is no limit to how many changes a single route could have, but I include this stat to show that the number is likely to remain small for the foreseeable future.

I can add any required indexes in order to optimize a suggested query. The question is more about finding the best strategy, assuming all reasonable optimizations are made to the considered strategies, than about finding the best optimization of a particular strategy.

db<>fiddle here

Best Answer

You could increase performance of your setup, as shown in your question, by changing the dbo.Routes table to:

CREATE TABLE dbo.Routes(
      RouteID int NOT NULL
    , [Type] varchar(50) NOT NULL
    , StartDate datetime NOT NULL
    , CONSTRAINT PK_Routes
        PRIMARY KEY CLUSTERED
        (RouteID, StartDate DESC)
) WITH (DATA_COMPRESSION = PAGE)
ON [PRIMARY];

The key here is we're defining the clustered index, which is the table, on the compound of RouteID and StartDate DESC. This provides the data in exactly the way that is most efficient for the query you've written. The caveat emptor here is inserts into the dbo.Routes for an existing route with a new date will cause page splits to occur since we'll be filling rows in descending order of date. Having said that, with a small number of rows in the Route table, and with the occasional index maintenance, this should not be a big concern.

Instead of doing that, I would consider modifying the dbo.Routes table to include an EndDate column. This eliminates the need to do a subquery with TOP(1) and ORDER BY .... Something like:

CREATE TABLE dbo.Routes(
      RouteID int NOT NULL
    , [Type] varchar(50) NOT NULL
    , StartDate datetime NOT NULL
    , EndDate datetime NOT NULL
    , CONSTRAINT PK_Routes
        PRIMARY KEY CLUSTERED
        (RouteID, StartDate ASC)
);

Note the clustered index is now on (RouteID, StartDate ASC).

The query can now use an INNER JOIN, instead of the correlated subquery, and looks like:

SELECT
      t.TRANSIT_DAY
    , t.ROUTE_ID
    ,  NCTD_MODE = r.Type 
FROM Transactions t
    INNER JOIN dbo.Routes r ON t.ROUTE_ID = r.RouteID 
        AND t.TRANSIT_DAY >= r.StartDate 
        AND t.TRANSIT_DAY < r.EndDate
ORDER BY t.TRANSIT_DAY
    , t.ROUTE_ID;

This allows SQL Server to do a simple inner loop join to obtain results. Granted, if you are returning a large amount of rows, there will be a significant sort required, that will probably spill to tempdb.

Using the MCVE I've shown below, we can compare plans for the the two variants. The first plan is your original query with the correlated subquery. The second plan is with the EndDate column included.

enter image description here

enter image description here

The 2nd variant has a plan cost which is about 4 times lower than the 1st variant. The sort operators in both plans are requesting 108MB of memory and spilling over 9,000 pages to tempdb - however it's fairly unlikely you'll be requesting the entire result set vs getting a single route, or perhaps a date range. If you add a filter for a single route, there is no large memory grant or spill to tempdb.

What follows is a sample MCVE with 10,000 route rows, and 1,000,000 transaction rows, that can be used to run tests against various designs:

Do this in tempdb to avoid any "accidents" with real tables.

USE tempdb;

Drop the tables if they exist (this works on SQL Server 2016+):

DROP TABLE IF EXISTS dbo.Routes;
DROP TABLE IF EXISTS dbo.Transactions;

Create the dbo.Routes table, with a clustered index on RouteID, StartDate DESC:

CREATE TABLE dbo.Routes(
        RouteID int NOT NULL
    , [Type] varchar(50) NOT NULL
    , StartDate datetime NOT NULL
    , CONSTRAINT PK_Routes
        PRIMARY KEY CLUSTERED
        (RouteID, StartDate DESC)
);

Insert 10,000 route rows:

;WITH src AS (
    SELECT t.n
    FROM (VALUES (0), (1), (2), (3), (4), (5), (6), (7), (8), (9))t(n)
)
, src2 AS (
SELECT RouteID = (s1.n * 1000) + (s2.n * 100) + (s3.n * 10)
    , Type = REPLICATE(CHAR(65 + CONVERT(int, CRYPT_GEN_RANDOM(1) % 26)), 50)
FROM src s1
    CROSS JOIN src s2
    CROSS JOIN src s3
    CROSS JOIN src s4
)
INSERT INTO dbo.Routes (RouteID, [Type], StartDate)
SELECT s.RouteID
    , s.Type
    , StartDate = DATEADD(DAY, ROW_NUMBER() OVER (PARTITION BY RouteID ORDER BY s.RouteID) - 1, '1997-01-01T00:00:00')
FROM src2 s

Create the dbo.Transactions, with a clustered index on ROUTE_ID, TRANSIT_DAY. Building the clustered index like that optimizes queries that filter on both route and day. 

CREATE TABLE dbo.Transactions(
     TRANSIT_DAY datetime NOT NULL
    , ROUTE_ID int NOT NULL
    , CONSTRAINT PK_Transactions
        PRIMARY KEY CLUSTERED
        (ROUTE_ID, TRANSIT_DAY)
);

Insert 1,000,000 rows into the dbo.Transactions table:

;WITH src AS (
    SELECT t.n
    FROM (VALUES (0), (1), (2), (3), (4), (5), (6), (7), (8), (9))t(n)
)
INSERT INTO dbo.Transactions (TRANSIT_DAY, ROUTE_ID)
SELECT DATEADD(DAY, CONVERT(int, CRYPT_GEN_RANDOM(1)), '1997-01-01') + DATEADD(MILLISECOND, ABS(CONVERT(int, CRYPT_GEN_RANDOM(4))), '00:00:00')
    , r.RouteID
FROM dbo.Routes r
CROSS JOIN src s1
CROSS JOIN src s2

For a Routes table with an EndDate column that can be used for comparative tests, I used this:

CREATE TABLE dbo.RoutesEndDate(
      RouteID int NOT NULL
    , [Type] varchar(50) NOT NULL
    , StartDate datetime NOT NULL
    , EndDate datetime NOT NULL
    , CONSTRAINT PK_RoutesEndDate
        PRIMARY KEY CLUSTERED
        (RouteID, StartDate ASC)
);

INSERT INTO dbo.RoutesEndDate (RouteID, [Type], StartDate, EndDate)
SELECT r.RouteID
    , R.Type
    , R.StartDate
    , EndDate = COALESCE(LEAD(r.StartDate) OVER (PARTITION BY r.RouteID ORDER BY r.StartDate), GETDATE())
FROM dbo.Routes r

Query both tables for a specific route:

SELECT
      t.TRANSIT_DAY
    , t.ROUTE_ID
    ,  NCTD_MODE = (
        SELECT TOP (1) Type 
        FROM Routes r
        WHERE (r.RouteID = t.ROUTE_ID) AND (r.StartDate <= t.TRANSIT_DAY)
        ORDER BY r.StartDate DESC
        ) 
FROM Transactions t
WHERE t.ROUTE_ID = 750
ORDER BY t.TRANSIT_DAY
    , t.ROUTE_ID;

The plan for the above query:

enter image description here

I/O and time Stats:

Table 'Routes'. Scan count 1000, logical reads 2142, physical reads 0, read-ahead reads 0, lob logical reads 0, lob physical reads 0, lob read-ahead reads 0.
Table 'Transactions'. Scan count 1, logical reads 7, physical reads 0, read-ahead reads 0, lob logical reads 0, lob physical reads 0, lob read-ahead reads 0.

 SQL Server Execution Times:
   CPU time = 2 ms,  elapsed time = 2 ms.
SQL Server parse and compile time: 
   CPU time = 0 ms, elapsed time = 0 ms.

Query for all transactions/routes:

SELECT
      t.TRANSIT_DAY
    , t.ROUTE_ID
    ,  NCTD_MODE = (
        SELECT TOP (1) Type 
        FROM Routes r
        WHERE (r.RouteID = t.ROUTE_ID) AND (r.StartDate <= t.TRANSIT_DAY)
        ORDER BY r.StartDate DESC
        ) 
FROM Transactions t
ORDER BY t.TRANSIT_DAY
    , t.ROUTE_ID;

The plan:

enter image description here

Nasty spill to tempdb for sort operator:

enter image description here

If we modify the clustered index on dbo.Transactions to be (TRANSIT_DAY, ROUTE_ID), and re-run the full query, we see a plan without that ugly sort and spill-to-tempdb:

enter image description here

Related Question