Инновации и инсайты в мире Java из первых уст. Новая конференция Java Fest — 21 марта >>
×Закрыть

Как делался сервис поисковых подсказок на prom.ua

На prom.ua есть сервис, предлагающий подсказки по мере ввода текста в строку поиска:

Несколько фактов о нем:

  • полнотекстовый поиск подсказок осуществляется среди миллиона фраз;
  • индекс из миллиона фраз занимает менее 100Мб оперативной памяти;
  • все запросы к сервису, идущие с prom.ua, обслуживаются по очереди одним процессом в одном потоке;
  • сервис написан на Python.

История развития сервиса

Сначала подсказки хранились в таблице БД (MongoDB), проиндексированной по фразам, приведенным к каноническому виду. Под каноническим видом понимается фраза в нижнем регистре с удаленными знаками пунктуации и без лишних пробелов. Чтобы показать подсказки к введенному пользователем запросу, этот запрос приводился к каноническому виду, а затем выполнялся запрос к MongoDB, который можно представить в виде SQL:

SELECT suggestion
FROM search_suggestions
WHERE text_canonical LIKE ‘search_query_canonical%’
ORDER BY weight DESC
LIMIT N

Таким образом, выборка делалась только по началу поисковой фразы и выводились первые N подсказок c максимальным весом. У этой реализации было две проблемы:

  • Запрос к БД мог тормозить, если под фильтр text_canonical LIKE ‘search_query_canonical%’ попадало слишком много фраз, которые нужно было отсортировать по весу и только затем выбрать первые N из них. Т.к. эта же MongoDB использовалась другими сервисами, то у этих сервисов могли начаться проблемы, если кто-то решал заDoSить сервис поисковых подсказок.
  • Поиск подсказок производился строго по полному совпадению с началом поискового запроса. Например, по запросу «платье» выводились подсказки «Платье женское», «платье летнее», но не выводились подсказки «женское платье», «чем красное платье лучше белого?». По запросу «s4 gala» выводились подсказки «s4 Galaxy», «S4 GALAXY круче iphone5», но не выводились подсказки «samsung galaxy s4200», «s4 Samsung galaxy - копия s3?».

Однажды было решено переписать сервис поисковых подсказок, чтобы он удовлетворял следующим условиям:

  • Должен быть полностью автономным. Т.е. не должен зависеть от внешних сервисов типа БД, а также не должен влиять на работу других сервисов.
  • Должен искать по совпадению отдельных слов поисковой фразы в любом месте подсказки, чтобы по запросу «бетон аренда» находились не только «бетон аренда дешево», но и «аренда бетономешалок», «бетононасос аренда», «аренда миксера с бетононасосом в Одессе». В дальнейшем будем называть это полнотекстовым поиском по префиксам.
  • По возможности должен возвращать найденные подсказки с максимальным весом. Т.е. если по запросу «перфоратор» найдено 100500 подсказок, то нужно вернуть только N из них с максимальным весом.
  • Должен работать быстрее старого сервиса.
  • Должен поддерживать поиск среди нескольких миллионов подсказок.
  • Должен поддерживать периодическое обновление базы поисковых подсказок.

Удивительно, но было решено писать этот сервис на Python. Чтобы был супер-скоростным :) На самом деле, чтобы все наши программисты, которые знают python, могли быстро разобраться в коде этого сервиса. К тому же, разработка с нуля аналогичного сервиса на каком-нибудь C заняла бы в несколько раз больше времени.

Т.к. к сервису идут AJAX-запросы, он должен поддерживать http и делать это с минимальными накладными расходами. Поэтому было решено использовать проверенный временем gevent, который уже успешно использовался в других сервисах prom.ua.

Технические детали реализации

Как сделать полнотекстовый поиск по префиксам? Правильно — с помощью слегка модифицированного инвертированного индекса. Вот классический алгоритм. Каждая фраза, среди которых осуществляется поиск, разбивается на отдельные слова (токены). Для каждого токена создается список фраз, содержащих этот токен. Теперь, чтобы найти фразы, содержащие заданный набор слов, достаточно найти пересечение списков для этих слов. Вот псевдокод на Python:

def get_suggestions(search_query):
    return frozenset.intersection(*(
        get_suggestions_for_token(token)
        for token in token_split(search_query)
    ))

Это алгоритм полнотекстового поиска по точному совпадению слов. Т.е. по запросу «шило» будут найдены все фразы с этим словом, но не будет найдены фразы, содержащие префиксы этого слова — «прибор Шилова» или «шиловидный флокс». Для того, чтобы можно было находить фразы по префиксам, нужно для каждого слова из поискового запроса найти все токены, начинающиеся с этого слова, после чего объединить связанные с этими токенами списки фраз. Затем нужно найти пересечение получившихся списков по каждому слову из поисковой фразы. Псевдокод на Python:

def get_suggestions_for_prefix(prefix):
    return frozenset.union(*(
        get_suggestions_for_token(token)
        for token in get_tokens_with_prefix(prefix)
    ))

def get_suggestions(search_query):
    return frozenset.intersection(*(
        get_suggestions_for_prefix(prefix)
        for prefix in token_split(search_query)
    ))

Первый рабочий прототип класса, реализующего полнотекстовый поиск по префиксам, был написан за полдня и занимал около 100 строчек кода на Python. Затем началась работа по оптимизации потребления памяти и скорости работы, по защите от DoS-атак и улучшению качества выдачи.

Первое, что нужно было исправлять — повышенное потребление памяти. Для построения индекса по миллиону фраз требовалось 3Гб памяти, а нужно было уложиться хотя бы в 500Мб. Вначале список фраз для каждого токена был заменен списком индексов этих фраз в глобальном списке фраз под названием keywords:

# если раньше get_suggestions_for_token(“foobar”)
# возвращал frozenset((“foobar”, “bar fooBar”)),
# то теперь возвращает frozenset((9000,100500)),
# где 9000 и 100500 - индексы фраз “foobar” и “bar booBar”
# в глобальном списке фраз keywords.

Затем keywords был преобразован в один большой bytearray, где фразы отделялись друг от друга с помощью специального символа-разделителя. Псевдокод формирования keywords:

def get_keywords_bytearray(keywords_list):
    keywords = bytearray()
    for keyword in keywords_list:
        keywords.extend(keyword)
        keywords.extend(KEYWORDS_DELIMITER)
    return keywords
Затем списки индексов фраз были заменены списками смещений в keywords, закодировнных в бинарную строку с помощью struct.pack(). Теперь каждое смещение занимало ровно 4 байта. Затем списки смещений для всех токенов были объединены в один большой bytearray под названием offsets. Затем отсортированный по алфавиту список пар (токен, смещение в offsets) был заменен на все тот же bytearray под названием tokens. В итоге мы получили три больших bytearray’я:
  • keywords — список фраз, по которым производится полнотекстовый поиск.
  • offsets — список, содержащий список смещений в keywords для каждого токена.
  • tokens — отсортированный по алфавиту список пар (токен, смещение в offsets).

Теперь индекс для миллиона поисковых фраз стал занимать меньше 100Мб. Но для перестроении индекса все еще требовалось 1Гб памяти — столько занимал список пар (токен, смещение в keywords) для миллиона фраз, из которого затем строился сжатый индекс. Была предпринята попытка положить этот список в bytearray, сохраняя смещение каждой пары в array(‘L’). Но это не дало существенного выигрыша в потреблении памяти. Поэтому было решено разбить список фраз на подсписки меньшей длины — шарды — и строить индекс по каждому шарду. Это немного усложнило индексацию и алгоритм поиска, но позволило снизить максимальное потребление памяти при построении индекса. Например, на шардах размером 500К фраз потребление памяти не выходило за пределы 400Мб при построении индекса для миллиона фраз. На этом этапе оптимизация по потреблению памяти была окончена и началась оптимизация по скорости.

