Apache Pinot - это распределенное хранилище данных OLAP в реальном времени, созданное для предоставления масштабируемой аналитики в реальном времени с низкой задержкой.

Pinot поддерживает сверхбыструю обработку запросов через свои индексы в столбцах, отличных от BLOB. Запросы с фильтрами точного соответствия выполняются эффективно за счет комбинации кодировки словаря, инвертированного индекса и отсортированного индекса. Однако произвольные запросы текстового поиска не могут использовать индексы и требуют полного сканирования таблицы.

В этом посте мы обсудим недавно добавленную поддержку текстовых индексов в Pinot и то, как их можно использовать для эффективных полнотекстовых поисковых запросов.

Давайте рассмотрим несколько примеров, чтобы лучше понять это.

Точное совпадение со сканированием

ВЫБЕРИТЕ СЧЕТЧИК (*) ИЗ MyTable, ГДЕ firstName = «Джон»

В приведенном выше запросе мы выполняем точное соответствие столбца firstName, не имеющего индекса. Механизм выполнения найдет соответствующие docIds (также известный как rowId) следующим образом:

Точное совпадение с инвертированным индексом

Если в столбце firstName есть инвертированный индекс, для поиска по инвертированному индексу будет использоваться dictionaryId. вместо сканирования прямого индекса.

Точное совпадение с отсортированным индексом

Если таблица отсортирована по столбцу firstName, мы используем dictionaryId, чтобы найти отсортированный индекс и получить начальные и конечные docIds всех строк, которые имеют значение «John».

На следующем графике показаны задержки для запросов с точным соответствием с индексом и без него для набора данных из 500 миллионов строк и избирательности (количества строк, прошедших фильтр) 150 миллионов.

Текстовый поиск со сканированием

Что, если пользователь заинтересован в поиске произвольного текста? В настоящее время Пино поддерживает это с помощью встроенной функции REGEXP_LIKE.

SELECT COUNT(*) FROM MyTable WHERE REGEXP_LIKE(firstName, ‘John*’)

Предикат - это регулярное выражение (префиксный запрос). В отличие от точных совпадений, индексы нельзя использовать для оценки фильтра регулярных выражений, и мы прибегаем к полному сканированию таблицы. Для каждого необработанного значения сопоставление с образцом выполняется с помощью регулярного выражения «John *», чтобы найти соответствующие docIds..

Текстовый поиск с индексом

Для произвольных текстовых данных, которые попадают в территорию BLOB / CLOB, нам нужно больше, чем точное совпадение. Пользователи заинтересованы в выполнении регулярных выражений, фразовых и нечетких запросов к данным, подобным BLOB. Как мы только что видели, REGEXP_LIKE очень неэффективен, поскольку использует сканирование всей таблицы. Во-вторых, он не поддерживает нечеткие поисковые запросы.

В Pinot 0.3.0 мы добавили поддержку текстовых индексов для эффективного выполнения произвольного текстового поиска в столбцах STRING, где каждое значение столбца представляет собой BLOB разнородного текста. Выполнение стандартных операций фильтрации (равенство, диапазон, между, в) не соответствует требованиям к текстовым данным.

Текстовый поиск можно выполнить в Пино с помощью новой встроенной функции TEXT_MATCH.

SELECT COUNT(*) FROM Foo 
WHERE TEXT_MATCH (<column_name>, <search_expression>)

При поддержке текстовых индексов давайте сравним эффективность запроса текстового поиска с индексом и без него для набора данных из 500 миллионов строк и избирательности фильтра 150 миллионов.

Проблема индексирования текста

Как и другие индексы базы данных, целью текстового индекса является эффективная обработка фильтров для повышения производительности запросов.

Для эффективной поддержки регулярного, фразового и нечеткого поиска структура данных текстового индекса должна иметь несколько фундаментальных строительных блоков для хранения ключевой информации.

Словарь

