Postgres Pro Standard : Документация: 9.5: F.36. pg_trgm : Компания Postgres Professional

RU
EN
RU EN

F.36. pg_trgm
Пред.	Наверх	Приложение F. Дополнительно поставляемые модули	Начало	След.

F.36. pg_trgm

F.36.1. Понятия, связанные с триграммами (или триграфами)
F.36.2. Функции и операторы
F.36.3. Параметры GUC
F.36.4. Поддержка индексов
F.36.5. Интеграция с текстовым поиском
F.36.6. Ссылки
F.36.7. Авторы

Модуль pg_trgm предоставляет функции и операторы для определения схожести алфавитно-цифровых строк на основе триграмм, а также классы операторов индексов, поддерживающие быстрый поиск схожих строк.

F.36.1. Понятия, связанные с триграммами (или триграфами)

Триграмма — это группа трёх последовательных символов, взятых из строки. Мы можем измерить схожесть двух строк, подсчитав число триграмм, которые есть в обеих. Эта простая идея оказывается очень эффективной для измерения схожести слов на многих естественных языках.

Примечание

pg_trgm, извлекая триграммы из строк, игнорирует символы, не относящиеся к словам (не алфавитно-цифровые). При выделении триграмм, содержащихся в строке, считается, что перед каждым словом находятся два пробела, а после — один пробел. Например, из строки «cat» выделяется набор триграмм: « c», « ca», «cat» и «at ». Из строки «foo|bar» выделяются триграммы: « f», « fo», «foo», «oo », « b», « ba», «bar» и «ar ».

F.36.2. Функции и операторы

Реализованные в модуле pg_trgm функции перечислены в Таблице F.26, а операторы — в Таблице F.27.

Таблица F.26. Функции pg_trgm

Функция	Возвращает	Описание
`similarity(text, text)`	`real`	Возвращает число, показывающее, насколько близки два аргумента. Диапазон результатов — от нуля (это значение указывает, что две строки полностью различны) до одного (это значение указывает, что две строки идентичны).
`word_similarity(text, text)`	`real`	Возвращает число, показывающее, насколько слово в первой строке схоже с наиболее похожим на него словом во второй строке. Эта функция ищет во второй строке наиболее похожее слово, а не подстроку. Результат выдаётся в интервале от нуля (строки полностью различны) до одного (первая строка в точности совпадает с одним из слов во второй строке).
`show_trgm(text)`	`text[]`	Возвращает массив всех триграмм в заданной строке. (На практике это редко бывает полезно, кроме как для отладки.)
`show_limit()`	`real`	Возвращает текущий порог схожести, который использует оператор `%`. Это значение задаёт минимальную схожесть между двумя словами, при которой они считаются настолько близкими, что одно может быть, например, ошибочным написанием другого (устаревшая).
`set_limit(real)`	`real`	Задаёт текущий порог схожести, который использует оператор `%`. Это значение должно быть в диапазоне от 0 до 1 (по умолчанию 0.3). Возвращает то же значение, что было передано на вход (устаревшая).

Таблица F.27. Операторы pg_trgm

Оператор	Возвращает	Описание
`text` `%` `text`	`boolean`	Возвращает `true`, если схожесть аргументов выше текущего порога, заданного параметром `pg_trgm.similarity_threshold`.
`text` `%>` `text`	`boolean`	Возвращает `true`, если первый аргумент функции содержит слово, похожее на слово во втором аргументе, и их степень схожести выше текущего порога, заданного параметром `pg_trgm.word_similarity_threshold`.
`text` `<->` `text`	`real`	Возвращает «расстояние» между аргументами, то есть один минус значение `similarity()`.
`text` `<->>` `text`	`real`	Возвращает «расстояние» между аргументами, то есть один минус значение `word_similarity()`.

F.36.3. Параметры GUC

