F.21. ltree

Этот модуль реализует тип данных ltree для представления меток данных в иерархической древовидной структуре. Он также предоставляет расширенные средства для поиска в таких деревьях.

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

F.21.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.

    Этот запрос выберет путь, который:

    1. начинается с метки Top

    2. и затем включает от нуля до двух меток до

    3. метки, начинающейся с префикса sport (без учёта регистра)

    4. затем одну или несколько меток, отличных от football и tennis

    5. и заканчивается меткой, которая начинается подстрокой Russ или в точности равна Spain.

  • ltxtquery представляет подобный полнотекстовому запрос поиска подходящих значений ltree. Значение ltxtquery содержит слова, возможно с модификаторами @, *, % в конце; эти модификаторы имеют то же значение, что и в lquery. Слова можно объединять символами & (И), | (ИЛИ), ! (НЕ) и скобками. Ключевое отличие от lquery состоит в том, что ltxtquery выбирает слова независимо от их положения в пути метки.

    Пример ltxtquery:

    Europe & Russia*@ & !Transportation

    Этот запрос выберет пути, содержащие метку Europe или любую метку с начальной подстрокой Russia (без учёта регистра), но не пути, содержащие метку Transportation. Положение этих слов в пути не имеет значения. Кроме того, когда применяется %, слово может быть сопоставлено с любым другим отделённым подчёркиваниями словом в метке, вне зависимости от его положения.

Замечание: ltxtquery допускает пробелы между символами, а ltree и lquery — нет.

F.21.2. Операторы и функции

Для типа ltree определены обычные операторы сравнения =, <>, <, >, <=, >=. Сравнение сортирует пути в порядке движения по дереву, а потомки узла сортируются по тексту метки. В дополнение к ним есть и специализированные операторы, перечисленные в Таблице F.13.

Таблица F.13. Операторы ltree

Оператор

Описание

ltree @> ltreeboolean

Левый аргумент является предком правого (или равен ему)?

ltree <@ ltreeboolean

Левый аргумент является потомком правого (или равен ему)?

ltree ~ lqueryboolean

lquery ~ ltreeboolean

Значение ltree соответствует lquery?

ltree ? lquery[]boolean

lquery[] ? ltreeboolean

Значение ltree соответствует одному из lquery в массиве?

ltree @ ltxtqueryboolean

ltxtquery @ ltreeboolean

Значение ltree соответствует ltxtquery?

ltree || ltreeltree

Соединяет два пути ltree.

ltree || textltree

text || ltreeltree

Преобразует текст в ltree и соединяет с путём.

ltree[] @> ltreeboolean

ltree <@ ltree[]boolean

Массив содержит предка ltree?

ltree[] <@ ltreeboolean

ltree @> ltree[]boolean

Массив содержит потомка ltree?

ltree[] ~ lqueryboolean

lquery ~ ltree[]boolean

Массив содержит какой-либо путь, соответствующий lquery?

ltree[] ? lquery[]boolean

lquery[] ? ltree[]boolean

Массив ltree содержит путь, соответствующий какому-либо lquery?

ltree[] @ ltxtqueryboolean

ltxtquery @ ltree[]boolean

Массив содержит путь, соответствующий ltxtquery?

ltree[] ?@> ltreeltree

Выдаёт первый элемент массива, являющийся предком ltree, или NULL, если такого элемента нет.

ltree[] ?<@ ltreeltree

Выдаёт первый элемент массива, являющийся потомком ltree, или NULL, если такого элемента нет.

ltree[] ?~ lqueryltree

Выдаёт первый элемент массива, соответствующий lquery, или NULL, если такого элемента нет.

ltree[] ?@ ltxtqueryltree

Выдаёт первый элемент массива, соответствующий ltxtquery, или NULL, если такого элемента нет.


Операторы <@, @>, @ и ~ имеют аналоги в виде ^<@, ^@>, ^@, ^~, которые отличатся только тем, что не используют индексы. Они полезны только для тестирования.

Доступные функции перечислены в Таблице F.14.

Таблица F.14. Функции ltree

Функция

Описание

Примеры

subltree ( ltree, start integer, end integer ) → ltree

Выдаёт подпуть ltree от позиции start до позиции end-1 (отсчитывая от 0).

subltree('Top.Child1.Child2', 1, 2)Child1

subpath ( ltree, offset integer, len integer ) → ltree

Выдаёт подпуть ltree, начиная с позиции offset, длиной len. Если offset меньше нуля, подпуть начинается с этого смещения от конца пути. Если len меньше нуля, будет отброшено заданное число меток с конца строки.

subpath('Top.Child1.Child2', 0, 2)Top.Child1

subpath ( ltree, offset integer ) → ltree

Выдаёт подпуть ltree, начиная с позиции offset и до конца пути. Если offset меньше нуля, подпуть начинается с этого смещения от конца пути.

subpath('Top.Child1.Child2', 1)Child1.Child2

nlevel ( ltree ) → integer

Выдаёт число меток в пути.

nlevel('Top.Child1.​Child2')3

index ( a ltree, b ltree ) → integer

Выдаёт позицию первого вхождения b в a; -1, если искомого вхождения нет.

index('0.1.2.3.5.4.5.6.8.5.6.8', '5.6')6

index ( a ltree, b ltree, offset integer ) → integer

Выдаёт позицию первого вхождения b в a или -1, если искомого вхождения нет. Поиск начинается с позиции offset; если offset меньше 0, начальное смещение -offset отсчитывается от конца пути.

index('0.1.2.3.5.4.5.6.8.5.6.8', '5.6', -4)9

text2ltree ( text ) → ltree

Приводит значение text к типу ltree.

ltree2text ( ltree ) → text

Приводит ltree к типу text.

lca ( ltree [, ltree [, ... ]] ) → ltree

Вычисляет наибольшего общего предка путей (принимая до 8 аргументов).

lca('1.2.3', '1.2.3.4.5.6')1.2

lca ( ltree[] ) → ltree

Вычисляет наибольшего общего предка путей в массиве.

lca(array['1.2.3'::ltree,'1.2.3.4'])1.2


F.21.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.21.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.21.5. Трансформации

Также имеются дополнительные расширения, реализующие трансформации типа ltree для языка PL/Python. Эти расширения называются ltree_plpythonu, ltree_plpython2u и ltree_plpython3u (соглашения об именовании, принятые для интерфейса PL/Python, описаны в Разделе 45.1). Если вы установите эти трансформации и укажете их при создании функции, значения ltree будут отображаться в списки Python. (Однако обратное преобразование не поддерживается.)

Внимание

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

F.21.6. Авторы

Разработку осуществили Фёдор Сигаев () и Олег Бартунов (). Дополнительные сведения можно найти на странице http://www.sai.msu.su/~megera/postgres/gist/. Авторы выражают благодарность Евгению Родичеву за полезные дискуссии. Замечания и сообщения об ошибках приветствуются.