В действительности вы описали связь "многие ко многим".
Один пользователь может быть связан с несколькими городами и к одному городу может быть привязано несколько пользователей.
Вам нужно реализовать подобную структуру в БД
А дальше нужны грамотные индексы по таблицам.
В таблице связей первичный ключ делаете составным из 2х полей