Словарь сопоставляет каждый проиндексированный термин (слово) с соответствующим dictionaryId, чтобы обеспечить эффективное сравнение с использованием целочисленных кодов фиксированной ширины по сравнению с необработанными значениями.

Инвертированный индекс

Инвертированный индекс сопоставляет dictionaryId каждого проиндексированного термина с соответствующим docId. На запросы с точным соответствием терминов (один или несколько терминов) можно эффективно ответить с помощью словаря и инвертированного индекса.

Информация о позиции

Фразовые запросы (например, поиск документов, соответствующих фразе «машинное обучение») являются расширением точных запросов терминов, где термины должны располагаться в одном и том же порядке в соответствующих документах. Эти запросы нуждаются в информации о местоположении вместе со словарем и инвертированным индексом.

Автоматы для регулярных выражений и нечетких запросов

Запросы с регулярными выражениями (включая префикс, подстановочные знаки) и нечеткие запросы потребуют сравнения с каждым термином в словаре, если префикс не является фиксированным. Должен быть способ избавиться от сравнений.

Если мы можем представить входящее регулярное выражение как конечный автомат, так что конечный автомат является детерминированным и принимает набор терминов, тогда мы можем использовать конечный автомат вместе со словарем, чтобы получить dictionaryIds всех совпадающих терминов, принятых конечным автоматом.

Поиск на расстоянии с нечетким редактированием также может быть эффективно выполнен путем представления запроса в виде конечного автомата на основе автоматов Левенштейна и пересечения автоматов со словарем.

Как обсуждалось ранее, словарь и инвертированный индекс Пино могут помочь эффективно ответить на запросы терминов с точным соответствием. Однако запросы с фразами, регулярными выражениями, подстановочными знаками, префиксами и нечеткими запросами требуют информации о местоположении и конечных автоматов, которые в настоящее время не поддерживаются в Пино.

Мы узнали, что в Apache Lucene есть необходимые недостающие элементы, и решили использовать его для поддержки полнотекстового поиска в Pinot, пока мы не улучшим наши структуры индекса.

Создание текстовых индексов в Пино

Давайте обсудим создание текстовых индексов Lucene в Пино как ряд ключевых дизайнерских решений и проблем.

Текстовый индекс на столбец

Формат хранения таблиц Пино - столбец. Структуры индекса (прямой, инвертированный, отсортированный, словарь) для таблицы также создаются для каждого столбца, для каждого сегмента (осколка). Для текстового индекса мы решили придерживаться этого фундаментального дизайна по следующим причинам:

  • Эволюция и обслуживание проще. Пользователь может включать или отключать индексирование текста для каждого столбца таблицы.
  • Наши эксперименты с производительностью показали, что создание глобального индекса в Lucene для всех столбцов таблицы с включенным текстовым индексом снижает производительность. Глобальный индекс больше, чем индекс для столбца, что увеличивает время поиска.

Формат текстового указателя

Как и другие индексы, текстовый индекс создается как часть создания сегмента Пино. Для каждой строки в таблице мы берем значение столбца, в котором включена индексация текста, и инкапсулируем его в документ.

Документ состоит из двух полей:

  • Текстовое поле - содержит фактическое значение столбца (docValue), представляющее основной текст, который необходимо проиндексировать.
  • Сохраненное поле - содержит монотонно увеличивающийся счетчик docId для обратного сопоставления каждого документа, проиндексированного в Lucene, с его docId ( rowId) в Пино. Это поле не токенизируется и не индексируется. Он просто хранится внутри Lucene.

Хранение Pinot DocId в Lucene Document

Сохраненное поле критично. Для каждого документа, добавляемого в текстовый индекс, Lucene назначает документу монотонно увеличивающийся docId. Позже операция поиска по индексу возвращает список совпадающих идентификаторов документов.

Индекс Lucene состоит из нескольких независимых субиндексов, называемых сегментами (не путать с сегментом Пино). Каждый субиндекс Lucene является независимым автономным индексом. В зависимости от размера проиндексированных данных, от того, как часто документы в памяти из индекса сбрасываются в представление на диске, один текстовый индекс может состоять из нескольких субиндексов.

