Recursive queries using Postgres

Question

In the table: flights (id,origin_apt, destination_apt, departure_time, arrival_time)

I need to build routes for the flight with the condition that there can be a direct flight from point A to point Z, and with transfers from point A to point B, then from point B to point Z and so on. The maximum number of transfers is 5.

I started to do this with requests in Postgres, but I managed to do only a direct flight and with one transfer

But to master the routes with 3-5 transfers, I do not have enough knowledge:

A -> Z

A -> B -> Z

A -> B -> C -> Z

A -> B -> C -> D -> Z

A -> B -> C -> D -> E -> Z

 WITH RECURSIVE segs AS ( SELECT f0.id::text as flights , origin_apt, destination_apt , departure_time AS departure , arrival_time AS arrival , 1 as hops , (arrival_time - departure_time)::interval AS total_time , '00:00'::interval as waiting_time FROM flights f0 WHERE origin_apt = 'SVX' -- <ORIGIN_APT = SVX> AND departure_time >= '2016-01-19' UNION ALL SELECT s.flights || '-->' || f1.id::text as flights , s.origin_apt, f1.destination_apt , s.departure AS departure , f1.arrival_time AS arrival , s.hops + 1 AS hops , s.total_time + (f1.arrival_time - f1.departure_time)::interval AS total_time , s.waiting_time + (f1.departure_time - s.arrival)::interval AS waiting_time FROM segs s JOIN flights f1 ON f1.origin_apt = s.destination_apt AND f1.departure_time >= s.arrival + '8 hour' -- <DEFAULT_TRANSIT_TIME = 8 hours > ) SELECT * FROM segs WHERE destination_apt = 'PEK' -- <DESTINATION_APT = PEK> AND waiting_time < '25 day'-- <DEFAULT_DELIVERY_DAYS = 25 day> ORDER BY departure, waiting_time asc;

