Launch week: the Season Pass & Fundamentals Week are 50% off — ends in 19d 13h 38m — See the sale
BRENT OZARUnlimited

Performance Tuning

Query Exercise: Return Routes in the Right Order

By Brent Ozar · June 4, 2025 · 53 comments

I’mma be honest with you, dear reader: this query exercise stems from a client problem that I couldn’t figure out how to solve in the time constraints that I had, and it drove me crazy. I wanted to put hours into this to figure it out, and I was sure there’d be a fun T-SQL way to do it.

I was onsite at a client helping them design a database, and part of the database involved storing routes for stations. For the purposes of this blog post, say we’ve got a station for each letter of the alphabet:

The Stations table content looks like this:

Stations table content

Most of the time, we want our route to start at the lowest StationPhysicalOrder (in this case, 1 for A) and then proceed through the stations by their StationPhysicalOrder, like this:

Station order

However, during emergencies, we may need to override the routing. To handle that, we have an override routing table:

The contents of that table:

Station Routing Overrides

Your exercise this week is to return a result set that:

  • Starts with the station with the lowest StationPhysicalOrder
  • For each row, if there’s a row in StationRoutingOverride to dictate the next step, jump to that station
  • Otherwise, go to the station with the next StationPhysicalOrder

In this case, your successful result set will look like this, sorted in this order:

The Dude Abides

As a side note, it took me a good solid hour to write this demo in a way that I could share it publicly, and end up with a station routing list that beautifully illustrated the problem at stake. You would think it would be easy to ask an LLM like ChatGPT for a word that’s:

  • An isogram (a word that doesn’t repeat any letters)
  • That has two adjacent letters in alphabetical order (like AB and DE)
  • Starts with a lower letter of the alphabet
  • Ends with a higher letter of the alphabet

I only asked for the first two requirements, and lots of LLMs got the answers terribly wrong! Here’s ChatGPT 4o trying its best, for example:

Oh, sweet ChatGPT

HAHAHA, poor thing. Bless its robotic little heart. It struggled when trying to solve this query exercise, too – I think it was on the right track, and it showed signs that it vaguely understood what it was doing, but the first few attempts didn’t get across the finish line. I do think this is a really fun challenge to use with LLMs, though – it’s the kind of thing where AI can write a query in a matter of seconds, but then it’ll take you minutes or hours to understand what the heck it’s doing, let alone troubleshoot the hidden problems.

Anyhoo, back to the challenge. I’m not being humble when I say I don’t think I’m very good at T-SQL, and this week’s Query Exercise is a great example. I stared at this client problem for a good 20 minutes, and I couldn’t come up with a set-based way to do it. I could think of procedural ways to do it, like loop through the stations one at a time with a while loop, cursor, or row-by-row function, but I couldn’t come up with a simple set-based way. I told the client, “I’m no Itzik Ben-Gan, but I bet if I post this as a Query Exercise on the blog, a bunch of readers will come up with awesome answers.” For the record, I’m not asking you to do my work: I came up with a quick way to return the data without the correct sorting, and the client’s app sorts it client-side.

Give it your best shot first, experimenting with ideas, because this is WAY harder than it looks. Then check out the solutions from other folks, compare and contrast your work, and finally read my answers and thoughts.

Free, 3× a week

Get my new posts by email

Three posts a week, plus a Monday roundup of the best database news from around the web.

Keep digging

Query Exercise: Fix This Computed Column. Query Exercise: Find the Best Time for Maintenance Query Exercise: Finding Long Values Faster

