Počítat vzdálenost mezi 400 městy a optimalizovat pro to MySQL?

Viděl jsem dvě možná řešení.

První:
Pro každé město uložte do databáze jeho zeměpisnou šířku a délku; když uživatel dostane dotaz, vypočítáte vzdálenost s každým dalším městem a vrátíte výsledky.
Profesem je, že můžete přidat každé město v db, aniž byste museli přidávat další informace.
Zde můžete také najít vzorce, vzorky a kód pro výpočet vzdálenosti zeměpisné šířky a délky...

Za druhé:
Vytvořte tabulku cities_dist se třemi poli:city1_id, city2_id, distance a vložte do každé možné kombinace mezi svými městy. S tím můžete napsat dotaz s vybraným městem ve tvaru city1_id nebo city2_id.
Výhodou je, že můžete použít jednoduchý dotaz bez jakéhokoli výpočtu, zatímco nevýhody jsou, že musíte vyplnit tuto tabulku kdykoli vložíte nové město do své databáze.

UPRAVENO po komentáři uživatele:
Představte si, že máte tři města

ID  NAME
1   New York
2   Rome
3   Berlin

Ta tabulka by měla vypadat takto

CITY1  CITY2  DIST
1      2      1500
1      3      1200
2      3       400

Když uživatel chce letět z Berlína, můžete použít

SELECT c1.name, c2.name, cd.dist 
FROM cities_dist cd
  INNER JOIN cities c1 ON cd.city1 = c1.id
  INNER JOIN cities c2 ON cd.city2 = c2.id
WHERE cd.city1 = your_id
   OR cd.city2 = your_id
ORDER BY cd.dist ASC