Comments 18
Исходная ситуация такова: таблица в MS SQL базе, 50 миллионов записей, записи добавляются постоянно, удаляются или обновляются крайне редко.
Идея описана интересная. Но это же прям случай, когда очевидно напрашивается горизонтальное масштабирование. Не очень понятно, почему вы не посмотрели в эту сторону, тогда ведь можно было бы не пытаться влезть в ограничения памяти одного сервера?
Все просто, горизонтальное масштабирование позволит хранить больше данных, но не позволит MS SQL Server быстрее искать по полнотекстовому индексу. Вызов функции Containstable на таком объеме данных занимает 98% времени обработки запроса, то есть, по сути те 2-5 секунд, о которых я писал вначале, и принципиально его не ускорить. Вместо этого мы сделали метод, который работает за 10 миллисекунд, эта часть ускорилась в 200-500 раз.
А что до ограничений памяти сервера, то аренда сервера с 64 гигабайтами стоит 50 евро в месяц. И ещё запас для роста в 2 раза остался.
Я не знаю, при помощи какого инструмента можно добиться такого результата "из коробки".
Простите, не так вас понял. Да, это можно. Конкретно в нашей ситуации сначала проще докупать память на одном сервере, чем делать масштабирование. До 256 ГБ можно докупить, дальше упираемся в ограничения используемого железа.
Если же делать из этого публичное решение, то конечно, масштабирование необходимо.
Может что-то упустил, но чем не подошел стандартный "sql server full text search" с их CONTAINS, NEAR, RANK, etc.?
Используем на больших массивах. Скорость высокая. Хотя, изначально тоже что-то пытались создавать свое через CLR-ки.
Нам нужно искать слова с опечатками и просто похожие варианты, и поиск не ограничивается только словами русского / английского языка. Например, на запрос "65U710KB" нужно предложить вариант "65U790KB", если ничего лучшего не было найдено.
Это поиск не для пользователей интернет-магазина, а для администраторов, и такой поиск упрощает их работу.
А почему нельзя хранить уже разбитые на NGram данные в MS SQL (что позволяет исключить этап загрузки) и выполнять поиск на стороне сервера - внутри stored procedure ?
Я в свое время именно так реализовал нечеткий поиск по справочнику лекарственных средств.
Эээ, разве слов, используемых в названиях товаров так много? При добавлении товара, название должно разбиваться на слова, куда войдут все используемые слова (ошибки можно исключить заранее готовым словарем) и индексы и коды товаров, их будет явно меньше 50кк, и уже потом поиск проводить по этим словам, хочешь четкий, хочешь не четкий, если нужно больше (расстояние и порядок слов) доводились уже результат
buckets можно инициализировать по мере появления информации - уменьшит потребление памяти в части пустых списков которые никогда не используется - много кстати таких?
Хорошее замечание, спасибо.
Я даже не знаю, сколько пустых, но давайте попробуем посчитать потенциальную экономию.
public class List<T> : IList<T>, IList, IReadOnlyList<T>
{
private const int DefaultCapacity = 4;
internal T[] _items; // Do not rename (binary serialization)
internal int _size; // Do not rename (binary serialization)
private int _version; // Do not rename (binary serialization)
private static readonly T[] s_emptyArray = new T[0];
........
}Это фрагмент исходного кода .NET 5
Для хранения пустого списка на 64-битной системе потребуется 8 + 4 + 4 = 16 байт. Плюс хранение ссылки на этот список потребует 8 байт, итого 24 байта без учета выравнивания. Потребление памяти с выравниванием я сходу не посчитаю, к сожалению, поэтому оставим так.
Всего у нас 343 000 списков, это дает 8 232 000 байт потенциальной экономии для случаев, когда индекс создали, а использовать не стали.
Думаю, в нашем случае, когда индекс создается в одном экземпляре, экономией 8 мегабайт памяти можно пренебречь ради упрощения кода. С другой стороны, если бы речь шла про переиспользуемую библиотеку, учесть это обязательно нужно.
Возможно, я найду время и оформлю эту идею в виде nuget - пакета, и тогда сделаю ленивую инициализацию.
Первоначальное заполнение занимает около 20-30 минут.
Что касается готовых движков, то те, с которыми я работал раньше, не умели искать по подстроке, то есть, были не способны найти "65U790KB" по запросу "65U790K", а это в нашем случае важно. По сути, такое поведение понятно, они создавались для поиска по тексту на естественном языке. Возможно, сейчас кто-то уже так может, но я положился на свой прошлый опыт.
Второй вариант - использовать готовый движок, но с индексом не по словам, а по триграммам. И сначала у нас был именно такой подход, но в какой-то момент перестала устраивать скорость работы.
Есть еще два аргумента против готового:
Свой поиск получился довольно простым по устройству, и его мы полностью контролируем, а не ограничены настройками готового движка. С другой стороны, мы ограничены своими возможностями, и, например, морфологии у нас никогда не будет.
Мы стараемся минимизировать количество инфраструктурных зависимостей. Сейчас такая зависимость только одна - SQL Server. В общем, такой вот keep it simple.
По поводу префиксного поиска, тот же самый ElasticSearch это прекрасно умеет. Но с другой стороны это инфраструктурная зависимость, возможно есть смысл рассмотреть какой-нибудь LuceneNet?
Все-таки пока 50, и 20-30 минут - это для 50. Но ради заголовка я попробовал и 100, просто продублировав товары с разными Id - работает.
Что касается LuceneNet, то определенно стоит изучить возможности. Но я люблю работать с алгоритмами больше, чем с конфигурациями, а тут такая возможность появилась.
Поиск для конечных пользователей, когда до него дойдет очередь, будем строить на сторонних библиотеках, скорее всего. А требования (или пожелания) к поиску для администраторов как раз лучше закрываются самописным алгоритмом.
Делаем быстрый поиск по неточному совпадению среди 100 миллионов товаров