Стендап Сьогодні
📢
Канал в Telegram @stendap_sogodni
🦣
@stendap_sogodni@shevtsov.me в Федиверсі
16.12.2025
Як пошук LIKE взагалі може бути швидким?
Дивись, є в тебе запит: SELECT timestamp FROM logs WHERE message LIKE *failed*. Як можна реалізувати його в базі? (Повнотекстовий пошук поки взагалі забудемо, бо він ще складніший.)
Звичайні індекси за полем нам не допоможуть. Вони є деревом пошуку, та щоб пересуватися в цьому дереві, ми мусимо знати початок рядка. Тож якщо на початку зірочка, то база просто не знає, де до того індексу підступитися.
Та дійсно, навіть за наявністю індексу базі доведеться попросту перебирати всі значення. Звісно, що це буде… повільно. Втім, на допомогу нам прийде індекс за триграмами. (Ну, або N-грамами, узагальнено.)
Триграма — це шматочок тексту довжиною до 3 символів. Наше поле розрізаєaться на всі можливі шматочки:
request failed => r, re, req, e, eq, equ, ... led, ed, d
(Шматочки з одним та двома символами потрібні для коротких запитів. Хоча, скільки разів ти бачив “Для пошуку введіть хоча б 3 символи?” Тепер знаєш, чому.)
Тепер ми будуємо таке саме “традиційне” дерево пошуку, але вже для кожної триграми. Потім, пошуковий запит теж розрізається:
failed => fai, ail, ile, led
Ми шукаємо записи для кожної триграми окремо, а потім перетинаємо результати. Залишається тільки зробити зачистку, щоб прибрати випадкові записи на кшталт fai ail ile led - цей перебір займає вже зовсім трохи часу.
Такий механізм є не у всіх базах; його можна реалізувати й вручну, але тут багато залежить від того, як впорається база з поєднанням всіх цих результатів в один.
Зокрема, в ElasticSearch, де є надшвидкий пошук за багатьма критеріями, це взагалі працює чудово. Особливо якщо то поле має високу кардинальність, наприклад, як база імен — тоді замість довжелезного словника за іменем, де майже кожному імені відповідає лише один документ, буде компактний та ефективний словник за триграмами.