Сперва разобрались с тормозами при поиске часто встречающихся префиксов (например «про» или «купить»). Такому запросу удовлетворяет примерно 100500 фраз, из которых нужно выбрать N с наибольшим весом. Очевидно, что каждый раз выбирать и сортировать все эти фразы по весу было бы очень накладно. Поэтому список фраз для каждого токена заранее сортировался по весу во время построения индекса, а при поиске выбирались первые N фраз из этого списка. Встал вопрос — как выбирать фразы с наибольшим весом, если несколько токенов начинается с заданного префикса (например, токены «проект» и «продать» для префикса «про»)? Попробовали использовать алгоритм объединения сортированных списков на основе heapq.merge(), чтобы выбрать N фраз с наибольшим весом. Но это оказалось слишком медленным при большом количестве токенов с заданным префиксом, поэтому было решено «схалтурить» и выдавать подряд первые встретившиеся N фраз, содержащих заданный префикс.

Далее нужно было решить вопрос со скоростью поиска по поисковым запросам, содержащим несколько слов. Нужно было находить пересечение списков фраз, содержащих каждое слово. Как уже известно, такие списки могли оказаться слишком большими. Поэтому в целях оптимизации было решено снова «схалтурить» и выбирать не более заданного количества фраз (Nmax) для каждого префикса перед тем, как находить их пересечение. Это ухудшило качество подсказок для поисковых запросов, состоящих из нескольких слов. Поэтому, чтобы немного сгладить вину, в алгоритм поиска были внесены изменения — если хотя бы один из списков содержит меньше, чем Nmax фраз, то вместо того, чтобы находить пересечение списков, сканировались все фразы из списка, содержащего минимальное количество фраз, на предмет содержания всех слов из поискового запроса.

Производительность и потребление памяти

Вот лог тестирования скорости поиска среди миллиона фраз в интерактивном режиме с помощью ipython на моем ноуте:

$ ipython -i suggester.py
In [1]: s = Suggester()
In [2]: s.update_keywords(
   ...:     ('keyword %d' % i, 'payload %d' % i)
   ...:     for i in range(1000000)
   ...: )
In [3]: def bench_suggester(suggester, query, n):
   ...:     import time
   ...:     start_time = time.time()
   ...:     for i in range(n):
   ...:         suggester.suggest_keywords(query)
   ...:     print '%.0f ops/s' % (
   ...:         n / (time.time() - start_time)
   ...:     )
   ...:     
In [4]: bench_suggester(s, u'foobar', 10000)
10009 ops/s
In [5]: bench_suggester(s, u'1234', 10000)
4654 ops/s
In [6]: bench_suggester(s, u'key', 10000)
4702 ops/s
In [7]: bench_suggester(s, u'key 1234', 10000)
1077 ops/s
In [8]: bench_suggester(s, u'zkey 1234', 10000)
1226 ops/s
In [9]: bench_suggester(s, u'zkey z1234', 10000)
6416 ops/s

Нагрузочное тестирование показало, что один сервис поисковых подсказок, работающий в одном потоке на одном процессоре, справляется с нагрузкой в 2000 типичных запросов в секунду. На данный момент один сервис поисковых подсказок спокойно справляется с трафиком prom.ua, потребляя при этом не более 200 Мб памяти (для сервиса, содержащего около миллиона подсказок, хватило бы и 100Мб — остальные 100Мб нужны для подсказок, используемых в других частях сайта). На остальных наших сайтах — tiu.ru, deal.by, satu.kz и prom.md — установлены отдельные копии сервиса поисковых подсказок. Это сделано не из-за того, что один сервис не справился бы с нагрузкой со всех сайтов, а из-за того, что в разных странах нужно показывать разные поисковые подсказки.

Заключение

Новый сервис поисковых подсказок достиг всех поставленных целей:

  • является полностью автономным — если он выходит из строя либо его начинают DoS’ить, то остальные части сайта продолжают работать как ни в чем не бывало;
  • быстро осуществляет полнотекстовый поиск по префиксам среди миллиона подсказок, учитывая по возможности их вес;
  • поддерживает периодическое обновление базы подсказок.

Конечно, он не является идеальным. Существует море улучшений, которые можно было бы реализовать в этом сервисе. Надеюсь, ваши комментарии к этой статье помогут улучшить качество выводимых подсказок.

В данной статье описаны лишь некоторые детали разработки нашего сервиса поисковых подсказок. Эта статья является примером того, что на Python можно и нужно разрабатывать высокопроизводительные сервисы, оптимизированные по потреблению памяти. Gevent, struct, bytearray, array, heapq — лучшие друзья при разработке таких сервисов.

P.S. (небольшой холиварчик)

У Python’а есть преимущество перед другими популярными языками программирования типа Java и C# — обычно код на Python пишется быстрее и получается понятнее и короче. Например, на данный момент весь код, ответственный за индексацию и поиск подсказок, занимает 268 строк, включая комментарии, пустые строчки и дополнительные возможности, не описанные в этой статье — привязка произвольных данных к каждой фразе в индексе, запись и чтение индекса в/из файла, возможность поиска по не полному совпадению фраз, возможность задания различных методов разбиения фраз на токены, разбиение списка фраз на шарды с последующим объединением результатов поиска по каждому шарду.

Желающие могут ознакомиться с исходниками Suggester’а на github — главной составляющей сервиса поисковых подсказок на prom.ua. Если кому-нибудь интересны технические детали, упущенные в этой статье, задавайте вопросы в комментариях — постараюсь ответить.

LinkedIn

Лучшие комментарии пропустить

Спасибо, интересно.

Вы рассматривали готовые платформы для полнотекстного поиска (solr, sphinx), и почему решили писать свой сервис?

Наконец-то нормальная техническая статья на ДОУ. Спасибо, очень интересно :)

Какой то странный велосипед.
Почему не Lucene/Solar/ +ngrams/стемминг/VSM?

Фу, какой-то SQL, какой-то Python в статье, вы тут на developers.org.ua совсем уже охренели? Что скажет ваша целевая аудитория?!

117 комментариев

Подписаться на комментарииОтписаться от комментариев Комментарии могут оставлять только пользователи с подтвержденными аккаунтами.

Вообще конечно странно изобретать свой велосипед, фиксить баги и тд, в наше время, когда уже все что можно изобретено — хоть elasticsearch, sphinx, solr etc

Префиксное дерево, trigram search уже обсудили? Или хоть приведение слов в общему падежу, а потом поиск?

Насколько мне видно, то нет. Если можете отписать по этой теме что-либо конкретное, либо поделится опытом написание своего инструмента полнотекстового поиска, будет интересно прочитать. Спасибо.

Я конечно не попагандирую велосипедостроение, именно эти алгоритмы уже реализованы для различных СУБД.

Часто строят таблицу превращение слов в общий падеж. "деревом"->"дерево", "деревья"->"дерево«. Это решение обычно не подразумевает исправление орфографии. Тогда можно просто индексировать документы по словам в этих падежах и потом делать самый обычный поиск.

Еще иногда используют префиксное/суффиксное дерево. О том как выглядит подобное дерево можно посмотреть в википедии. Первое легко позволяет найти все обьекты, которые начинаются на определенную строку. Запрос под «дерев», найдет очень быстро все слова которые начинаются на эту строку. Суффиксное дерево чуть не такое очевидное, но ищет не только по началу слова. Обычно эти структуры в памяти. Можно реализовать и в СУБД, но может просто получиться слишком много запросов и вообще не ясно чем это лучше чем LIKE в таком случае.

