E.21. ltree

E.21.1. Определения

Метка — это последовательность алфавитно-цифровых символов и знаков подчёркивания (например, в локали C допускаются символы A-Za-z0-9_). Метки должны занимать меньше 256 байт.

Примеры: 42, Personal_Services

Путь метки — это последовательность из нуля или более меток, разделённых точками, (например, L1.L2.L3), представляющая путь от корня иерархического дерева к конкретному узлу. Длина пути метки должна быть меньше 65 КБ, но лучше, если она будет в пределах 2 КБ. На практике это ограничение не является критичным; например, самый длинный путь в каталоге DMOZ (http://www.dmoz.org) имеет длину около 240 байт.

Пример: 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}

  В конце метки, отличной от звёздочки, в 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.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 — нет.

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

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

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

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

E.21.3. Индексы

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

• B-дерево по значениям ltree: <, <=, =, >=, >

• GiST по значениям ltree: <, <=, =, >=, >, @>, <@, @, ~, ?

  Пример создания такого индекса:

  CREATE INDEX path_gist_idx ON test USING GIST (path);

• GiST по колонке ltree[]: ltree[] <@ ltree, ltree @> ltree[], @, ~, ?

  Пример создания такого индекса:

  CREATE INDEX path_gist_idx ON test USING GIST (array_path);

  Примечание: Индекс этого типа является неточным.

E.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)

E.21.5. Авторы

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