pg_trgm.similarity_threshold (real): Задаёт текущий порог схожести, который использует оператор %. Это значение должно быть в диапазоне от 0 до 1 (по умолчанию 0.3).
pg_trgm.word_similarity_threshold (real): Задаёт текущий порог схожести, который использует оператор %>. Это значение должно быть в диапазоне от 0 до 1 (по умолчанию 0.6).

F.36.4. Поддержка индексов

Модуль pg_trgm предоставляет классы операторов индексов GiST и GIN, позволяющие создавать индекс по текстовым столбцам для очень быстрого поиска по критерию схожести. Эти типы индексов поддерживают вышеописанные операторы схожести и дополнительно поддерживают поиск на основе триграмм для запросов с LIKE, ILIKE, ~ и ~*. (Эти индексы не поддерживают простые операторы сравнения и равенства, так что вам может понадобиться и обычный индекс-B-дерево.)

Пример:

CREATE TABLE test_trgm (t text);
CREATE INDEX trgm_idx ON test_trgm USING GIST (t gist_trgm_ops);

или

CREATE INDEX trgm_idx ON test_trgm USING GIN (t gin_trgm_ops);

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

SELECT t, similarity(t, 'слово') AS sml
  FROM test_trgm
  WHERE t % 'слово'
  ORDER BY sml DESC, t;

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

Другой вариант предыдущего запроса:

SELECT t, t <-> 'слово' AS dist
  FROM test_trgm
  ORDER BY dist LIMIT 10;

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

Вы также можете использовать индекс по столбцу t для поиска по схожести. Например:

SELECT t, word_similarity('word', t) AS sml
  FROM test_trgm
  WHERE t %> 'word'
  ORDER BY sml DESC, t;

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

Другой вариант предыдущего запроса:

SELECT t, t <->> 'word' AS dist
  FROM test_trgm
  ORDER BY dist LIMIT 10;

Он может быть довольно эффективно выполнен с применением индексов GiST, а не GIN.

Начиная с PostgreSQL 9.1, эти типы индексов также поддерживают поиск с операторами LIKE и ILIKE, например:

SELECT * FROM test_trgm WHERE t LIKE '%foo%bar';

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

Начиная с PostgreSQL 9.3, индексы этих типов также поддерживают поиск по регулярным выражениям (операторы ~ и ~*), например:

SELECT * FROM test_trgm WHERE t ~ '(foo|bar)';

При таком поиске из регулярного выражения извлекаются триграммы, а затем они ищутся в индексе. Чем больше триграмм удаётся извлечь из регулярного выражения, тем более эффективным будет поиск по индексу. В отличие от поиска по B-дереву, искомая строка не должна привязываться к левому краю.

Относительно поиска по регулярному выражению или с LIKE, имейте в виду, что при отсутствии триграмм в искомом шаблоне поиск сводится к полному сканирования индекса.

Выбор между индексами GiST и GIN зависит от относительных характеристик производительности GiST и GIN, которые здесь не рассматриваются. Как правило, индекс GIN быстрее индекса GiST при поиске, но строится или обновляется он медленнее; поэтому GIN лучше подходит для статических, а GiST для часто изменяемых данных.

F.36.5. Интеграция с текстовым поиском

Сопоставление триграмм — очень полезный приём в сочетании с применением полнотекстового индекса. В частности это может помочь найти слова, написанные неправильно, которые не будут находиться непосредственно механизмом полнотекстового поиска.

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

CREATE TABLE words AS SELECT word FROM
        ts_stat('SELECT to_tsvector(''simple'', bodytext) FROM documents');

Здесь documents — это таблица с текстовым полем bodytext, по которому мы будем выполнять поиск. Конфигурация simple используется с функцией to_tsvector вместо конфигурации для определённого языка по той причине, что нам нужен список исходных (необработанных стеммером) слов.

Затем нужно создать индекс триграмм по столбцу со словами:

CREATE INDEX words_idx ON words USING GIN (word gin_trgm_ops);