Здесь важно отметить, что внутренние идентификаторы документов Lucene относятся к каждому субиндексу. Это может привести к ситуациям, когда документ, добавленный в текстовый индекс для данной строки в таблице Пино, не имеет того же Lucene docId, что и Пино docId.

Для запроса с фильтром текстового поиска это приведет к неверным результатам, поскольку наш механизм выполнения (обработка фильтров, поиск по индексу и т. Д.) Основан на docIds. Поэтому нам нужно однозначно связать каждый документ, добавленный в индекс Lucene, с соответствующим Pinot docId. Вот почему StoredField используется в качестве второго поля в документе.

Текстовый анализатор

Обычный текст используется в качестве входных данных для генерации индекса. Анализатор выполняет шаги предварительной обработки предоставленного входного текста.

  • Нижний кожух
  • Разбивает текст на индексируемые и доступные для поиска токены / термины.
  • Удаляет стоп-слова (a, an, the и т. Д.)

В настоящее время мы используем StandardAnalyzer, который достаточно хорош для стандартного английского алфавитно-цифрового текста и использует алгоритм сегментации текста Unicode для разбиения текста на токены. Анализатор также используется при выполнении запроса при поиске по текстовому индексу.

Создание текстового индекса как в автономном режиме, так и в режиме реального времени

Pinot поддерживает прием и запросы данных в режиме реального времени. Текстовые индексы поддерживаются для офлайн, реального времени и гибридных таблиц Пино.

IndexWriter используется для создания текстовых индексов. Он буферизует документы в памяти и периодически сбрасывает их в каталог индексов Lucene на диске. Однако данные не видны IndexReader (используемому в пути поискового запроса) до тех пор, пока писатель не зафиксирует и не закроет индекс, который fsync’s каталог индекса и не сделает данные индекса доступными для читателя.

IndexReader всегда просматривает моментальный снимок (зафиксированных данных) индекса на момент открытия средства чтения из каталога индекса. Это хорошо работает для автономных таблиц, поскольку автономные сегменты Пино не обслуживают данные для запросов до тех пор, пока они не будут полностью созданы, и являются неизменяемыми после создания. Текстовый индекс создается во время генерации сегмента пино и готов обслуживать данные для запросов после того, как сегмент полностью построен и загружен (отображение памяти) на серверах пино. Таким образом, средство чтения текстового индекса на пути запроса всегда просматривает все данные сегмента для автономных таблиц.

Однако описанный выше подход не будет работать для таблиц Пино реального времени или гибридных таблиц Пино, поскольку эти таблицы можно запрашивать во время использования данных. Для этого требуется возможность поиска по текстовому индексу на пути запроса, поскольку IndexWriter выполняет незафиксированные изменения. В следующих разделах подробно рассматривается выполнение запросов как в автономном режиме, так и в режиме реального времени.

Запрос текстовых индексов в Пино

Мы улучшили наш синтаксический анализатор запросов и механизм выполнения с помощью новой встроенной функции text_match (), которая будет использоваться в предложении WHERE запросов. Синтаксис:

TEXT_MATCH (‹columnName›, ‹searchExpression›)

  • columnName: Имя столбца, по которому выполняется текстовый поиск.
  • searchExpression: поисковый запрос в соответствии с синтаксисом запроса Lucene.

Возьмем пример файла журнала запросов и файла резюме:

  • Сохраните журнал запросов и возобновите текст в двух столбцах STRING в таблице Пино.
  • Создайте текстовые индексы для обоих столбцов.

Теперь мы можем выполнять различные виды анализа текста в журнале запросов и данных возобновления:

Подсчитайте количество групп по запросам между фильтрами по времени

SELECT count(*) FROM MyTable 
WHERE text_match(logCol, ‘\”timecol between\” AND \”group by\”’)

