Ололёша Ололоев

Данная проблема называется "k-nearest neighbors", и существует очень много способов ее решения.

В целом они все сводятся к этому:

• Сначала нужно определить функцию расстояния для элементов из таблицы (т.е. юзеров). Это может быть как Эвклидово расстояние, так и любое другое (например, cosine или jaccard для слов из описания)
  
• Затем для каждого из юзеров находим N самых близких на основе этой функции
  
• Сравнивать всех пользователей со всеми - задача затратная, поэтому часто используются индексы для ускорения этого процесса. На уровне БД это может быть R-tree или quad-tree, а на уровне приложения - Locality Sensitive Hashing.
  

Порядок следования полей в индексе лучше всего определять для данных в вашей таблице.
Если вы хотите построить индекс для оптимизации какого-то определенного запроса, то существует правило, по которому колонки для индекса следует выбирать по selectivity условий в вашем запросе. Т.е. самой первой колонкой должна быть та, where условие для которой фильтрует больше всего записей.

И еще, попробуйте выборку поместить в подзапрос, а order by оставить во внешнем запросе

А если UUID использовать?