Чуть более интересный алгоритм — trigram search (или ngram, где n=3, внезапно). Там строка разбивается плавающим окном на комбинации по три символа. «Дерево» -> " дерево " -> (" д", " де«, «дер», «ере»,..., «о »). По ним строится индекс для каждого документа. Потом так же обрабатывается искомая строка. После для каждой триграммы производится поиск документов, которые содержат искомую триграмму. Потом выбираются документы, которые больше всего были найдены в результатах поиска. Плюсами алгоритма является исправление орфографии, опечаток, перестановки слов местами, хорошие возможности к параллелизму. Минусы — в зависимости от того как реализовывать можно просто оперировать слишком большими обьемами найденых документов, тут нужно как-то ограничивать результаты. Если документы большие, то trigram обычно показывает погоду на марсе. Потому лучше разбить их на что-то поменьше, например на предложения и искать по ним

Еще его часто используют для функциональности «Возможно вы имели ввиду...». Я использовал для нечеткого матчинга обьектов друг с другом по названиях, когда нужно было угадывать что разные ID из фидов двух разных организаций связаны с одним и тем же географическим объектом. В БД можно реализовать одним SQL или одной MapReduce job. Я писал ручками поверх H2, но вот в PostgreSQL есть готовый ngram/

Спасибо, Игорь, за интересный и развернутый ответ.

Автор топика тоже предложил поиск по префиксам и еще предложил некоторые возможности сжатия, что тоже вообщем хорошие подходы

Все верно. У PostgreSQL есть индекс и по LIKE ( dou.ua/...ggester/#353016 ), поэтому данное решение остается с вопросом «Зачем?», если и стандартная RDBSM имеет в наборе ngram + tsearch2

Если есть в распоряжении PostgreSQL, то руками писать ничего не нужно. У других людей другие БД, у меня вообще была in-memory аналитика.

Не могли бы вы привести ссылку на документацию PostgreSQL, где описано, каким образом индекс по LIKE помогает при полнотекстовом префиксном поиске? Т.е. чтобы по запросу «iph 3» вернулось «iphone 3gs» и «32GB iphone».
Может, вы имели ввиду GIN и GIST индексы? Так они вроде не поддерживают префиксный поиск.

www.postgresql.org/...PARSING-QUERIES

И что бы долго не искать пример:


=> SELECT to_tsvector('iphone') @@ to_tsquery('iph:*');
 ?column? 
----------
 t
(1 row)

Здорово! Беру свои слова обратно насчет поддержки префиксного поиска с помощью GIN & GIST индексов.

Остается открытым вопрос насчет производительности SELECT’а по GIN индексу с применением сортировки, если заданному префиксу соответствует большое количество фраз. Например, если следующий запрос возвращает 100500:
SELECT COUNT(*) FROM t WHERE text_tsv @@ to_tsquery('п:*')

Насколько долго будет выполняться вот этот запрос?
SELECT text FROM t WHERE text_tsv @@ to_tsquery('п:*') ORDER BY weight LIMIT N
Сколько записей должен будет просканировать postgresql при выполнении этого запроса? Можно ли заменить это сканирование выборкой по индексу первых N записей с максимальным весом?

weight — я не знаю как определяется вес, но если это коофициент ранжирования, то можно рассмотреть готовый функционал в БД:



SELECT title, ts_rank_cd(text_tsv, query) AS rank
FROM t, to_tsquery('п:*') query
WHERE query @@ text_tsv
ORDER BY rank DESC
LIMIT 10;

ts_rank_cd бужет измерять насколько ревалентный данные в text_tsv для запроса.

Остается открытым вопрос насчет производительности SELECT’а по GIN индексу с применением сортировки, если заданному префиксу соответствует большое количество фраз.

Для этого и существуют индексы, что бы ускорить поиск. Если брать GIN (а он в три раза быстрее GiST), то скорость будет достаточно высокой при милионах записей в таблице. Тут главное, что бы индекс в память помещался :) Ну а на сортировочное поле weight как уже писалось добавить отдельный индекс — для более быстрой сортировки по нему. Тогда нас не пугает, что при выборки много получилось — сортировка будет по индексу.

Своеобразная поддержка префиксных деревьев уже есть — для этого достаточно использовать fullchar_tokenizer при создании объекта Suggester. Тогда поиск будет осуществляться по совпадению произвольной подстроки. Например, по запросу «foo» будут найдены не только «foo bar» с «foobar», но и «barfoo» с «barfoobaz».
Использование trigram search в сервисе поисковых подсказок, может быть, появится в будущем.
Приведение слов к общему падежу уже реализовано при поиске — попробуйте поискать на prom.ua что-нибудь вроде трикотажным платьем.

Спасибо за статью!
Скажите, почему так важно было вписаться в 500МБ? Сколько ресурсов кушает весь prom.ua в production?

Скажите, почему так важно было вписаться в 500МБ?

Жесткого ограничения по максимальному потреблению памяти не было. Тут действуют простые законы экономики — чем меньше памяти требует сервис, тем меньше затрат на его содержание. 500Мб он потребляет только при перестроении индекса. Затем working set сервиса держится на уровне 100Мб. Это значит, что на данный момент при необходимости мы можем:

  • держать кучу других сервисов на компе, где работает сервис поисковых подсказок;
  • держать штук 10 сервисов поисковых подсказок для разных стран на одном компе с 1-2Гб памяти;
  • увеличить количество подсказок с миллиона до 10 миллионов.
Сколько ресурсов кушает весь prom.ua в production?

На этот вопрос, может быть, ответят наши админы. Пойду просить, чтобы написали статью :)

Очень интересная статья. А на англоязычных ресурсах вы не пишете — было бы круто показать статью англоязычным товарищам :(

Пока не пишу, но в планах давно есть — руки пока не доходят. В первую очередь хочу написать про проектирование и разработку кэша для блобов — github.com/valyala/ybc .

Якщо не таємниця, яким чином створювався список підказок?

В первую очередь показываются подсказки по моделям товаров (например, «zanussi»), потом — по категориям (например, «одежда»), а затем — по поисковым запросам пользователей, которые вернули ненулевой результат. Алгоритм формирования и сортировки поисковых запросов пользователей является тайной, чтобы его не накручивали :)

Кстати, а не думали коммерческого инфа завести с iii.ru? Он смог бы давать советы более осмысленно.

В первый раз вижу этот сервис. Спасибо за ссылку — посмотрим, что это такое, и может быть где-нибудь будем использовать.

+1
Почему именно велосипед, а не «проверенные» фреймворки? Потому что задача простая и не стоит её усложнять. Фактически это словарь данных. Для которого требуется собрать обычную древовидную структуру памяти.

Дальнейшим развитием я бы докрутил нейросеть. С целью находить то, чего даже не предполагалось. В первую очередь подбрасывая контекстную рекламу.

Кстати, с миллионом слов — это уже перебор. Я бы выделил примерно 2-3 тысячи наиболее юзабельных фразы и частым посетителям скормил его прямо в LocalStorage. Отдельно следует собрать словарь торговых марок — эти слова заслуживают отдельной модели монетезации, то бишь услугу рекламы через подсказки. Вплоть до точно чтобы вообще обнаглеть и советовать исключительно монетезируемую рекламу. Ну а что — деньги не пахнут!

Prom.ua ещё предстоит пройти много этапов развития, и это всего лишь ступенька.

ЗЫ. Попробовал найти «жопа» — он подсказал мне кондиционер за 150 евро :)

Да, и интересный момент — «жопа с ушами», которая направляет на какую-то книгу. :)

ЗЫ. Попробовал найти «жопа» — он подсказал мне кондиционер за 150 евро :)

Тут уже сработал solr, а не сервис поисковых подсказок. Может быть, этот кондиционер отлично подходит для охлаждения пятой точки :)

Да, и интересный момент — «жопа с ушами», которая направляет на какую-то книгу. :)
это либо проблемы солра, либо там действительно книга про жопу с ушами :)

Насчет жопы с ушами — вот цитата из описания этой книжки —

Короче, на этом детском утреннике ей выпало быть вечным зайчиком в дурацких белых гольфах, с ушами осла и комком ваты на жопе.

Оставляю комментарий не столько для критики вашего решения — (вас оно устраивает, зачем что-то еще?), сколько для вопросов «на подумать», если кто-то будет реализовывать что-то подобное:
1. Почему нельзя было создать аналогичный индекс по слогам в mongodb? Да, это будет несколько медленнее (у меня 130~220 операций в секунду на таких тестах, индекс — 0.2GB (mongodb)), но есть несколько важных плюсов:
— индекс будет обновляться автоматически (сколько занимает (пере-)запуск процесса?)
— код является всего лишь одним из методов основного веб приложения
— приложение работает с объектами, а не абстрактными строками. Это дает возможность показывать thumbnail, сгенерировать правильный url, сгруппировать похожие результаты по категориям, поднять товары с акциями выше.
— задачу можно масштабировать вместе с всем проектом без дополнительных усилий по администрированию