Подсчитайте количество кандидатов, у которых есть "машинное обучение" и "обработка графического процессора"

SELECT count(*) FROM MyTable 
WHERE text_match(resume, ‘\”machine learning\” AND \”gpu processing\”’)

Пожалуйста, обратитесь к документации пользователя, где вы найдете подробное руководство по различным типам запросов текстового поиска и по написанию поисковых выражений.

Создание читателя текстового индекса для автономных сегментов Пино

Текстовый индекс создается в каталоге с помощью IndexWriter как часть генерации сегмента пино. Когда серверы pinot загружают (карту памяти) автономный сегмент, мы создаем IndexReader, который отображает в памяти каталог текстового индекса. Экземпляр IndexReader и IndexSearcher создается один раз для сегмента таблицы в столбце с текстовым индексом.

Мы решили использовать MMapDirectory вместо RAMDirectory, поскольку первый использует эффективный ввод-вывод с отображением памяти и генерирует меньше мусора. RAMDirectory может быть очень эффективным для небольших индексов в памяти, но значительно увеличивает накладные расходы кучи.

Выполнение текстового фильтра

На следующей диаграмме показано выполнение на уровне сегмента следующего запроса текстового поиска.

SELECT count(*) from Table 
WHERE text_match(textCol1, expression1) 
AND text_match(textCol2, expression2)

Создание читателя текстового индекса для сегментов Пино в реальном времени

Текстовые индексы в сегментах Пино в реальном времени можно запрашивать во время использования данных. Lucene поддерживает поиск NRT (почти в реальном времени), позволяя открывать программу чтения из живого писателя, тем самым позволяя читателю просматривать все незафиксированные данные индекса из писателя. Однако, как и любой другой считыватель индексов в Lucene, считыватель NRT также является считывателем моментальных снимков. Таким образом, считыватель NRT необходимо будет периодически открывать заново, чтобы видеть инкрементальные изменения, вносимые модулем записи динамического индекса.

  • Наш читатель текстового индекса в реальном времени также действует как писатель, поскольку он как добавляет документы в индекс как часть потребления сегмента в реальном времени, так и используется потоками запросов Pinot.
  • Во время запуска сервера Pinot мы создаем единый фоновый поток. Поток поддерживает глобальную кольцевую очередь сегментов реального времени по всем таблицам.
  • Поток просыпается после настраиваемого порогового значения, опрашивает очередь, чтобы получить сегмент в реальном времени, и обновляет средство поиска индекса в модуле чтения в реальном времени для каждого столбца, имеющего текстовый индекс.

Как часто должно происходить обновление?

Определение настраиваемого порога между последовательными обновлениями фоновым потоком - это то, что следует настраивать в зависимости от требований.

  • Если порог низкий, мы часто обновляем, и запросы с фильтрами text_match на потребляющих сегментах быстро увидят новые строки. Обратной стороной является множество мелких операций ввода-вывода, поскольку для обновления средства чтения текстовых индексов требуется очистка от активного средства записи.
  • Если порог высокий, мы сбрасываем его реже, что увеличивает задержку между добавлением строки в текстовый индекс потребляющего сегмента и появлением в результатах поиска по запросу с фильтром text_match.
  • Это компромисс между постоянством и производительностью.

Ключевые оптимизации

До сих пор мы обсуждали, как текстовый индекс создается и запрашивается в Пино. Мы также поговорили о некоторых дизайнерских решениях и проблемах. Теперь давайте обсудим детали оптимизации, которую мы реализовали, чтобы получить желаемую функциональность и производительность.

Использование коллектора

Для поискового запроса поведение Lucene по умолчанию - это оценка и ранжирование. Результатом вызова to indexSearcher.search() является TopDocs, который представляет N первых совпадений запроса, отсортированных по убыванию оценок. В настоящее время в Пино нам не нужны никакие функции оценки и ранжирования. Мы просто заинтересованы в получении всех совпадающих идентификаторов документов для данного запроса текстового поиска.

