“Heap, Heap, Array!”Getting AroundLet’s Build a Simple Journey Planner Using SQL

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

When all you have is a relational database, everything looks like a table. And you know what? It works! Sort of.

Oh, would you look at the timetable?

I could create a small toy network to demonstrate how this works, but to keep things a bit more interesting I’m going to do this with real public transport data.

Let me show you to your tables

We’ll make use of a public GTFS static feed for all public transport in the Netherlands, which is published under a CC0 license. For now, we’ll only consider trains, because reasons.

Timetables

agency

Public transport services are operated under a brand, i.e. an agency. Most travellers will think of a brand as the company that offers services. In practice a company may operate under multiple brands, and some brands are used by multiple companies.

route

Routes are what most people would call lines. Routes are associated with a transportation type (e.g. trams, metros, trains, and buses). From a traveller’s perspective lines are generally identified by a number, a letter or a name. Not to be confused with the exact path that a vehicle travels along, which is called a “shape” in GTFS parlance.

trip

Each route is served by trains that make trips (often in one direction or the other) throughout the day. The headsign informs travellers of the final destination of the train.

stop

Vehicles stop at stops. Somewhat confusingly, a stop can be anything from a bus stop pole to (part of) a platform to an entire station. Technically it can also be other things, but we’re just going to ignore that for now.

The table above shows the records for two train stations, “Nijmegen” and “Nijmegen Heyendaal”. The first train station has four platforms (1, 3, 4, and 35), some of which are subdivided into an “a” and “b” section. The second, local station only has two platforms.

stop_time

Stop times are the main component of a timetable. The data in this table can be used to deduce which lines serve a particular stop, when vehicles arrive and depart at stops, how many stops a line has (and skips), and what the distance between each stop is.

transfer

Transfers between lines sometimes require you to walk from one stop or platform to another. This may take a considerable amount of time – especially on larger stations – which is why GTFS provides a way to define minimal transfer times.

Network graph

Let’s say we want to travel from Radboud University in Nijmegen, whose nearest station is Nijmegen Heyendaal, to the University of Amsterdam’s Science Park campus, which has its own Amsterdam Science Park station. How would we go about this?

Normal people don’t try to navigate through public transport networks by looking at timetables, and neither should we. What we need is a map of the network, like the one below:

A (slightly) outdated map of the Dutch railway network. Click on the image for a larger version. Reproduced without permission, because I found the original a bit hard to read.

node

For simplicity’s sake we’re going to combine stops that are very similar to each other. For instance, instead of the 13 “Nijmegen” stops that we saw earlier, we now only need one node that represents the entire station, including all of its platforms.

We’ll also add a node_id field to the stop table, so that we can keep track of the relationship between nodes in the graph and corresponding stops in the timetable.

edge

Edges can be created from stop_time by joining the table with itself in such a way that the result contains every way to travel directly from one node to another.

Of course, not all edges are equal, so we also need to assign weights to each edge. I haven’t really thought this part through, so I’m just going to use the traversed distance (along the route) and the total number of stops that will be made by the train.

Sometimes there are multiple ways to travel between nodes, e.g. two nodes might be directly connected by an intercity (express) service, or a local train that takes a meandering route. In such cases we’ll store the shortest distance and number of stops as the weights.

Poor man’s pathfinding

Now that we have a graph with weighted edges, we can start working on a pathfinding algorithm. SQL isn’t exactly known as a nice programming language, so to make my life easier I’m not going to use a fancy solution like scalable transfer patterns, but an approach that resembles the horrendously inefficient – but easy to implement – breadth-first search (BFS) algorithm.

BFS is an algorithm that can find the shortest path between a start node and a destination node in a graph. It does this by iteratively exploring the graph “layer by layer”, where each layer consists of nodes that are directly adjacent to the current node and have not been visited yet. This process is repeated until the algorithm has found a path to the destination node or has traversed the entire graph.

I expect that our implementation will be very unoptimised and slow. To ease the pain somewhat I’ll try to limit our search to only a part of the graph. The following query determines which nodes can be visited by our pathfinding algorithm:

SELECT DISTINCT
    node_id
FROM
    stop
INNER JOIN (
    SELECT
        -- 0.25 latitude and 0.20 longitude should be roughly equivalent
        -- to 22 kilometres in the Netherlands
        MIN(latitude)  - 0.25 AS min_lat,
        MAX(latitude)  + 0.25 AS max_lat,
        MIN(longitude) - 0.20 AS min_lon,
        MAX(longitude) + 0.20 AS max_lon
    FROM
        stop
    WHERE
        node_id IN (
            21601, -- Nijmegen Heyendaal (start)
            21473  -- Amsterdam Science Park (destination)
        )
) bounding_box ON
    latitude BETWEEN min_lat AND max_lat
    AND
    longitude BETWEEN min_lon AND max_lon
    AND
    -- This is a stupid hack to remove anything that’s not clearly a
    -- train station, as bus/tram/metro stops in this dataset tend to
    -- have names that include both a place and a street name, e.g.
    -- “Amsterdam, Rokin”.
    name NOT LIKE '%,%'

