Query Exercise Answers: Returning Routes in the Right Order

Last Updated June 11, 2025

In your most recent Query Exercise challenge, I gave you these two tables:

DROP TABLE IF EXISTS dbo.Stations;
CREATE TABLE dbo.Stations
    (StationId INT IDENTITY(1,1) PRIMARY KEY CLUSTERED,
     StationName VARCHAR(50),
     StationPhysicalOrder INT);

INSERT INTO dbo.Stations (StationName, StationPhysicalOrder)
    SELECT CHAR(64 + n), n
    FROM (VALUES 
        (1),(2),(3),(4),(5),(6),(7),(8),(9),(10),(11),
        (12),(13),(14),(15),(16),(17),(18),(19)
    ) AS Numbers(n);

DROP TABLE IF EXISTS dbo.StationRoutingOverride;
CREATE TABLE dbo.StationRoutingOverride
    (StationRoutingOverrideId INT IDENTITY(1,1) PRIMARY KEY CLUSTERED,
     StationFromName VARCHAR(50),
     StationToName VARCHAR(50));

INSERT INTO dbo.StationRoutingOverride (StationFromName, StationToName)
    VALUES ('E', 'S'), ('B', 'I'), ('I', 'D');

DROP TABLE IF EXISTS dbo.Stations;

CREATE TABLE dbo.Stations

(StationId INT IDENTITY(1,1) PRIMARY KEY CLUSTERED,

StationName VARCHAR(50),

StationPhysicalOrder INT);

INSERT INTO dbo.Stations (StationName, StationPhysicalOrder)

SELECT CHAR(64 + n), n

FROM (VALUES

(1),(2),(3),(4),(5),(6),(7),(8),(9),(10),(11),

(12),(13),(14),(15),(16),(17),(18),(19)

) AS Numbers(n);

DROP TABLE IF EXISTS dbo.StationRoutingOverride;

CREATE TABLE dbo.StationRoutingOverride

(StationRoutingOverrideId INT IDENTITY(1,1) PRIMARY KEY CLUSTERED,

StationFromName VARCHAR(50),

StationToName VARCHAR(50));

INSERT INTO dbo.StationRoutingOverride (StationFromName, StationToName)

VALUES ('E', 'S'), ('B', 'I'), ('I', 'D');

And your assignment was to return a result set that started with the first station by StationPhysicalOrder, and then move through the rows in StationPhysicalOrder – unless there was a matching StationRoutingOverride row, in which case you needed to follow that routing instead. A successful result would look like this:

In the challenge, I explained that I wasn’t actually able to solve it without using procedural code: looping through the rows one by one with a while loop or cursor, I knew y’all would be able to do it because the audience includes some real T-SQL wizards. All of y’all who solved it in the comments should officially feel Smarter Than Brent Ozar™.

An Against-the-Rules (But Real-World) Answer First

Brian Boodman first posted this answer, and then apologized for not reading the instructions about not using loops. However, I wanna show his answer because it was the first kind of answer I thought about doing at the client – because after all, this kind of brute force programming works, it’s just not elegant:

declare @Result Table(StationName VarChar(50))
declare @Position VarChar(50) = 'A'

while(@Position is not null)
BEGIN
    insert into @Result values(@Position)
    declare @Override varchar(50) = (select top 1 StationToName from StationRoutingOverride where StationFromName = @position)
    declare @Failover varchar(50) =
    (select top 1 S2.StationName from Stations S1
    join Stations S2 on S2.StationPhysicalOrder = S1.StationPhysicalOrder+1
    where S1.StationName = @Position)
    set @Position = coalesce(@Override,@Failover)
END
select * from @Result

declare @Result Table(StationName VarChar(50))

declare @Position VarChar(50) = 'A'

while(@Position is not null)

BEGIN

insert into @Result values(@Position)

declare @Override varchar(50) = (select top 1 StationToName from StationRoutingOverride where StationFromName = @position)

declare @Failover varchar(50) =

(select top 1 S2.StationName from Stations S1

join Stations S2 on S2.StationPhysicalOrder = S1.StationPhysicalOrder+1

where S1.StationName = @Position)

set @Position = coalesce(@Override,@Failover)

END

select * from @Result

When I was working with the client, I said that if I had to get across the finish line in 15-30 minutes, this is the kind of solution I’d write. As it happened, this query would end up getting called millions of times per minute, and every millisecond of CPU would count, so I didn’t wanna do this. But I’m showing it here because it works, and I bet a lot of y’all went to this in your head first too – I did!

Using CTEs

The first answer was Ilya Makarov’s. Even though his was the fastest, he managed to work in cool examples of T-SQL features like LEAD, OUTER APPLY, and CASTing an integer for safety purposes:

