Бази даних і структури даних / крок 05
Як працює повнотекстовий пошук: будуємо інвертований індекс на практиці
Про що це відео
Автор із нуля будує інвертований індекс промислового рівня на JavaScript і влаштовує йому перегони з MySQL на своїй таблиці товарів на 16.5 млн рядків — спираючись на реальний проєкт, де його команда проіндексувала 300 ТБ даних власноруч написаним інвертованим індексом (наявні інструменти не підходили: незмінні поденні індекси, гео-дані, власна мова запитів). Постановка: B-tree-індекс робить LIKE 'exploiter%' миттєвим, але LIKE '%telegraphers%' — непридатним, бо не можна відсортувати колонку за словом усередині значення (повнотекстовий пошук). Розв’язок: зіставити кожне слово → списку пар (id документа, позиція); позиції вмикають запити на точну фразу і на близькість. Концептуально «оце й усе», решта — інженерія. Оскільки наївна in-memory мапа з 16.5 млн описів потребувала б 10–15 ГБ RAM, він будує індекс через Map-reduce (стаття Google 2004 року, Hadoop, Hadoop streaming — з використанням його власного npm-модуля hadoop-streaming-utils): Node.js-скрипт map видає пари слово/(документ, позиція), Unix sort робить shuffle, скрипт reduce групує по токену. Крок токенізації розібрано по-справжньому: розбиття на токени, викидання stop-words і токенів ≤2 символи, стемінг («conferences»→«conferenc») проти лематизації (краще — його український контрприклад: стемінг «німці» дає «німц», тож пошук «німець» промахується; його проєкт на 300 ТБ використовував лематизатор), і приведення до нижнього регістру. Потім стиснення індексу, етап за етапом із розмірами файлів на екрані: сирий індекс 4 ГБ → сплющення масивів пар 3.4 ГБ → delta-кодування відсортованих id документів (зберігати 100,3,5 замість 100,103,108) 2.3 ГБ → varbyte (variable-byte) стиснення за ідеєю fastintcompress, із бінарним виводом, загорнутим у Base64, щоб лишатися newline-безпечним у текстовому файлі → 1.3 ГБ, менше за власний FULLTEXT-індекс MySQL (1.7 ГБ, який ще й будувався 14 хвилин). Розв’язка: MySQL LIKE '%three words%' = 40 секунд; його JS-пошуковик по файлу = 21 мс, ті самі id документів. Вердикт: у звичайному житті не пишіть це руками — використовуйте вбудований FULLTEXT у MySQL/Postgres або Elasticsearch — але тепер ви знаєте, що вони роблять.
Головне
- B-tree-індекси не можуть обслужити
LIKE '%word%'— сортування за колонкою не може сортувати за словом усередині неї; відповідь — інвертований індекс: слово → [(id документа, позиція), ...], де позиції розблоковують запити на точну фразу і «в межах N слів» (Повнотекстовий пошук, Індекси баз даних). - Концептуально інвертований індекс — це весь фокус («на цьому можна відео закінчити»); усе решта — токенізація, стиснення і механізм запитів.
- Токенізація — це конвеєр: розбиття на токени, фільтрація stop-words (артиклі/прийменники роздувають індекс, не допомагаючи пошуку) і коротких токенів, стемінг або краще лематизація, нижній регістр; той самий конвеєр має виконуватися на кожному пошуковому запиті. Стемінг падає на словах на кшталт «німці/німець»; його продакшн-система на 300 ТБ використовувала лематизатор.
- Він будує індекс через Map-reduce, бо 16.5 млн документів не влізуть у RAM: Node.js-map видає пари,
sort= shuffle, reduce групує по токену — код працював би на справжньому Hadoop streaming, і він написав npm-модульhadoop-streaming-utils, який той використовує. - Стиснення індексу, виміряне наживо: 4 ГБ сирих → 3.4 ГБ сплющені масиви → 2.3 ГБ після delta-кодування відсортованих id документів → 1.3 ГБ після varbyte-кодування (+обгортка Base64, яка коштує +33% і все одно виграє) — обходить розмір FULLTEXT-індексу MySQL (1.7 ГБ).
- Varbyte-стиснення пояснено на дошці: використовуй 7 бітів на байт для числа і 1 біт продовження — малі числа (які й дає delta-кодування) влазять у 1–2 байти замість фіксованих 4/8.
- Результат: 40 с у MySQL з
LIKEпроти 21 мс із його JS-пошуковиком на тих самих 16.5 млн рядків; власний FULLTEXT-індекс MySQL теж відповідає миттєво після побудови (побудова 14 хв). - Історія з фронту: система на 300 ТБ зберігала свій інвертований індекс у MongoDB, мала незмінні поденні індекси («вчорашній індекс уже не оновлюється»), гео-атрибути і власну мову запитів, розібрану через PEG-граматики; він робив про це доповідь на KyivJS. Elasticsearch і FULLTEXT у MySQL/Postgres — це той самий механізм у зручній обгортці, а Sphinx частково втратив популярність, бо спочатку міг лише перебудовувати свій індекс з нуля через cron.