2. Тестировать скорость на повторящихся строках не совсем корректно. У меня я легко добился 100+ mbps html. Но на практике ситуация существенно отличается. Мы сделали внутренний сервис который получает лог сервера и выполняет реальный операции, выполнявшиеся пользователями. Результат совсем другой )
В вашем случае, если все в памяти, разница будет «всего» раз в 6 (скорость кэша процессора — 45GBps, памяти — до 7gbps [source — zsmith.co/bandwidth.html]), но в других сценариях такие тесты могут разбиться о суровую реальность.

PS: По критике — изобретение специально велосипеда намного актуальнее, чем кажется. Спасибо за интересное решение.

1. Почему нельзя было создать аналогичный индекс по слогам в mongodb?
От mongodb отказались по следующим причинам:
  • чтобы не мешать другим, более важными частями проекта, которые тоже используют mongodb. Раньше бывало, что тяжелые запросы к mongodb, идущие от сервиса поисковых подсказок, тормозили выполнение запросов от других частей проекта
  • чтобы свести количество внешних зависимостей сервиса поисковых подсказок к нулю. Сейчас он представляет из себя три файла на python, которые можно просто скопировать на любой комп и запустить. Больше ничего настраивать не нужно
  • как вы уже сами сказали, сервис поисковых подсказок на mongodb работает медленнее, чем на нашем «велосипеде»
— индекс будет обновляться автоматически (сколько занимает (пере-)запуск процесса?)

Мы не перезапускаем процесс — у него есть специальные http хэндлеры, через которые можно обновлять индекс в рантайме. Обновление индекса из миллиона фраз занимает секунд 10.

— приложение работает с объектами, а не абстрактными строками. Это дает возможность показывать thumbnail, сгенерировать правильный url, сгруппировать похожие результаты по категориям, поднять товары с акциями выше.

Наш сервис поддерживает это искаропки — каждой фразе можно привязать произвольную строку, в которой можно хранить произвольный сериализованный объект. И мы это активно используем. Например, подсказки по категориям содержат сразу ссылку на соответствующую категорию, подсказки по моделям товаров — ссылку на страницу модели и т.д. Так что тут преимуществ у mongodb нет.

— задачу можно масштабировать вместе с всем проектом без дополнительных усилий по администрированию

С этим в ближайшие пару лет проблем быть не должно, т.к. в данный момент у нас средняя нагрузка на сервис поисковых подсказок не превышает 5 запросов в секунду, т.е. у сервиса запас прочности составляет более двух порядков.

2. Тестировать скорость на повторящихся строках не совсем корректно.

Согласен. Если бы в этой статье я стал описывать методику правильного тестирования производительности, то ее пришлось бы переименовывать в «как правильно выполнять нагрузочное тестирование для сервиса поисковых подсказок» :) У меня по этому поводу уже есть одна занимательная статья.

Спасибо, Сергей, за интересный и развернутый комментарий. У меня к Вам есть пару вопросов относительно Вашей реализации полнотекстового поиска на базе mongodb. Если можно, то ответьте, пожалуйста, в таком же духе:
1. Поддерживается ли у Вас идея с использованием списка нерелевантных слов с точки зрения поиска (список Stop words)? Для разных языков? Если да, то можете, пожалуйста, вкратце рассказать, как Вы это реализовали?
2. Поддерживается ли у Вас идея с использованием стемминга? Для разных языков? Если да, то можете, пожалуйста, вкратце рассказать, как Вы это реализовали?
3. Поддерживается ли у Вас идея с использованием словарей, например: для обработки синонимов; разноспрягаемых глаголов (например: сыпать — сыплют/сыпят); сложных слов (например: Академгородок — академический городок; Колхоз — коллективное хозяйство)? Для разных языков? Если да, то можете, пожалуйста, вкратце рассказать, как Вы это реализовали?

Заранее благодарна за любой Ваш ответ.

UPD:
* Под стеммингом подразумевается отсечение от слова окончаний и суффиксов, чтобы оставшаяся часть, называемая stem, была одинаковой для всех грамматических форм слова, например: сметь — посметь

1. Поддерживается ли у Вас идея с использованием списка нерелевантных слов с точки зрения поиска (список Stop words)?
Поддерживается ли у Вас идея с использованием словарей, например: для обработки синонимов;
Я что-то пропустил. А в велосипеде на 268 строк оно поддерживается? (При беглом просмотре в статье и в коде я этого не увидел. Если есть то ткните носом в строку)

Простите, Богдан, но вопрос был не Вам адресован. То, что вы думаете, я уже прочла и поняла.
Отвечу на эту провокацию, с моей точки зрения, так: я задала вопрос не для того, чтоб подчеркнуть значимость или ничтожность чей бы то нибыло реализации, а для того, чтоб иметь более полную картину того, как можно было бы реализовать поисковый механизм на базе mongodb, так как мне показалась идея Сергея очень интересной, и даже больше скажу, думаю, что не только мне.

Отвечу на эту провокацию
я задала вопрос не для того, чтоб подчеркнуть значимость или ничтожность чей бы то нибыло реализации
Деффачка, надо быть добрее и непредвзятие :)
Я так же спросил не с целью зачмырить, а узнать «может я чего не увидел».
как можно было бы реализовать поисковый механизм на базе mongodb, так как мне показалась идея Сергея очень интересной
Несмотря на то что вопрос был задан не мне, я отвечу:
Никак. А если конкретно это можно прикрутить, то найдется что-то чего нельзя. И тут всплывают Салр/ЕластикСерч, про который тут все говорили.

Отличная статья про то, как программисты без нужной теоретической базы решают задачу в лоб. Потом героически борются с последствиями. А если добавит еще 1-2 измерения?

Иногда решение проблемы в лоб позволяет оттянуть проблему во времени, чтоб собраться и решить ее более правильным путем. Я с Вами не соглашусь. На мой взгляд, статья как раз о том, как ребята решили проблему наиболее быстрым/удобным способом, когда этого требовали обстоятельства, и сейчас открыты для предложений, как такое решение можно было бы сделать лучше.

Решение поисковых задач в relative data model вызывает недоумение. Молодцы, что решили. Но эти задачи решаются системно по-другому

Позволю себе немного пофилософствовать. Как-то с опытом лично ко мне приходит все больше и больше недоверие к идеально правильным менеджерам, идеально правильным архитектурам, идеально правильной спецификации, идеально правильной составленным тестам, идеально написанному коду, идеально правильно проведенной демо и тд и тп. По себе я замечать стала, что идеализация каких либо процессов, реализаций, действий приводит к окаменению мозга, и порой очень больно и неохотно осознавать свои ошибки, что приводит к еще большим проблем в будущем не только для меня. Я хочу этим сказать, что я не думаю, что есть идеальный системный способ решения на каждую существующую проблему, слишком много внешних факторов может влиять на конечное решение: от настроения и состояния человека/команды, до финансовой составляющей. И от проекта к проекту эти факторы могут быть разные.
На тот момент, возможно, единственным правильным решением для команды казалось реализовать сервис именно таким образом. И как мне кажется, из прочтенной статьи, автор не ожидает, чтоб на него только показали пальцем и сказали, что он не правильно сделал, а и чтоб конструктивно подкрепили свою точку зрения практикой/ссылкой(ами), так как в любом случае если не статья, то комментарии к ней могут послужить полезную службу не только нашей компании, но и другим, кто будет/планирует столкнуться с подобными проблемами. Поэтому с этим утверждением я также несогласна.

Решение поисковых задач в relative data model вызывает недоумение. Молодцы, что решили. Но эти задачи решаются системно по-другому

Напишите об этом статью — было бы интересно почитать. Или хотя бы скиньте сюда пару ссылок. А не то я думаю, тут мало кто знает, что такое relative data model.

