LINUX.ORG.RU

with recursive в PostgreSQL

 ,


0

3

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

CREATE TABLE test (
   tid serial PRIMARY KEY,
   pid INTEGER,
   name VARCHAR NOT NULL
   -- на самом деле тип name это домен с проверкой, но в данном случае это не важно КМК
   -- да и constraint'ы опустим.
);

И есть две задачи:

  • Найти запись в соответствии с заданным путём n1.n2.n3.n4
  • Найти ближайший элемент к заданному пути. Т.е. например для n1.n2.n3.n4 вернуть запись с путём n1.n2 т.к. у n1.n2 нет потомков.

Покопавшись с WITH RECURSIVE для первой задачи получилось такое себе решение:

WITH RECURSIVE r1 as (
  SELECT t1.tid, t1.pid, t1.name, cast( t1.name as text ) as path
  FROM test t1 WHERE pid is null and t1.name = split_part('n1.n2.n3.n4', '.', 1)
    UNION
  SELECT t2.tid, t2.pid, t2.name, r1.path || '.'|| t2.name as path
  FROM test t2
  join r1 on t2.pid = r1.id
)
select * from r1 where path = 'n1.n2.n3.n4';

Хотя меня несколько напрягает сравнение строк, но я не уверен как сделать быстрее.

И по второму вопросу не могу докумекать, как всё это реализовать. Может кто-нибудь чего подскажет?

★★★★★

Я хз чего и как (пятница и я, как нормальный? пацан пьян), но пяток лет назад я деревья хранил в постгре через ltree. Там можно было делать поиск через * типа *.n2.*.n10 и т.п. погуглди может это то что тебе надо.

пс. https://habr.com/ru/post/130371/

vtVitus ★★★★★ ()
Последнее исправление: vtVitus (всего исправлений: 2)

Можно добавить вычислимый индекс, который будет считать путь в момент вставки. Это решит первую задачу.

kmeaw=# create or replace function path(id integer) returns varchar language plpgsql as $$
declare
  _name varchar;
  _pid integer;
begin
  select into _name, _pid test.name, test.pid from test where test.tid = id;
  if _pid is null then return _name; else return path(_pid) || '.' || _name; end if;
end;
$$
;
CREATE FUNCTION
kmeaw=# select path(tid), * from test;
   path   | tid | pid | name 
----------+-----+-----+------
 n1       |   1 |     | n1
 n1.n2    |   2 |   1 | n2
 n1.n2.n3 |   3 |   2 | n3
(3 rows)

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

kmeaw=# create or replace function rpath(path varchar) returns integer language plpgsql as $$
declare
  _path varchar;
  _cand integer; _best integer;
  _part varchar;
begin
  foreach _part in array string_to_array(path, '.')
  loop
    if _path is null
    then
      _path := _part;
    else
      _path := _path || '.' || _part;
    end if;
    select into _cand tid from test where path(tid) = _path;
    _best := coalesce(_cand, _best);
    if _cand is null then return _best; end if;
  end loop;
  return _best;
end;
$$
;

Если путь чаще присутствует, чем отсутствует, можно попробовать развернуть перебор в обратную сторону - от полного пути к первому компоненту.

kmeaw ★★★ ()