Префикс это начальная последовательность символов незавершенного запроса. Автодополнение это подбор и сортировка кандидатов по этому префиксу до того, как пользователь закончил ввод.
Система хранит отдельный словарь кандидатов с весами. При вводе «gam» она ищет не любое вхождение подстроки, а совпадение с началом слова или фразы, причем проверять может каждое слово внутри названия, а не только первое. Кандидаты приходят из нескольких источников сразу: названия, подборки, разделы.
Читать: Solr Suggester; Elasticsearch: suggesters; Обзор A Survey of Query Auto Completion in Information Retrieval; Патент Apple US8364694B2