Наши первоначальные эксперименты показали, что путь кода поиска по умолчанию в Lucene приводит к значительным накладным расходам кучи, поскольку он использует PriorityQuery в TopScoreDocCollector. Во-вторых, накладные расходы кучи возрастают с увеличением количества совпадающих документов.

Мы реализовали интерфейс Коллектор, чтобы обеспечить простой обратный вызов indexSearcher.search(query, collector) операции. Для каждого соответствующего docId Lucene вызывает обратный вызов нашего сборщика, который сохраняет docId в растровом изображении.

Удаление стоп-слов

Текстовые документы, скорее всего, содержат общеупотребительные английские слова, такие как a, an, the и т. Д.. Они известны как стоп-слова. Стоп-слова обычно никогда не используются при анализе текста, но из-за высокой частоты их появления размер индекса может резко увеличиваться, что, в свою очередь, снижает производительность запроса. Мы можем настроить Анализатор для создания пользовательских фильтров токенов для входящего текста. Процесс фильтрации в анализаторе удаляет все стоп-слова при построении индекса.

Использование предварительно созданного сопоставления Lucene docId с Pinot docId

Как обсуждалось выше, настоятельно необходимо хранить docId Пино в каждом документе, добавленном в индекс Lucene. Это приводит к двухпроходному выполнению запроса:

  • Операция поиска возвращает растровое изображение соответствующих lucene docIds.
  • Перебирайте каждый docId, чтобы получить соответствующий документ. Получите идентификатор пино из документа.

Получение всего документа из Lucene сильно затруднило работу ЦП и стало серьезным узким местом при тестировании пропускной способности. Чтобы избежать этого, мы повторяем текстовый индекс один раз, чтобы получить все сопоставления ‹lucene docId, pinot docId› и записать их в файл с отображением памяти.

Поскольку текстовый индекс для автономных сегментов неизменяем, это работает хорошо, поскольку мы оплачиваем стоимость извлечения всего документа только один раз, когда сервер загружает текстовый индекс. Файл сопоставления позже используется во время выполнения запроса с помощью обратного вызова сборщика для сокращения пути поиска и непосредственного построения растрового изображения результатов pinot docIds.

Эта оптимизация вместе с сокращением стоп-слов дала нам 40–50-кратное повышение производительности запросов, позволяя масштабировать задержку с увеличением количества запросов в секунду. На следующем графике сравнивается задержка до и после этой оптимизации.

Отключить кеш результатов запросов Lucene

В Lucene есть кеш для повышения производительности запросов с повторяющимися выражениями текстового поиска. Хотя повышение производительности заметно, кеш увеличивает накладные расходы кучи. Мы решили отключить его по умолчанию и позволить пользователю включать (при необходимости) для каждого текстового индекса.

Использовать составной формат файла

Структуры индексов на диске Lucene хранятся в нескольких файлах. Рассмотрим случай 2000 сегментов таблицы на сервере Pinot, каждый сегмент таблицы Pinot имеет текстовый индекс в 3 столбца с 10 файлами на текстовый индекс. Мы смотрим на 60k открытых файловых дескрипторов. Очень вероятно, что система столкнется с проблемой слишком много открытых файлов.

Итак, IndexWriter использует формат составного файла. Во-вторых, когда текстовый индекс полностью построен для столбца, мы принудительно объединяем несколько субиндексов Lucene (которые также называются сегментами в терминологии Lucene) в один индекс.

Настроить порог буфера в памяти

