Let’s build a simple journey planner using SQL (part 2 of probably more than 2)

Last month we started our humble journey on a path towards becoming an ass-hat developer who builds journey planners using SQL. In the previous blog I described the data model for our journey planner and introduced a simple yet ludicrously inefficient pathfinding algorithm in SQL that generates a list of possible paths from one station to another.

Today, we’re continuing the idiocy by writing SQL code that generates travel plans so that you know where you need to go and when.

Let’s start with a short recap of some of the things we discussed last time. Feel free to skip this section if you still remember how everything works.

We have a MySQL database that contains a node table, which lists every train station that is directly reachable from the Netherlands.

id	name
21392	Nijmegen
21598	Nijmegen Dukenburg
21601	Nijmegen Heyendaal
21603	Nijmegen Lent
21803	Nijmegen Goffert

Trains don’t just stop at train stations – they stop at specific platforms at those train stations. Those platforms are defined in the stop table.

Trains are scheduled to arrive at and depart from specific platforms at specific times. Once a train departs, it continues its trip towards the next stop. All this information can be found in the stop_time table.

Passengers may need to change trains to reach their destination. Changing trains takes a non-zero amount of time. The transfer table tells us how much time is needed to transfer from one platform to another (side note: In practice it’s usually less if you’re an able-bodied person familiar with the station.).

id	from_stop_id	to_stop_id	min_transfer_time
8612	35025	35036	240
8613	35025	35026	240
8614	35025	35027	240
4959	35026	35027	180

The final building block that we need for our journey planner is the result we get from querying from possible_path, which lists the best ways to travel from one station to another through the Dutch train network.

As you may recall from the previous blog, we wrote a query that helps us navigate the train network from Nijmegen Heyendaal station to Amsterdam Science Park station. Now it’s time for us to pick up where we left off and generate some travel plans!

Before we start, let’s take a look at the website of the Dutch Railways. When we use its travel planner to generate plans for this route, we get the following result:

If we assume that our time of departure is 08:00, our best option is to take the 08:03 train from Nijmegen Heyendaal. After a few transfers on Nijmegen and Amsterdam Centraal, we should arrive at Amsterdam Science Park at 09:49.

Let’s try to replicate this advice using SQL by following the corresponding possible_path (21601 – 21392 – 21680 – 21473).

I’ll first show how we can do this manually, step by step. The first step we need to take is to determine which trains depart from Nijmegen Heyendaal around 08:00. For simplicity’s sake, let’s assume that people are willing to spend at most 30 minutes waiting for a train.

We can use the following trip retrieval query to retrieve all departures from Nijmegen Heyendaal between 08:00 and 08:30:

Executing the query gives us eight results. Trains depart from this station every 15 minutes in both directions.

The second station in our path was 21392 (Nijmegen), so let’s query the database to find out which trips from the previous search results can take us to Nijmegen:

As expected, only four out of those eight trips allow us to reach Nijmegen:

Once we are in Nijmegen, it’s time to change trains. We will want to retrieve all departures from this station again. Sadly, we can’t simply execute a modified version of the query that we just used for Nijmegen Heyendaal. Our journey no longer starts at “a station”, but at a specific platform (35 or 1b). Walking from one platform to another may take considerable time, especially at larger stations.

The trip retrieval query below retrieves all departures within the next 30 minutes that are realistically possible if one starts their journey from platforms 35 or 1b:

Executing this query gives us the following results:

Planning the remainder of the trip should be a walk in the park. We can repeatedly modify and execute the last two trip retrieval queries with the remaining node_ids until we reach our final destination.

You should now have a rough idea of how we can generate a travel plan by iteratively executing queries to retrieve departures and arrivals at each of the nodes in our path. If we were building an application using a normal programming language that’s probably exactly what we would implement in the final version, but that’s not what I’m going to do.

Instead, I’m going to write a stored procedure. A stored procedure is kind of like a function (side note: SQL also has things that are actually called functions, but those are only used to return single values within queries.) in a normal programming language. And since my manager seems to be very excited about this “big query thing, I am going to write one big-ass stored procedure that does everything. To hell with functional decomposition.

We’ll start with the following template:

Here we define a procedure GET_PATH_ADVICE, which given a path (as computed using the possible_path CTE) and a time of departure, will generate several travel plans in a WHILE loop, using modified versions of the three trip retrieval queries we saw earlier.

It doesn’t look very chonky yet, but that’s because it still contains a lot of TODOs that we need to process. In the remainder of this section, we’ll slowly feed it lines of SQL code until it’s morbidly obese.

Declaring variables

We begin by declaring some variables at the top of our procedure:

• We use node and step to keep track of the current state. node keeps track of the station we are currently at, while step is a counter that we can use to determine which of the three trip retrieval queries we need to execute, among other things.