Теперь мы можем использовать запрос SELECT, подобный показанному в предыдущем примере, и предлагать варианты исправлений слов, введённых пользователем с ошибками. Кроме того, может быть полезно дополнительно проверить, что выбранные слова также имеют длину, примерно равную длине ошибочных слов.

Примечание

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

F.36.6. Ссылки

Сайт разработки GiST http://www.sai.msu.su/~megera/postgres/gist/

Сайт разработки Tsearch2 http://www.sai.msu.su/~megera/postgres/gist/tsearch/V2/

F.36.7. Авторы

Олег Бартунов <oleg@sai.msu.su>, Москва, Московский Государственный Университет, Россия

Фёдор Сигаев <teodor@sigaev.ru>, Москва, ООО «Дельта-Софт», Россия

Документация: Кристофер Кингс-Линн

Разработку этого модуля спонсировало ООО «Дельта-Софт», г. Москва, Россия.

Пред.	Наверх	След.
F.35. pgstattuple	Начало	F.37. pg_variables

F.29. ltree
Prev	Up	Appendix F. Additional Supplied Modules	Home	Next

F.29. ltree

F.29.1. Definitions
F.29.2. Operators and Functions
F.29.3. Indexes
F.29.4. Example
F.29.5. Transforms
F.29.6. Authors

This module implements a data type ltree for representing labels of data stored in a hierarchical tree-like structure. Extensive facilities for searching through label trees are provided.

F.29.1. Definitions

A label is a sequence of alphanumeric characters and underscores (for example, in C locale the characters A-Za-z0-9_ are allowed). Labels must be less than 256 characters long.

Examples: 42, Personal_Services

A label path is a sequence of zero or more labels separated by dots, for example L1.L2.L3, representing a path from the root of a hierarchical tree to a particular node. The length of a label path cannot exceed 65535 labels.

Example: Top.Countries.Europe.Russia

The ltree module provides several data types:

ltree stores a label path.
lquery represents a regular-expression-like pattern for matching ltree values. A simple word matches that label within a path. A star symbol (*) matches zero or more labels. For example:
```
foo         Match the exact label path foo
*.foo.*     Match any label path containing the label foo
*.foo       Match any label path whose last label is foo
```
Star symbols can also be quantified to restrict how many labels they can match:
```
*{n}        Match exactly n labels
*{n,}       Match at least n labels
*{n,m}      Match at least n but not more than m labels
*{,m}       Match at most m labels — same as  *{0,m}
```
There are several modifiers that can be put at the end of a non-star label in lquery to make it match more than just the exact match:
```
@           Match case-insensitively, for example a@ matches A
*           Match any label with this prefix, for example foo* matches foobar
%           Match initial underscore-separated words
```
The behavior of % is a bit complicated. It tries to match words rather than the entire label. For example foo_bar% matches foo_bar_baz but not foo_barbaz. If combined with *, prefix matching applies to each word separately, for example foo_bar%* matches foo1_bar2_baz but not foo1_br2_baz.
Also, you can write several possibly-modified labels separated with | (OR) to match any of those labels, and you can put ! (NOT) at the start to match any label that doesn't match any of the alternatives.
Here's an annotated example of lquery:
```
Top.*{0,2}.sport*@.!football|tennis.Russ*|Spain
a.  b.     c.      d.               e.
```
This query will match any label path that:
1. begins with the label Top
2. and next has zero to two labels before
3. a label beginning with the case-insensitive prefix sport
4. then a label not matching football nor tennis
5. and then ends with a label beginning with Russ or exactly matching Spain.
ltxtquery represents a full-text-search-like pattern for matching ltree values. An ltxtquery value contains words, possibly with the modifiers @, *, % at the end; the modifiers have the same meanings as in lquery. Words can be combined with & (AND), | (OR), ! (NOT), and parentheses. The key difference from lquery is that ltxtquery matches words without regard to their position in the label path.
Here's an example ltxtquery:
```
Europe & Russia*@ & !Transportation
```
This will match paths that contain the label Europe and any label beginning with Russia (case-insensitive), but not paths containing the label Transportation. The location of these words within the path is not important. Also, when % is used, the word can be matched to any underscore-separated word within a label, regardless of position.