Поскольку документы добавляются к текстовому индексу во время генерации сегмента Пино, они буферизируются в памяти и периодически сбрасываются в структуры на диске в каталоге индексов. По умолчанию Lucene сбрасывает данные после использования памяти до 16 МБ. Мы поэкспериментировали с этим значением и сделали несколько наблюдений:

  • Флеш дает сегмент Lucene. По мере создания большего количества из них Lucene может решить объединить несколько / все из них в фоновом режиме. Наличие нескольких таких сегментов увеличивает количество файлов.
  • Пороговое значение по умолчанию, равное 16 МБ, не означает, что средство записи индекса будет использовать 16 МБ кучи перед сбросом. Фактическое потребление намного выше (около 100 МБ), по-видимому, потому, что в Java нет хорошего способа программно отслеживать объем используемой памяти кучи.
  • Меньшие пороги приводят к большому количеству мелких операций ввода-вывода, а не к меньшему количеству больших операций ввода-вывода. Мы решили оставить это значение настраиваемым и выбрали 256 МБ по умолчанию, чтобы сохранить хороший баланс между накладными расходами памяти и количеством операций ввода-вывода.

Дополнительные номера производительности

Мы также провели микротест, чтобы сравнить время выполнения text_match и regexp_like на таблице Пино с одним Сегмент, содержащий 1 миллион строк. Использовались два разных типа тестовых данных:

  • Данные журнала: столбец STRING в таблице Пино, где каждое значение представляет собой строку журнала из журнала доступа к apache.
  • Не журнальные данные: столбец STRING в таблице Пино, где каждое значение представляет собой текст резюме.

На следующем графике показано, что поисковые запросы с использованием текстового индекса выполняются значительно быстрее по сравнению с сопоставлением с образцом на основе сканирования.

Другая оценка была проведена с помощью собственного инвертированного индекса Пино, чтобы понять, когда использование текстового индекса может быть неправильным решением.

  • Текст, разделенный пробелами, может быть сохранен в Пино как многозначный столбец STRING.
  • Пино создаст словарь и инвертированный индекс для этого столбца.
  • Если требуются только точные совпадения терминов (с использованием операторов =, IN), то текстовый индекс не является правильным решением. Инвертированный индекс Пино может определять точное совпадение терминов в 5 раз быстрее, чем Lucene.
  • Однако, если требуется фраза, регулярное выражение (включая префикс и подстановочный знак) или нечеткий поиск, то текстовый индекс является правильным выбором как с точки зрения функциональности, так и производительности.

Предстоящая работа

Предварительно построенное сопоставление lucene docId с pinot docId работает для автономных сегментов, поскольку текстовый индекс неизменен. Для сегментов, потребляющих в реальном времени, эта оптимизация неприменима, поскольку индекс изменяется во время обслуживания запросов. Работа по оптимизации перевода Lucene docId в Pinot продолжается.

Точная настройка потока фонового обновления для работы на основе таблицы или индекса. Текущая реализация имеет один фоновый поток для управления всеми сегментами в реальном времени и их текстовыми индексами.

Вывод

В этом сообщении блога мы обсудили, как мы использовали Lucene для разработки решения текстового поиска в Pinot, чтобы удовлетворить наши функциональные требования и требования к производительности (QPS и задержка). Пожалуйста, посетите пользовательскую документацию текстового поиска, чтобы узнать больше об использовании этой функции.

Если вам интересно узнать больше об Apache Pinot, эти ресурсы - отличное место для начала.

Документы: http://docs.pinot.apache.org
Начало работы: «https://docs.pinot.apache.org/getting -началось"

Специальная благодарность

Я хотел бы поблагодарить нашу команду Пино OSS за их неустанные усилия по улучшению Пино: Маянк Шривастава, Джеки Цзян, Цзялян Ли , Кишор Гопалакришна , Неха Павар , Сынхён Ли , Суббу Субраманиам , Саджад Моради , Дино Очкиалини , Анураг Шендге , Вальтер Хуф Джон Гутманн, наш технический менеджер Шраддха Сахай и менеджер SRE Прасанна Рави. Мы также хотели бы поблагодарить руководство LinkedIn Эрика Балдешвилера, Капила Сурлакера и Игоря Перишича за их руководство и продолжение поддержку, а также Тим Сантос за технический обзор этой статьи.