Solr таки швидчий спосіб) Перший раз запустити на ньому пошук заняв 1 день-людину. 2й раз раз солр піднімається за 2 години з тюнінгом і настройкою оновленням бази солара.

Спасибо, а мой любимый цвет — салатовый

ееей, я ж конкретно написав чим кращий.. написав конкретний час затрачений на розгортання...
P.S. не буду більш кормити..

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

Шикарно! А качество библиотек и проектов вы наверное по цвету исходников оцениваете?)

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

Мы используем solr для поиска и фильтрации товаров по характеристикам, категориям, товарным группам, регионам, компаниям и т.д. Для сервиса поисковых подсказок решили создать собственный велосипед, т.к. солр — слишком сложная штука для такой простой задачи. Зачем палить из пушки по воробьям?

Solr таки швидчий спосіб) Перший раз запустити на ньому пошук заняв 1 день-людину. 2й раз раз солр піднімається за 2 години з тюнінгом і настройкою оновленням бази солара.

Наш велосипедик поднимается в два шага за 10 секунд:

  • Скопировать три файла с исходниками сервиса поисковых подсказок на сервер
  • Запустить сервис поисковых подсказок
солр — слишком сложная штука для такой простой задачи
Не достатньо проста, щоб відмовитись від солара
Зачем палить из пушки по воробьям?
в соларі передбачено один з механізмів, спеціально заточений під підказки
Плюси:
для пошуку і підказок використовується один сервіс, що означає легшу підтримку, оновлення БД і куча тд., тим паче якщо ви ВЖЕ використовуєте солр..

лан, зробили то зробили, всім добра

А какие последствия? Это подсказчик. Его задача — кормить пользователя языковыми конструкциями из словаря. И не нужно додумывать велосипеду его задачи!

Это далеко не решение проблемы в лоб, а весьма профессиональный подход, с пониманием теоретической базы. Если и есть недостатки [а они есть], то порождаются самой сущностью сервиса [человеческой логикой], а никак на поисковым механизмом.

Последствия как раз и описаны в статье. Курите multi dimensional data modelling

Последствия как раз и описаны в статье. Курите multi dimensional data modelling

Приведите, пожалуйста, цитаты из статьи с описанием последствий. И как в решении этих последствий может помочь магическое сочетание слов multidimensional data modelling?

Отличная статья про то, как программисты без нужной теоретической базы решают задачу в лоб. Потом героически борются с последствиями. А если добавит еще 1-2 измерения?

1. Не могли бы вы изложить более развернуто свои мысли, приведя конкретную аргументацию со ссылками на теоретическую базу? Конечно, мы могли бы потратить пару человеко-лет на исследования, а затем воплотить последние достижения в этой области из computer science в мега-навороченном коде, понятному только авторам этих достижений. Но зачем, если за полдня можно изобрести собственный велосипед, который отлично справляется с поставленной задачей и легко может быть адаптирован под меняющиеся требования?
2. Мы пока ни с какими последствиями не боремся, а только пожинаем плоды :)
3. Что такое 1-2 измерения и зачем их добавлять?

Какой то странный велосипед.
Почему не Lucene/Solar/ +ngrams/стемминг/VSM?

А вы нехотели бы написать свою статью по опыту разработки аналогичных сервисов на указанной Вами связке технологий? Я бы с удовольствием эту статью прочла. Либо просто объяснить для блондинки, почему Вы считаете, что вышеперечисленная Вами связка технологий позволят это сделать эффективней в контексте описанной в статье проблемы?

Либо просто объяснить для блондинки, почему Вы считаете, что вышеперечисленная Вами связка технологий позволят это сделать эффективней в контексте описанной в статье проблемы?
Эээээ??? Ну для уж совсем блондинок:
Солр — это зрелое решение, которое поддерживается коммюнити (со всеми вытекающими), а то что описано в статье — какой-то велосипед, который:
один сервис не справился бы с нагрузкой со всех сайтов, а из-за того, что в разных странах нужно показывать разные поисковые подсказки.
то есть не держит ни какую нагрузку.

Вопрос небыл озвучен мной, как наезд, хотя мог бы таким показаться, судя по реакции. Прочитать, что аббревиатуры, указанные выше означают несложно, имея обычный доступ к интернету. Вопрос был озвучен мной лишь для того, чтоб сместить диалог в более предметную область, а именно:
если человек имел опыт в разработки подобных сервисов, то мог бы он рассказать, почему abcd/efgh + ijk связка ему кажется эталонным вариантом при решении проблемы, описанной в статье (так как именно ее он указал >> Lucene/Solar/ +ngrams/стемминг/VSM). Почему не klmn/opqr + stu (условно). Может быть поделился бы ссылкой на какие-либо бенчмарки...

если человек имел опыт в разработки подобных сервисов
связка ему кажется эталонным вариантом при решении проблемы,
А опыт тут не важен. Важен простой инженерный подход (который вбивают в ВУЗах в течении 5 лет):
Сделать “Огляд існуючих ришень”, перед тем как писать свое.
Именно такой порядок. Сначала поняли чем не подходит, потом начали делать свое или исправлять те моменты которые не подходят.
Вопрос не в эталонности, а в том что уже есть готовое решение.
А так это похоже на исправление “фатального недостатка” (другие решения написаны не автором этого решение :) )

Да потому что это интрументы, которые применяются по умолчанию.
Lucene/Solar/ElasticSearch(Lucene под капотом) — стандартные инструменты для организации поиска.
ngrams и VSM — стандартные инструменты для поиска похожих фраз и текстов
стемминг — стандартное средство для «нормализации» текста.

Иногда бывает полезно мыслить нестандартно :)

Представьте — вам нужно создать сервис поисковых подсказок. До появления исходников Suggester’а вам пришлось бы думать, как бы настроить стандартные средства, описанные вами, под решение этой задачи. Теперь же вы не раздумывая возьмете новое стандартное средство — наш велосипед, т.к. он:
— идеально подходит для создания сервиса поисковых подсказок;
— легко настраивается под свои нужды, т.к. его код совсем небольшой и понятный;
— работает искаропки.

Не удивлюсь, если вскоре Suggester станет «инструментом, применяемым по умолчанию» для создания сервиса поисковых подсказок.

то есть не держит ни какую нагрузку.

Задача для первого класса:
В данный момент средняя нагрузка на сервис составляет 5 запросов в секунду, а он способен выдержать 2К запросов в секунду. Во сколько раз нужно поднять нагрузку на сервис, чтобы он перестал справляться с ней?

Решите сами или помочь?

1) Про нагрузку отбой.
dou.ua/...ggester/#352766
2)

В данный момент средняя нагрузка на сервис составляет 5 запросов в секунду, а он способен выдержать 2К запросов в секунду.
Подстава аднака.
Если 5 запросов — это реальная нагрузка, то нах было городить свой велосипед?
Момент № 2 2К — это в тестовой среде, а когда пойдут реальные пользователи, там может быть и больше, но в более реально что сильно меньше. От когда будут реальные данные тогда можете сравнить их с Солр-ом/ЕлсатикСерч-ем.
Если 5 запросов — это реальная нагрузка, то нах было городить свой велосипед?

Перечитайте еще раз раздел «История развития сервиса». Там указаны причины, по которым было решено изобрести свой велосипед

В данный момент средняя нагрузка на сервис составляет 5 запросов в секунду, а он способен выдержать 2К запросов в секунду.
Стоп, стоп, стоп... 2к шттп запросов? Я так понимаю речь о них, правильно? Тогда откуда 2к? Ваш тест тестит методы классов, а не делает шттп запросы.

И сколько эта связка будет памяти кушать, при той же функциональности? Уверен, что на порядок больше.

Памяти на индекс вероятно уйдет даже меньше. У нас 20 млн доков == 3ГБ индекс на диске. У автора в 20 раз меньше и не документов, а поисковых фраз, что еще меньше.

Почему не Lucene/Solar/ +ngrams/стемминг/VSM?

Мы внимательно изучили все эти решения и обнаружили в них общий фатальный недостаток — они разработаны не нами :)