Sample data:

 CREATE TABLE flights ( id serial NOT NULL, origin_apt character varying, destination_apt character varying, departure_time timestamp without time zone, arrival_time timestamp without time zone, CONSTRAINT flights_pkey PRIMARY KEY (id) ); insert into flights VALUES (1,'GOJ','TAS','2016-01-04 06:00','2016-01-04 11:30'), (2,'GOJ','TAS','2016-01-11 06:00','2016-01-11 11:30'), ('3','GOJ','TAS','2016-01-18 06:00','2016-01-18 11:30'), ('4','GOJ','TAS','2016-01-25 06:00','2016-01-25 11:30'), ('5','GOJ','TAS','2016-02-01 06:00','2016-02-01 11:30'), ('6','GOJ','TAS','2016-02-08 06:00','2016-02-08 11:30'), ('7','GOJ','TAS','2016-02-15 06:00','2016-02-15 11:30'), ('8','GOJ','TAS','2016-02-22 06:00','2016-02-22 11:30'), ('9','GOJ','TAS','2016-02-29 06:00','2016-02-29 11:30'), ('10','GOJ','TAS','2016-03-07 06:00','2016-03-07 11:30'), ('11','GOJ','TAS','2016-03-14 06:00','2016-03-14 11:30'), ('12','GOJ','TAS','2016-03-21 06:00','2016-03-21 11:30'), ('13','GOJ','DYU','2016-01-02 03:40','2016-01-02 09:30'), ('14','GOJ','DYU','2016-01-09 03:40','2016-01-09 09:30'), ('15','GOJ','DYU','2016-01-16 03:40','2016-01-16 09:30'), ('16','GOJ','DYU','2016-01-23 03:40','2016-01-23 09:30'), ('17','GOJ','DYU','2016-01-30 03:40','2016-01-30 09:30'), ('18','GOJ','DYU','2016-02-06 03:40','2016-02-06 09:30'), ('19','GOJ','DYU','2016-02-13 03:40','2016-02-13 09:30'), ('20','GOJ','DYU','2016-02-20 03:40','2016-02-20 09:30'), ('21','GOJ','DYU','2016-02-27 03:40','2016-02-27 09:30'), ('22','GOJ','DYU','2016-03-05 03:40','2016-03-05 09:30'), ('23','GOJ','DYU','2016-03-12 03:40','2016-03-12 09:30'), ('24','GOJ','DYU','2016-03-19 03:40','2016-03-19 09:30'), ('25','GOJ','DYU','2016-03-26 03:40','2016-03-26 09:30'), ('26','TAS','PEK','2016-01-06 13:40','2016-01-06 22:00'), ('27','TAS','PEK','2016-01-13 13:40','2016-01-13 22:00'), ('28','TAS','PEK','2016-01-20 13:40','2016-01-20 22:00'), ('29','TAS','PEK','2016-01-27 13:40','2016-01-27 22:00'), ('30','TAS','PEK','2016-02-03 13:40','2016-02-03 22:00'), ('31','TAS','PEK','2016-02-10 13:40','2016-02-10 22:00'), ('32','TAS','PEK','2016-02-17 13:40','2016-02-17 22:00'), ('33','TAS','PEK','2016-02-24 13:40','2016-02-24 22:00'), ('34','TAS','PEK','2016-03-02 13:40','2016-03-02 22:00'), ('35','TAS','PEK','2016-03-09 13:40','2016-03-09 22:00'), ('36','TAS','PEK','2016-03-16 13:40','2016-03-16 22:00'), ('37','TAS','PEK','2016-03-23 13:40','2016-03-23 22:00'), ('38','PRG','PEK','2016-01-08 13:00','2016-01-09 05:55'), ('39','PRG','PEK','2016-01-15 13:00','2016-01-16 05:55'), ('40','PRG','PEK','2016-01-22 13:00','2016-01-23 05:55'), ('41','PRG','PEK','2016-01-29 13:00','2016-01-30 05:55'), ('42','PRG','PEK','2016-02-05 13:00','2016-02-06 05:55'), ('43','PRG','PEK','2016-02-12 13:00','2016-02-13 05:55'), ('44','PRG','PEK','2016-02-19 13:00','2016-02-20 05:55'), ('45','PRG','PEK','2016-02-26 13:00','2016-02-27 05:55'), ('46','PRG','PEK','2016-03-04 13:00','2016-03-05 05:55'), ('47','PRG','PEK','2016-03-11 13:00','2016-03-12 05:55'), ('48','PRG','PEK','2016-03-18 13:00','2016-03-19 05:55'), ('49','PRG','PEK','2016-03-25 13:00','2016-03-26 05:55'), ('50','PRG','PEK','2016-01-04 13:00','2016-01-05 06:00'), ('51','PRG','PEK','2016-01-11 13:00','2016-01-12 06:00'), ('52','PRG','PEK','2016-01-18 13:00','2016-01-19 06:00'), ('53','PRG','PEK','2016-01-25 13:00','2016-01-26 06:00'), ('54','PRG','PEK','2016-02-01 13:00','2016-02-02 06:00'), ('55','PRG','PEK','2016-02-08 13:00','2016-02-09 06:00'), ('56','PRG','PEK','2016-02-15 13:00','2016-02-16 06:00'), ('57','PRG','PEK','2016-02-22 13:00','2016-02-23 06:00'), ('58','PRG','PEK','2016-02-29 13:00','2016-03-01 06:00'), ('59','PRG','PEK','2016-03-07 13:00','2016-03-08 06:00'), ('60','PRG','PEK','2016-03-14 13:00','2016-03-15 06:00'), ('61','PRG','PEK','2016-03-21 13:00','2016-03-22 06:00'), ('62','GYD','PEK','2016-01-03 19:20','2016-01-04 06:20'), ('63','GYD','PEK','2016-01-10 19:20','2016-01-11 06:20'), ('64','GYD','PEK','2016-01-17 19:20','2016-01-18 06:20'), ('65','GYD','PEK','2016-01-24 19:20','2016-01-25 06:20'), ('66','GYD','PEK','2016-01-31 19:20','2016-02-01 06:20'), ('67','GYD','PEK','2016-02-07 19:20','2016-02-08 06:20'), ('68','GYD','PEK','2016-02-14 19:20','2016-02-15 06:20'), ('69','GYD','PEK','2016-02-21 19:20','2016-02-22 06:20'), ('70','GYD','PEK','2016-02-28 19:20','2016-02-29 06:20'), ('71','GYD','PEK','2016-03-06 19:20','2016-03-07 06:20'), ('72','GYD','PEK','2016-03-13 19:20','2016-03-14 06:20'), ('73','GYD','PEK','2016-03-20 19:20','2016-03-21 06:20'), ('74','GYD','PEK','2016-03-27 19:20','2016-03-28 06:20'), ('75','MUC','SVX','2016-01-16 10:40','2016-01-16 19:20'), ('76','MUC','SVX','2016-01-23 10:40','2016-01-23 19:20'), ('77','MUC','SVX','2016-01-30 10:40','2016-01-30 19:20'), ('78','MUC','SVX','2016-02-06 10:40','2016-02-06 19:20'), ('79','MUC','SVX','2016-02-13 10:40','2016-02-13 19:20'), ('80','MUC','SVX','2016-02-20 10:40','2016-02-20 19:20'), ('81','MUC','SVX','2016-02-27 10:40','2016-02-27 19:20'), ('82','MUC','SVX','2016-03-05 10:40','2016-03-05 19:20'), ('83','MUC','SVX','2016-03-12 10:40','2016-03-12 19:20'), ('84','MUC','SVX','2016-03-19 10:40','2016-03-19 19:20'), ('85','MUC','SVX','2016-03-26 10:40','2016-03-26 19:20'), ('86','PRG','SVX','2016-01-07 16:25','2016-01-08 00:40'), ('87','PRG','SVX','2016-01-14 16:25','2016-01-15 00:40'), ('88','PRG','SVX','2016-01-21 16:25','2016-01-22 00:40'), ('89','PRG','SVX','2016-01-28 16:25','2016-01-29 00:40'), ('90','PRG','SVX','2016-02-04 16:25','2016-02-05 00:40'), ('91','PRG','SVX','2016-02-11 16:25','2016-02-12 00:40'), ('92','PRG','SVX','2016-02-18 16:25','2016-02-19 00:40'), ('93','PRG','SVX','2016-02-25 16:25','2016-02-26 00:40'), ('94','PRG','SVX','2016-03-03 16:25','2016-03-04 00:40'), ('95','PRG','SVX','2016-03-10 16:25','2016-03-11 00:40'), ('96','PRG','SVX','2016-03-17 16:25','2016-03-18 00:40'), ('97','PRG','SVX','2016-03-24 16:25','2016-03-25 00:40'), ('98','PRG','SVX','2016-01-03 10:10','2016-01-03 18:15'), ('99','PRG','SVX','2016-01-10 10:10','2016-01-10 18:15'), ('100','PRG','SVX','2016-01-17 10:10','2016-01-17 18:15'), ('101','PRG','SVX','2016-01-24 10:10','2016-01-24 18:15'), ('102','PRG','SVX','2016-01-31 10:10','2016-01-31 18:15'), ('103','PRG','SVX','2016-02-07 10:10','2016-02-07 18:15'), ('104','PRG','SVX','2016-02-14 10:10','2016-02-14 18:15'), ('105','PRG','SVX','2016-02-21 10:10','2016-02-21 18:15'), ('106','PRG','SVX','2016-02-28 10:10','2016-02-28 18:15'), ('107','PRG','SVX','2016-03-06 10:10','2016-03-06 18:15'), ('108','PRG','SVX','2016-03-13 10:10','2016-03-13 18:15'), ('109','PRG','SVX','2016-03-20 10:10','2016-03-20 18:15'), ('110','PRG','SVX','2016-03-27 10:10','2016-03-27 18:15'), ('111','SVX','GYD','2016-01-07 17:00','2016-01-07 19:00'), ('112','SVX','GYD','2016-01-14 17:00','2016-01-14 19:00'), ('113','SVX','GYD','2016-01-21 17:00','2016-01-21 19:00'), ('114','SVX','GYD','2016-01-28 17:00','2016-01-28 19:00'), ('115','SVX','GYD','2016-02-04 17:00','2016-02-04 19:00'), ('116','SVX','GYD','2016-02-11 17:00','2016-02-11 19:00'), ('117','SVX','GYD','2016-02-18 17:00','2016-02-18 19:00'), ('118','SVX','GYD','2016-02-25 17:00','2016-02-25 19:00'), ('119','SVX','GYD','2016-03-03 17:00','2016-03-03 19:00'), ('120','SVX','GYD','2016-03-10 17:00','2016-03-10 19:00'), ('121','SVX','GYD','2016-03-17 17:00','2016-03-17 19:00'), ('122','SVX','GYD','2016-03-24 17:00','2016-03-24 19:00'), ('123','SVX','GYD','2016-01-02 17:00','2016-01-02 19:00'), ('124','SVX','GYD','2016-01-09 17:00','2016-01-09 19:00'), ('125','SVX','GYD','2016-01-16 17:00','2016-01-16 19:00'), ('126','SVX','GYD','2016-01-23 17:00','2016-01-23 19:00'), ('127','SVX','GYD','2016-01-30 17:00','2016-01-30 19:00'), ('128','SVX','GYD','2016-02-06 17:00','2016-02-06 19:00'), ('129','SVX','GYD','2016-02-13 17:00','2016-02-13 19:00'), ('130','SVX','GYD','2016-02-20 17:00','2016-02-20 19:00'), ('131','SVX','GYD','2016-02-27 17:00','2016-02-27 19:00'), ('132','SVX','GYD','2016-03-05 17:00','2016-03-05 19:00'), ('133','SVX','GYD','2016-03-12 17:00','2016-03-12 19:00'), ('134','SVX','GYD','2016-03-19 17:00','2016-03-19 19:00'), ('135','SVX','GYD','2016-03-26 17:00','2016-03-26 19:00'), ('136','SVX','DYU','2016-01-07 06:45','2016-01-07 09:55'), ('137','SVX','DYU','2016-01-14 06:45','2016-01-14 09:55'), ('138','SVX','DYU','2016-01-21 06:45','2016-01-21 09:55'), ('139','SVX','DYU','2016-01-28 06:45','2016-01-28 09:55'), ('140','SVX','DYU','2016-02-04 06:45','2016-02-04 09:55'), ('141','SVX','DYU','2016-02-11 06:45','2016-02-11 09:55'), ('142','SVX','DYU','2016-02-18 06:45','2016-02-18 09:55'), ('143','SVX','DYU','2016-02-25 06:45','2016-02-25 09:55'), ('144','SVX','DYU','2016-03-03 06:45','2016-03-03 09:55'), ('145','SVX','DYU','2016-03-10 06:45','2016-03-10 09:55'), ('146','SVX','DYU','2016-03-17 06:45','2016-03-17 09:55'), ('147','SVX','DYU','2016-03-24 06:45','2016-03-24 09:55'), ('148','SVX','DYU','2016-01-05 06:45','2016-01-05 09:55'), ('149','SVX','DYU','2016-01-12 06:45','2016-01-12 09:55'), ('150','SVX','DYU','2016-01-19 06:45','2016-01-19 09:55'), ('151','SVX','DYU','2016-01-26 06:45','2016-01-26 09:55'), ('152','SVX','DYU','2016-02-02 06:45','2016-02-02 09:55'), ('153','SVX','DYU','2016-02-09 06:45','2016-02-09 09:55'), ('154','SVX','DYU','2016-02-16 06:45','2016-02-16 09:55'), ('155','SVX','DYU','2016-02-23 06:45','2016-02-23 09:55'), ('156','SVX','DYU','2016-03-01 06:45','2016-03-01 09:55'), ('157','SVX','DYU','2016-03-08 06:45','2016-03-08 09:55'), ('158','SVX','DYU','2016-03-15 06:45','2016-03-15 09:55'), ('159','SVX','DYU','2016-03-22 06:45','2016-03-22 09:55'), ('160','SVX','DYU','2016-01-02 06:45','2016-01-02 09:55'), ('161','SVX','DYU','2016-01-09 06:45','2016-01-09 09:55'), ('162','SVX','DYU','2016-01-16 06:45','2016-01-16 09:55'), ('163','SVX','DYU','2016-01-23 06:45','2016-01-23 09:55'), ('164','SVX','DYU','2016-01-30 06:45','2016-01-30 09:55'), ('165','SVX','DYU','2016-02-06 06:45','2016-02-06 09:55'), ('166','SVX','DYU','2016-02-13 06:45','2016-02-13 09:55'), ('167','SVX','DYU','2016-02-20 06:45','2016-02-20 09:55'), ('168','SVX','DYU','2016-02-27 06:45','2016-02-27 09:55'), ('169','SVX','DYU','2016-03-05 06:45','2016-03-05 09:55'), ('170','SVX','DYU','2016-03-12 06:45','2016-03-12 09:55'), ('171','SVX','DYU','2016-03-19 06:45','2016-03-19 09:55'), ('172','SVX','DYU','2016-03-26 06:45','2016-03-26 09:55'), ('173','SVX','TAS','2016-01-04 07:40','2016-01-04 10:50'), ('174','SVX','TAS','2016-01-11 07:40','2016-01-11 10:50'), ('175','SVX','TAS','2016-01-18 07:40','2016-01-18 10:50'), ('176','SVX','TAS','2016-01-25 07:40','2016-01-25 10:50'), ('177','SVX','TAS','2016-02-01 07:40','2016-02-01 10:50'), ('178','SVX','TAS','2016-02-08 07:40','2016-02-08 10:50'), ('179','SVX','TAS','2016-02-15 07:40','2016-02-15 10:50'), ('180','SVX','TAS','2016-02-22 07:40','2016-02-22 10:50'), ('181','SVX','TAS','2016-02-29 07:40','2016-02-29 10:50'), ('182','SVX','TAS','2016-03-07 07:40','2016-03-07 10:50'), ('183','SVX','TAS','2016-03-14 07:40','2016-03-14 10:50'), ('184','SVX','TAS','2016-03-21 07:40','2016-03-21 10:50'), ('185','SVX','PEK','2016-01-07 19:45','2016-01-08 04:00'), ('186','SVX','PEK','2016-01-14 19:45','2016-01-15 04:00'), ('187','SVX','PEK','2016-01-21 19:45','2016-01-22 04:00'), ('188','SVX','PEK','2016-01-28 19:45','2016-01-29 04:00'), ('189','SVX','PEK','2016-02-04 19:45','2016-02-05 04:00'), ('190','SVX','PEK','2016-02-11 19:45','2016-02-12 04:00'), ('191','SVX','PEK','2016-02-18 19:45','2016-02-19 04:00'), ('192','SVX','PEK','2016-02-25 19:45','2016-02-26 04:00'), ('193','SVX','PEK','2016-03-03 19:45','2016-03-04 04:00'), ('194','SVX','PEK','2016-03-10 19:45','2016-03-11 04:00'), ('195','SVX','PEK','2016-03-17 19:45','2016-03-18 04:00'), ('196','SVX','PEK','2016-03-24 19:45','2016-03-25 04:00'), ('197','SVX','PEK','2016-01-05 19:45','2016-01-06 04:00'), ('198','SVX','PEK','2016-01-12 19:45','2016-01-13 04:00'), ('199','SVX','PEK','2016-01-19 19:45','2016-01-20 04:00'), ('200','SVX','PEK','2016-01-26 19:45','2016-01-27 04:00'), ('201','SVX','PEK','2016-02-02 19:45','2016-02-03 04:00'), ('202','SVX','PEK','2016-02-09 19:45','2016-02-10 04:00'), ('203','SVX','PEK','2016-02-16 19:45','2016-02-17 04:00'), ('204','SVX','PEK','2016-02-23 19:45','2016-02-24 04:00'), ('205','SVX','PEK','2016-03-01 19:45','2016-03-02 04:00'), ('206','SVX','PEK','2016-03-08 19:45','2016-03-09 04:00'), ('207','SVX','PEK','2016-03-15 19:45','2016-03-16 04:00'), ('208','SVX','PEK','2016-03-22 19:45','2016-03-23 04:00'), ('209','SVX','PEK','2016-01-08 19:45','2016-01-09 04:00'), ('210','SVX','PEK','2016-01-15 19:45','2016-01-16 04:00'), ('211','SVX','PEK','2016-01-22 19:45','2016-01-23 04:00'), ('212','SVX','PEK','2016-01-29 19:45','2016-01-30 04:00'), ('213','SVX','PEK','2016-02-05 19:45','2016-02-06 04:00'), ('214','SVX','PEK','2016-02-12 19:45','2016-02-13 04:00'), ('215','SVX','PEK','2016-02-19 19:45','2016-02-20 04:00'), ('216','SVX','PEK','2016-02-26 19:45','2016-02-27 04:00'), ('217','SVX','PEK','2016-03-04 19:45','2016-03-05 04:00'), ('218','SVX','PEK','2016-03-11 19:45','2016-03-12 04:00'), ('219','SVX','PEK','2016-03-18 19:45','2016-03-19 04:00'), ('220','SVX','PEK','2016-03-25 19:45','2016-03-26 04:00'), ('221','SVX','PEK','2016-01-03 19:45','2016-01-04 04:00'), ('222','SVX','PEK','2016-01-10 19:45','2016-01-11 04:00'), ('223','SVX','PEK','2016-01-17 19:45','2016-01-18 04:00'), ('224','SVX','PEK','2016-01-24 19:45','2016-01-25 04:00'), ('225','SVX','PEK','2016-01-31 19:45','2016-02-01 04:00'), ('226','SVX','PEK','2016-02-07 19:45','2016-02-08 04:00'), ('227','SVX','PEK','2016-02-14 19:45','2016-02-15 04:00'), ('228','SVX','PEK','2016-02-21 19:45','2016-02-22 04:00'), ('229','SVX','PEK','2016-02-28 19:45','2016-02-29 04:00'), ('230','SVX','PEK','2016-03-06 19:45','2016-03-07 04:00'), ('231','SVX','PEK','2016-03-13 19:45','2016-03-14 04:00'), ('232','SVX','PEK','2016-03-20 19:45','2016-03-21 04:00'), ('233','SVX','PEK','2016-03-27 19:45','2016-03-28 04:00')

