And again about recursive queries
This post will cover how to write recursive queries. This topic has been raised more than once and not twice, but usually everything is limited to simple “wooden” cases: descend from the top to the leaves, rise from the top to the root. We will deal with a more complicated case of an arbitrary graph.
Let's start with repeating the theory (very briefly, because everything is clear with it), and then we will talk about what to do if it is not clear how to approach the real task, or seemingly understandable, but the query does not want to work hard.
For the exercise, we will use the demo database, described in detail earlier , and try to write a query in it to search for the shortest path from one airport to another.
Good old relational SQL does well with unordered sets: for them, both in the language itself and under the hood, the DBMS has a whole arsenal of tools. What SQL doesn't like is when it is pulled in a loop, line by line, instead of performing a task with a single statement. The optimizer lowers hands and moves aside, and you are left alone with performance.
')
So a recursive query is such a way to arrange a loop right inside SQL. Not that it is needed very often, but sometimes it still happens. And here begins the complexity, since the recursive query is not very similar to a normal query, much less a normal cycle.
The general scheme of the recursive query is as follows:
First, the non-recursive part (1) is executed. Then the recursive part (2) is executed until it returns any rows. The recursive part is called so because it can refer to the result of the previous iteration, which is available to it under the name t.
Along the way, the result of each iteration is added to the resulting table, which will be available under the same name t after the entire query has completed (3). If instead of UNION ALL we write UNION, then duplicate rows will be eliminated at each iteration.
In the form of a pseudo-code, it can be represented like this:
A simple example:
Well, enough to remember. If already at this stage, not everything is clear, it's time to read the documentation .
Armed with the theory, we can now (theoretically) take and write the query mentioned above: finding the shortest path from, say, Ust-Kut (UKX) to Neryungri (CNN).
From the entire demo database, we need two tables: airports (airports) and routes (routes). Formally, routes are a materialized view, but you can not think about it. (If you are not familiar with the structure of the demonstration base, see its description .)
A query might look like this:
This, of course, is great, but how to get to it, when there is still nothing on the screen, except for a blinking cursor?
For example, I can not write such a request from the head. Therefore, we will move consistently.
So we need to get a path. The route from point A to point B is a sequence of flights. The first flight takes off from And somewhere, the next one - from somewhere somewhere else and so on, until the last flight ends at the search point B. This is a chain of flights with a fixed start, fixed end and unknown middle, and we need to find.
How to present such a chain? From a relational point of view, it would be logical for it to be a table with columns number in order and airport . But we need to work with the chain as one object, so the most convenient is to present it with an array: [ airport , airport , ...]. (If there are difficulties with this, then read about arrays and functions for working with them.)
Where to start the iteration is clear: from the airport in Ust-Kut.
Why not just ARRAY ['UKX']? It is useful to insure a bit: if you suddenly get stuck in the airport code, the request will not return anything.
Now let's imagine that the result of this initial iteration lies in the table, and we need to do the second iteration. You can do this: create and fill in a table and write queries with it. But it is easier to use WITH:
We called the hops column so as not to get confused. In addition, we added one more ( last_arrival ) for the last item in our future chain. Instead, one could calculate the last element of the array (p.hops [cardinality (p.hops)]), but this is not so clear.
Now the second iteration:
What have we done? We took the first iteration (table p) and connected it to the routes. We indicated the last airport from our chain as the airport of departure, and added the airport of arrival to the chain on the right. It turns out that you can fly from Ust-Kut to Krasnoyarsk alone.
Now it is more or less clear how to build a recursive query. Add the magic word RESURSIVE, and combine the query with the first iteration using UNION ALL. And in the main query, we select the chain, which ultimately led to the destination airport (CNN).
Like that?
Hm Postgres is upset that the second column is of type character (3) [] in the non-recursive part (non-recursive term), but in general the type is bpchar []. The type bpchar (blank-padded char) is the internal name for the type char; unfortunately, concatenation of arrays does not preserve the type of elements, so explicit type conversion is required.
There is no more error, but alas - the request has hung. And now what i can do?
We'll figure out. Let's try to execute our query “step by step” and see what happens at each iteration.
It is clear that the focus can be repeated with the first iteration crammed into the table and the gradual addition of new iterations, but this is very dreary, and it is easy to make a mistake. But there is a better way.
Let's add to our query another column with an iteration number (let's call it level). In the first iteration, it will be equal to one, and then we will increase it. This in itself does not help, but now we can stop the execution of the request anywhere. The first two iterations we saw, let's look at the third:
Something unexpected.
First, some lines are duplicated (for example, {UKX, KJA, OVB}). This is, in fact, correct, because there are two different flights from Krasnoyarsk (KJA) to Novosibirsk (OVB):
Add the flight number to the request to distinguish the lines; we still need it.
But the other oddity is worse. One of the lines shows that we can fly back: {UKX, KJA, UKX}. And this means that we will fly in a circle indefinitely, the request will not stop. Here is the key to freeze.
What to do with it? It is necessary to add a condition that each airport can be visited no more than once (in this case, the route will still not be optimal).
It seems now order. Run without limits?
Formally, now everything should work out ... but the request hangs again, and if you have patience, you may fall with the error "the place for temporary files has ended."
Why is that? And because we have to build all possible paths of arbitrary length from point A, and only at the very end we select those that end at point B. This, to put it mildly, is not the most efficient algorithm. To understand the scale of the disaster, you can see how many lines are obtained at each step by changing the level limit to:
Well and so on, and each following request works significantly slower than the previous one.
Let's think about what number we expect to see in the answer? If we had big cities, then, most likely, 2 (with a transfer in Moscow). In our case, it is expected to add at least another couple on regional flights in order to fly to a major city. That is somewhere 4 or 5, well, maybe 6. However, the request is not going to stop at eight either: it will reach (if you have enough strength and health) up to a hundred, until it can extend any of the chains!
In this case, the algorithm works "in width": first, we add all the paths with a length of 1, then all the paths with a length of 2, and so on. That is, as soon as we find at least some first path from A to B, this path will be the shortest (in the number of transfers). The question now is how to stop the search in time.
The idea is to set the “path found” attribute at each step if at least one of the newly constructed paths ends at the destination. Then we can write down the stop condition.
Let's start by adding a destination to the request itself (before that, it only appeared at the very end, when it came to filtering all the results found). We calculate it at the very beginning, and in the recursive part of the query we simply leave it unchanged:
Now it is easy to calculate the sign of the found path: it must be set if the last point of the path coincides with the destination for at least one line. For this we need the bool_or window function (if window functions are something new for you, start with an introduction , at the end of which there are references to a more detailed description).
Here we checked how the request will work for the route from Ust-Kut (UKX) to Novosibirsk (OVB), which, as we already know, has a length of 3. (By the way, for this, you had to change CNN to OVB only in one place - a trifle, but nice.) Everything works!
The sign we are calculating and in the non-recursive part of the query. One could simply write false, but the request would be more universal and would correctly determine the number of transfers from A to A.
It remains to add a stop condition and you can run:
That's all. We came to the request from the beginning of the article, and it works out instantly. Now you can remove the "debug" level ... but you can leave.
Let's summarize the useful tricks:
To consolidate the skill, you can perform several variations on the same topic.
When you cope with the third task - share your success with us ( edu@postgrespro.ru ). And we will be happy to present an invitation to PgConf.Russia 2017 to the authors of the solutions you like.
Let's start with repeating the theory (very briefly, because everything is clear with it), and then we will talk about what to do if it is not clear how to approach the real task, or seemingly understandable, but the query does not want to work hard.
For the exercise, we will use the demo database, described in detail earlier , and try to write a query in it to search for the shortest path from one airport to another.
Some theory
Good old relational SQL does well with unordered sets: for them, both in the language itself and under the hood, the DBMS has a whole arsenal of tools. What SQL doesn't like is when it is pulled in a loop, line by line, instead of performing a task with a single statement. The optimizer lowers hands and moves aside, and you are left alone with performance.
')
So a recursive query is such a way to arrange a loop right inside SQL. Not that it is needed very often, but sometimes it still happens. And here begins the complexity, since the recursive query is not very similar to a normal query, much less a normal cycle.
The general scheme of the recursive query is as follows:
WITH RECURSIVE t AS (
(1)
UNION ALL
(2)
)
SELECT * FROM t; (3)
First, the non-recursive part (1) is executed. Then the recursive part (2) is executed until it returns any rows. The recursive part is called so because it can refer to the result of the previous iteration, which is available to it under the name t.
Along the way, the result of each iteration is added to the resulting table, which will be available under the same name t after the entire query has completed (3). If instead of UNION ALL we write UNION, then duplicate rows will be eliminated at each iteration.
In the form of a pseudo-code, it can be represented like this:
res ← EMPTY;
t ← ( );
WHILE t IS NOT EMPTY LOOP
res ← res UNION ALL t;
aux ← ( );
t ← aux;
END LOOP;
t ← res;
A simple example:
demo=# WITH RECURSIVE t(n,factorial) AS (
VALUES (0,1)
UNION ALL
SELECT t.n+1, t.factorial*(t.n+1) FROM t WHERE tn < 5
)
SELECT * FROM t;
n | factorial
---+-----------
0 | 1
1 | 1
2 | 2
3 | 6
4 | 24
5 | 120
(6 )
Well, enough to remember. If already at this stage, not everything is clear, it's time to read the documentation .
Practice
Armed with the theory, we can now (theoretically) take and write the query mentioned above: finding the shortest path from, say, Ust-Kut (UKX) to Neryungri (CNN).
From the entire demo database, we need two tables: airports (airports) and routes (routes). Formally, routes are a materialized view, but you can not think about it. (If you are not familiar with the structure of the demonstration base, see its description .)
A query might look like this:
WITH RECURSIVE p(last_arrival, destination, hops, flights, found) AS (
SELECT a_from.airport_code,
a_to.airport_code,
ARRAY[a_from.airport_code],
ARRAY[]::char(6)[],
a_from.airport_code = a_to.airport_code
FROM airports a_from, airports a_to
WHERE a_from.airport_code = 'UKX'
AND a_to.airport_code = 'CNN'
UNION ALL
SELECT r.arrival_airport,
p.destination,
(p.hops || r.arrival_airport)::char(3)[],
(p.flights || r.flight_no)::char(6)[],
bool_or(r.arrival_airport = p.destination) OVER ()
FROM routes r, p
WHERE r.departure_airport = p.last_arrival
AND NOT r.arrival_airport = ANY(p.hops)
AND NOT p.found
)
SELECT hops,
flights
FROM p
WHERE p.last_arrival = p.destination;
This, of course, is great, but how to get to it, when there is still nothing on the screen, except for a blinking cursor?
In this place of the cassette he always thinks that he accidentally put a beer on the rewind button: the dancers no longer viciously parody Randy himself and suddenly begin to move in a completely professional manner. It seems that the movements are the same as before, but damn it, if you can distinguish them in creative execution. There is no smooth transition, this is what infuriates and always infuriated Randy in these video tutorials. Any idiot can learn basic steps in half an hour. But when half an hour expires, the coach for some reason waits for you to start to flutter around the stage, as if the captions “a few years” flashed by. Probably, the humanities in mathematics lessons feel the same, Randy thinks. Here the teacher writes a couple of simple equations on the blackboard, and ten minutes later the speed of light in a vacuum is already deduced from them.
- Neil Stephenson, "Kryptonomicon" (my translation)
For example, I can not write such a request from the head. Therefore, we will move consistently.
So we need to get a path. The route from point A to point B is a sequence of flights. The first flight takes off from And somewhere, the next one - from somewhere somewhere else and so on, until the last flight ends at the search point B. This is a chain of flights with a fixed start, fixed end and unknown middle, and we need to find.
How to present such a chain? From a relational point of view, it would be logical for it to be a table with columns number in order and airport . But we need to work with the chain as one object, so the most convenient is to present it with an array: [ airport , airport , ...]. (If there are difficulties with this, then read about arrays and functions for working with them.)
Where to start the iteration is clear: from the airport in Ust-Kut.
demo=# SELECT ARRAY[airport_code] FROM airports WHERE airport_code = 'UKX';
array
-------
{UKX}
(1 )
Why not just ARRAY ['UKX']? It is useful to insure a bit: if you suddenly get stuck in the airport code, the request will not return anything.
Now let's imagine that the result of this initial iteration lies in the table, and we need to do the second iteration. You can do this: create and fill in a table and write queries with it. But it is easier to use WITH:
demo=# WITH p(last_arrival, hops) AS (
SELECT airport_code,
ARRAY[airport_code]
FROM airports
WHERE airport_code = 'UKX'
)
SELECT * FROM p;
last_arrival | hops
--------------+-------
UKX | {UKX}
(1 )
We called the hops column so as not to get confused. In addition, we added one more ( last_arrival ) for the last item in our future chain. Instead, one could calculate the last element of the array (p.hops [cardinality (p.hops)]), but this is not so clear.
Now the second iteration:
demo=# WITH p(last_arrival, hops) AS (
SELECT airport_code,
ARRAY[airport_code]
FROM airports
WHERE airport_code = 'UKX'
)
SELECT r.arrival_airport AS last_arrival,
p.hops || ARRAY[r.arrival_airport] AS hops
FROM routes r, p
WHERE r.departure_airport = p.last_arrival;
last_arrival | hops
--------------+-----------
KJA | {UKX,KJA}
(1 )
What have we done? We took the first iteration (table p) and connected it to the routes. We indicated the last airport from our chain as the airport of departure, and added the airport of arrival to the chain on the right. It turns out that you can fly from Ust-Kut to Krasnoyarsk alone.
Now it is more or less clear how to build a recursive query. Add the magic word RESURSIVE, and combine the query with the first iteration using UNION ALL. And in the main query, we select the chain, which ultimately led to the destination airport (CNN).
Like that?
demo=# WITH RECURSIVE p(last_arrival, hops) AS (
SELECT airport_code,
ARRAY[airport_code]
FROM airports
WHERE airport_code = 'UKX'
UNION ALL
SELECT r.arrival_airport,
p.hops || r.arrival_airport
FROM routes r, p
WHERE r.departure_airport = p.last_arrival
)
SELECT *
FROM p
WHERE p.last_arrival = (
SELECT airport_code FROM airports WHERE airport_code = 'CNN'
);
: "p" 2 character(3)[] , bpchar[]
3: ARRAY[airport_code]
^
: .
Hm Postgres is upset that the second column is of type character (3) [] in the non-recursive part (non-recursive term), but in general the type is bpchar []. The type bpchar (blank-padded char) is the internal name for the type char; unfortunately, concatenation of arrays does not preserve the type of elements, so explicit type conversion is required.
demo=# WITH RECURSIVE p(last_arrival, hops) AS (
SELECT airport_code,
ARRAY[airport_code]
FROM airports
WHERE airport_code = 'UKX'
UNION ALL
SELECT r.arrival_airport,
( p.hops || r.arrival_airport )::char(3)[]
FROM routes r, p
WHERE r.departure_airport = p.last_arrival
)
SELECT *
FROM p
WHERE p.last_arrival = (
SELECT airport_code FROM airports WHERE airport_code = 'CNN'
);
There is no more error, but alas - the request has hung. And now what i can do?
We'll figure out. Let's try to execute our query “step by step” and see what happens at each iteration.
It is clear that the focus can be repeated with the first iteration crammed into the table and the gradual addition of new iterations, but this is very dreary, and it is easy to make a mistake. But there is a better way.
Let's add to our query another column with an iteration number (let's call it level). In the first iteration, it will be equal to one, and then we will increase it. This in itself does not help, but now we can stop the execution of the request anywhere. The first two iterations we saw, let's look at the third:
demo=# WITH RECURSIVE p(last_arrival, hops, level ) AS (
SELECT airport_code,
ARRAY[airport_code],
1
FROM airports
WHERE airport_code = 'UKX'
UNION ALL
SELECT r.arrival_airport,
(p.hops || r.arrival_airport)::char(3)[],
p.level + 1
FROM routes r, p
WHERE r.departure_airport = p.last_arrival
AND p.level < 3
)
SELECT * FROM p;
last_arrival | hops | level
--------------+---------------+-------
UKX | {UKX} | 1
KJA | {UKX,KJA} | 2
UKX | {UKX,KJA,UKX} | 3
OVB | {UKX,KJA,OVB} | 3
OVB | {UKX,KJA,OVB} | 3
NOZ | {UKX,KJA,NOZ} | 3
NOZ | {UKX,KJA,NOZ} | 3
AER | {UKX,KJA,AER} | 3
SVO | {UKX,KJA,SVO} | 3
NUX | {UKX,KJA,NUX} | 3
UIK | {UKX,KJA,UIK} | 3
UIK | {UKX,KJA,UIK} | 3
BAX | {UKX,KJA,BAX} | 3
KRO | {UKX,KJA,KRO} | 3
OVS | {UKX,KJA,OVS} | 3
(15 )
Something unexpected.
First, some lines are duplicated (for example, {UKX, KJA, OVB}). This is, in fact, correct, because there are two different flights from Krasnoyarsk (KJA) to Novosibirsk (OVB):
demo=# SELECT flight_no
FROM routes
WHERE departure_airport = 'KJA'
AND arrival_airport = 'OVB';
flight_no
-----------
PG0206
PG0207
(2 )
Add the flight number to the request to distinguish the lines; we still need it.
demo=# WITH RECURSIVE p(last_arrival, hops, flights, level) AS (
SELECT airport_code,
ARRAY[airport_code],
ARRAY[]::char(6)[],
1
FROM airports
WHERE airport_code = 'UKX'
UNION ALL
SELECT r.arrival_airport,
(p.hops || r.arrival_airport)::char(3)[],
(p.flights || r.flight_no)::char(6)[],
p.level + 1
FROM routes r, p
WHERE r.departure_airport = p.last_arrival
AND p.level < 3
)
SELECT * FROM p;
last_arrival | hops | flights | level
--------------+---------------+-----------------+-------
UKX | {UKX} | {} | 1
KJA | {UKX,KJA} | {PG0022} | 2
UKX | {UKX,KJA,UKX} | {PG0022,PG0021} | 3
OVB | {UKX,KJA,OVB} | {PG0022,PG0206} | 3
OVB | {UKX,KJA,OVB} | {PG0022,PG0207} | 3
NOZ | {UKX,KJA,NOZ} | {PG0022,PG0351} | 3
NOZ | {UKX,KJA,NOZ} | {PG0022,PG0352} | 3
AER | {UKX,KJA,AER} | {PG0022,PG0501} | 3
SVO | {UKX,KJA,SVO} | {PG0022,PG0548} | 3
NUX | {UKX,KJA,NUX} | {PG0022,PG0623} | 3
UIK | {UKX,KJA,UIK} | {PG0022,PG0625} | 3
UIK | {UKX,KJA,UIK} | {PG0022,PG0626} | 3
BAX | {UKX,KJA,BAX} | {PG0022,PG0653} | 3
KRO | {UKX,KJA,KRO} | {PG0022,PG0673} | 3
OVS | {UKX,KJA,OVS} | {PG0022,PG0689} | 3
(15 )
But the other oddity is worse. One of the lines shows that we can fly back: {UKX, KJA, UKX}. And this means that we will fly in a circle indefinitely, the request will not stop. Here is the key to freeze.
What to do with it? It is necessary to add a condition that each airport can be visited no more than once (in this case, the route will still not be optimal).
demo=# WITH RECURSIVE p(last_arrival, hops, flights, level) AS (
SELECT airport_code,
ARRAY[airport_code],
ARRAY[]::char(6)[],
1
FROM airports
WHERE airport_code = 'UKX'
UNION ALL
SELECT r.arrival_airport,
(p.hops || r.arrival_airport)::char(3)[],
(p.flights || r.flight_no)::char(6)[],
p.level + 1
FROM routes r, p
WHERE r.departure_airport = p.last_arrival
AND NOT r.arrival_airport = ANY(p.hops)
AND p.level < 3
)
SELECT * FROM p;
last_arrival | hops | flights | level
--------------+---------------+-----------------+-------
UKX | {UKX} | {} | 1
KJA | {UKX,KJA} | {PG0022} | 2
OVB | {UKX,KJA,OVB} | {PG0022,PG0206} | 3
OVB | {UKX,KJA,OVB} | {PG0022,PG0207} | 3
NOZ | {UKX,KJA,NOZ} | {PG0022,PG0351} | 3
NOZ | {UKX,KJA,NOZ} | {PG0022,PG0352} | 3
AER | {UKX,KJA,AER} | {PG0022,PG0501} | 3
SVO | {UKX,KJA,SVO} | {PG0022,PG0548} | 3
NUX | {UKX,KJA,NUX} | {PG0022,PG0623} | 3
UIK | {UKX,KJA,UIK} | {PG0022,PG0625} | 3
UIK | {UKX,KJA,UIK} | {PG0022,PG0626} | 3
BAX | {UKX,KJA,BAX} | {PG0022,PG0653} | 3
KRO | {UKX,KJA,KRO} | {PG0022,PG0673} | 3
OVS | {UKX,KJA,OVS} | {PG0022,PG0689} | 3
(14 )
It seems now order. Run without limits?
demo=# WITH RECURSIVE p(last_arrival, hops, flights, level) AS (
SELECT airport_code,
ARRAY[airport_code],
ARRAY[]::char(6)[],
1
FROM airports
WHERE airport_code = 'UKX'
UNION ALL
SELECT r.arrival_airport,
(p.hops || r.arrival_airport)::char(3)[],
(p.flights || r.flight_no)::char(6)[],
p.level + 1
FROM routes r, p
WHERE r.departure_airport = p.last_arrival
AND NOT r.arrival_airport = ANY(p.hops)
-- AND p.level < 3
)
SELECT *
FROM p
WHERE p.last_arrival = (
SELECT airport_code FROM airports WHERE airport_code = 'CNN'
);
Formally, now everything should work out ... but the request hangs again, and if you have patience, you may fall with the error "the place for temporary files has ended."
Why is that? And because we have to build all possible paths of arbitrary length from point A, and only at the very end we select those that end at point B. This, to put it mildly, is not the most efficient algorithm. To understand the scale of the disaster, you can see how many lines are obtained at each step by changing the level limit to:
eleven 2 2 3 14 4,165 5 1978 6 22322 7 249942 8 2316063
Well and so on, and each following request works significantly slower than the previous one.
Let's think about what number we expect to see in the answer? If we had big cities, then, most likely, 2 (with a transfer in Moscow). In our case, it is expected to add at least another couple on regional flights in order to fly to a major city. That is somewhere 4 or 5, well, maybe 6. However, the request is not going to stop at eight either: it will reach (if you have enough strength and health) up to a hundred, until it can extend any of the chains!
In this case, the algorithm works "in width": first, we add all the paths with a length of 1, then all the paths with a length of 2, and so on. That is, as soon as we find at least some first path from A to B, this path will be the shortest (in the number of transfers). The question now is how to stop the search in time.
The idea is to set the “path found” attribute at each step if at least one of the newly constructed paths ends at the destination. Then we can write down the stop condition.
Let's start by adding a destination to the request itself (before that, it only appeared at the very end, when it came to filtering all the results found). We calculate it at the very beginning, and in the recursive part of the query we simply leave it unchanged:
demo=# WITH RECURSIVE p(last_arrival, destination, hops, flights, level) AS (
SELECT a_from.airport_code,
a_to.airport_code,
ARRAY[a_from.airport_code],
ARRAY[]::char(6)[],
1
FROM airports a_from, airports a_to
WHERE a_from.airport_code = 'UKX'
AND a_to.airport_code = 'CNN'
UNION ALL
SELECT r.arrival_airport,
p.destination,
(p.hops || r.arrival_airport)::char(3)[],
(p.flights || r.flight_no)::char(6)[],
p.level + 1
FROM routes r, p
WHERE r.departure_airport = p.hops[cardinality(p.hops)]
AND NOT r.arrival_airport = ANY(p.hops)
AND p.level < 3
)
SELECT * FROM p;
last_arrival | destination | hops | flights | level
--------------+-------------+---------------+-----------------+-------
UKX | CNN | {UKX} | {} | 1
KJA | CNN | {UKX,KJA} | {PG0022} | 2
OVB | CNN | {UKX,KJA,OVB} | {PG0022,PG0206} | 3
OVB | CNN | {UKX,KJA,OVB} | {PG0022,PG0207} | 3
NOZ | CNN | {UKX,KJA,NOZ} | {PG0022,PG0351} | 3
NOZ | CNN | {UKX,KJA,NOZ} | {PG0022,PG0352} | 3
AER | CNN | {UKX,KJA,AER} | {PG0022,PG0501} | 3
SVO | CNN | {UKX,KJA,SVO} | {PG0022,PG0548} | 3
NUX | CNN | {UKX,KJA,NUX} | {PG0022,PG0623} | 3
UIK | CNN | {UKX,KJA,UIK} | {PG0022,PG0625} | 3
UIK | CNN | {UKX,KJA,UIK} | {PG0022,PG0626} | 3
BAX | CNN | {UKX,KJA,BAX} | {PG0022,PG0653} | 3
KRO | CNN | {UKX,KJA,KRO} | {PG0022,PG0673} | 3
OVS | CNN | {UKX,KJA,OVS} | {PG0022,PG0689} | 3
(14 )
Now it is easy to calculate the sign of the found path: it must be set if the last point of the path coincides with the destination for at least one line. For this we need the bool_or window function (if window functions are something new for you, start with an introduction , at the end of which there are references to a more detailed description).
demo=# WITH RECURSIVE p(last_arrival, destination, hops, flights, found, level) AS (
SELECT a_from.airport_code,
a_to.airport_code,
ARRAY[a_from.airport_code],
ARRAY[]::char(6)[],
a_from.airport_code = a_to.airport_code,
1
FROM airports a_from, airports a_to
WHERE a_from.airport_code = 'UKX'
AND a_to.airport_code = 'OVB' -- CNN
UNION ALL
SELECT r.arrival_airport,
p.destination,
(p.hops || r.arrival_airport)::char(3)[],
(p.flights || r.flight_no)::char(6)[],
bool_or(r.arrival_airport = p.destination) OVER (),
p.level + 1
FROM routes r, p
WHERE r.departure_airport = p.last_arrival
AND NOT r.arrival_airport = ANY(p.hops)
AND p.level < 3
)
SELECT * FROM p;
last_arrival | destination | hops | flights | found | level
--------------+-------------+---------------+-----------------+-------+-------
UKX | OVB | {UKX} | {} | f | 1
KJA | OVB | {UKX,KJA} | {PG0022} | f | 2
OVB | OVB | {UKX,KJA,OVB} | {PG0022,PG0206} | t | 3
OVB | OVB | {UKX,KJA,OVB} | {PG0022,PG0207} | t | 3
NOZ | OVB | {UKX,KJA,NOZ} | {PG0022,PG0351} | t | 3
NOZ | OVB | {UKX,KJA,NOZ} | {PG0022,PG0352} | t | 3
AER | OVB | {UKX,KJA,AER} | {PG0022,PG0501} | t | 3
SVO | OVB | {UKX,KJA,SVO} | {PG0022,PG0548} | t | 3
NUX | OVB | {UKX,KJA,NUX} | {PG0022,PG0623} | t | 3
UIK | OVB | {UKX,KJA,UIK} | {PG0022,PG0625} | t | 3
UIK | OVB | {UKX,KJA,UIK} | {PG0022,PG0626} | t | 3
BAX | OVB | {UKX,KJA,BAX} | {PG0022,PG0653} | t | 3
KRO | OVB | {UKX,KJA,KRO} | {PG0022,PG0673} | t | 3
OVS | OVB | {UKX,KJA,OVS} | {PG0022,PG0689} | t | 3
(14 )
Here we checked how the request will work for the route from Ust-Kut (UKX) to Novosibirsk (OVB), which, as we already know, has a length of 3. (By the way, for this, you had to change CNN to OVB only in one place - a trifle, but nice.) Everything works!
The sign we are calculating and in the non-recursive part of the query. One could simply write false, but the request would be more universal and would correctly determine the number of transfers from A to A.
It remains to add a stop condition and you can run:
demo=# WITH RECURSIVE p(last_arrival, destination, hops, flights, found, level) AS (
SELECT a_from.airport_code,
a_to.airport_code,
ARRAY[a_from.airport_code],
ARRAY[]::char(6)[],
a_from.airport_code = a_to.airport_code,
1
FROM airports a_from, airports a_to
WHERE a_from.airport_code = 'UKX'
AND a_to.airport_code = 'CNN'
UNION ALL
SELECT r.arrival_airport,
p.destination,
(p.hops || r.arrival_airport)::char(3)[],
(p.flights || r.flight_no)::char(6)[],
bool_or(r.arrival_airport = p.destination) OVER (),
p.level + 1
FROM routes r, p
WHERE r.departure_airport = p.last_arrival
AND NOT r.arrival_airport = ANY(p.hops)
AND NOT p.found
-- AND p.level < 3
)
SELECT hops, flights
FROM p
WHERE p.last_arrival = p.destination;
hops | flights
-----------------------+-------------------------------
{UKX,KJA,OVB,MJZ,CNN} | {PG0022,PG0206,PG0390,PG0035}
{UKX,KJA,OVB,MJZ,CNN} | {PG0022,PG0207,PG0390,PG0035}
{UKX,KJA,SVO,MJZ,CNN} | {PG0022,PG0548,PG0120,PG0035}
{UKX,KJA,OVB,MJZ,CNN} | {PG0022,PG0206,PG0390,PG0036}
{UKX,KJA,OVB,MJZ,CNN} | {PG0022,PG0207,PG0390,PG0036}
{UKX,KJA,SVO,MJZ,CNN} | {PG0022,PG0548,PG0120,PG0036}
{UKX,KJA,OVS,LED,CNN} | {PG0022,PG0689,PG0686,PG0245}
{UKX,KJA,SVO,LED,CNN} | {PG0022,PG0548,PG0472,PG0245}
{UKX,KJA,SVO,LED,CNN} | {PG0022,PG0548,PG0471,PG0245}
{UKX,KJA,SVO,LED,CNN} | {PG0022,PG0548,PG0470,PG0245}
{UKX,KJA,SVO,LED,CNN} | {PG0022,PG0548,PG0469,PG0245}
{UKX,KJA,SVO,LED,CNN} | {PG0022,PG0548,PG0468,PG0245}
{UKX,KJA,OVB,PEE,CNN} | {PG0022,PG0206,PG0186,PG0394}
{UKX,KJA,OVB,PEE,CNN} | {PG0022,PG0207,PG0186,PG0394}
{UKX,KJA,BAX,ASF,CNN} | {PG0022,PG0653,PG0595,PG0427}
{UKX,KJA,SVO,ASF,CNN} | {PG0022,PG0548,PG0128,PG0427}
{UKX,KJA,OVS,DME,CNN} | {PG0022,PG0689,PG0544,PG0709}
{UKX,KJA,OVS,DME,CNN} | {PG0022,PG0689,PG0543,PG0709}
{UKX,KJA,KRO,DME,CNN} | {PG0022,PG0673,PG0371,PG0709}
{UKX,KJA,OVB,DME,CNN} | {PG0022,PG0206,PG0223,PG0709}
{UKX,KJA,OVB,DME,CNN} | {PG0022,PG0207,PG0223,PG0709}
{UKX,KJA,NUX,DME,CNN} | {PG0022,PG0623,PG0165,PG0709}
{UKX,KJA,BAX,DME,CNN} | {PG0022,PG0653,PG0117,PG0709}
(23 )
That's all. We came to the request from the beginning of the article, and it works out instantly. Now you can remove the "debug" level ... but you can leave.
Let's summarize the useful tricks:
- Representing the “path” as an array helps in many cases. You can concatenate strings instead, but this is less convenient.
- Prevent looping (using the same array).
- Debugging by limiting the number of iterations.
- Sometimes to improve performance you need a way to stop in time.
- Using window functions allows you to work wonders.
As an exercise
To consolidate the skill, you can perform several variations on the same topic.
- What is the maximum number of transfers you need to get from any airport to any other?
Tip 1: The first part of the request should contain all pairs of airports of departure and arrival.
Tip 2: a sign of the path found must be considered separately for each pair of airports. - Find a path (from UKX to CNN) that is optimal for the total duration of flights (excluding the expectation of transfers).
Tip 1: it may turn out that such a path is not optimal in terms of the number of transplants.
Tip 2: you need to come up with a sign that further search is useless. - Find a path (from UKX to CNN) that is optimal for the total duration of flights , taking into account the waiting time for transfers. Consider that we are ready for the first flight at the time of
bookings.now() - interval '20 days'.
When you cope with the third task - share your success with us ( edu@postgrespro.ru ). And we will be happy to present an invitation to PgConf.Russia 2017 to the authors of the solutions you like.
Source: https://habr.com/ru/post/318398/
All Articles