А если серьезно, зачем привязывать сюда громоздкий комбайн-solr (который у нас много где используется), если можно написать небольшой полностью автономный велосипедик на 268 строчек, который замечательно решает поставленную задачу и который легче адаптировать под новые требования по сравнению с solr’ом?

ну например потому что нет смысла тратить человекочасы на изобретение того, что уже давно изобретено и оттестировано множеством сервисов?

Или вашему руководству деньги не нужны, главное, чтобы программисты махали шашками в песочнице?

За статью о разраотке большое спасибо, но хотелось бы услышать ответ на вопрос:
почему не Lucene или его производные, или аналогичные решения?
Немного холиварчика:

У Python’а есть преимущество перед другими популярными языками программирования типа Java и C# — обычно код на Python пишется быстрее и получается понятнее и короче.
А приимущества джавы и тд начнут проявлятся когда начнете __решать__ проблемы вроде:
установлены отдельные копии сервиса поисковых подсказок. Это сделано не из-за того, что один сервис не справился бы с нагрузкой со всех сайтов, а из-за того, что в разных странах нужно показывать разные поисковые подсказки.
Ключевое слово «решать», а не просто делать затычки, которой является «установка отдельной копии на каждый сайт».

Почему Вы считаете, что изменение языка способно решить проблемы затычек? Я думаю, что у Python не меньше инструментов для того, чтоб решить проблемы затычек. Если уж заговорили о достоинствах Java, то приведите, пожалуйста, конкретные примеры того, с чем, по вашему мнению, не справляется Python, а Java справляется, так как то, что описано в тексте статьи совсем не утверждает того, что из-за Python не можно обойти проблемы с копированием сервиса поисковых подсказок.
На мой взгляд, проблемы затычек могут быть вызваны разными факторами: недостаток времени на гибкую, расширяемую и легко управляемую архитектуру; больших затрат по времени на переработку существующей архитектуры. Также мне кажется, что на затычку можно вполне закрыть глаза, если она вполне сносно справляется со своей задачей и соответствует требованиям к системе, при условии, что есть более приоритетные проблемы, которые нужно решать в первую очередь.
Я не думаю, что цель статьи была как раз показать какие мы классные (что лично для меня бесспорно так и есть), и как мы справились с проблемой, описанной выше, а просто продемонстрировать один из вариантов решения проблемы, возможно и не самый лучший, для того, чтоб услышать конструктивные комментарии по поводу того, какие проблемы могут возникнуть при нашей текущей реализации и взять их на заметку для дальнейшего устранения.
Спасибо.

Я думаю, что у Python не меньше инструментов для того, чтоб решить проблемы затычек.

Сорри, у питона объективно меньше инструментов (disclaimer: на джаве я не писал, зато на питоне — довольно долго). У питона есть умеренной продвинутости профайлеры, а у джавы здоровенная экосистема инструментов, значительно больше всего, чем есть у питона.

Не так чтоб я был согласен с Богданом. Из слов «мы держим отдельные инстансы для каждой страны» он откуда-то выдумал «оно не выдержит нагрузки», что довольно интересный ход мыслей.

Из слов «мы держим отдельные инстансы для каждой страны» он откуда-то выдумал «оно не выдержит нагрузки»
Где-то из этого:
что один сервис не справился бы с нагрузкой со всех сайтов
UPD. Бл... читал по диагонали, пропустил отрицание. Вопрос снят.
У питона есть умеренной продвинутости профайлеры, а у джавы здоровенная экосистема инструментов, значительно больше всего, чем есть у питона

А вы не думали, что у питона меньше всяких профайлеров и прочих костылей инструментов лишь потому, что они ему не нужны? Инструменты же появляются не сами собой, а под конкретные нужды.

А вы не думали, что у питона меньше всяких профайлеров и прочих костылей инструментов лишь потому, что они ему не нужны?
Вы пропустили слово «пока». До тех пор пока вы пишите велосипеды на 5 запросов/сек вам не нужны профайлеры и тд. Пока ваша логика
Поэтому список фраз для каждого токена заранее сортировался по весу во время построения индекса, а при поиске выбирались первые N фраз из этого списка.
отладчики и 100500 классов (с которыми уже не так удобно работать при динамической типизации) так же не особо нужны.
А от когда пойдут те самые 2К и когда надо будет исключить из саджеста слово «Навальный» и выдавать инфу в зависимости от времени (например в пт по слову «купить» выдавать «купить пиво», а в пн «купить альказельцер»), от тогда и обсудим нужны инструменты или нет.
Вы пропустили слово «пока». До тех пор пока вы пишите велосипеды на 5 запросов/сек вам не нужны профайлеры и тд.

prom.ua почти полностью написан на python. Он никогда не испытывал, не испытывает и, надеюсь, не будет испытывать трудностей в связи с нехваткой инструментов под python. В то же время он развивается в десять раз быстрее и мы тратим на это в десять раз меньше сил по сравнению с проектами аналогичных размеров на java / C#, на которых мне приходилось работать до этого.

А от когда пойдут те самые 2К

Подумайте насчет уровня нагрузки на наших сайтах после изучения вот этой статистики (которая не учитывает запросы от поисковых роботов, а у нас их ходит очень много).

и когда надо будет исключить из саджеста слово «Навальный» и выдавать инфу в зависимости от времени (например в пт по слову «купить» выдавать «купить пиво», а в пн «купить альказельцер»), от тогда и обсудим нужны инструменты или нет.

Это детский сад по сравнению с уровнем сложности бизнес-логики, реализованной на prom.ua в различных местах (особенно в кабинете компании, админке и crm’ке). И, представьте, каким-то образом обходимся без 100500 классов и java :)

prom.ua почти полностью написан на python. Он никогда не испытывал, не испытывает
И снова нет слова «пока» или «еще» :)
Кстати, твиттер он так же не испытывал трудностей ... некоторое время.А результат: переход с руби на ДжВМ (скала + джава).
мы тратим на это в десять раз меньше сил по сравнению с проектами аналогичных размеров на java / C#
Зато тратите в десять раз больше сил и денег на поиск программистов, знающих python.

Влад, да ладно :) Не так уж и плохо с этим сейчас стало на рынке.

Сорри, пропустила частичку «не». (:

пани имеет что-то против теплого лампового PHP ?

Нет, я имею что-то против аргументов:

Зато тратите в десять раз больше сил и денег на поиск программистов, знающих python.

Ты не хуже меня знаешь, что по-настоящему хороших PHP — разработчиков, не намного больше чем питонистов.

Я просто часто сталкиваюсь с этим аргументом, крик души в общем.

вообще хороших разработчиков на любом языке найти уже сегодня сложненько. Это все знают :)

Не, зато я думал о том, что инструментов меньше просто потому, что в экосистеме питона куда меньше денег крутится, чем в экосистеме джавы.

Нужны вам инструменты или вы справляетесь без них — это ваше дело, но то, что их меньше и они примитивнее — это факт.

почему не Lucene или его производные, или аналогичные решения?

Потому что Lucene с Solr’ом слишком громоздки для такой простой задачи. Solr успешно используется в других частях prom.ua, где его использование оправдано — при поиске, фильтрации и создании фасетов по товарам, компаниям, характеристикам, регионам и другим параметрам.

А приимущества джавы и тд начнут проявлятся когда начнете __решать__ проблемы вроде:
установлены отдельные копии сервиса поисковых подсказок. Это сделано не из-за того, что один сервис не справился бы с нагрузкой со всех сайтов, а из-за того, что в разных странах нужно показывать разные поисковые подсказки.
Ключевое слово «решать», а не просто делать затычки, которой является «установка отдельной копии на каждый сайт».

Извините, но не уловил вашей мысли. В чем преимущество java перед python в этом случае?
«Установка отдельной копии на каждый сайт» не является затычкой — она позволяет разворачивать сайты для разных стран в разных датацентрах.

