Оптимальная реализация поиска и сортировки объектов с фиксированным количеством полей?
Есть объект с фиксированным количеством полей.
Необходимо реализовать поиск по заранее неизвестному количеству полей и сортировку по одному из полей.
Допустим есть поля field1, field2 и field3. В один момент времени может потребоваться поиск только по field1, в другой — по field1 и field3, в третий по всем вместе, и одновременно с этим нужна возможность сортировки по одному из этих полей.
Каково решение? Не хочется перегружать таблицу большим количеством индексов перебирая все возможные варианты фильтра (полей в реальной задаче 15)
Исходные данные: mySQL и PHP
Как я вижу решение:
создать один общий индекс
1) index idx1(field1, field2, field3)
и по одному индексу на каждое поле, в котором нужна сортировка:
2) index idx2(field2)
3) index idx3(field3)
Итого доступна сортировка по каждому из 3-х полей, плюс полный поиск
А запрос формировать так, чтобы всегда использовались все компоненты индекса.
Т.е. если нужен поиск только по field2 и field3, а поле field1 например foreign key (int, unsigned, null), т.е. не может быть 0, то where должно получиться следующим:
field1 > 0 AND field2 = 'searchValue2' AND field3 = 'searchValue3'
Решение:
MySQL оптимизирует обращение к индексу. Основное требование — наличие крайнего левого компонента.
Т.е. если есть индекс field1, field2, field3, то в любом запросе главное, чтобы присутствовал первый компонент, а остальные, промежуточные компоненты, не используемые в текущем запросе, могут отсутствовать, лишь бы не нарушился порядок следования компонентов
> А запрос формировать так, чтобы всегда использовались все компоненты индекса.
> Т.е. если нужен поиск только по field2 и field3, а поле field1 например foreign key (int, unsigned, null), т.е. не может быть 0, то where должно получиться следующим:
> field1 > 0 AND field2 = 'searchValue2' AND field3 = 'searchValue3'
В данном случае будет использоваться только часть индекса idx1 (которая использует field1), т.е. MySQL будет идти по индексу idx1, начиная с первой записи, где field1 > 0, заканчивая концом таблицы, и для каждой записи проверять условия field2/field3. То есть индекс idx1 (field1) дал бы тот же эффект.
Если столбцов много (миллионы-миллиарды), то обычный подход с индексами и WHERE не подойдет. Не так давно я сталкивался с подобной проблемой. Варианты я вижу такие:
1. Sphinx. Предназначен для полнотекстового поиска, но может искать и только по числовым полям (при docinfo=extern). Если записей в базе много, то он сильно расходует память. Работает быстро.
2. Таблицы в памяти. Аналогично п. 1.
3. EAV или хранение каждого поля в отдельной таблице. Немного медленнее, если пользователь задал мало параметров, и намного — если много.
4. OLAP-подобные способы. Самые большие требования к памяти и к дисковому пространству (при большом количестве вариантов — запредельные), но быстрый поиск по большому количеству параметров.
Для себя я решил, что оптимальный вариант — это Sphinx (docinfo=inline) при необходимости текстового поиска, а при отсутствии такой необходимости — комбинированный вариант п. 3 и 4, т.е. OLAP-подобная индексация работает только для наиболее частых вариантов полей.
Спасибо, сфинкс используем в других проектах.
Но сейчас вопрос — классическая реализация задачи. Записей до 10000 если наберется за пару лет — будет хорошо, так что записей мало. Но поиск сейчас жутко тормознутый — запросы до 80ms на продакшене, в то время как практически все остальные страницы с трудом за 50ms переваливают.
>Записей до 10000 если наберется за пару лет — будет хорошо, так что записей мало
На таких объемах я бы делал индексы по каждой колонке и на наболее чеастые комбинации. Нечему там тормозить…
Sphinx и не стоит что-то придумывать, в добавок есть SphinxQL, что сильно облегчает миграцию. У нас более миллиона записей, довольно объемных, ищет очень быстро.
Ха, делаете поиск по пользователям в очередной недосоциальной сети или сайте знакомств? ну-ну, на майскуле с кучей индексов ваш поиск будет работать ровно до 10 000 пользователей. Вообще, стоило бы сначала изучить, какие параметры используют чаще для поиска, и делать индексы по ним.
С ростом числа юзеров, как вариант костыля на первое время, можно попробовать прикрутить сфинкс или какой-нибудь Lucene, но с ростом нагрузки все равно этот функционал придется выносить в отдельный кастомный модуль. Спросите у вконтактеров, например, как у них сделан поиск по людям (отдельным модулем на Си).
Еще можно кстати изучить вопрос с созданием индекса в отдельной таблице, с полями типа user_id, field_name, int_value, string_value, но тут надо проводить тесты, я так не скажу, выгоднее это или нет.
Не стоит делать поспешные выводы о прикладном назначении. В любом случае вопрос абсолютно не об этом и описан абстрагировано от области применения, т.к. она как бы не влияет на решение.
Вы говорите, даже не вникнув задачу — необходим одновременный поиск по нескольким параметрам
Хранить все поля в одной таблице — плохое решение, оно может быть применимо лишь к объектам с динамическим количеством полей. У меня же их заранее известное статическое количество, так что калечить систему нет надобности, а сделать ее быстрее — нужно. Остается вопрос — как правильнее? (с возможностью масштабирования в последствии — вдруг заказчик добавит пару критериев)
> необходим одновременный поиск по нескольким параметрам
Если у вас 15 полей, лучшее, что вы можете сделать на MySQL — одиночные индексы на каждое поле. И то, подозреваю, 15 индексов резко нагрузят вставку/обновление записей и каждый следующий инlекс только ухудшит ситуацию. Чтобы работал поиск + сортировка по индексу, нужны двойные индексы, и их число уже получается заоблачным.
И вы не указали, сколько у вас записей, как часто будут приходить поисковые запросы — это тоже важно, может в данном случае можно просто тупо таблицу в память запихать (или настроить MySQL, чтобы у нее был большой буфер для кусков таблиц, или прямо использовать таблицу типа MEMORY) и не мучаться с индексами.
Средний
