Query Exercise: Return Routes in the Right Order
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:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
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); SELECT * FROM dbo.Stations; |
The Stations table content looks like this:
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:
However, during emergencies, we may need to override the routing. To handle that, we have an override routing table:
|
1 2 3 4 5 6 7 8 |
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'); |
The contents of that table:
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:
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:
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.
53 Comments. Leave new
Aren’t you supposed to say “a friend of mine is having this problem” for questions like this? 😀
“Please do the needful.”
Hello, Brent!
Here is my solution: https://gist.github.com/IAMakarov/ade78466445b73598c00ba92799b519c
You didn’t mention if gaps are possible in stationPhysicalOrder and how to handle them, so query finds next station nearest by PhysicalOrder.
Possible loops in routes are not handled.
Query doesn’t bother if there are duplicates in station names.
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.
Hi Brent, here is my attempt https://gist.github.com/MikeBogdanov/5e97f9a4fc6169a7a140714edf21411e
It doesn’t take into account possible gaps and loops, designed for the simplest case, but I think it’ll be easy to adjust if necessary
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.
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];
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.
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.)
I think the blog eats comments if they are link-only comments so here goes again 😀 My version –
https://gist.github.com/parrotdba/3617ac39243b72956e4ffcda7dd79d2b
HappyDBA – hmm, does your code produce the correct answer shown in the blog post?
Right my quick stab at it had the same results as Jorriss – the route kept going after the “end” through the rest of the stops.
Here’s another gist. Completely gross SQL which could probably be refined given more time but I was determined to not do a recursive cte or a TOP (1)’ing type of thing just to see if it was possible 😀
https://gist.github.com/parrotdba/58ea0aa57f41d8a4de46888a28783cc0
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).
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
BRIAN
BRIAN
C’mon, man, you gotta read the instructions. 😉
Mine turned out similar to Sebastian’s
https://gist.github.com/jameslegrand2/f8d63274e231cd8b84007b8d517b2722
James – good work!
Here is a different approach…
https://gist.github.com/antoopan/d191c9f8c9d39049c83c387c7f8d2e91
Good work!
My 2 cents…
https://gist.github.com/RuudDeheij60/a62c12cf48e65273ac6bd7d1ea60bc04
Good work!
Fun! 28 minutes.
I used a CTE to “walk” along the station route and I used a function to help me determine which step is next. I’m allowing myself the use of a function, because if it’s from a real problem, then having everything in a single query is probably not among the constraints.
https://gist.github.com/mjswart-d2l/a4fbefb9bc83abbdd0ffef860ff7b40e
Excellent work as always, sir! Yeah, a function would have been fine here (although not a stored procedure, long story.)
Here is a more condensed version of my earlier attempt…
https://gist.github.com/RuudDeheij60/bb4b006b4dff913740061807febad037
Should not the order be: A, B, I, C, D, E, S…?
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
https://gist.github.com/Replicant000/24bce9014899fe3ac4424f2ac7d5af71
fairly simple hierarchical query and yes, lazy aliases
https://gist.github.com/jasperfrog/133290781e7bc61fd6bb2e02c17f1bdb
Here’s my five minute swag. It’s a bit different.
https://gist.github.com/Jorriss/6d252b6eceb27f9f106245a81cee34b1
Also from browsing wikipedia just now:
https://en.wiktionary.org/wiki/Appendix:English_isograms
My favorite isogram is absolutely “shlockumentary”
This version allows for ending a route at any station by adding a row to the StationRoutingOverride table with StationToName empty, like (‘C’, ”).
https://gist.github.com/RuudDeheij60/f5ffb83dd164b5d8616cb71e908b4385
Haven’t read all the others, but this is probably a close copy to someone else.
https://gist.github.com/smilieface/a72d34db5a48fa9f3cc6e3eec1d203da
A combination of lead and recursion
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.
For some reason the gist link didn’t stick.
https://gist.github.com/KipTheElder/121d456ab8a2d07c1263c554b7a7be53
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
nice!
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.
Copy paste the question in AI, adapted the images to text.
Correct on the 1st try!
https://gist.github.com/github4manu/f666376a4e42a0cbfbf4157a801623d7
another one , based on Tom’s proposal , and commented :
https://gist.github.com/github4manu/adb83a49a49120783c6ffa933d8ff4c1
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
;
That was a fun one: https://gist.github.com/gdoddsy/45b0bee7803c55649e6117c12a9b0817
I took a few liberties and made some assumptions about starting at ‘A’ and station Id’s be sequential, both of those are fixable
[…] Brent Ozar recently posted a coding exercise on his site which looked fun: Query Exercise: Return Routes in the Right Order – Brent Ozar Unlimited® […]
I was thinking about this a little more, and if you assume the stations are single letters, you can manipulate the order of the strings.
Here’s something that *looks* relational.
https://gist.github.com/mjswart-d2l/3fa24bf5a50fab039a707eeb3f620782
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!
[…] your most recent Query Exercise challenge, I gave you these two […]
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
I’m late to the party (just noticed this problem in Brent’s email), but here is my answer.
https://gist.github.com/0x7FFFFFFFFFFFFFFF/2f30248a216141a10cbf44bc3f490b30
A little late … I just found the time to handle this.
My key point , is to prepare the data source, so that I will have the StationFrom and StationTo , allready set it, with the help of LEAD , Left join RoutingOverride : ISNULL(s.StationToName, s.next_StationName)
then simple recursive…
https://gist.github.com/SabinWeb/4a59236bac23277d5109b7a5509819ed
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)
Does that match the correct answer given in the post?
[…] Brent had a query exercise recently about train stations moving in some order and having overrides to this order in emergencies. I suppose he’s been traveling a lot lately and ran into an issue. […]
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
Read the last sentence of the post, where I link to my answers. Cheers!