Потому что Lucene с Solr’ом слишком громоздки для такой простой задачи. Solr успешно используется в других частях
Но он уже есть (как оказалось), и в общем случае надо доказать что он не подходит. __Доказать в первую очередь себе__, а не на форуме.
Пока из ваших описаний помимо «фатального недостатка», есть только 1 недостаток — оно не на питоне, а у вас в основном питон-программисты. Но он довольно слабый, так как джава как язык очень простая, похожа на Ц, в некоторой мере на питон, поэтому для нормального инженера не должно составить труда подправить пару классов в «плагине» для Солр-а/ЕластикСерч-а (Люсен уже сложнее, но вроде как не очень).
Извините, но не уловил вашей мысли. В чем преимущество java перед python в этом случае?
dou.ua/...ggester/#352990
А от когда пойдут те самые 2К и когда надо будет исключить из саджеста слово «Навальный» и выдавать инфу в зависимости от времени (например в пт по слову «купить» выдавать «купить пиво», а в пн «купить альказельцер»)
------------
«Установка отдельной копии на каждый сайт» не является затычкой — она позволяет разворачивать сайты для разных стран в разных датацентрах.
В такой формулировке — вполне нормальное решение.
а из-за того, что в разных странах нужно показывать разные поисковые подсказки.
В такой гуано-затычка, ибо ваш поиск не масштабируется (см. выше)
Запрос к БД мог тормозить, если под фильтр text_canonical LIKE ‘search_query_canonical%’ попадало слишком много фраз, которые нужно было отсортировать по весу и только затем выбрать первые N из них.
Вообще-то в таких случаях строят индекс по сортируемому полю, в вашем случае weight. Сравнение будет проходить по уже отсортированному индексу и остановиться как только достигнет первых N строк. Никаких сортировок не требуется.
Это справедливо для RDBMS, но не думаю, что в монго идея отличается.

Вот здесь подробнее www.slideshare.net/...art-of-indexing

Вообще-то в таких случаях строят индекс по сортируемому полю, в вашем случае weight. Сравнение будет проходить по уже отсортированному индексу и остановиться как только достигнет первых N строк. Никаких сортировок не требуется.

А если еще раз подумать? Решите наводящую задачку:

Таблица содержит 100500 строк с весом 10, начинающихся с <b>bar</b>, и 10 строк с весом 1, начинающихся с <b>foo</b>. Сколько строк просканирует БД с индексом по weight DESC при выполнении запроса:
SELECT text FROM t WHERE text LIKE 'foo%' ORDER BY weight DESC LIMIT 10;

Читаю ваши мысли «а что если построить индекс по (text, weight DESC)?». Вот задачка для этого случая:

Таблица содержит 100500 строк с весом 10, начинающихся с <b>bar</b>, 100500 строк с весом 1, начинающихся с <b>foo</b> и 10 строк с весом 5, начинающихся также с <b>foo</b>. Сколько строк просканирует БД с индексом по (text, weight DESC) при выполнении запроса:
SELECT text FROM t WHERE text LIKE 'foo%' ORDER BY weight DESC LIMIT 10;

А зачем гадать. Сделаем расчет. Берем PostgreSQL и создадим таблицу с индексами:


CREATE TABLE t
(
  id serial NOT NULL,
  description text,
  weight integer,
  CONSTRAINT t_pkey PRIMARY KEY (id)
)
WITH (
  OIDS=FALSE
);

CREATE INDEX t_weight_index ON t USING btree(weight); // индекс по weight
CREATE INDEX t_description_index ON t (description text_pattern_ops); // индекс по LIKE патерну
CREATE INDEX t_description_lower_tag ON t USING btree(lower(description) text_pattern_ops); // индекс по LIKE патерну для lower case (так проще делать LIKE с игнором кейса)

И производим анализ запроса:


EXPLAIN SELECT description FROM t WHERE description LIKE 'foo%' ORDER BY weight DESC LIMIT 10;

"Limit  (cost=13.86..13.87 rows=6 width=36)"
"  ->  Sort  (cost=13.86..13.87 rows=6 width=36)"
"        Sort Key: weight"
"        ->  Bitmap Heap Scan on t  (cost=4.31..13.78 rows=6 width=36)"
"              Filter: (description ~~ 'foo%'::text)"
"              ->  Bitmap Index Scan on t_description_index  (cost=0.00..4.31 rows=6 width=0)"
"                    Index Cond: ((description ~>=~ 'foo'::text) AND (description ~<~ 'fop'::text))"

Игнорируем кейс:


EXPLAIN SELECT description FROM t WHERE lower(description) LIKE 'foo%' ORDER BY weight DESC LIMIT 10;

"Limit  (cost=13.88..13.89 rows=6 width=36)"
"  ->  Sort  (cost=13.88..13.89 rows=6 width=36)"
"        Sort Key: weight"
"        ->  Bitmap Heap Scan on t  (cost=4.32..13.80 rows=6 width=36)"
"              Filter: (lower(description) ~~ 'foo%'::text)"
"              ->  Bitmap Index Scan on t_description_lower_tag  (cost=0.00..4.32 rows=6 width=0)"
"                    Index Cond: ((lower(description) ~>=~ 'foo'::text) AND (lower(description) ~<~ 'fop'::text))"

Итак, мы получаем поиск по двум индексам (нет никакого Sequences Scan), тоесть сканирование идет не по строкам. А значит скорость поиска по индексам будет Log(N), где N — количество записей.

Такое решение подойдет?

Как можно заметить, индекс по weight ( t_weight_index ) в данном случае не используется. Скорость поиска по такому индексу будет равна не O(log(N)), а O(log(N)) + O(M), где M — количество записей, удовлетворяющих условию LIKE ’foo%’. Ведь для каждой такой записи нужно достать значение weight, чтобы затем отсортировать по нему и вернуть 10 записей с максимальным весом. Поэтому индекс по description будет работать эффективно лишь в случаях, когда таблица содержит малое количество записей, начинающихся с искомого префикса.
Если не доверяете моим выкладкам, попробуйте заполнить таблицу следующими строчками со случайным весом:
— миллионом строчек, начинающихся с foo.
— миллионом рандомных строчек. Они нужны для того, чтобы слишком умный postgresql не додумался использовать индекс по weight вместо индекса по description.

Как можно заметить, индекс по weight ( t_weight_index ) в данном случае не используется.

У меня в примере используется оба индекса. На всякий случай цитирую Тома Лейна, если вас ввело в заблуждение Bitmap Heap Scan:

Bitmap Index Scan / Bitmap Heap Scan / Recheck Cond

A plain Index Scan fetches one tuple-pointer at a time from the index, and immediately visits that tuple in the table. A bitmap scan fetches all the tuple-pointers from the index in one go, sorts them using an in-memory “bitmap” data structure, and then visits the table tuples in physical tuple-location order.

www.postgresql.org/...1@sss.pgh.pa.us

Вот пример с данными:



insert into t(weight, description) values ( generate_series(1, 111000), md5(random()::text)); 
insert into t(weight, description) values ( generate_series(1, 400000), 'foofoo');

SELECT count(*) FROM t ;
511000

SELECT count(*) FROM t WHERE description LIKE 'foo%';
400000

 EXPLAIN ANALYZE SELECT description,weight FROM t WHERE description LIKE 'foo%' ORDER BY weight DESC LIMIT 10;

Limit  (cost=0.00..0.82 rows=10 width=16) (actual time=0.037..0.051 rows=10 loops=1)
   ->  Index Scan Backward using t_weight_index on t  (cost=0.00..32967.34 rows=400533 width=16) (actual time=0.035..0.048 rows=10 loops=1)
         Filter: (description ~~ 'foo%'::text)
         Rows Removed by Filter: 3
 Total runtime: 0.095 ms
(5 rows)

— миллионом строчек, начинающихся с foo.

INSERT INTO t(weight, description) VALUES ( generate_series(1, 1000000), 'foo' || md5(random()::text)); 

SELECT count(*) FROM t;
1000000

