F.28. ltree
Этот модуль реализует тип данных ltree
для представления меток данных в иерархической древовидной структуре. Он также предоставляет расширенные средства для поиска в таких деревьях.
Данный модуль считается «доверенным», то есть его могут устанавливать обычные пользователи, имеющие право CREATE
в текущей базе данных.
F.28.1. Определения
Метка — это последовательность алфавитно-цифровых символов и знаков подчёркивания (например, в локали C допускаются символы A-Za-z0-9_
). Метки должны занимать меньше 256 символов.
Примеры: 42
, Personal_Services
Путь метки — это последовательность из нуля или нескольких разделённых точками меток (например, L1.L2.L3
), представляющая путь от корня иерархического дерева к конкретному узлу. Путь не может содержать больше 65535 меток.
Пример: Top.Countries.Europe.Russia
Модуль ltree
предоставляет несколько типов данных:
ltree
хранит путь метки.lquery
представляет напоминающий регулярные выражения запрос для поиска нужных значенийltree
. В нём простое слово выбирает соответствующую метку в заданном пути, а звёздочка (*
) — ноль или более любых меток. Отдельные компоненты можно соединить точками и получить запрос, которому будет соответствовать весь путь с указанными метками. Например:foo Выбирает путь ровно с одной меткой
foo
*.foo.* Выбирает путь, содержащий меткуfoo
*.foo Выбирает путь с последней меткойfoo
И для звёздочки, и для простых слов можно добавить количественное значение, определяющее число меток, которые будут соответствовать этому компоненту:
*{
n
} Выбирает ровноn
меток *{n
,} Выбирает как минимумn
меток *{n
,m
} Выбирает не меньшеn
, но и не болееm
меток *{,m
} Выбирает не большеm
меток — равнозначно *{0,m
} foo{n
,m
} Выбирает как минимумn
, но не большеm
вхожденийfoo
foo{,} Выбирает любое количество вхожденийfoo
, в том числе нольВ отсутствие явного числового ограничения символу звёздочки по умолчанию соответствует любое количество меток (то есть
{,}
), а обычному слову — ровно одно вхождение (то есть{1}
).После отличного от звёздочки элемента
lquery
могут быть добавлены модификаторы, позволяющие выбрать не только простые совпадения:@ Выбирает совпадение без учёта регистра; например, запросу
a@
соответствуетA
* Выбирает любую метку с заданным префиксом, например, запросуfoo*
соответствуетfoobar
% Выбирает в метке начальные слова, разделённые подчёркиваниямиПоведение модификатора
%
несколько нетривиальное. Он пытается найти соответствие по словам, а не по всей метке. Например, запросfoo_bar%
выбираетfoo_bar_baz
, но неfoo_barbaz
. В сочетании с*
сопоставление префикса применяется отдельно к каждому слову, например запросfoo_bar%*
выбираетfoo1_bar2_baz
, но неfoo1_br2_baz
.Также можно записать несколько различных меток, отличных от звёздочек, через знак
|
(обозначающий ИЛИ) для выбора любой из этих меток, либо добавить знак!
(НЕ) в начале группы без звёздочки для выбора метки, не соответствующей ни одной из указанных альтернатив. Количественное ограничение, если оно требуется, задаётся в конце группы; это означает, что оно действует на всю группу в целом (то есть ограничивает число меток, соответствующих или не соответствующих одной из альтернатив).Расширенный пример
lquery
:Top.*{0,2}.sport*@.!football|tennis{1,}.Russ*|Spain a. b. c. d. e.
Этот запрос выберет путь, который:
начинается с метки
Top
и затем включает от нуля до двух меток до
метки, начинающейся с префикса
sport
(без учёта регистра)затем одну или несколько меток, отличных от
football
иtennis
и заканчивается меткой, которая начинается подстрокой
Russ
или в точности равнаSpain
.
ltxtquery
представляет подобный полнотекстовому запрос поиска подходящих значенийltree
. Значениеltxtquery
содержит слова, возможно с модификаторами@
,*
,%
в конце; эти модификаторы имеют то же значение, что и вlquery
. Слова можно объединять символами&
(И),|
(ИЛИ),!
(НЕ) и скобками. Ключевое отличие отlquery
состоит в том, чтоltxtquery
выбирает слова независимо от их положения в пути метки.Пример
ltxtquery
:Europe & Russia*@ & !Transportation
Этот запрос выберет пути, содержащие метку
Europe
или любую метку с начальной подстрокойRussia
(без учёта регистра), но не пути, содержащие меткуTransportation
. Положение этих слов в пути не имеет значения. Кроме того, когда применяется%
, слово может быть сопоставлено с любым другим отделённым подчёркиваниями словом в метке, вне зависимости от его положения.
Замечание: ltxtquery
допускает пробелы между символами, а ltree
и lquery
— нет.
F.28.2. Операторы и функции
Для типа ltree
определены обычные операторы сравнения =
, <>
, <
, >
, <=
, >=
. Сравнение сортирует пути в порядке движения по дереву, а потомки узла сортируются по тексту метки. В дополнение к ним есть и специализированные операторы, перечисленные в Таблице F.18.
Таблица F.18. Операторы ltree
Оператор Описание |
---|
Левый аргумент является предком правого (или равен ему)? |
Левый аргумент является потомком правого (или равен ему)? |
Значение |
Значение |
Значение |
Соединяет два пути |
Преобразует текст в |
Массив содержит предка |
Массив содержит потомка |
Массив содержит какой-либо путь, соответствующий |
Массив |
Массив содержит путь, соответствующий |
Выдаёт первый элемент массива, являющийся предком |
Выдаёт первый элемент массива, являющийся потомком |
Выдаёт первый элемент массива, соответствующий |
Выдаёт первый элемент массива, соответствующий |
Операторы <@
, @>
, @
и ~
имеют аналоги в виде ^<@
, ^@>
, ^@
, ^~
, которые отличатся только тем, что не используют индексы. Они полезны только для тестирования.
Доступные функции перечислены в Таблице F.19.
Таблица F.19. Функции ltree
F.28.3. Индексы
ltree
поддерживает несколько типов индексов, которые могут ускорить означенные операции:
B-дерево по значениям
ltree
:<
,<=
,=
,>=
,>
GiST по значениям
ltree
(класс операторовgist_ltree_ops
):<
,<=
,=
,>=
,>
,@>
,<@
,@
,~
,?
Класс операторов GiST
gist_ltree_ops
аппроксимирует набор меток пути в виде сигнатуры битовой карты. В его необязательном целочисленном параметреsiglen
можно задать размер сигнатуры в байтах. Размер сигнатуры по умолчанию — 8 байт. Параметр может принимать положительные значения до 2024, кратные выравниванию по целым (int
) (4 байта для большинства машин). При увеличении размера сигнатуры поиск работает точнее (сканируется меньшая область в индексе и меньше страниц кучи), но сам индекс становится больше.Пример создания такого индекса с размером сигнатуры по умолчанию (8 байт):
CREATE INDEX path_gist_idx ON test USING GIST (path);
Пример создания такого индекса с длиной сигнатуры 100 байт:
CREATE INDEX path_gist_idx ON test USING GIST (path gist_ltree_ops(siglen=100));
GiST-индекс по массиву
ltree[]
(gist__ltree_ops
opclass):ltree[] <@ ltree
,ltree @> ltree[]
,@
,~
,?
Класс операторов GiST
gist__ltree_ops
работает подобноgist_ltree_ops
и также принимает в параметре длину сигнатуры. По умолчанию значениеsiglen
вgist__ltree_ops
составляет 28 байт.Пример создания такого индекса с размером сигнатуры по умолчанию (28 байт):
CREATE INDEX path_gist_idx ON test USING GIST (array_path);
Пример создания такого индекса с длиной сигнатуры 100 байт:
CREATE INDEX path_gist_idx ON test USING GIST (array_path gist__ltree_ops(siglen=100));
Примечание: Индекс этого типа является неточным.
F.28.4. Пример
Для этого примера используются следующие данные (это же описание данных находится в файле contrib/ltree/ltreetest.sql
в дистрибутиве исходного кода):
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);
В итоге мы получаем таблицу test
, наполненную данными, представляющими следующую иерархию:
Top / | \ Science Hobbies Collections / | \ Astronomy Amateurs_Astronomy Pictures / \ | Astrophysics Cosmology Astronomy / | \ Galaxies Stars Astronauts
Мы можем выбрать потомки в иерархии наследования:
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)
Несколько примеров выборки по путям:
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)
Ещё несколько примеров полнотекстового поиска:
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)
Образование пути с помощью функций:
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)
Эту процедуру можно упростить, создав функцию SQL, вставляющую метку в определённую позицию в пути:
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.28.5. Трансформации
Также имеются дополнительные расширения, реализующие трансформации типа ltree
для языка PL/Python. Эти расширения называются ltree_plpythonu
, ltree_plpython2u
и ltree_plpython3u
(соглашения об именовании, принятые для интерфейса PL/Python, описаны в Разделе 47.1). Если вы установите эти трансформации и укажете их при создании функции, значения ltree
будут отображаться в списки Python. (Однако обратное преобразование не поддерживается.)
Внимание
Расширения, реализующие трансформации, настоятельно рекомендуется устанавливать в одну схему с ltree
. Выбор какой-либо другой схемы, которая может содержать объекты, созданные злонамеренным пользователем, чреват угрозами безопасности во время установки расширения.
F.28.6. Авторы
Разработку осуществили Фёдор Сигаев (<teodor@stack.net>
) и Олег Бартунов (<oleg@sai.msu.su>
). Дополнительные сведения можно найти на странице http://www.sai.msu.su/~megera/postgres/gist/. Авторы выражают благодарность Евгению Родичеву за полезные дискуссии. Замечания и сообщения об ошибках приветствуются.