Вообще если хочется прям а-ля яндекс, то задача достаточно нетривиальная и вариантов много. Если нет, то самое банальное решение поиск сначала точного вхождения всей фразы и отдача этого результата в верху подсказки. Далее то же для n-1 граммы (минус последнее слово) и отдачей результата во вторую очередь. Затем поиск по отдельным словам и отдачей в третью очередь.
Если есть желание заморочиться, можно придумать много интересных подзадач: поиск с учетом морфологии, предлогов, приведение фразы к единому виду (например размеры: 120 на 120, 120*120, 120х120, 120 120), учитывать сокращения, логировать частотность поисковых фраз и искать с ее учетом, исправление опечаток, языка ввода при неверной раскладке и так далее.
Или просто прикрутить поисковый движек. Сфинкс или Эластиксёрч.