Note: ltxtquery allows whitespace between symbols, but ltree and lquery do not.

F.29.2. Operators and Functions

Type ltree has the usual comparison operators =, <>, <, >, <=, >=. Comparison sorts in the order of a tree traversal, with the children of a node sorted by label text. In addition, the specialized operators shown in Table F.19 are available.

Table F.19. ltree Operators

Operator	Returns	Description
`ltree` `@>` `ltree`	`boolean`	is left argument an ancestor of right (or equal)?
`ltree` `<@` `ltree`	`boolean`	is left argument a descendant of right (or equal)?
`ltree` `~` `lquery`	`boolean`	does `ltree` match `lquery`?
`lquery` `~` `ltree`	`boolean`	does `ltree` match `lquery`?
`ltree` `?` `lquery[]`	`boolean`	does `ltree` match any `lquery` in array?
`lquery[]` `?` `ltree`	`boolean`	does `ltree` match any `lquery` in array?
`ltree` `@` `ltxtquery`	`boolean`	does `ltree` match `ltxtquery`?
`ltxtquery` `@` `ltree`	`boolean`	does `ltree` match `ltxtquery`?
`ltree` `\|\|` `ltree`	`ltree`	concatenate `ltree` paths
`ltree` `\|\|` `text`	`ltree`	convert text to `ltree` and concatenate
`text` `\|\|` `ltree`	`ltree`	convert text to `ltree` and concatenate
`ltree[]` `@>` `ltree`	`boolean`	does array contain an ancestor of `ltree`?
`ltree` `<@` `ltree[]`	`boolean`	does array contain an ancestor of `ltree`?
`ltree[]` `<@` `ltree`	`boolean`	does array contain a descendant of `ltree`?
`ltree` `@>` `ltree[]`	`boolean`	does array contain a descendant of `ltree`?
`ltree[]` `~` `lquery`	`boolean`	does array contain any path matching `lquery`?
`lquery` `~` `ltree[]`	`boolean`	does array contain any path matching `lquery`?
`ltree[]` `?` `lquery[]`	`boolean`	does `ltree` array contain any path matching any `lquery`?
`lquery[]` `?` `ltree[]`	`boolean`	does `ltree` array contain any path matching any `lquery`?
`ltree[]` `@` `ltxtquery`	`boolean`	does array contain any path matching `ltxtquery`?
`ltxtquery` `@` `ltree[]`	`boolean`	does array contain any path matching `ltxtquery`?
`ltree[]` `?@>` `ltree`	`ltree`	first array entry that is an ancestor of `ltree`; NULL if none
`ltree[]` `?<@` `ltree`	`ltree`	first array entry that is a descendant of `ltree`; NULL if none
`ltree[]` `?~` `lquery`	`ltree`	first array entry that matches `lquery`; NULL if none
`ltree[]` `?@` `ltxtquery`	`ltree`	first array entry that matches `ltxtquery`; NULL if none

The operators <@, @>, @ and ~ have analogues ^<@, ^@>, ^@, ^~, which are the same except they do not use indexes. These are useful only for testing purposes.

The available functions are shown in Table F.20.

Table F.20. ltree Functions

