Полнотекстовый поиск

Елена Дворядкина

Содержание

Обзор
Управление индексами
Пример

Обзор

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

В ADQM/ClickHouse инвертированный индекс строится следующим образом:

Текст каждой ячейки в столбце, по которому составляется индекс, разбивается на токены — термы (terms). По умолчанию разбиение осуществляется по пробелам, но также возможно разбить текст на n-граммы. Все термы записываются в отсортированный список — словарь (dictionary).
Для каждого терма составляется отсортированный список идентификаторов строк, содержащих этот терм (posting list).

Иными словами, инвертированный индекс реализует хранение сопоставления всех термов с указателями на их расположение в таблице (номера соответствующих строк). Если в таблице для текстового столбца создан инвертированный индекс, ADQM автоматически его применяет при выполнении запроса с поиском терма в этом столбце (например, запрос типа SELECT … WHERE <column_name> == | IN | LIKE '<term>') — быстро находит терм в словаре и возвращает нужные строки таблицы, используя posting list.

Например, рассмотрим таблицу со столбцом text типа String:

┌─row_id─┬─text────────────┐
│      0 │ Lower East Side │
│      1 │ Upper West Side │
│      2 │ West Village    │
│      3 │ East Village    │
└────────┴─────────────────┘

Инвертированный индекс по столбцу text в общем виде будет составлен следующим образом.

Dictionary (terms)	Posting lists
East	0, 3
Lower	0
Side	0, 1
Upper	1
Village	2, 3
West	1, 2

ВАЖНО

В настоящее время инвертированные индексы поддерживаются в экспериментальном режиме — не рекомендуется их использовать в production-системах.

Управление индексами

Перед созданием инвертированного индекса необходимо включить следующую опцию:

SET allow_experimental_inverted_index = true;

Инвертированный индекс описывается так же как и другие типы индекса пропуска данных — с помощью выражения INDEX в секции описания столбцов запроса CREATE TABLE:

CREATE TABLE <table_name>
(   <column_name> <column_type>, ...
    INDEX <index_name> <index_expr> TYPE inverted([<n>], [<max_rows_per_posting_list>]), ...)
ENGINE = MergeTree
...;

где:

<index_name> — имя индекса.
<index_expr> — выражение, по которому будет строиться индекс (часто это имя текстового столбца).
<n> — токенизатор (tokenizer), который определяет, как строка в ячейке текстового столбца разбивается на термы:
- inverted(0) (сокращенно inverted() или inverted) — строка разбивается на слова по пробелам;
- inverted(n) (где n — число в диапазоне [2, 8]) — строка разбивается на n-граммы (подстроки из n символов).
<max_rows_per_posting_list> — максимальное количество идентификаторов строк, содержащих терм, которое может быть записано в список posting list (если 0 — размер списка posting list для терма не ограничивается, если параметр не указан — устанавливается ограничение по умолчанию, равное 64K).

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

В существующую таблицу инвертированный индекс можно добавить с помощью следующего запроса:

ALTER TABLE <table_name> ADD INDEX <index_name> <index_expr> TYPE inverted([<n>], [<max_rows_per_posting_list>]);

Когда индекс добавляется в существующую таблицу, он не обновляется автоматически. ALTER TABLE изменяет метаданные, поэтому индекс будет рассчитываться только для новых данных, вставляемых в таблицу. Чтобы применить индекс к существующим данным, выполните дополнительную команду:

ALTER TABLE <table_name> MATERIALIZE INDEX <index_name>;

Удалить индексы можно запросами:

ALTER TABLE <table_name> DROP INDEX <index_name> — удаляет описание индекса из метаданных таблицы и удаляет индексные файлы с диска;
ALTER TABLE <table_name> CLEAR INDEX <index_name> — удаляет файлы индекса с диска без удаления описания индекса из метаданных.

Пример

Создайте таблицу trips с данными такси Нью-Йорка, как описано в примере документации ClickHouse:

CREATE TABLE trips (
    trip_id             UInt32,
    pickup_datetime     DateTime,
    dropoff_datetime    DateTime,
    pickup_longitude    Nullable(Float64),
    pickup_latitude     Nullable(Float64),
    dropoff_longitude   Nullable(Float64),
    dropoff_latitude    Nullable(Float64),
    passenger_count     UInt8,
    trip_distance       Float32,
    fare_amount         Float32,
    extra               Float32,
    tip_amount          Float32,
    tolls_amount        Float32,
    total_amount        Float32,
    payment_type        Enum('CSH' = 1, 'CRE' = 2, 'NOC' = 3, 'DIS' = 4, 'UNK' = 5),
    pickup_ntaname      LowCardinality(String),
    dropoff_ntaname     LowCardinality(String)
)
ENGINE = MergeTree
PRIMARY KEY (pickup_datetime, dropoff_datetime);

INSERT INTO trips
SELECT
    trip_id,
    pickup_datetime,
    dropoff_datetime,
    pickup_longitude,
    pickup_latitude,
    dropoff_longitude,
    dropoff_latitude,
    passenger_count,
    trip_distance,
    fare_amount,
    extra,
    tip_amount,
    tolls_amount,
    total_amount,
    payment_type,
    pickup_ntaname,
    dropoff_ntaname
FROM s3(
    'https://datasets-documentation.s3.eu-west-3.amazonaws.com/nyc-taxi/trips_{0..2}.gz',
    'TabSeparatedWithNames');

Выполните тестовый запрос на выборку данных с условием по столбцу pickup_ntaname:

SELECT pickup_datetime,pickup_datetime,pickup_ntaname,dropoff_ntaname
FROM trips
WHERE (pickup_ntaname LIKE '%Village%') OR (pickup_ntaname LIKE '%Square%');

┌─────pickup_datetime─┬─────pickup_datetime─┬─pickup_ntaname─────────────────────────────┬─dropoff_ntaname───────┐
│ 2015-07-01 00:02:24 │ 2015-07-01 00:02:24 │ East Village                               │ Gramercy              │
│ 2015-07-01 00:03:15 │ 2015-07-01 00:03:15 │ Hudson Yards-Chelsea-Flatiron-Union Square │ West Village          │

...

│ 2015-07-09 00:32:13 │ 2015-07-09 00:32:13 │ West Village                               │ East Village          │
└─────────────────────┴─────────────────────┴────────────────────────────────────────────┴───────────────────────┘
  Showed first 10000.

714664 rows in set. Elapsed: 0.831 sec. Processed 3.00 million rows, 18.00 MB (3.61 million rows/s., 21.66 MB/s.)
Peak memory usage: 13.04 MiB.

Добавьте в таблицу инвертированный индекс:

SET allow_experimental_inverted_index = true;

ALTER TABLE trips ADD INDEX inv_idx(pickup_ntaname) TYPE inverted;

ALTER TABLE trips MATERIALIZE INDEX inv_idx;

Повторите запрос — обратите внимание, что скорость его выполнения увеличилась:

SELECT pickup_datetime,pickup_datetime,pickup_ntaname,dropoff_ntaname
FROM trips
WHERE (pickup_ntaname LIKE '%Village%') OR (pickup_ntaname LIKE '%Square%');

┌─────pickup_datetime─┬─────pickup_datetime─┬─pickup_ntaname─────────────────────────────┬─dropoff_ntaname───────┐
│ 2015-07-01 00:02:24 │ 2015-07-01 00:02:24 │ East Village                               │ Gramercy              │
│ 2015-07-01 00:03:15 │ 2015-07-01 00:03:15 │ Hudson Yards-Chelsea-Flatiron-Union Square │ West Village          │

...

│ 2015-07-09 00:32:13 │ 2015-07-09 00:32:13 │ West Village                               │ East Village          │
└─────────────────────┴─────────────────────┴────────────────────────────────────────────┴───────────────────────┘
  Showed first 10000.

714664 rows in set. Elapsed: 0.129 sec. Processed 3.00 million rows, 18.00 MB (23.27 million rows/s., 139.63 MB/s.)
Peak memory usage: 13.04 MiB.

С помощью выражения EXPLAIN с параметром indexes можно убедиться, что при выполнении запроса использовался инвертированный индекс:

EXPLAIN indexes = 1 SELECT pickup_datetime,pickup_datetime,pickup_ntaname,dropoff_ntaname
FROM trips
WHERE (pickup_ntaname LIKE '%Village%') OR (pickup_ntaname LIKE '%Square%');

┌─explain─────────────────────────────────────┐
│ Expression ((Project names + Projection))   │
│   Expression                                │
│     ReadFromMergeTree (default.trips)       │
│     Indexes:                                │
│       PrimaryKey                            │
│         Condition: true                     │
│         Parts: 2/2                          │
│         Granules: 368/368                   │
│       Skip                                  │
│         Name: inv_idx                       │
│         Description: inverted GRANULARITY 1 │
│         Parts: 2/2                          │
│         Granules: 368/368                   │
└─────────────────────────────────────────────┘

Нашли ошибку? Выделите текст и нажмите Ctrl+Enter чтобы сообщить о ней