Query (or algorithm?) to find cheapest overlapping flights from two distinct locations to one shared location

user_2693851 0
Viewed 89

Say we have a dataset of 500 000 flights from Los Angeles to 80 cities in Europe and back and from Saint Petersburg to same 80 cities in Europe and back. We want to find such 4 flights:

  • from LA to city X, from city X back to LA, from St P to city X and from city X back to St P
  • all 4 flights have to be in a time window of 4 days
  • we are looking for the cheapest combined price of 4 flights
  • city X can be any of 80 cities, we want to find such cheapest combination for all of them and get the list of these 80 combinations

The data is stored in BigQuery and I've created an SQL query, but it has 3 joins and I assume that under the hood it can have complexity of O(n^4), because the query didn't finish in 30 minutes and I had to abort it.

Here's the schema for the table:

enter image description here

See the query below:

select * from (
  select in_led.`from` as city, 
    in_led.price + out_led.price + in_lax.price + out_lax.price as total_price,
    out_led.carrier as out_led_carrier, 
    out_led.departure as out_led_departure, 
    in_led.departure as in_led_date, 
    in_led.carrier as in_led_carrier, 
    out_lax.carrier as out_lax_carrier, 
    out_lax.departure as out_lax_departure, 
    in_lax.departure as in_lax_date, 
    in_lax.carrier as in_lax_carrier, 
    row_number() over(partition by in_led.`from` order by in_led.price + out_led.price + in_lax.price + out_lax.price) as rn
  from skyscanner.quotes as in_led
  join skyscanner.quotes as out_led on out_led.`to` = in_led.`from`
  join skyscanner.quotes as out_lax on out_lax.`to` = in_led.`from`
  join skyscanner.quotes as in_lax on in_lax.`from` = in_led.`from`
  where in_led.`to` = "LED"
    and out_led.`from` = "LED"
    and in_lax.`to` in ("LAX", "LAXA")
    and out_lax.`from` in ("LAX", "LAXA")
    and DATE_DIFF(DATE(in_led.departure), DATE(out_led.departure), DAY) < 4
    and DATE_DIFF(DATE(in_led.departure), DATE(out_led.departure), DAY) > 0
    and DATE_DIFF(DATE(in_lax.departure), DATE(out_lax.departure), DAY) < 4
    and DATE_DIFF(DATE(in_lax.departure), DATE(out_lax.departure), DAY) > 0
  order by total_price
) 
where rn=1

Additional details:

  • all flights' departure dates fall in a 120 days window

Questions:

  1. Is there a way to optimize this query for better performance?
  2. How to properly classify this problem? The brute force solution is way too slow, but I'm failing to see what type of problem this is. Certainly doesn't look like something for graphs, kinda feels like sorting the table a couple of times by different fields with a stable sort might help, but still seems sub-optimal.
google-bigquery sql algorithm
2 Answers

the query didn't finish in 30 minutes and I had to abort it.
Is there a way to optimize this query for better performance?

My "generic recommendation" is to always learn the data, profile it, clean it - before actual coding! In your example - the data you shared has 469352 rows full of duplicates. After you remove duplicates - you got ONLY 14867 rows. So then I run your original query against that cleaned data and it took ONLY 97 sec to get result. Obviously, it does not mean we cannot optimize code itself - but at least this addresses your issue with "query didn't finish in 30 minutes and I had to abort it"

user_52219440

Below is for BigQuery Standard SQL

The brute force solution is way too slow, but I'm failing to see what type of problem this is. so I would like to see solutions other than brute force if anyone here has ideas

#standardSQL
WITH temp AS (
  SELECT DISTINCT *, UNIX_DATE(DATE(departure)) AS dep FROM `skyscanner.quotes`
), round_trips AS (
  SELECT t1.from, t1.to, t2.to AS back, t1.price, t1.departure, t1.dep first_day, t1.carrier, t2.departure AS departure2, t2.dep AS last_day, t2.price AS price2, t2.carrier AS carrier2, 
  FROM temp t1
  JOIN temp t2
  ON t1.to = t2.from
  AND t1.from = t2.to
  AND t2.dep BETWEEN t1.dep + 1 AND t1.dep + 3
  WHERE t1.from IN ('LAX', 'LED')
)
SELECT cityX, total_price,
  ( SELECT COUNT(1)
    FROM UNNEST(GENERATE_ARRAY(t1.first_day, t1.last_day)) day
    JOIN UNNEST(GENERATE_ARRAY(t2.first_day, t2.last_day)) day
    USING(day)
  ) overlap_days_in_cityX, 
  (SELECT AS STRUCT departure, price, carrier, departure2, price2, carrier2 
    FROM UNNEST([t1])) AS LAX_CityX_LAX, 
  (SELECT AS STRUCT departure, price, carrier, departure2, price2, carrier2 
    FROM UNNEST([t2])) AS LED_CityX_LED
FROM (
  SELECT AS VALUE ARRAY_AGG(t ORDER BY total_price LIMIT 1)[OFFSET(0)]
  FROM (
    SELECT t1.to cityX, t1.price + t1.price2 + t2.price + t2.price2 AS total_price, t1, t2 
    FROM round_trips t1
    JOIN round_trips t2
    ON t1.to = t2.to
    AND t1.from < t2.from
    AND t1.departure2 > t2.departure
    AND t1.departure < t2.departure2
  ) t
  GROUP BY cityX
)
ORDER BY overlap_days_in_cityX DESC, total_price

with output (just top 10 out of total 60 rows)

enter image description here

Brief explanation:

  • temp CTE: Dedup data and introduce dep field - number of days since epoch to eliminate costly TIMESTAMP functions
  • round_trips CTE: identify all round trip candidates with at most 4 days apart
  • identify those LAX and LED round trips which have overlaps
  • for each cityX take the cheapest combination
  • final output does extra calculation on overlapping days in cityX and lean a little output to have info about all involve flights

Note: in your data - duration field are all zeros - so it is not involved - but if you would have it - it is easy to add it to logic

user_52219440
Related