Function	Return Type	Description	Example	Result
`subltree(ltree, int start, int end)`	`ltree`	subpath of `ltree` from position `start` to position `end`-1 (counting from 0)	`subltree('Top.Child1.Child2',1,2)`	`Child1`
`subpath(ltree, int offset, int len)`	`ltree`	subpath of `ltree` starting at position `offset`, length `len`. If `offset` is negative, subpath starts that far from the end of the path. If `len` is negative, leaves that many labels off the end of the path.	`subpath('Top.Child1.Child2',0,2)`	`Top.Child1`
`subpath(ltree, int offset)`	`ltree`	subpath of `ltree` starting at position `offset`, extending to end of path. If `offset` is negative, subpath starts that far from the end of the path.	`subpath('Top.Child1.Child2',1)`	`Child1.Child2`
`nlevel(ltree)`	`integer`	number of labels in path	`nlevel('Top.Child1.Child2')`	`3`
`index(ltree a, ltree b)`	`integer`	position of first occurrence of `b` in `a`; -1 if not found	`index('0.1.2.3.5.4.5.6.8.5.6.8','5.6')`	`6`
`index(ltree a, ltree b, int offset)`	`integer`	position of first occurrence of `b` in `a`, searching starting at `offset`; negative `offset` means start `-offset` labels from the end of the path	`index('0.1.2.3.5.4.5.6.8.5.6.8','5.6',-4)`	`9`
`text2ltree(text)`	`ltree`	cast `text` to `ltree`
`ltree2text(ltree)`	`text`	cast `ltree` to `text`
`lca(ltree, ltree, ...)`	`ltree`	longest common ancestor of paths (up to 8 arguments supported)	`lca('1.2.3','1.2.3.4.5.6')`	`1.2`
`lca(ltree[])`	`ltree`	longest common ancestor of paths in array	`lca(array['1.2.3'::ltree,'1.2.3.4'])`	`1.2`

F.29.3. Indexes

ltree supports several types of indexes that can speed up the indicated operators:

B-tree index over ltree: <, <=, =, >=, >
GiST index over ltree: <, <=, =, >=, >, @>, <@, @, ~, ?
Example of creating such an index:
```
CREATE INDEX path_gist_idx ON test USING GIST (path);
```
GiST index over ltree[]: ltree[] <@ ltree, ltree @> ltree[], @, ~, ?
Example of creating such an index:
```
CREATE INDEX path_gist_idx ON test USING GIST (array_path);
```
Note: This index type is lossy.

F.29.4. Example

This example uses the following data (also available in file contrib/ltree/ltreetest.sql in the source distribution):

CREATE TABLE test (path ltree);
INSERT INTO test VALUES ('Top');
INSERT INTO test VALUES ('Top.Science');
INSERT INTO test VALUES ('Top.Science.Astronomy');
INSERT INTO test VALUES ('Top.Science.Astronomy.Astrophysics');
INSERT INTO test VALUES ('Top.Science.Astronomy.Cosmology');
INSERT INTO test VALUES ('Top.Hobbies');
INSERT INTO test VALUES ('Top.Hobbies.Amateurs_Astronomy');
INSERT INTO test VALUES ('Top.Collections');
INSERT INTO test VALUES ('Top.Collections.Pictures');
INSERT INTO test VALUES ('Top.Collections.Pictures.Astronomy');
INSERT INTO test VALUES ('Top.Collections.Pictures.Astronomy.Stars');
INSERT INTO test VALUES ('Top.Collections.Pictures.Astronomy.Galaxies');
INSERT INTO test VALUES ('Top.Collections.Pictures.Astronomy.Astronauts');
CREATE INDEX path_gist_idx ON test USING GIST (path);
CREATE INDEX path_idx ON test USING BTREE (path);

Now, we have a table test populated with data describing the hierarchy shown below:

                        Top
                     /   |  \
             Science Hobbies Collections
                 /       |              \
        Astronomy   Amateurs_Astronomy Pictures
           /  \                            |
Astrophysics  Cosmology                Astronomy
                                        /  |    \
                                 Galaxies Stars Astronauts

We can do inheritance:

ltreetest=> SELECT path FROM test WHERE path <@ 'Top.Science';
                path
------------------------------------
 Top.Science
 Top.Science.Astronomy
 Top.Science.Astronomy.Astrophysics
 Top.Science.Astronomy.Cosmology
(4 rows)

Here are some examples of path matching:

ltreetest=> SELECT path FROM test WHERE path ~ '*.Astronomy.*';
                     path