Mikhail Lutsko 203 one 15 · Accepted Answer · 2016-01-19T17:44:18

Your request can already choose any nested recursion. Your test benchmarks do not contain suitable routes, so that the query could issue more connections. When adding the insert into flights VALUES(234,'DYU','PRG','2016-02-18 09:00','2016-02-18 15:30') record insert into flights VALUES(234,'DYU','PRG','2016-02-18 09:00','2016-02-18 15:30') your query immediately starts to find a bunch of other options, Unfortunately, there are many with repeated flights through Koltsovo. So the request should be limited, not allowing you to choose routes in which the same AP occurs more than once. Like that:

  WITH RECURSIVE segs AS ( SELECT f0.id::text as flights ,'/'||origin_apt||'/'||destination_apt||'/' as route -- <-- Добавил полный маршрут , origin_apt, destination_apt , departure_time AS departure , arrival_time AS arrival , 1 as hops , (arrival_time - departure_time)::interval AS total_time , '00:00'::interval as waiting_time FROM flights f0 WHERE origin_apt = 'SVX' -- <ORIGIN_APT = SVX> AND departure_time >= '2016-01-19' UNION ALL SELECT s.flights || '-->' || f1.id::text as flights ,s.route||f1.destination_apt||'/' -- <-- добавляем АП посадки в маршрут , s.origin_apt, f1.destination_apt , s.departure AS departure , f1.arrival_time AS arrival , s.hops + 1 AS hops , s.total_time + (f1.arrival_time - f1.departure_time)::interval AS total_time , s.waiting_time + (f1.departure_time - s.arrival)::interval AS waiting_time FROM segs s JOIN flights f1 ON f1.origin_apt = s.destination_apt AND f1.departure_time >= s.arrival + '8 hour' -- <DEFAULT_TRANSIT_TIME = 8 hours > AND NOT s.route like '%/'||f1.destination_apt||'/%' -- <-- АП назначения не в полном маршруте AND s.hops < 5 ) SELECT * FROM segs WHERE destination_apt = 'PEK' -- <DESTINATION_APT = PEK> AND waiting_time < '25 day'-- <DEFAULT_DELIVERY_DAYS = 25 day> ORDER BY departure, waiting_time asc;

And how can you limit the request so that he would not build a route with more than 5 transfers, what would be the maximum A -> B -> C -> D -> E -> Z because now he builds requests with an unlimited number of of type A -> B -> C -> D -> E -> H -> J -> K -> X -> Z
In the second part of union AND s.hops<4 , the figure is 1 less, because it will add one flight after the condition has been worked out.

Recursive queries using Postgres

1 answer 1

More articles: