NGRAM

Индекс NGRAM в Milvus построен для ускорения запросов LIKE по полям VARCHAR или определенным путям JSON внутри полей JSON. Перед построением индекса Milvus разбивает текст на короткие, перекрывающиеся подстроки фиксированной длины n, называемые n-граммами. Например, при n = 3 слово "Milvus" разбивается на 3 грамма: "Mil", "ilv", "lvu" и "vus". Эти n-грамм хранятся в инвертированном индексе, который сопоставляет каждую грамму с идентификаторами документов, в которых она встречается. Во время запроса этот индекс позволяет Milvus быстро сузить поиск до небольшого набора кандидатов, что приводит к значительному ускорению выполнения запроса.

Используйте его, когда вам нужна быстрая префиксная, суффиксная, инфиксная или подстановочная фильтрация, например:

• name LIKE "data%"

• title LIKE "%vector%"

• path LIKE "%json"

Как это работает

Milvus реализует индекс NGRAM в двухфазном процессе:

1. Построение индекса: Генерирование n-грамм для каждого документа и построение инвертированного индекса во время загрузки.

2. Ускорение запросов: Используйте индекс для фильтрации по небольшому набору кандидатов, а затем проверяйте точные совпадения.

Этап 1: Построение индекса

Во время ввода данных Milvus строит индекс NGRAM, выполняя два основных этапа:

1. Разложить текст на n-граммы: Milvus скользит окном n по каждой строке в целевом поле и извлекает перекрывающиеся подстроки, или n-граммы. Длина этих подстрок находится в настраиваемом диапазоне, [min_gram, max_gram].

   • min_gram: Самая короткая n-грамма для генерации. Это также определяет минимальную длину подстроки запроса, для которой может быть использован индекс.

   • max_gram: Самая длинная генерируемая n-грамма. Во время запроса она также используется в качестве максимального размера окна при разбиении длинных строк запроса.

   Например, при использовании min_gram=2 и max_gram=3 строка "AI database" разбивается следующим образом:

Построить индекс Ngram

- **2-grams:** `AI`, `I_`, `_d`, `da`, `at`, ...

- **3-grams:** `AI_`, `I_d`, `_da`, `dat`, `ata`, ...

<div class="alert note">

- For a range `[min_gram, max_gram]`, Milvus generates all n-grams for every length between the two values (inclusive). For example, with `[2,4]` and the word `"text"`, Milvus generates:

- **2-grams:** `te`, `ex`, `xt`

- **3-grams:** `tex`, `ext`

- **4-grams:** `text`

- N-gram decomposition is character-based and language-agnostic. For example, in Chinese, `"向量数据库"` with `min_gram = 2` is decomposed into: `"向量"`, `"量数"`, `"数据"`, `"据库"`.

- Spaces and punctuation are treated as characters during decomposition.

- Decomposition preserves original case, and matching is case-sensitive. For example, `"Database"` and `"database"` will generate different n-grams and require exact case matching during queries.

</div>

1. Построение инвертированного индекса: Создается инвертированный индекс, который сопоставляет каждую сгенерированную n-грамму со списком содержащих ее идентификаторов документов.

   Например, если 2-грамма "AI" встречается в документах с идентификаторами 1, 5, 6, 8 и 9, в индекс записывается {"AI": [1, 5, 6, 8, 9]}. Этот индекс затем используется во время запроса для быстрого сужения области поиска.

Построение индекса Ngram 2

<div class="alert note">

A wider `[min_gram, max_gram]` range creates more grams and larger mapping lists. If memory is tight, consider mmap mode for very large posting lists. For details, refer to [Use mmap](https://zilliverse.feishu.cn/wiki/P3wrwSMNNihy8Vkf9p6cTsWYnTb).

</div>

Этап 2: ускорение запросов

Когда выполняется фильтр LIKE, Milvus использует индекс NGRAM для ускорения запроса на следующих этапах:

Ускорение запросов

1. Извлечение термина запроса: Из выражения LIKE извлекается непрерывная подстрока без подстановочных знаков (например, "%database%" становится "database").

2. Декомпозиция термина запроса: Термин запроса декомпозируется на n-граммы в зависимости от его длины (L) и параметров min_gram и max_gram.

   • Если L < min_gram, индекс не может быть использован, и запрос возвращается к полному сканированию.

   • Если min_gram ≤ L ≤ max_gram, то весь термин запроса рассматривается как одна n-грамма, и дальнейшая декомпозиция не требуется.

   • Если L > max_gram, то термин запроса разбивается на перекрывающиеся графы с помощью окна размером max_gram.

   Например, если для max_gram установлено значение 3, а термин запроса "database" имеет длину 8, он разбивается на 3-граммовые подстроки "dat", "ata", "tab" и так далее.

3. Поиск каждой грамы и пересечение: Milvus ищет каждую граму запроса в инвертированном индексе, а затем пересекает полученные списки идентификаторов документов, чтобы найти небольшой набор документов-кандидатов. Эти кандидаты содержат все граммы из запроса.

4. Проверка и возврат результатов: Оригинальный фильтр LIKE затем применяется в качестве окончательной проверки только к небольшому набору кандидатов, чтобы найти точные совпадения.

Создание индекса NGRAM

Вы можете создать индекс NGRAM на поле VARCHAR или на определенном пути внутри поля JSON.

Пример 1: Создание на поле VARCHAR

Для поля VARCHAR достаточно указать field_name и настроить min_gram и max_gram.

from pymilvus import MilvusClient

client = MilvusClient(uri="http://localhost:19530") # Replace with your server address

# Assume you have defined a VARCHAR field named "text" in your collection schema

# Prepare index parameters
index_params = client.prepare_index_params()

# Add NGRAM index on the "text" field
index_params.add_index(
    field_name="text",   # Target VARCHAR field
    index_type="NGRAM",           # Index type is NGRAM
    index_name="ngram_index",     # Custom name for the index
    min_gram=2,                   # Minimum substring length (e.g., 2-gram: "st")
    max_gram=3                    # Maximum substring length (e.g., 3-gram: "sta")
)

# Create the index on the collection
client.create_index(
    collection_name="Documents",
    index_params=index_params
)

Эта конфигурация генерирует 2-граммы и 3-граммы для каждой строки в text и сохраняет их в инвертированном индексе.

Пример 2: Создание по пути JSON

Для поля JSON, помимо настроек грамматики, необходимо также указать:

• params.json_path - путь JSON, указывающий на значение, которое вы хотите индексировать.

• params.json_cast_type - должен быть "varchar" (без учета регистра), поскольку индексация NGRAM работает со строками.

# Assume you have defined a JSON field named "json_field" in your collection schema, with a JSON path named "body"

# Prepare index parameters
index_params = client.prepare_index_params()

# Add NGRAM index on a JSON field
index_params.add_index(
    field_name="json_field",              # Target JSON field
    index_type="NGRAM",                   # Index type is NGRAM
    index_name="json_ngram_index",        # Custom index name
    min_gram=2,                           # Minimum n-gram length
    max_gram=4,                           # Maximum n-gram length
    params={
        "json_path": "json_field[\"body\"]",  # Path to the value inside the JSON field
        "json_cast_type": "varchar"                  # Required: cast the value to varchar
    }
)

# Create the index on the collection
client.create_index(
    collection_name="Documents",
    index_params=index_params
)

В данном примере:

• Индексируется только значение по адресу json_field["body"].

• Значение приводится к VARCHAR перед токенизацией n-грамм.

• Milvus генерирует подстроки длиной от 2 до 4 и сохраняет их в инвертированном индексе.

Для получения дополнительной информации о том, как индексировать поле JSON, обратитесь к разделу Индексирование JSON.

Запросы, ускоренные с помощью NGRAM

Чтобы индекс NGRAM был применен:

• Запрос должен быть направлен на поле VARCHAR (или путь JSON), которое имеет индекс NGRAM.

• Буквенная часть шаблона LIKE должна быть длиной не менее min_gram символов(например, если самый короткий ожидаемый термин запроса составляет 2 символа, при создании индекса установите min_gram=2).

Поддерживаемые типы запросов:

• Префиксное совпадение

  # Match any string that starts with the substring "database"
  filter = 'text LIKE "database%"'
  

• Суффиксное совпадение

  # Match any string that ends with the substring "database"
  filter = 'text LIKE "%database"'
  

• Инфиксное совпадение

  # Match any string that contains the substring "database" anywhere
  filter = 'text LIKE "%database%"'
  

• совпадение с диким знаком

  Milvus поддерживает как % (ноль или более символов), так и _ (ровно один символ).

  # Match any string where "st" appears first, and "um" appears later in the text 
  filter = 'text LIKE "%st%um%"'
  

• Запросы пути в формате JSON

  filter = 'json_field["body"] LIKE "%database%"'
  

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

Удалить индекс

Используйте метод drop_index(), чтобы удалить существующий индекс из коллекции.

client.drop_index(
    collection_name="Documents",   # Name of the collection
    index_name="ngram_index" # Name of the index to drop
)

Примечания по использованию

• Типы полей: Поддерживаются поля VARCHAR и JSON. Для JSON необходимо указать params.json_path и params.json_cast_type="varchar".

• Юникод: Разложение NGRAM основано на символах, не зависит от языка и включает пробельные символы и знаки препинания.

• Компромисс между пространством и временем: более широкие диапазоны грамм [min_gram, max_gram] дают больше грамм и большие индексы. Если память ограничена, используйте режим mmap для больших списков постинга. Для получения дополнительной информации обратитесь к разделу Использование mmap.

• Неизменяемость: min_gram и max_gram не могут быть изменены на месте - для их корректировки нужно перестроить индекс.

Лучшие практики

• Выберите min_gram и max_gram в соответствии с поведением поиска.

  • Начните с min_gram=2, max_gram=3.

  • Установите min_gram на самый короткий литерал, который, как вы ожидаете, наберут пользователи.

  • Установите max_gram около типичной длины значимых подстрок; больший max_gram улучшает фильтрацию, но увеличивает пространство.

• Избегайте графем с низкой селективностью

  Сильно повторяющиеся шаблоны (например, "aaaaaa") обеспечивают слабую фильтрацию и могут дать ограниченный выигрыш.

• Нормализуйте последовательно

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