Як працює повнотекстовий пошук? Розбираємо на практиці інвертовані індекси
HTML-код
- Опубликовано: 22 май 2024
- Розбір в деталях, як працюють інвертовані індекси. Інвертовані індекси використовуються для повнотектового пошуку в MySQL, PostgreSQL, Elastic Search та інших базах даних.
Спробував відповісти на наступні питання:
✅Навіщо потрібні інвертовані індекси й які їх можливості?
✅Чому не працюють звичайні індекси для повнотекстового пошуку?
✅Як влаштовані інвертовані індекси всередені?
✅Що таке стемінг й лематизація?
✅Які є механізми компресії інвертованих індексів?
✅Як працює VByte Encoding?
✅Як використати Map Reduce для побудови інвертованого індексу, коли індекс не влазить в пам'ять?
✅Як створити інвертований індекс в MySQL
Приклади коду з відео - github.com/koorchik/jabascrip...
Станьте спонсором цього каналу: / @aboutprogramming
Допоможіть каналу розвиватися й отримуйте доступ до ексклюзивного контенту.
Зміст відео:
0:00 - Вступ
1:29 - Опис даних
2:00 - Чому не працють звичайні індекси
4:45 - Інвертований індекс
9:50 - Навіщо потрібен Map Reduce
15:52 - Код Map
17:10 - Токенизація
18:30 - Стоп слова
19:25 - Стемінг та лематизація
22:20 - Запускаємо Map
22:45 - Фаза Shuffle
24:15 - Код й запуск Reduce
27:25 - Компресія індексу
29:22 - Дельта компресія
33:16 - VByte encoding
41:10 - JS Searcher проти MySQL (без FTS)
44:2 - Повнотекстовий індекс в MySQL
45:32 - Розмір FTS індексу MySQL
46:17 - Деталі про проект
46:46 - Що за кадром?
47:55 - Завершення
🏠 Мої соцмережі:
Жабаскрипт в телеграмі - t.me/jabascript
Я в Твітер - / viktorturskyi
Мій Linkedin - / turskyi
#програмування #українською #mysql #postgres #sql #indexes #programming #javascript #fulltextsearch #elasticsearch #mapreduce
Це найкраще відео, що я бачив з цієї теми. компетенції автора можна тільки позаздрити і поставити собі на мету її досягти! Дякую ❤
Кожне ваше відео додає впевненості щодо наявногоу вас чудового поєднання практичної кваліфікації та вміння ділитись досвідом👏🏻
ого оце якість, мені здається таких каналів або дуже мало або узагалі не має. Дуже дуже дякую за всі відео на каналі
Все по полочках розклав, дякую! Еластіксерч став зрозуміліше)
Величезне дякую, за вашу працю, ваш канал просто знахідка. Дуже круто поданий матеріал, у вас талант)) В попередньому році в університеті частково проходили тему з HDFS, і до кінця не було зрозуміла логіка Map-Reduce, ви за декілька хвилин пояснили сенс:)
Серія відео по базам даних це якась суцільна насолода. Дуже часто платні курси не покривають поглиблених нюансів, а тут все ще й безкоштовно. Дякую!
Дякую за відео, кожну тему дуже цікаво розповідаєте! Якщо можливо, викладайте відео частіше - у вас круто виходить пояснювати складні теми. Окреме дякую за практичну частину
тільки нещодавно задавався питанням про повнотекстовий пошук ,як раз відео
дуже круто! дякую велике за таку цікаву інформацію!
дякую, за вашу роботу, Віктор! ви - крутий:)
Круто, дуже повчально, дуже зрозуміло та гарно пояснено, та продемонстровано! Дуже якісне відео, продовжуйте викладувати, дуже ціную вашу роботу!
супер, дуже круто пояснюєш і головне є код і практика, а не лише теорія! дякую
Унікальний контент. Теорія і практика просто і доступно.
Кльовий відос. Дуже доступно і без води. Віктор, дякую за цікавий контент :)
Супер цікава тема! Дякую 😎
Неймовірно! Просто неймовірно. За академічну годину прояснити досить непросту тему та ще й з адекватними прикладами і кодом.
Дякую, що ділишся глибоким розумінням теми і практичним досвідом!
Це топ! Дякую вам!
гарне відео, дякую
Надзвичайно цікаво та максимально корисно! Дякую за контент
Дуже круте відео!
Дякую за детальні, але при цьому прості і зрозумілі пояснення!
Крутяк. Дуже дякую за такий матеріал.
Дуже цікаво, дякую!
Дякую за розбір цікавої теми! Відео ТОП.
P.S. (є чудовий command-line client для роботи із БД - mycli, раджу спробувати)
Я фронт, але вже хочу вчити бек) Мега інформативно! Буду дивитись всі відоси підряд і всі лайкати по дефолту) дякую!
Як завжди все на вищому рівні. Дякую за цікавий та корисний контент. Чекаємо на наступний випуск)
Як завжди цікаво і як ніколи вчасно. Дякую)
Дуже дякую, топ!
Як завжди, крутий контент, і те що поки-що так мало лайків і переглядів дивує, а з іншої сторони тішить, меньше конкурентів на цьому ринку )))
Дякую! Ціль - зробити ютуб канал, де інженери зможуть покращити свої фундаментальні знання - й такі знання не втрачають актуальності й через роки. Можливо контент не самий хайповий, але він не застаріває, тому впевнений, що ще набере свої перегляди :)
@@AboutProgramming хайпового контенту дуже багато, а унікального, якісного україномовного по програмуванню можна на пальцях однієї руки нарахувати. В деяких авторах україномовний контект починаєтсья і закіньчуєтсья словами "ми з України" (хоча і сам контент цікавий). Так що ваша ціль важлива.
Неймовірно якісне та інформативне відео! Дякую ❤
Клас. Кайфую з кожного відоса, дуже корисно!
Дякую, дуже інформативне і просте для сприйняття відео.
Дуже потужне відео. Дякую!
Дякую за відео, дуже якісно і цікаво)
Топовий Контент
Прикольно. Як завжди цікаво, хоча особисто для себе мало нового дізнався, бо якраз недавно працював над цим і розібрався у темі. Але якби подивився таке відео раніше, то це було б дуже корисно.
Дякую!
Шикарне відео!!! Зрештою, як і всі попередні.
Бракує таких викладачів в університетах, не кажучи, вже про «псевдо курси».
Дякую, що знаходите час ділитися своїми знаннями і досвідом!
дякую за відео
Отличная подача. Благодарность автору
Доступно, практично, цікаво. Дякую за хороший навчальний матеріал і мотивацію до підвищення кваліфікації
Гарне відео
Дуже круті відео та подача, браво
дякую!!!
Дякую за відео, як би було круто якби такі речі розповідали ще в університетах і так само якісно.
Дякую за нові знання)
Невероятно просто и понятно. Огромное спасибо за контент ) Надеюсь видео будут появляться и дальше в стабильном режиме) Успехов тебе 😊
Дуже класне відео - просто і зрозуміло. Хотілося б ще відео по MapReduce/Hadoop/Spark..
Дуже дякую! Гарне відео!
Тепер потрібне відео про усі популярні методології компресій
Згадував цілий пейпер з різними алгоритмами в другій частині про інвестовані індекси. Відео зараз для патронів, але ось посилання на сам пейпер arxiv.org/pdf/1908.10598.pdf 🙂
Це найкраще відео на ютубі) Дякую Віктор! Було не просто цікаво, було захоплююче
Ну ні, найкраще відео на ютубі це ось це ruclips.net/video/VGRQGm4-A4k/видео.htmlsi=SpsxQL_xipsV1Y8R
дякую
Дуже цікавий та зрозумілий розбір, круте відео вийшло. Якщо можна, то як ідея для ще одного - це просторові індекси. Дякую!
О, дякую! Це дуже класна тема. Можна розповісти про той самий Quad tree й в контексті гео пошуку, так й в контексті інших застосувань. Ну й розібрати той самий R tree
Після усіх попередніх відео пазл склався) якщо до цього моменту по темі була лиш база, то тепер вже провиднюється межа, за якою лежать специфічні знання.
та ти крутий чувак)))😎
Надзвичайно корисний матеріал!
❤❤❤❤❤❤❤❤❤❤❤
Круте відео, дякую. Не знаю, як у ноди з оптимізацією, тому можу порадити кілька мікрооптимізацій: 1) створювати сет стоп слів один раз, а не при кожному виклиці функції 2) використовувати reduce замість filter+map для функції tokenize 3) змінити регулярку в функції stemmer, зараз вона не прибирає останню букву s, тому підозрюю, що exact пошук по `inelegantly drop hum` нічого б не знайшов
Думаю, що особливо різниці не буде в загальному перформансі. Але є посилання на код в описі, тому є можливість протестувати 🙂
Чудовий контент, побільше би таких публікаці .🔥
Доречі, що використовуєте для малюваля?
Дякую!) Малюю в стандартному софті на Galaxy Tab
Дякую, легко зрозумів концепції. Питання - яку можна зробити компресію якщо ід документа ююід?
Додати додаткове не UUID поле в таблицю. Так робить той самий MySQL - dev.mysql.com/doc/refman/8.0/en/innodb-fulltext-index.html#innodb-fulltext-index-docid
або окремий мапінг з INTEGER на UUID. Це буде сильно дешевше, оскільки UUID документа буде зустрічатися стільки разів в інвертованому індексі, скільки є слів/токенів в документі
Супер відео! 👍👍👍 є питання від чайника: індекси для всіляких blob/longblob, varchar(max) мають будуватись за іншими принципами? Чи різниці в підході нема?
Концептуально різниці немає. Але пару невеликих особливостей є, які зумовлені розміром даних. blob й text занадто великі, щоб їх класти в індекс (зараз про додаткові індекси) - тому в індекс можна помістити тільки частину блобу (тобто треба вказати довжину, яку взяти при створенні індексу). Але тоді виникає питання, як бути з кластерними індексами, якщо кластерний індекс й є наші дані й ми не можемо зберігти лише частину даних. Тому тут поведінка така, якщо розмір даних в межах певних лімітів, то зберігаємо в кластерному індексі, якщо за межами ліміту, то в індексі зберігаємо вказівник на блоб, а сам блоб в окремих сторінках даних (щось схоже на файлову систему виходить)
🤝🤝🤝
Буууууууум 🤯
Це база, яка прям дуже необхідна і цікава. 2+ роки працюю фронт-енд девом і без цих знать.... Аж соромно😅
90% - 95% -- матеріалу зрозуміло. Дякую і продовжуй)))
Завтра на роботі додивлюсь, всеодно на бенчі вже пів року😓
які ще індекси на фронт-енді?) всі фронт деви, яких я коли-небудь знав це html, css і show/hide/animation на джаваскріпті)
Відео супер, дякую автору. Вікторе, ви робите дуже корисну справу!
Не зрозумів лише одне по відео: якщо ми шукаємо не все слово всередині опису товару, а, наприклад, якийсь склад, як в такому разі має будуватись індекс?
Умовно маємо:
Id, description
1, best clocks you ever wear
2, some socks for your family
Конкретний приклад працює лише для слів. А якщо юзер буде шукати %ock%?
Дякую за відгук :) Відносно пошуку по складу, то це залежить від токенайзера. Наприклад, можна використати ngram tokenizer. Тоді слово family буде розбите на наступні токени біграми (беремо 2 літери після кожного символу): fa, am, mi, il, ly. Й тоді, коли йде пошук по "mil", то будуть шукатися токени mi, il (або для пошуку можна задати інший токенайзер, не той, що викоритовувася для індексу). Також можна написати токенайзери під специфічні задачі, наприклад щоб індексувати тегі або url розбивати на частинки. Основна ідея, що з пошуком особливо не вигадаєш, а от в індекс можна класти будь-що :)
Ну, й ngram tokenizer сильно збільшить розмір індекусу, оскільки у нас значно зросте кількість токенів в індексі
@@AboutProgramming дякую! Ось цей момент і цікавив. Що якщо ми розбиваємо по складам, то виходить в рази більше данних в індексі.
З ваших пояснень стає все на багато зрозуміліше і на дахає копатися ще глибше. Чи не могли б ще розповісти про нереляційні БД?
Там всередин в цілому те саме. Хоча Redis цікаво реалізований, можливо про нього треба зробити якось відео
@@AboutProgramming а як щодо касандри?
База цікава, але дуже небагато проектів її потребують
цікаво скільки би вийшло якщо відмовитись від base64 і наприклад додавати після кожного слова довжину бінарної строки. Класне відео, аж самому захотілось так поексперементувати. Ще раз дякую!
Є ще спонсорське відео (продовження), в якому я придбав base64 й розбив індекс на два файли. Вдалося зменшити відповідно розмір індексу й зробити дешевшим бінарний пошук по словам
Пане Вікторе, дуже дякую за відео, дізнався багато чого нового. Не зрозумів один момент: як ми змогли суттєво зменшити розмір файлу після дельта компресії, якщо числа, як Ви сказали потім, зберігаються у 32/64 байтах. Економія завдяки комбінації методів дельта компресії та vbyte очевидна, а от тільки завдяки компресії, не до кінця.
Дякую!) Відносно дельта компресії гарне питання. Число займає 32/64 біти в пам'яті процесу, але при серіалізації в JSON короткі числа займають менше місця, бо JSON це просто строка. Наприклад, число 5 це один символ й відповідно один байтів, а число 1000000000 десять символів й відповідно десять байтів
@@AboutProgramming Дуже дякую
+
скільки зараз може отримувати програміст SQL початківець та на скільки важко влаштуватися на роботу ?
Роботу початківцю зараз дуже складно. Відносно SQL, то це зазвичай одна з навичок потрібна для програміста чи дата аналітика. Відносно ЗП, то на DOU є гарна аналітика з фільтрами по рокам досвіду й по профілю jobs.dou.ua/salaries/
GO UA!
для ElasticSearch є плагін Ukrainian analysis. Але по ньому щось немає ніякої інформації. Хтось із цим працював? Може знаєте, де можна більше інформації про нього знайти? Можна якось кастомно задати токенайзер для українського аналізатора?
Думаю, можна просто підключити будь який токенайзер написавши свій analysis плагін. Відносно Ukrainian analysis, то ніби він там просто юзає Morfologic github.com/elastic/elasticsearch/blob/f42b7652bfb4949630347558fc4cae90926cb388/plugins/analysis-ukrainian/src/main/java/org/elasticsearch/plugin/analysis/ukrainian/UkrainianAnalyzerProvider.java#L19
Ось - lucene.apache.org/core/7_3_0/analyzers-morfologik/org/apache/lucene/analysis/uk/UkrainianMorfologikAnalyzer.html
Але сам я з цим плагіном не працював 🙂
Я гадаю що замість того щоб окремо компресити - потрібно початково писати код який буде в норм форматі/структурі на виході. Також, думаю, що дельта компресія тільки гірше швидкості пошуку може зробити, без неї можливо швидше шукатиме
Буду радий побачити робочий приклад) Інвертоааний індекс це й є структура, яка передбачає, що у нас є слова й списки айдішек до них. Можна змінити формат серіалізації, щоб прибрати base64 (робив в іншому відео), але структура залишиться така сама. Відносно дельта компресії, то можете протестувати, але ймовірно, що буде тільки повільніше, бо треба буде читати більше даних з диску. Дельта компресія це ключова вимога для всіх інших видів компресії, бо вони вимагають малих чисел. Ось гарний аналіз на цю тему arxiv.org/pdf/1908.10598.pdf
А що якщо ми додамо новий рядок в БД, нам ж не треба перетворювати цілий індекс?
Залежить від того, як він збережений. Той самий sphinx колись вимагав повної перебудови, а потім додали інкрементний апдейт. Тобто перебудовувати весь може й не треба, але додаткові дані треба додати й тоді треба буде вигадувати якусь блочну системи зберігання даних, щоб можна було перезберігати тільки специфічні блоки. Або використовувати sparse матрицю (наприклад, hbase) для зберігання індексу й тоді можна оновлювати все в реальному часі . Якщо ми використовуємо full text search фічу бази даних, то там вона працює з блоками завжди й там інкрементальна перебудова
чого stemmer не називають normalise? чи називають ?
Normilise це просто ширше поняття. Наприклад, приведення до нижнього регістру це теж нормалізація. Тобто нормалізація може включати крок стемінгу, а може й не включати. Також замість стемінгу може використовуватися лематизація
Цікаво чи користуються великі компанії самописними індексами. Хотів би ще попросити якщо буде у вас можливість створити відео про роботу пошти. А саме протоколи, безпека, відправка з локальної машини на лінуксі.
Відносно індексів.
Якщо компанія створює індекси, то це по сути власний механізм зберігання й пошуку по даним, тобто власна база даних й це часто зустрічається (rocksdb, dynamodb, spanner, documentdb, mssql etc). Якщо питання саме про повнотекстові індекси, то Google й Microsoft точно роблять, бо у них є пошук. У Facebook є Graph Search. Часом це повноцінні системи написані з нуля, часом це якісь системи, які використовують якісь бібліотеки по типу Lucene, як це робить Elastic. Але це значна інвестиція й в більшості випадків просто беруть готове рішення.
Відносно відео про пошту. Може бути цікава тема, доводилося приймати участь в розробці декількох поштових систем. Дякую за ідею :)
Як ідея для наступного відео - як працює реплікація даних коли в тебе є декілька data storage. Наприклад основна БД - MySQL для OLTP а Elasticsearch для хитрого пошуку.
Тут складно щось конкретне розповісти, бо це буде сильно залежати від нюансів проекту. Тобто в залежності від задачі можна прийти до зовсім різних архитектур. Але як варіант можна зробити відео про реплікацію й шардінг як просто концептів й розібрати різні варіанти імплементації
Это... Просто... Ахуенно...
Еще можно проиндексировать сами слова индексы и можно обгонять FTS :D
Цікаво що робити, якщо в слові граматична помилка. В українській мові це не велика проблема, а от в англійській чи німецькій, мені здається це дуже поширено, коли важко правильно написати слово. Доволі популярне “treat or trick” клієнтом може бути просто неправильно написано. Наче як ElasticSearch має повернути якісь результати, але з нижчим score. Та й у Google певно також має бути якийсь механізм пошуку по помилково написаним словам? 🤔 чи це stemmer якось вирішує заміняючи слова на граматично правильні? Чи слова бʼються на частини, а потім ці частини порівнюються?
Гарне запитання. По ідеї, це можна робити на етапі стемінгу, але це може бути просто окремий крок в пайплайні. Також в пайплайн можна додати й фонетичну обробку, щоб шукати по вимові, наприклад. Також слова не обов'язково заміняти, а можна зберігати відразу декілька варіантів
@@AboutProgramming Я так розумію однозначно правильного рішення тут прям немає і треба дивитися що краще працює? Фонетична обробка звучить не тривіально, а зберігати одразу декілька варіантів значно збільшить розмір індексу. Цікаво як саме Google вирішує цу проблему?
@@UAFMeyer відносно Гугла, то таких деталей навіть не й знаю. Там пошук значно складніший, той самий knowledge graph, який намагається працювати з сенсом слова й багато всього іншого
@@AboutProgramming Дякую. Треба буде почитати детальніше про це все 👍
Хочу поставити 2 лайки або навіть 3)
на кожний пук в таблиці перезаписувать більше 1гб на такій к-ті даних, ну хз, можливо є краще рішення
Це найпростіша схема збереження, але можна мати блочну структуру й оновлювати частину файлів. Різні імплементації працюють по різному. Той самий sphinx колись вмів тільки повністю перебудовувати індекс, зараз підтримує інкрементний апдейт. Насправді, insert нового документа не така велика проблема, а от модифікації це проблема (той самий еластік не дозволяє апдейти, але можна зробити інсерт нової версії). Але так, навіть інсерт вимагатиме апдейту великої кількості блоків, бо треба оновити індекс для кожного токена з документа, тому часто дані пишуться в пам'ять й періодично флашаться на диск (але так працює навіть звичайний інсерт в таблицю в MySQL)
Вцілому Python більш наочно виглядає ніж JavaScript.
Не сперечаюся, але JS має плюс, що його розуміє більша аудиторія й можна робити приклади й для фронту. Ну, й я маю досвіду більше з JS 🙂
погоджуюсь з "виглядає" та зовсім не практичний по швидкодії. Не знаю як зараз, але попередня версія була повільнішою в 10 раз в тестах з простими циклами. Загалом якщо поставит руку на серце і відповісти на запитання чим відрізняються мови програмування, то відповідь буде: зручністю роботою з масивами та об'єктами. Все інше повторюється, але швидкість виконання у кожного різна. На диво JS працює супер швидко. Робив власні тести на 5 мовах в тому числі і Пайтон, який найбільше розчарував. Однак нейронку писати зручно на Пайтон, оскільки там ми й використовуємо зручність і простоту роботи з масивами. Це університетська мова, зручна для викладання, презентацій
Дуже цікаве і корисне відео. Але є недоліки.
Автор занадто відхилився в сторонні теми, якось підзабувши про власне повнотекстовий пошук.
І найгірше, упустив головний нюанс повнотекстового пошуку - relevance score, тобто сортування по релевантності.
Повнотекстовий пошук не для того, щоб вибрати якусь підмножину з множини всіх документів. Ні, він може повертати навіть ВСІ документи - але посортовані по релевантності.
Грубо кажучи, якщо є веб магазин де в описі одного товару - нехай це буде книга - слово макроекономіка зустрічається один раз, а в описі іншого - два рази, то при пошуці по цьому слову мають повернутись обидва товари, але другий із вищою релевантністю, тобто першим в результатах.
Ну і звичайно є ще важливі фічі у ElasticSearch які дає Lucene - fuzzy пошук та facets, про які варто було розказати.
Для мене головне як влаштований індекс, а як працює сортування результатів, то вже додатковий аспект. Відео й так найдовше на каналі вийшло 🙂 Сортування в різних системах часто працює по різному. Наприклад MySQL in boolean mode взагалі не використовує relevance score. У Google для relevance score є knowledge graph й page rank. Той самий sphinx спочатку мав одні режими запитів, а потім був розширений більш складними й тд. Також не було задачі розповісти про якийсь рушій для пошуку, а показати, що всередині концептуально. Демо реалізації власного алгоритму ранжування не було б таким корисним в межах цього відео. А розповідати про facets, це як розповідати про джойни в відео про B-tree індекси. Але так, згадати, що таке є, можна було б в відео. Дякую за коментар
@@AboutProgramming Це не питання лише сортування - як сортування по якійсь колонці в реляційних базах. Суть змінюється якщо query повертає всі документи.
"Наприклад MySQL in boolean mode взагалі не використовує relevance score"
Власне. Бо це реляційна база а не повноцінний full text search engine.
Привіт цікаві відео, ось тема яка можливо також була б цікава webrtc, дякую за контент
дуже цікаве відео, дякую