Бази даних і структури даних / крок 06
Як працює повнотекстовий пошук, частина 2: запитання-відповіді й подальші оптимізації
Про що це відео
Перше відео в новому форматі, який автор придумав для своїх патронів: збирати питання під наявним відео і відповідати на них ґрунтовно — тут це продовження до його власноруч побудованого інвертованого індексу (повнотекстовий пошук). Головне покращення прийшло від пропозиції глядача і вбиває накладні витрати Base64 з частини 1: замість одного текстового файлу з бінарником, загорнутим у base64, розділити індекс на два файли — крихітний файл tokens (відсортовані токени + байтовий зсув/довжина блока постингів кожного) і сирий бінарний файл entries. Результат: 1.3 ГБ стискається до 938 МБ + 2 МБ файл токенів; латентність пошуку падає з 15 мс до ~5 мс, бо файл токенів на 2 МБ (зазвичай 200–300 тис. токенів навіть на масштабі, ~6 МБ) просто читається в пам’ять і бінарно шукається там, а потім рівно одне діапазонне читання дістає потрібні постинги. Його улюблений наслідок: великий файл entries може лежати на S3/хмарному сховищі й запитуватися через HTTP Range-запити — робочий повнотекстовий пошук по величезних даних «без жодного сервера, що тримає щось у пам’яті». Q1: як шукати за фрагментом слова (наприклад, «cks» усередині «socks»)? Відповідь: шукати по-іншому не можна, треба по-іншому індексувати — токенайзер вирішує, що можна знайти: n-gram токенайзери (він малює триграми, що ковзають по «family»), edge n-gram, letter/whitespace/keyword/pattern токенайзери, розбиття URL, навіть власні токенайзери, що витягують хештеги чи IP — проходить по довіднику токенайзерів Elasticsearch — ціною у 2–3 рази більшого індексу. Q2: як стискати індекс, коли id документів — це UUID? Відповідь: по суті ніяк — кожна серйозна схема стиснення списків постингів (він показує оглядову статтю про них) припускає відсортовані цілі числа; тож зіставте UUID з int’ами (додаткова int-колонка чи окремий маппінг UUID↔int), що саме й робить MySQL/InnoDB усередині своєю прихованою auto-increment колонкою FTS_DOC_ID (стиснення індексу, UUID проти auto-increment у первинних ключах).
Головне
- Розділення індексу на малий файл токенів (токен + байтовий зсув/довжина) і сирий бінарний файл entries усуває +33% накладних витрат base64: 1.3 ГБ → 938 МБ + 2 МБ, а пошук пришвидшився з 15 мс до ~5 мс (Інвертований індекс, Base64).
- Словник токенів крихітний (88 тис. токенів ≈ 2 МБ; рідко понад 200–300 тис. ≈ 6 МБ), тож він може повністю жити в пам’яті й бінарно шукатися за ~0.2 мс — жодного ризикованого бінарного пошуку по величезному файлу, де можна приземлитися посеред рядка.
- Ідея serverless-пошуку, яку він виділяє: залишити файл entries на S3/CDN і діставати постинги через HTTP Range-запити — повнотекстовий пошук по величезних даних без stateful-сервера пошуку.
- «Якщо хочеш шукати по-іншому — індексуй по-іншому»: пошук підрядка в слові потребує n-gram (або іншого власного) токенайзера, а не хитрішого запиту — показано на триграмах по «family» і довіднику токенайзерів Elasticsearch (n-gram, edge n-gram, letter, keyword, pattern, URL, власні витягувачі хештегів/IP) (Повнотекстовий пошук).
- N-gram-індексація множить розмір індексу в 2–3 рази: ті самі документи, але кожен id документа тепер з’являється проти кожної n-грами замість одного слова — «тут особливо нічого не вдієш».
- Алгоритми стиснення списків постингів (delta, varbyte, багато варіантів з оглядової статті, яку він показує) усі передбачають відсортовані цілі числа; найкращого немає — різні дані вимагають різних схем, а varbyte працює пристойно всюди.
- UUID як id документів перемагають ці компресори; стандартне рішення — маппінг UUID→ціле число — саме це й робить FULLTEXT у MySQL через приховану 8-байтну auto-increment колонку
FTS_DOC_ID(можна оголосити її самому, щоб уникнути прихованої колонки) (UUID проти auto-increment у первинних ключах, MySQL). - На повільнішому залізі розрив жорстокий: звичайний
LIKE-пошук по тих самих даних на HDD просто впав по таймауту за хвилини, тоді як інвертований індекс на розділених файлах працював нормально.