Ну совсем тупой вариант
select * from (select
least(city.id, city2.id) as id1,
greatest(city.id, city2.id) as id2
from city
join city as city2 on city.id != city2.id
group by least(city.id, city2.id), greatest(city.id, city2.id)
) as t join city as city1 on city1.id = id1 join city as city2 on city2.id = id2;
Если подумать
то конечно можно проще
select
LEAST(city.name, city1.name), GREATEST(city.name, city1.name)
from city
inner join city as city1 on city1.id != city.id
GROUP BY LEAST(city.name, city1.name), GREATEST(city.name, city1.name);