-----------------------------------------------
 Top.Science.Astronomy
 Top.Science.Astronomy.Astrophysics
 Top.Science.Astronomy.Cosmology
 Top.Collections.Pictures.Astronomy
 Top.Collections.Pictures.Astronomy.Stars
 Top.Collections.Pictures.Astronomy.Galaxies
 Top.Collections.Pictures.Astronomy.Astronauts
(7 rows)

ltreetest=> SELECT path FROM test WHERE path ~ '*.!pictures@.*.Astronomy.*';
                path
------------------------------------
 Top.Science.Astronomy
 Top.Science.Astronomy.Astrophysics
 Top.Science.Astronomy.Cosmology
(3 rows)

Here are some examples of full text search:

ltreetest=> SELECT path FROM test WHERE path @ 'Astro*% & !pictures@';
                path
------------------------------------
 Top.Science.Astronomy
 Top.Science.Astronomy.Astrophysics
 Top.Science.Astronomy.Cosmology
 Top.Hobbies.Amateurs_Astronomy
(4 rows)

ltreetest=> SELECT path FROM test WHERE path @ 'Astro* & !pictures@';
                path
------------------------------------
 Top.Science.Astronomy
 Top.Science.Astronomy.Astrophysics
 Top.Science.Astronomy.Cosmology
(3 rows)

Path construction using functions:

ltreetest=> SELECT subpath(path,0,2)||'Space'||subpath(path,2) FROM test WHERE path <@ 'Top.Science.Astronomy';
                 ?column?
------------------------------------------
 Top.Science.Space.Astronomy
 Top.Science.Space.Astronomy.Astrophysics
 Top.Science.Space.Astronomy.Cosmology
(3 rows)

We could simplify this by creating a SQL function that inserts a label at a specified position in a path:

CREATE FUNCTION ins_label(ltree, int, text) RETURNS ltree
    AS 'select subpath($1,0,$2) || $3 || subpath($1,$2);'
    LANGUAGE SQL IMMUTABLE;

ltreetest=> SELECT ins_label(path,2,'Space') FROM test WHERE path <@ 'Top.Science.Astronomy';
                ins_label
------------------------------------------
 Top.Science.Space.Astronomy
 Top.Science.Space.Astronomy.Astrophysics
 Top.Science.Space.Astronomy.Cosmology
(3 rows)

F.29.5. Transforms

Additional extensions are available that implement transforms for the ltree type for PL/Python. The extensions are called ltree_plpythonu, ltree_plpython2u, and ltree_plpython3u (see Section 44.1 for the PL/Python naming convention). If you install these transforms and specify them when creating a function, ltree values are mapped to Python lists. (The reverse is currently not supported, however.)

Caution

It is strongly recommended that the transform extensions be installed in the same schema as ltree. Otherwise there are installation-time security hazards if a transform extension's schema contains objects defined by a hostile user.

F.29.6. Authors

All work was done by Teodor Sigaev (<teodor@stack.net>) and Oleg Bartunov (<oleg@sai.msu.su>). See http://www.sai.msu.su/~megera/postgres/gist/ for additional information. Authors would like to thank Eugeny Rodichev for helpful discussions. Comments and bug reports are welcome.

Prev	Home	Next
F.28. lo	Up	F.30. mchar

Вход в личный кабинет

Восстановление пароля

Подтверждение аккаунта

Изменение пароля

F.36. pg_trgm

F.36.1. Понятия, связанные с триграммами (или триграфами)

Примечание

F.36.2. Функции и операторы

F.36.3. Параметры GUC

F.36.4. Поддержка индексов

F.36.5. Интеграция с текстовым поиском

Примечание

F.36.6. Ссылки

F.36.7. Авторы

F.29. ltree

F.29.1. Definitions

F.29.2. Operators and Functions

F.29.3. Indexes

F.29.4. Example

F.29.5. Transforms

Caution

F.29.6. Authors