SELECT description FROM t LIMIT 10;
"foo89448d015071204ffcb90de6c4f0dd8b"
"foo810b2f42e05159604513413cfe7f4cd5"
"foo174e9210c3c7dd5fc5b3f8f9133ea812"
"foob837d4d2334aa8dfd4696a6becf2cccc"
"foo47f29c44426ea4b5e2d6e158d4190e76"
"foo9506414aaa59fd25cd90f954a5dbcfb6"
"foo8bb07854c1e65a7947bb65b0dffa4a1d"
"foo5b3a2367c08c95bdca35b4162debda4f"
"foodca671f581369cd9a349398d374ea804"
"foo4940ce3d9950052e38a78a50b55660a0"

EXPLAIN ANALYZE SELECT description,weight FROM t WHERE description LIKE 'foo%' ORDER BY weight DESC LIMIT 10;

"Limit  (cost=0.00..0.38 rows=10 width=40) (actual time=0.063..0.072 rows=10 loops=1)"
"  ->  Index Scan Backward using t_weight_index on t  (cost=0.00..37829.36 rows=999900 width=40) (actual time=0.062..0.068 rows=10 loops=1)"
"        Filter: (description ~~ 'foo%'::text)"
"Total runtime: 0.095 ms"

— миллионом рандомных строчек. Они нужны для того, чтобы слишком умный postgresql не додумался использовать индекс по weight вместо индекса по description.

INSERT INTO t(weight, description) VALUES ( generate_series(1, 1000000), md5(random()::text)); 

SELECT count(*) FROM t;
1000000

EXPLAIN ANALYZE SELECT description,weight FROM t WHERE description LIKE 'foo%' ORDER BY weight DESC LIMIT 10;

"Limit  (cost=10.81..10.84 rows=10 width=37) (actual time=8.663..8.666 rows=10 loops=1)"
"  ->  Sort  (cost=10.81..11.06 rows=100 width=37) (actual time=8.661..8.662 rows=10 loops=1)"
"        Sort Key: weight"
"        Sort Method: top-N heapsort  Memory: 25kB"
"        ->  Index Scan using t_description_index on t  (cost=0.00..8.65 rows=100 width=37) (actual time=0.042..7.379 rows=4066 loops=1)"
"              Index Cond: ((description ~>=~ 'foo'::text) AND (description ~<~ 'fop'::text))"
"              Filter: (description ~~ 'foo%'::text)"
"Total runtime: 8.741 ms"

Aliaksandr, судя по вашему чтению моих мыслей и по задачам, которые вы ставите, вы не до конца понимаете принципы работы БД.
Никакие строки сканироваться не будут, у вас будет index scan. Хотите избежать так же row-lookup — сделайте covering index. Если у вас достаточно памяти, индекс может целиком поместиться в кэш и никаких обращений к жесткому диску не будет вообще. Тут еще и партиционирование может помочь.

БД на основе статистики по природе распределения ваших данных в состоянии выбирать наиболее оптимальные пути выполнения запроса. Это называется cost-based оптимизацией.
Исходя из этого, мы можем создать два индекса. Один для покрытия случая когда выборку выгоднее делать по условию c последующей внешней сортировкой и для случая, когда обход по индексу будет дешевле. БД сама выберет наиболее подходящий план выполнения (если говорить о mysql, он бывает ошибается, но, как правило, ему можно подсказать используя `use index`/`ignore index` директивы либо немного изменив запросы).
Попробуйте поиграться с этим на ваших же задачках, используя следующие индексы (можете сделать их covering):
create index idx_text on t(text);
create index idx_weight on t(weight);

Я все же порекомендовал бы вам еще раз ознакомиться с ссылкой, что я дал выше. Так же, не лишним будет больше почитать о cost-based оптимизации и
понятии index cardinality.

Наконец-то нормальная техническая статья на ДОУ. Спасибо, очень интересно :)

Спасибо, с интересом прочитал!

Фу, какой-то SQL, какой-то Python в статье, вы тут на developers.org.ua совсем уже охренели? Что скажет ваша целевая аудитория?!

и при этом ни слова о зарплатах и 23летних синиорах:) ниочём статья вышла :D

Спасибо, интересно.

Вы рассматривали готовые платформы для полнотекстного поиска (solr, sphinx), и почему решили писать свой сервис?

+ поисковый движок Солра наверняка будет быстрее своего велосипеда + Солр это готовый http сервак.

+ поисковый движок Солра наверняка будет быстрее своего велосипеда + Солр это готовый http сервак.

Насчет скорости — не факт. Зачастую выходит, что инструменты, заточенные для решения конкретной задачи, оказываются быстрее, чем generic инструменты-комбайны-фреймворки, с помощью которых можно решить широкий круг задач, поработав немного (или много) напильником.

Насчет готового http сервака — gevent, используемый нами, также является почти готовым http сервером :)

Насчет скорости — не факт.
Ну Вашу «нагрузку» в 5 рек/cек он выдержит. 50 ревестов в сек — не напрягаясь. Тут узкое место не в движке, а в транспортном уровне — шттп. Кстати, у Солра сразу из коробки есть кеш, то есть при наличии памяти вопрос вычислений вообще не стоит.
оказываются быстрее
Как говрится, it depends.

Solr мы используем в полный рост, но в данной конкретной задаче, кроме собственно слова, нужно хранить его популярность, и под это solr не очень предназначен.

кроме собственно слова, нужно хранить его популярность, и под это solr не очень предназначен.
То есть если вбить в гугл что-то вроде «solr ranking results», то результат будет нулевым?

а еще есть готовый elasticsearch и там есть и это и много еще чего ;)

elasticsearch
А вот это уже очень дорого
Он же вроде как бесплатный. Так же как и Solr на Lucene.
В чем дороговизна?

Упс, перепутал с cloudsearch от амазона.

Потому что:
— быстродействие
— потребление памяти

Вы рассматривали готовые платформы для полнотекстного поиска (solr, sphinx), и почему решили писать свой сервис?

Если кратко, то потому что готовые платформы слишком тяжеловесны для решения такой простой задачи, как создание сервиса поисковых подсказок. Развернутый ответ я уже давал в других комментариях.

в каком месте тяжеловесен тот же Sphinx, уточните пожалуйста?

Тут говорится о том, что sphinx тяжеловесен, если его применение попытаться оправдать KISS принципом при проектировании сервиса.

wat ? Что за ерунду я тут прочитал?

Станислав, ерунда не в том, что вы прочитали, а в том, что вы ничего не поняли не из высказывания Александра ни из моего.

Я боюсь, что я понял, но это всеравно ерунда. Причем тут принцип KISS, когда вы изобрели велосипед и потратили на это кучу человекочасов, когда Sphinx заводится за полчаса максимум.

Где у вас тут KISS, в каком месте?

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

Думаю имелось ввиду, что и с помощью микроскопа можно забивать гвозди и он будет решать поставленную на него задачу — забивать гвозди. Но микроскоп не лучший вариант для решения подобной задачи. Если используется DevOps на проекте (тот же Chef или Puppet), то расширяемость и гибкость архитектуры «облака» как вопрос в таком случае не стоит — он может быть решен достаточно быстро при грамотном проекторовании.

Тем более при

потребляя при этом не более 200 Мб памяти
тут любой из предложенных инструментов справится, что уже упоминались (PostgreSQL, Solr, Lucene, ElasticSearch).

Брр

sphinx тяжеловесен, если его применение попытаться оправдать KISS принципом при проектировании сервиса.
С точки зрения KISS использование готового решения предпочтительнее, чем ваше решение. И в разработке и в поддержке.
Вы лучше прямо скажите, что ваши специалисты не знали как работать с готовыми решениями.

Ах. да, насчет тяжеловесности
mysql> show index mp3olimp_hint status;

+-------------------+-----------+
| Variable_name     | Value     |
+-------------------+-----------+
| index_type        | disk      |
| indexed_documents | 1411228   |
| indexed_bytes     | 30097571  |
| ram_bytes         | 57866757  |
| disk_bytes        | 676686375 |
+-------------------+-----------+
5 rows in set (0.00 sec)

документов больше, памяти меньше. Есть нюанс по фичам инфиксного поиска, но это меняется с полпинка в настройках. Объем используемой памяти подрастет

Подписаться на комментарии