поиск подстроки.

Поиск подстроки это частный случай поиска пересечения множеств

в mongo поиск по фразе, если есть поиск аля "some phrase" идет по полному значению поля через стандартный посимвольный алгоритм sf или как его там

Скорее всего это уже в каком-нибудь бусте есть :)

вообщем я чета явно полез в зону где нихрена не знаю и что то новое сделал

в mongo поиск по фразе, если есть поиск аля "some phrase" идет по полному значению поля через стандартный посимвольный алгоритм sf или как его там

sf?

straight forward - посимвольная проверка

проверяем 1 символ, потом второй и так далее

он там case sensitive?

он там case sensitive?

только если указываешь как опцию при поиске

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

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

если не указываешь то поиск идет strcasestr

а, окей. т.е. там strstr

для case sensetive - return haystack.find(phrase) != string::npos;

метод find на строке, но я не колупал может под обложкой strstr

окей. с бейзлайном понятно

в чём новшество?

смотри. для не фраз, они просто удовлетворяются stemm

тоесть если в поиске не фраза, сверяется stemm только.

в итоге основной нагруз только на сравнении фраз

у фраз есть инетерсный pattern - и вот это и есть частный случай которым можно оптимизировать. собственно у меня получился модифицированный sf за счет того, что я проверяю 1 и последний символ в первую очередь

и в итоге это работает быстрее%

для case sensetive - return haystack.find(phrase) != string::npos;

-> https://github.com/abseil/abseil-cpp/blob/38b704384cd2f17590b3922b97744be0b43622c9/absl/strings/string_view.cc#L92 -> https://github.com/abseil/abseil-cpp/blob/38b704384cd2f17590b3922b97744be0b43622c9/absl/strings/internal/memutil.cc#L88

у фраз есть инетерсный pattern - и вот это и есть частный случай которым можно оптимизировать. собственно у меня получился модифицированный sf за счет того, что я проверяю 1 и последний символ в первую очередь

первый и последний символ где?

фразы

в текстовом поле обьекта который индексировался

т.е. после текстового индекса задача сводится к поиску вхождения одной строки (токен из запроса) в другую (значения в документе)

это то как было сделано в FTS в монго

FTS это что?

тоесть да. на STAGE_TEXT_MATCH вытянуто значение по индексу обьекта и в поле - которое индексировалось они ищуют вхождение фразы

FullTextSearch- и кстати модуль у них в fts папке тоже)

так. а ты перед этим сравниваешь что?

так. а ты перед этим сравниваешь что?

уточни малость. у меня или мозг кипит или я многовариантность вопроса вижу

если я правильно понял, то условно, у нас есть две строки «brown lazy fox jumps over lazy brown dog» и «lazy fox». первая строка это значение поля «foo» по которому построен text индекс. «lazy fox» это поисковый запрос по этому индексу. есть обратный индекс с токенами brown, lazy, fox, jumps, over, lazy, dog, где каждый токен указывает на документ в котором он содержится. после фильтра по префиксам fox и lazy в этом индексе мы получили какой-то набор номеров документов, прочитали эти документы и остались мы с этими двумя строками. дальше монга проверяет полноту вхождения (?) и ищет строку «lazy fox» в строке «brown lazy fox jumps over lazy brown dog» используя abseil string_view::find() string_view::find() берёт и делает сравнение «brown lazy fox jumps over lazy brown dog» с «lazy fox», сдвигая индекс начала поиска на 1 и делая memcmp

так?

абсолютно верно. есть мелкие технические детали что за фоном. но логика верная

так

и где происходит озвученная оптимизиация?

конкретно сейчас именно с memcmp

получается тут? https://github.com/abseil/abseil-cpp/blob/38b704384cd2f17590b3922b97744be0b43622c9/absl/strings/internal/memutil.cc#L88

по сути да. немного по другому цикл построен но это вроде SF

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

и это уже все 37К записи в памяти

так, разбираемся match = static_cast<const char*>( memchr(phaystack, pneedle[0], hayend - phaystack) memchr ищет по первым (hayend - phaystack) байтам в phaystack на предмет совпадения с pneedle[0]. если совпадение найдено, возвращается указатель на первое совпадение в этом случае этот указатель используется в memcmp(match, pneedle, neelen)

оптимизация заключается в том чтоб memcmp делать не по целой строке, а сначал сравнивать последний байт?

и делать memcmp по всей строке только если они совпали?

и делать memcmp по всей строке только если они совпали?

верно

тут особенность еще в том, что мы по сути текст сравниваем. а у него часто бывает именно разница в окончаниях

ну вобщем-то если последний байт не совпадает, то вся строка тоже не совпадает )

если мы ищем полное совпадение

возможно действительно такая оптимизация может иметь место. но я практически уверен что дополнительная проверка негативно скажется на сравнении коротких строк

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

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

в abseil вроде как есть бенчмарки, можно туда напихать своих кейсов и посмотреть

ещё есть тестфреймворк монговский

можно прогнать его несколько раз с патчем и без

но это делать надо на разных архитектурах

текс. малой ждет в садике. побег за ним. Я думаю оптимизацию этой части оставлю на следущий раз. спейчас и так уже не плохо получилось

метод поппера же. надо искать не подтверждение гипотезы, а опровержение :)

до "executionStats" : { "executionSuccess" : true, "nReturned" : 888, "executionTimeMillis" : 20789, "totalKeysExamined" : 473124, "totalDocsExamined" : 435962, после "executionStats" : { "executionSuccess" : true, "nReturned" : 887, "executionTimeMillis" : 10876, "totalKeysExamined" : 473124, "totalDocsExamined" : 37162,

888 vs 887

и то во втором случае не прогретые данные с диска. обычно около 4с

888 vs 887

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

ищет быстро но не очень точно)

надо докопать. возможно дубликат кстати

ну вобщем я бы искал подвох сначла

дя щя малого с садика заберу буду смотреть

у монги хороший тест сьюит

там сразу будет видно если что-то сломалось. а оно похоже сломалось

там сразу будет видно если что-то сломалось. а оно похоже сломалось

да, тесты прогнать надо будет

@dd_bb прикинь

в оригинальном коде ошибка

false positive на "Gas Stationclose" при поиске "Gas Station"

точно ли ошибка?

всмысле считается ли это фразой?

да

посмотри блейм

посмотри блейм

это о чем щя речь?

git blame?