with t as
(
    select 
        stationName s,
        stationPhysicalOrder o,
        lead(stationName) over (order by stationPhysicalOrder) ns,
        min(stationPhysicalOrder) over () mino
    from
        dbo.Stations
),
r as
(
    select cast(1 as int) o, s from t where o = mino
    union all
    select 
        r.o + 1, isnull(so.ns, t.ns)
    from
        r
        outer apply (select StationToName from dbo.StationRoutingOverride where StationFromName = r.s) so (ns)
        join t on r.s = t.s
)

select s from r 
where s is not null
order by o

with t as

(

select

stationName s,

stationPhysicalOrder o,

lead(stationName) over (order by stationPhysicalOrder) ns,

min(stationPhysicalOrder) over () mino

from

dbo.Stations

r as

(

select cast(1 as int) o, s from t where o = mino

union all

select

r.o + 1, isnull(so.ns, t.ns)

from

outer apply (select StationToName from dbo.StationRoutingOverride where StationFromName = r.s) so (ns)

join t on r.s = t.s

)

select s from r

where s is not null

order by o

Ilya used two CTEs: the first fetches the first station only, and then the second CTE joins to it to get all subsequent stations.

I got a chuckle out of Ilya’s answer because at the client, one of the developers had said, “Could we use OUTER APPLY to do this?” and my honest answer was, “Maybe, but I don’t use that a lot, and to get it right is going to take more time than we have here.” Hats off to Ilya (and the other commenters who banged out good answers.)

Michael Bogdanov’s answer came in next, managing to do it with a single CTE plus OUTER APPLY:

;WITH cte AS 
(
SELECT StationName , 
       StationPhysicalOrder
FROM Stations 
WHERE StationPhysicalOrder = (SELECT MIN(StationPhysicalOrder) FROM Stations)
UNION ALL 
SELECT COALESCE(StOverride.StationToName, Stations.StationName) AS StationName  , 
       COALESCE(StOverride.StationPhysicalOrder, Stations.StationPhysicalOrder) AS StationPhysicalOrder
FROM Stations 
JOIN cte 
ON Stations.StationPhysicalOrder = cte.StationPhysicalOrder + 1 
OUTER APPLY
    (
    SELECT StationRoutingOverride.StationToName, StationOverride.StationPhysicalOrder
    FROM  StationRoutingOverride
    JOIN Stations AS StationOverride 
    ON StationOverride.StationName = StationRoutingOverride.StationToName
    WHERE StationFromName = cte.StationName 
    ) StOverride
)
SELECT StationName
FROM cte

;WITH cte AS

(

SELECT StationName ,

StationPhysicalOrder

FROM Stations

WHERE StationPhysicalOrder = (SELECT MIN(StationPhysicalOrder) FROM Stations)

UNION ALL

SELECT COALESCE(StOverride.StationToName, Stations.StationName) AS StationName ,

COALESCE(StOverride.StationPhysicalOrder, Stations.StationPhysicalOrder) AS StationPhysicalOrder

FROM Stations

JOIN cte

ON Stations.StationPhysicalOrder = cte.StationPhysicalOrder + 1

OUTER APPLY

(

SELECT StationRoutingOverride.StationToName, StationOverride.StationPhysicalOrder

FROM StationRoutingOverride

JOIN Stations AS StationOverride

ON StationOverride.StationName = StationRoutingOverride.StationToName

WHERE StationFromName = cte.StationName

) StOverride

)

SELECT StationName

FROM cte

The first SELECT grabs the first station in the list, the one with the minimum order.

The second SELECT – still inside the CTE – queries back to the CTE itself. The first time it’s executed, it will only select the minimum row, then it’ll join to Stations again to get the next physical order. Then the OUTER APPLY also tacks on the overrides table.

Function-Based Answer

Michael J. Swart handled the recursion by using a user-defined function to fetch the next station for a route:

DROP FUNCTION IF EXISTS dbo.GetNextStationPhysicalOrder;
GO

CREATE FUNCTION dbo.GetNextStationPhysicalOrder
(
    @CurrentStationPhysicalOrder int
)
RETURNS INT
AS
BEGIN
    RETURN (
        SELECT TOP (1) StationPhysicalOrder
        FROM 
        (
            -- next one naturally
            SELECT TOP (1)
                StationPhysicalOrder,
                CAST(1 as bit) as IsNaturalNext
            FROM dbo.Stations
            WHERE StationPhysicalOrder > @CurrentStationPhysicalOrder
            ORDER BY StationPhysicalOrder ASC

            UNION ALL

            -- next one following override
            SELECT 
                NextStation.StationPhysicalOrder, 
                CAST(0 as bit) as IsNaturalNext
            FROM 
                dbo.Stations CurrentStation
            INNER JOIN 
                dbo.StationRoutingOverride O
                ON O.StationFromName = CurrentStation.StationName
            INNER JOIN 
                dbo.Stations NextStation
                ON NextStation.StationName = O.StationToName
            WHERE  
                CurrentStation.StationPhysicalOrder = @CurrentStationPhysicalOrder
        ) NextStation
        ORDER BY IsNaturalNext ASC /* prefer override --> NaturalNext == 0 */ 
    );
END
GO

WITH CTE AS
(
    SELECT TOP (1) 
        StationId,
        StationName,
        StationPhysicalOrder, 
        1 as OutputOrder
    FROM dbo.Stations
    ORDER BY StationPhysicalOrder ASC

    UNION ALL

    SELECT 
        S.StationId, 
        S.StationName,
        S.StationPhysicalOrder, 
        C.OutputOrder + 1
    FROM CTE C
    INNER JOIN 
        dbo.Stations S
        ON S.StationPhysicalOrder = dbo.GetNextStationPhysicalOrder(C.StationPhysicalOrder)
)
SELECT 
    StationId,
    StationName,
    StationPhysicalOrder
FROM 
    CTE
ORDER BY 
    OutputOrder ASC

DROP FUNCTION IF EXISTS dbo.GetNextStationPhysicalOrder;

CREATE FUNCTION dbo.GetNextStationPhysicalOrder

(

@CurrentStationPhysicalOrder int

)

RETURNS INT

BEGIN

RETURN (

SELECT TOP (1) StationPhysicalOrder

FROM

(

-- next one naturally

SELECT TOP (1)

StationPhysicalOrder,

CAST(1 as bit) as IsNaturalNext

FROM dbo.Stations

WHERE StationPhysicalOrder > @CurrentStationPhysicalOrder

ORDER BY StationPhysicalOrder ASC

UNION ALL

-- next one following override

SELECT

NextStation.StationPhysicalOrder,

CAST(0 as bit) as IsNaturalNext

FROM

dbo.Stations CurrentStation

INNER JOIN

dbo.StationRoutingOverride O

ON O.StationFromName = CurrentStation.StationName

INNER JOIN

dbo.Stations NextStation

ON NextStation.StationName = O.StationToName

WHERE

CurrentStation.StationPhysicalOrder = @CurrentStationPhysicalOrder

) NextStation

ORDER BY IsNaturalNext ASC /* prefer override --> NaturalNext == 0 */

);

END

WITH CTE AS

(

SELECT TOP (1)

StationId,

StationName,

StationPhysicalOrder,

1 as OutputOrder

FROM dbo.Stations

ORDER BY StationPhysicalOrder ASC

UNION ALL

SELECT

S.StationId,

S.StationName,

S.StationPhysicalOrder,

C.OutputOrder + 1

FROM CTE C

INNER JOIN

dbo.Stations S

ON S.StationPhysicalOrder = dbo.GetNextStationPhysicalOrder(C.StationPhysicalOrder)

)

SELECT

StationId,

StationName,

StationPhysicalOrder

FROM

CTE

ORDER BY

OutputOrder ASC

But then to put icing on the cake, Swart added another answer that uses string stuffing. I have to confess that this one was my favorite out of all of ’em because it was so out-of-left-field. I actually blurted out loud, “OH WOW!” when I walked through his code, hahaha.

All of the above answers get the job done! Good work, folks. Hope y’all had fun with that challenge – that was a little harder one than usual, for me at least!

SQLBits Added More Capacity to My Workshop! Move Quick.

[Video] Office Hours at the Barcelona Pavilion

5 Comments. Leave new

happydba
June 11, 2025 6:49 pm

Swart’s string stuffing is amazing

Reply
Michael J Swart
June 11, 2025 7:57 pm

Hahaha. Thanks. The string answer is a bit fragile, but it was written using the “rule of cool”. I wouldn’t check it in for work, but it was perfect to use as a comment on a friend’s blog post.

Reply
Shawn Oden
June 11, 2025 10:04 pm

I forgot about this exercise. I tried it when he first posted, then bailed on it when I misread the initial directions. I tried another solution today (rCTE-based), and then decided to throw a stupid amount of data at it to see how it performed. 1M rows in Stations and 500 Overrides. I was actually impressed that mine completed. 🙂

I’ll have to try to remember to blog about what I did this evening.

Thanks again, Brent, and to everyone else who participated and shared their results. This was a lot of fun.

Reply
Denny
June 17, 2025 11:31 pm

Hi Brent, FYI this is a concept from CS called Linked Lists. In the field of DBAs it’ll be pretty niche, but I thought I’d at least put the term in the comments in case anyone wants to go looking for more.

I found the exercise pretty useful in learning about recursive CTEs. I had a quick chat with Copilot which got me like 80% of the way there: https://copilot.microsoft.com/shares/Q61w1xzL6NQP82QZheFGT

After which the exercise was reduced to constructing the linked list table, which was relatively trivial.

Reply
- Brent Ozar
  June 18, 2025 6:49 am
  
  Yep, I’m quite familiar with linked lists, but to participate here, you’ll want to follow the instructions in the original post and show your work. Cheers!
  
  Reply