Задача - сделать поиск с выпадающим авто-дополнением. Задача усложняется тем что поиск может быть и на украинском и на русском и на английском, а подсказки надо давать красиво и только на украинском.

Как первичный источник данных был выбран XML собранный из википедии, основное достоинство которого - наличие написания населенных пунктах на разных языках.

Первая идея была - залить все в таблицу MySQL, натравить на нее Sphinx и дело в шляпе. Как показали эксперименты - мимо, причин две - отсутствие украинского стемминга у сфинкса и в больше степени то что вся база это имена собственные, которые он не "любит". Результаты поиска сфинксом были далеки от ожидаемых - оно даже работало местами но результаты были не пригодны для использования.

Далее было решено попробовать старые, и местами забытые, полнотекстовые индексы и поиск MySQL.

Структура таблицы для хранения:

CREATE TABLE `koatuu`
(
 `id` BIGINT(10) NOT NULL,
    `type` INTEGER NOT NULL,
    `title` VARCHAR(255) NOT NULL,
    `wikipedia` VARCHAR(255),
    `variants` LONGTEXT,
    `zip_from` INTEGER,
    `zip_till` INTEGER,
    `latitude` DOUBLE NOT NULL,
    `longitude` DOUBLE NOT NULL,
    `location` Point NOT NULL,
    PRIMARY KEY (`id`),
    SPATIAL INDEX `koatuu_i_a79bf5` (`location`)
) ENGINE=MyISAM;

CREATE TRIGGER db.`create_koatuu_point_geom`
BEFORE INSERT ON db.koatuu FOR EACH ROW
 BEGIN
    SET NEW.location = POINT(NEW.latitudeNEW.longitude);
  END;

CREATE TRIGGER db.`update_koatuu_point_geom`
BEFORE UPDATE ON db.koatuu FOR EACH ROW
 BEGIN
    SET NEW.location = POINT(NEW.latitudeNEW.longitude);
  END;

ALTER TABLE `koatuu` ADD FULLTEXT INDEX `search` (`title``variants`) ;

данные после выгрузки из XML в БД выглядят примерно так:

Выборка разбита на два этапа - выборка списка id который удовлетворяет искомой фразе, второй этап - выбор по списку id списка населенных пунктов.

Предположим, мы хотим найти Власовку, запросы для автодополнения по 5 символам получились такие:

SELECT id FROM `koatuu` WHERE MATCH (title,variants) AGAINST ('Власо*' IN BOOLEAN MODE) ORDER BY type ASC, MATCH (title,variants) AGAINST ('Власо*' IN BOOLEAN MODE) LIMIT 20;

Обратите внимание, тут используется несколько усложненная сортировка - хотелось что-бы в списке результатов сначала шли крупные города, потом поселки и села, тип населенного пункта в таблице задан полем type. 

Результирующая выборка:

3510945300
7421782403
3220286702
5321381601
6323180801
4421481102

Теперь выбираем собственно записи, обратите внимание на сортировку в запросе - сделано это для того что-бы вернуть записи в порядке задания списка id, который у нас отсортирован первым запросом по релевантности.

SELECT * from `koatuu` WHERE id IN(3510945300, 7421782403, 3220286702, 5321381601, 6323180801, 4421481102) ORDER BY FIND_IN_SET(id, '3510945300,7421782403,3220286702,5321381601,6323180801,4421481102');

Полученный результат, причем обратите внимание - пгт. Власовка(type = 2) идет первым, далее села.

PROFIT!

Код который получился в любимом ORM Propel:

class KoatuuQuery extends BaseKoatuuQuery
{
    public function filterByMatch($query)
    {
        $sql "SELECT id FROM `koatuu` WHERE MATCH (title,variants) AGAINST (? IN BOOLEAN MODE) ORDER BY type ASC, MATCH (title,variants) AGAINST (? IN BOOLEAN MODE)";

        $con = Propel::getServiceContainer()->getReadConnection($this->getDbName());

        $stmt $con->prepare($sql);
        $stmt->bindValue(1$query.'*');
        $stmt->bindValue(2$query.'*');

        $ids = [];
        if ($stmt->execute()) {
            while($id $stmt->fetchColumn()) {
                $ids[] = $id;
            }
        }

        return $this->filterById($idsCriteria::IN)->addAscendingOrderByColumn('FIND_IN_SET(id, \''.implode(','$ids).'\')'Criteria::RAW);
    }
}

Используется так:

foreach(KoatuuQuery::create()->filterByMatch($text)->limit(50)->find() as $koatuu) {

    //....
}

Дисклеймер: С точки зрения производительности - на текущей базе в 25тыс+ населенных пунктов проблем нет вообще никаких, НО на сильно бОльших объемах нужно вероятно внимательнее подойти к структурам и алгоритмам.