Common table expressions

We’ll implement our pathfinding algorithm using common table expressions. A common table expression (CTE) is a named temporary result set that can be used as a reusable building block within the scope of a single SQL statement, almost as if it were a view.

Although this may sound a bit vague, it’s actually quite simple. In the snippet below we convert our previous query into a CTE named allowed_node, and use it to find all of Nijmegen’s train stations that are located within our search space:

WITH allowed_node (node_id) AS (
    SELECT DISTINCT
        node_id
    FROM
        stop
    INNER JOIN (
        SELECT
            -- 0.25 latitude and 0.20 longitude should be roughly equivalent
            -- to 22 kilometres in the Netherlands
            MIN(latitude)  - 0.25 AS min_lat,
            MAX(latitude)  + 0.25 AS max_lat,
            MIN(longitude) - 0.25 AS min_lon,
            MAX(longitude) + 0.25 AS max_lon
        FROM
            stop
        WHERE
            node_id IN (
                21601, -- Nijmegen Heyendaal (start)
                21473  -- Amsterdam Science Park (destination)
            )
    ) bounding_box ON
        latitude BETWEEN min_lat AND max_lat
        AND
        longitude BETWEEN min_lon AND max_lon
        AND
        -- This is a stupid hack to remove anything that’s not clearly a
        -- train station, as bus/tram/metro stops in this dataset tend to
        -- have names that include both a place and a street name, e.g.
        -- “Amsterdam, Rokin”.
        name NOT LIKE '%,%'
)
SELECT
    *
FROM
    node
WHERE
    id IN (SELECT node_id FROM allowed_node)
    AND
    name LIKE 'Nijmegen%'
ORDER BY
    1

As you can see, it’s just like querying a normal table – except that now we define that table within the same query and the CTE ceases to exist once the query has finished.

According to this query, the city of Nijmegen has five train stations that may be considered by our pathfinding algorithm for journeys between Nijmegen Heyendaal and Amsterdam Science Park:

Finding adjacent nodes

As I mentioned earlier, the first step of our pathfinding algorithm involves finding nodes that are directly adjacent to the start node. The code snippet below shows that we can easily do this by querying the edge table. Feel free to ignore the non-highlighted parts; they’re still the same as in the previous snippet.

WITH allowed_node (node_id) AS (
    SELECT DISTINCT
        node_id
    FROM
        stop
    INNER JOIN (
        SELECT
            -- 0.25 latitude and 0.20 longitude should be roughly equivalent
            -- to 22 kilometres in the Netherlands
            MIN(latitude)  - 0.25 AS min_lat,
            MAX(latitude)  + 0.25 AS max_lat,
            MIN(longitude) - 0.25 AS min_lon,
            MAX(longitude) + 0.25 AS max_lon
        FROM
            stop
        WHERE
            node_id IN (
                21601, -- Nijmegen Heyendaal (start)
                21473  -- Amsterdam Science Park (destination)
            )
    ) bounding_box ON
        latitude BETWEEN min_lat AND max_lat
        AND
        longitude BETWEEN min_lon AND max_lon
        AND
        -- This is a stupid hack to remove anything that’s not clearly a
        -- train station, as bus/tram/metro stops in this dataset tend to
        -- have names that include both a place and a street name, e.g.
        -- “Amsterdam, Rokin”.
        name NOT LIKE '%,%'
)
SELECT
    CONCAT(from_node_id, ' – ', to_node_id) AS path,
    stops,
    distance
FROM
    edge
WHERE
    from_node_id = 21601 -- Nijmegen Heyendaal (start)
    AND
    to_node_id IN (SELECT node_id FROM allowed_node)
ORDER BY
    stops,
    distance

Executing this query gives us the following result:

Let’s make it recursive

A recursive (and very chonky) version of the previous query can be found below. Again, feel free to ignore the parts that haven’t been highlighted.

