Как осуществить поиск неточных совпадений по MySQL?

Приветствую!
Как осуществить подобного рода поиск по MySQL и реально ли это вообще?

Строка поиска: г Санкт-Петербург, тер Авиагородок
Строка в таблице: Авиагородок, Санкт-Петербург

Строка поиска: г Санкт-Петербург, тер. снт Торики
Строка в таблице: Торики, Красносельский р-н, Санкт-Петербург

Строка поиска: г Санкт-Петербург
Строка в таблице: Санкт-Петербург

Строка поиска: г Москва, Воскресенское п, п Воскресенское
Строка в таблице: Воскресенское поселение, Московская обл.

Плюс, нужно ранжировать - при запросе г Москва результат Москва должен иметь приоритет над результатами Десеновское, Москва и Бутово Южное, Москва.

И т. п., записей около 16 тыс., поиск производится один раз на каждого уника (проект не хайлоад, нишевый интернет-магазин).
Пробовал колдовать с FULLTEXT-поиском, но пока ничего дельного не вышло.
Рассматривается применение сторонних модулей - Sphinx, Elastic, может, даже nosql базы для каких-то промежуточных операций, но рабочей БД проекта является именно MySQL.
Сейчас главное - понять, в какую сторону копнуть.

Всем спасибо, в итоге удалось написать свой алгоритм, основанный на простых условиях и утверждении, что сегменты адреса в наших данных находятся в обратном порядке относительно исходного адреса.
Запрос разбивается по запятым, вырезаются все типы (р-н, район, обл, АО, г, поселок, хутор, снт и .п.), "разворачивается", затем последовательно производится поиск: город+район+регион, город+регион, город. Поиск останавливается на уровне, на котором появился результат.