• A dest variable makes it a bit easier for the algorithm to determine when it has created a travel plan for the complete journey (in this case from Nijmegen Heyendaal to Amsterdam Science Park).

• We also declare an earliest_arrival_time datetime. I’ll explain this one later, once we actually get to use it.

We also need a place to store intermediate and final query results. Although lists and maps (dictionaries) are not available in SQL, we can create a temporary table to store our data.

dest is used to determine whether a travel plan is “complete”. We set its value to the last node_id in the path string that is passed to the GET_PATH_ADVICE procedure.

The node variable is set in the first and every other iteration of the WHILE loop, i.e. when a traveller starts their journey at the first station or reaches a new station by train. When this happens, we also remove the current node from the path.

Departure from first station

The query that retrieves all departures from the origin station is based on the first of our three trip retrieval queries. I’ve made a few modifications to it. For starters, nodeand departure_time are no longer hardcoded, but determined dynamically. We also fetch different fields, which we insert into the tmp_path_advice table:

• stop_times stores references to relevant stop_time records, which contain all the information we need to generate human-friendly travel advice.

• cur_step stores the number of the current iteration. This allows the algorithm to properly append stop_time.ids to the stop_times field.

• cur_stop_id is used to determine which trips can be taken from a transfer station (like Nijmegen).

• cur_trip_id and cur_stop_sequence can be used to determine which trips can be taken to arrive at the next node.

• first_datetime is when someone boards a train for the first time. This value will stay the same in subsequent iterations.

• cur_datetime is either the current departure time or arrival time. This is used to determine which transfers are possible, among other things.

• is_complete is a boolean value that tells us whether the computed stop_times is complete. It’s always false here, because we haven’t even left the first station at this point.

After the first iteration, the tmp_path_advice table looks roughly like this:

Arrivals at subsequent stations

In the next iteration of the while loop, the procedure will attempt to find all stations that can be reached with the trips from the iteration directly before it. It then inserts a record for each of the reachable stops:

The tmp_path_advice table now has 18 new rows, with each row representing a stop that can be reached via one of the four trips at a specific time:

Departures from subsequent stations

The third trip retrieval query, which retrieves departures for subsequent stations on a journey, is similarly structured:

This query inserts the following records:

These two INSERT queries are repeated until the procedure has reached the end of the path. When this happens, the tmp_path_advice table hopefully has some records where is_complete is truthy (side note: This is not guaranteed to be the case, because some paths are only used during certain times of the day, e.g. peak times or past midnight.)!

Data cleanup

Once the while loop terminates, all that remains is to generate output that can be displayed to a user. But first we need to clean up some data.

Let’s start by removing all records from tmp_path_advice that we don’t need:

We then retrieve the earliest possible time of arrival and store it in the earliest_arrival_time variable. The best travel plans are those that have a cur_datetime equal to earliest_arrival_time.

A user may also be interested in alternative travel plans, e.g. plans that suggest taking a later train (keeping the overall travel time the same) or adding a bit more slack during transfers (increasing the overall travel time). However, what we would like to avoid are plans where a traveller would do this at every station along the path. Therefore, we only consider travel plans where the arrival time at the final destination is at most thirty minutes later than the earliest_arrival_time.

Generating advice

Now we can generate our travel advice. The tmp_path_advice table now only contains records that look a lot like this one here:

The stop_times fields contains stop_time.ids that can be used to look up almost all the information that we want to show to users. Unfortunately this field is a comma-separated list, so we can’t JOIN on this field directly. However, what we can do is convert stop_times values to a JSON list, parse it, and then CROSS JOIN with the resulting table. This allows us to simply SELECT the information we need from the joined result:

Now that everything is in place, it’s time to show the complete version of the GET_PATH_ADVICE procedure. The text continues below this snippet. Click here if you don’t feel like scrolling until your finger falls off.

We can call this stored procedure as follows:

The table below displays the results of the procedure call. I have excluded the last two columns to ensure that the table fits on the page. I have also given each travel plan a unique colour to make it easier to see where each journey starts and ends.

We can’t pat ourselves on the back yet: our GET_PATH_ADVICE() only works for one path, while the possible_path common table expression gave us five different paths to explore. What we want is a single procedure that is almost as easy to use as the official Dutch Railways travel planner. We’ll have to combine the possible_path query with GET_PATH_ADVICE() into one gargantuan procedure that does everything.

The resulting procedure is listed below. I’ve added a few explanatory comments here and there. Needless to say, it’s long, so feel free to click here to skip to the end.

We can call the PLAN_JOURNEY procedure as follows:

This gives us the following results:

That’s it, we’re almost done! There’s just one more thing we need to do, but I’ll leave that one for the next post…