WITH RECURSIVE
    allowed_node (node_id) AS (
        SELECT DISTINCT
            node_id
        FROM
            stop
        INNER JOIN (
            SELECT
                -- 0.25 latitude and 0.20 longitude should be roughly equivalent
                -- to 22 kilometres in the Netherlands
                MIN(latitude)  - 0.25 AS min_lat,
                MAX(latitude)  + 0.25 AS max_lat,
                MIN(longitude) - 0.25 AS min_lon,
                MAX(longitude) + 0.25 AS max_lon
            FROM
                stop
            WHERE
                node_id IN (
                    21601, -- Nijmegen Heyendaal (start)
                    21473  -- Amsterdam Science Park (destination)
                )
        ) bounding_box ON
            latitude BETWEEN min_lat AND max_lat
            AND
            longitude BETWEEN min_lon AND max_lon
            AND
            -- This is a stupid hack to remove anything that’s not clearly a
            -- train station, as bus/tram/metro stops in this dataset tend to
            -- have names that include both a place and a street name, e.g.
            -- “Amsterdam, Rokin”.
            name NOT LIKE '%,%'
    ),
    possible_path (nodes, transfers, stops, distance, current_node) AS (
        -- Base case
        SELECT
            CONCAT(' – ', CAST(from_node_id AS CHAR(255)), ' – '),
            0,
            stops,
            distance,
            to_node_id
        FROM
            edge
        WHERE
            from_node_id = 21601 -- Nijmegen Heyendaal (start)
            AND
            to_node_id IN (SELECT node_id FROM allowed_node)

        UNION ALL

        -- Recursive case
        SELECT
            CONCAT(nodes, from_node_id, ' – '),
            transfers + 1,
            possible_path.stops + edge.stops,
            possible_path.distance + edge.distance,
            to_node_id
        FROM
            possible_path
        INNER JOIN
            edge ON
                current_node = from_node_id
        WHERE
            -- Only consider nodes within that rectangular bounding box that we
            -- discussed earlier.
            to_node_id IN (SELECT node_id FROM allowed_node)
            AND
            -- Used to detect cycles within a possible path. It makes no sense
            -- to visit the same station twice!
            nodes NOT LIKE CONCAT('% – ', to_node_id, ' – %')
            AND
            -- This basically sets the number of “layers” that our pathfinding
            -- algorithm is allowed to explore. With transfers set to 3, the
            -- execution time is roughly a second on my machine. With 4 it’s
            -- about 20 seconds. I haven’t tried to set it to 5, but it’ll
            -- probably take *very* long to complete.
            transfers < 3
    )
SELECT DISTINCT
    -- The SUBSTRING() is used to remove the leading “ – ” that we added in the
    -- base case.
    SUBSTRING(CONCAT(nodes, current_node), 4) AS path,
    transfers,
    stops,
    distance
FROM
    possible_path
WHERE
    current_node = 21473 -- Amsterdam Science Park (destination)
ORDER BY
    -- This seems to work reasonably well as a way to score different paths. The
    -- basic idea is that direct connections (fewer transfers) are preferred
    -- over journeys with many transfers, and intercity/express trains (fewer
    -- stops) are preferred over slower, local trains (many stops).
    transfers * stops,
    distance
LIMIT
    5 -- Completely arbitrary limit

There’s a lot to unpack here, so let’s break it down.

We added the RECURSIVE keyword on the first line to indicate that at least one of the common table expressions in this statement is recursive.

The allowed_node CTE hasn’t changed, but we have added a second possible_path CTE that works recursively. This CTE has five fields (nodes, transfers, stops, distance and current_node) and consists of two parts: a base case and a recursive case, which are combined into a single result set using some UNION ALL magic.

The base case handles the first leg of the journey. It’s a modified version of the previous query. We have added two new fields, transfers and current_node. transfers keeps track of the number of times that a traveller would have to change trains, while current_node is the id of the node that is being visited by the pathfinding algorithm.

The recursive case handles all parts of the journey that require a transfer. This is where most of the magic happens. The base case previously yielded a set of all nodes that can be reached directly from the start node. In the recursive case, we now do the same for each of those adjacent nodes. Having said that, it differs from the base case in several ways:

• We now need to keep track of state. This is done in three ways: The sequence of visited nodes is stored as a string, to which we append new nodes using the CONCAT() function. The number of transfers and stops, and travelled distance are stored as integers and modified using addition (+). Finally, the to_node_id from the previous case is simply overwritten with the new value.

• To make sure we don’t visit a station more than once, we verify that a node isn’t already part of a sequence of nodes.

• It’d also be nice if the recursion terminates at some point. The query above achieves this by limiting the maximum number of transfers to 3. This doesn’t make a lot of sense for a real journey planner, but is good enough for our little toy project.

Querying the recursive possible_path CTE is easy. We simply select from possible_path as if it were a regular table. The destination node can be set using the WHERE clause.

You might be wondering why we don’t also filter by the start node here. That’s because it’s still hardcoded inside the possible_path CTE. This is done for stupid performance reasons; it appears that MySQL struggles to cache intermediate query results when we convert it into a variable. It’s ugly, but it gets the job done.

Anyway, executing this query gives us the following result:

Here is a slightly different version of that same table that uses node names in place of meaningless ids:

As it turns out, the path in the first row is indeed the best way to travel from Nijmegen Heyendaal to Amsterdam Science Park!

We can’t pat ourselves on the back yet though, because this still doesn’t tell us which trains we should take. Head over to part 2 if you’re eager to find out how that works!