53 comments

  1. Aren’t you supposed to say “a friend of mine is having this problem” for questions like this? 😀

    Reply

    1. Ilya – it works! Good job. I agree about not dealing with loops or duplicates, and it’s good to see that you thought about that as a possible issue.

      Reply

    1. Michael – good job, it works! I agree about not dealing with loops or duplicates, and it’s good to see that you thought about that as a possible issue.

      Reply

  4. I’ve got similar challenges at work sometimes, here’s my proposed solution for your exercise using a recursive CET:

    WITH Stations AS ( — first determine which station comes next after each given station, either by StationPhysicalOrder or by StationRoutingOverride
    SELECT *,ISNULL(SRO.StationToName,LEAD(StationName) OVER(ORDER BY StationPhysicalOrder)) AS NextStation,MAX([StationPhysicalOrder]) OVER() [LastStationPhysicalOrder]
    FROM dbo.Stations S
    LEFT JOIN dbo.StationRoutingOverride SRO
    ON SRO.StationFromName = S.StationName
    ),
    — now recursively query all stations from first to last linking each to their next one
    [Route] ([StationId],[StationName],[StationPhysicalOrder],[NextStation],[StationOrder]) AS (
    SELECT [StationId],[StationName],[StationPhysicalOrder],[NextStation],1
    FROM Stations
    WHERE [StationPhysicalOrder] = 1
    UNION ALL
    SELECT S2.[StationId],S2.[StationName],S2.[StationPhysicalOrder], S2.[NextStation], S1.[StationOrder] + 1
    FROM Stations S2
    INNER JOIN [Route] S1 ON S1.[NextStation] = S2.[StationName] — station of current record was the “next” on the previous record
    WHERE S1.[StationOrder] <= S2.[LastStationPhysicalOrder] — stop at the last station
    )
    SELECT [StationName]
    FROM [Route]
    ORDER BY [StationOrder];

    Reply

  5. I may be out in left-field and not understanding the issue properly, but why use a second table and not just a field in the original table the is the over-ride, that way, you can just update the over-ride in the original table. I’m assume that the order may change multiple times, up, down or sideways.

    Reply

    1. Nancy – great question! Because the design had to accommodate *multiple* routes through the stations, depending on other attributes like product types. (There’s more to the design, and I’m only sharing the simplest portion of it to illustrate the problem.)

      Reply

  7. I’ll offer a simple RBAR while loop: https://gist.github.com/briangithex/dcda51bec4ccd54244eefa6fc7c20679 .

    Imperative algorithms are rarely appropriate in SQL, and certainly DBAs tend to frown on them, though at least they’re easy to read. A scenario that justified bringing on a consultant probably has constraints that make this solution a non-option (e.g., this solution is likely problematic when working with large tables). Still, I feel obligated to include it for discussion: This sort of approach may well be acceptable in some contexts.

    This code does not include error-checking (nor loop detection).

    Reply

    1. Just noticed “I could think of procedural ways to do it, like loop through the stations one at a time with a while loop, cursor, or row-by-row function, but I couldn’t come up with a simple set-based way.”

      Sorry, Brent

      Reply

    1. I was thinking A B I D C E S until I read this a few more times….

      Your exercise this week is to return a result set that:

      Starts with the station with the lowest StationPhysicalOrder

      For each row, if there’s a row in StationRoutingOverride to dictate the next step, jump to that station

      ***** Otherwise, go to the station with the next StationPhysicalOrder *****

      B-I-D is defined in the station override (B goes to I and there is an entry for I goes to D) table and given the third stipulation, E-S must follow.

      Cheers

      Reply

  20. Here’s my attempt; took me a while to exclude station C (without excluding others) once I saw the earlier comments. Now I’ll have a look to see how everyone else solved it.

    Reply

  21. drop table if exists #map;

    select s1.StationName,s2.StationName as DefaultNextStationName, o.StationToName as OverrideStation, ROW_NUMBER() over (order by s1.StationId) as Seq
    into #map
    from dbo.Stations s1
    left join dbo.Stations s2 on s2.StationPhysicalOrder = s1.StationPhysicalOrder + 1
    left join dbo.StationRoutingOverride o on o.StationFromName = s1.StationName;

    –select * from #map;

    with Mapping
    as
    (
    select m.StationName, isnull(m.OverrideStation, m.DefaultNextStationName) as NextStation, m.Seq
    from #map m
    where m.Seq = 1
    union all
    select m.StationName, isnull(m.OverrideStation, m.DefaultNextStationName), mp.Seq + 1
    from #map m
    inner join Mapping mp on mp.NextStation = m.StationName
    )
    select StationName from Mapping order by Seq

    Reply

  22. I haven’t spent the 20 minutes the author did, but I also can’t think of a relational solution. Caring about the order of values is fundamentally not relational. I think that’s why this is so hard.

    Reply

  25. Tom’s nice approach : first preparation cte with windows function then recursive
    with
    map as
    (
    select s1.StationName,s2.StationName as DefaultNextStationName, o.StationToName as OverrideStation, ROW_NUMBER() over (order by s1.StationId) as Seq
    from dbo.Stations s1
    left join dbo.Stations s2 on s2.StationPhysicalOrder = s1.StationPhysicalOrder + 1
    left join dbo.StationRoutingOverride o on o.StationFromName = s1.StationName
    )
    ,Mapping
    as
    (
    select m.StationName, isnull(m.OverrideStation, m.DefaultNextStationName) as NextStation, m.Seq
    from map m
    where m.Seq = 1
    union all
    select m.StationName, isnull(m.OverrideStation, m.DefaultNextStationName), mp.Seq + 1
    from map m
    inner join Mapping mp on mp.NextStation = m.StationName
    )
    select Seq, StationName from Mapping order by Seq
    ;

    Reply

    1. I read through this on my phone and thought, “I have to test this.”

      Then I walked through it, returning the variables one at a time as I walked through it, and blurted out loud, “OH WOW!” Hahaha. Thanks for that joy!

      Reply

  30. We can break this complex problem into two super-simple problems:
    1) For each station get it’s actual next station. Optionally cache it for speed.
    This is simple left join of overrides, plus reading next row (eg. LEAD).
    2) Start from first station. Follow next station until no more stations.
    This is a classic “traverse down the tree”. Use CTE, loop, string aggregations, whatever.
    Notes: Data might contain infinite loops! CTE depth is limited.

    Solution: single-query, without APPLY

    ;WITH StationWithNext AS — for speed, materialize in temp (or permanent) table.
    ( SELECT s.StationName, NextStation = ISNULL(o.StationToName, LEAD (s.StationName) OVER (ORDER BY s.StationPhysicalOrder))
    FROM dbo.Stations s
    LEFT JOIN dbo.StationRoutingOverride o ON o.StationFromName = s.StationName
    ), TravelStation AS
    ( SELECT StationName = CONVERT(VARCHAR(50), ‘A’) — first station
    UNION ALL — add next station
    SELECT StationName = s.NextStation
    FROM TravelStation t
    JOIN StationWithNext s ON t.StationName = s.StationName AND s.NextStation IS NOT NULL
    ) SELECT * FROM TravelStation — list result

    Reply

  33. Sorry – late as well. I haven’t read any other responses but I’m sure this one has already been considered. This was how I did it.

    SELECT IIF(z.stationtoname IS NULL, stationname, stationtoname) AS list
    FROM
    (
    SELECT *
    , LAG(stationname) OVER (ORDER BY stationphysicalorder) AS x
    FROM #stations AS s
    ) y
    LEFT JOIN #stationroutingoverride AS z
    ON y.x = stationfromname;

    It displays this

    list
    ————————————————–
    A
    B
    I
    D
    E
    S
    G
    H
    I
    D
    K
    L
    M
    N
    O
    P
    Q
    R
    S

    (19 rows affected)

    Reply

  35. i tried the below query, let me know is this good or not?
    ;

    WITH cte
    AS (
    SELECT b.StationToName
    , a.StationPhysicalOrder + 1 AS physicalorder
    FROM Stations a
    INNER JOIN StationRoutingOverride b ON a.StationName = b.StationFromName
    )
    , cte1
    AS (
    SELECT StationName
    , StationPhysicalOrder
    FROM Stations
    WHERE StationPhysicalOrder NOT IN (
    SELECT physicalorder
    FROM cte
    )
    )
    SELECT *
    FROM (
    SELECT *
    FROM cte1

    UNION ALL

    SELECT *
    FROM cte
    ) AS k
    ORDER BY StationPhysicalOrder

    Reply

Leave a comment

Your email address will not be published. Required fields are marked *