Видимо, это осень так влияет, что за последний месяц на PostgreSQL
уже и
в Морской бой играли, и
Жизнь Конвея
эмулировали Что уж оставаться в стороне! Давайте и мы
потренируем мозг в реализации нетривиальных алгоритмов на SQL.
Тем более, сегодняшняя тема родилась из обсуждения моей же статьи
PostgreSQL Antipatterns: Бесконечность не предел!, или Немного о
рекурсии, где я показал, как можно заменить рекурсивное чтение
иерархичных данных из таблицы на линейное.
Прочитать-то мы прочитали, но ведь чтобы для вывода
упорядочить
элементы дерева в соответствии с иерархией, уж точно придется
воспользоваться рекурсией! Или нет? Давайте разберемся, а заодно
решим на SQL пару комбинаторных задач.
Давайте возьмем в качестве примера прочитанный из базы набор
записей чего-то вроде
справочника
сотрудников. Они образуют
ориентированное дерево из отделов и работающих в них
сотрудников, которое выглядит примерно вот так:
Точнее, это нам хочется, чтобы оно выглядело именно так
дочерний
узел под родительским, правильная сортировка детей внутри одного
предка, красивые отступы Но база-то нам отдаст записи
отсортированными в том порядке, который удобнее ей скорее всего, по
первичному ключу
id:
Давайте все-таки сначала формально определим те правила, которым
должен отвечать искомый порядок записей:
- элемент-предок стоит раньше любого из элементов его
поддерева
- дочерние элементы внутри одного родительского упорядочиваются
по дополнительному прикладному ключу
Второе требование отражает привычные для пользователя паттерны,
когда папки внутри одного каталога отображаются отсортированными по
названию, а ответы на сообщение в ветке форума по времени.
Мы, для простоты, возьмем в нашем примере в качестве такого ключа
data.
Таков путь!
Собственно, а что мы такое можем сконструировать, чтобы сортировка
этого чего-то давала нам желаемый результат?
Давайте для каждого элемента дерева вычислим путь
цепочку из
прикладных ключей всех элементов, которые надо пройти от корня,
чтобы его достигнуть:
Но если на каждом шаге такого пути мы сортируем элементы согласно
прикладному ключу, то и
массивы, составленные из этих
ключей, будучи отсортированными, дадут нам искомый порядок
записей!
Рекурсивная сортировка
Сначала воспользуемся наиболее традиционным и очевидным способом
получения нужного нам результата рекурсивным запросом:
WITH RECURSIVE src(id, pid, data) AS ( VALUES (1, NULL, 'A') , (2, 1, 'AA') , (3, 2, 'AAA') , (4, 1, 'AB') , (5, 2, 'AAB') , (6, 3, 'AAAA') , (7, 5, 'AABA') , (8, 4, 'ABA') , (9, 7, 'AABAA') , (10, 2, 'AAC')), T AS ( SELECT id , ARRAY[data] path -- инициализируем массив пути корневым элементом FROM src WHERE pid IS NULLUNION ALL SELECT s.id , T.path || s.data -- наращиваем путь FROM T JOIN src s ON s.pid = T.id)SELECT *FROM srcNATURAL JOIN TORDER BY path; -- сортируем согласно пути
id | pid | data | path----+-----+-------+----------------------- 1 | | A | {A} 2 | 1 | AA | {A,AA} 3 | 2 | AAA | {A,AA,AAA} 6 | 3 | AAAA | {A,AA,AAA,AAAA} 5 | 2 | AAB | {A,AA,AAB} 7 | 5 | AABA | {A,AA,AAB,AABA} 9 | 7 | AABAA | {A,AA,AAB,AABA,AABAA} 10 | 2 | AAC | {A,AA,AAC} 4 | 1 | AB | {A,AB} 8 | 4 | ABA | {A,AB,ABA}
Подключаем комбинаторику
А теперь вернемся к началу статьи и подумаем, как же все-таки для
той же самой задачи мы можем создать нерекурсивное решение. В этом
нам поможет
Комбинаторика (комбинаторный анализ) раздел математики,
изучающий дискретные объекты, множества (сочетания, перестановки,
размещения и перечисления элементов) и отношения на них (например,
частичного порядка).
Сначала решим несколько небольших типовых задач из этой
области.
Комбинации
Пусть у нас есть исходный массив
{A,B,C}, все элементы
которого уникальны. Получим
все комбинации массивов той же
длины, состоящие из его элементов:
{A,A,A}{A,A,B}{A,A,C}{A,B,A}{A,B,B}...{C,C,B}{C,C,C}
Достаточно очевидно, что при длине массива
N
таких вариантов будет ровно
N^N, но как
получить их на SQL?
Обратим внимание, что каждой комбинации элементов соответствует
комбинация позиций этих элементов в исходном массиве, если
пронумеровать их с нуля. А каждой такой комбинации
число в
N-ричной системе счисления:
3^2 | 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 2 2 2 2 2 2 2 2 23^1 | 0 0 0 1 1 1 2 2 2 0 0 0 1 1 1 2 2 2 0 0 0 1 1 1 2 2 23^0 | 0 1 2 0 1 2 0 1 2 0 1 2 0 1 2 0 1 2 0 1 2 0 1 2 0 1 2=== | 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26
Решение становится достаточно очевидным:
- генерируем каждое число в диапазоне
0 .. N^N -
1
- раскладываем в N-ричную систему счисления
- берем элемент на соответствующей позиции разложения
SELECT dstFROM -- исходный набор элементов (VALUES('{A,B,C}'::varchar[])) data(src) -- кэшируем размер набора, LATERAL array_length(src, 1) n -- кэшируем границу интервала, LATERAL (SELECT (n ^ n)::bigint l) X -- генерируем все числа на интервале, LATERAL generate_series(0, l - 1) num -- формируем разложение числа в N-ричной системе, LATERAL ( SELECT array_agg((num % (n ^ (pos + 1))::bigint) / (n ^ pos)::bigint ORDER BY pos DESC) num_n FROM generate_series(0, n - 1) pos ) Y -- собираем элементы согласно "цифрам", LATERAL ( SELECT array_agg(src[num_n[pos] + 1]) dst FROM generate_subscripts(num_n, 1) pos ) Z;
Перестановки
Но в оригинальном наборе у нас каждый элемент был уникален, а в
полученных нами комбинациях это правило не соблюдается. Исправим,
получив все возможные
перестановки. Для этого отфильтруем из
num_n
только те, где встречаются все цифры:
JOIN LATERAL( SELECT count(DISTINCT unnest) = n cond FROM unnest(num_n)) flt ON cond
Полный вариант запроса
SELECT dstFROM -- исходный набор элементов (VALUES('{A,B,C}'::varchar[])) data(src) -- кэшируем размер набора, LATERAL array_length(src, 1) n -- кэшируем границу интервала, LATERAL (SELECT (n ^ n)::bigint l) X -- генерируем все числа на интервале, LATERAL generate_series(0, l - 1) num -- формируем разложение числа в N-ричной системе, LATERAL ( SELECT array_agg((num % (n ^ (pos + 1))::bigint) / (n ^ pos)::bigint ORDER BY pos DESC) num_n FROM generate_series(0, n - 1) pos ) Y -- фильтруем комбинации с неполным набором "цифр"JOIN LATERAL( SELECT count(DISTINCT unnest) = n cond FROM unnest(num_n) ) flt ON cond -- собираем элементы согласно "цифрам", LATERAL ( SELECT array_agg(src[num_n[pos] + 1]) dst FROM generate_subscripts(num_n, 1) pos ) Z;
Это дает нам все возможные перестановки исходного набора:
{A,B,C}{A,C,B}{B,A,C}{B,C,A}{C,A,B}{C,B,A}
Можно использовать и
неэкспоненциальный алгоритм на основе тасований, работающий за
O(N*N!), но его реализация явно выходит за рамки
данной статьи.
Подмножества
Сделаем шаг чуть в сторону и научимся генерировать все подмножества
исходного набора с сохранением порядка. То есть для нашего набора
{A,B,C} должно получиться вот это:
{}{A}{B}{A,B}{C}{A,C}{B,C}{A,B,C}
В принципе, задача очень близка к первой решенной нами. Только
вместо позиции
двоичная цифра означает отсутствие или
наличие соответствующего элемента в результирующем наборе:
2^2 | 0 0 0 0 1 1 1 12^1 | 0 0 1 1 0 0 1 12^0 | 0 1 0 1 0 1 0 1=== | 0 1 2 3 4 5 6 7
Поскольку двоичная арифметика представлена в компьютерах гораздо
эффективнее, мы можем воспользоваться функциями работы с
битовыми строками:
-- кэшируем разложение числа в двоичной системе, LATERAL (SELECT num::bit(64) num_n) Y -- собираем элементы согласно "цифрам", LATERAL ( SELECT coalesce(array_agg(src[i]) FILTER(WHERE get_bit(num_n, 64 - i) = 1), '{}') dst FROM generate_series(1, n) i ) Z
Полный вариант запроса
SELECT dstFROM -- исходный набор элементов (VALUES('{A,B,C}'::varchar[])) data(src) -- кэшируем размер набора, LATERAL array_length(src, 1) n -- кэшируем границу интервала, LATERAL (SELECT (2 ^ n)::bigint l) X -- генерируем все числа на интервале, LATERAL generate_series(0, l - 1) num -- кэшируем разложение числа в двоичной системе, LATERAL (SELECT num::bit(64) num_n) Y -- собираем элементы согласно "цифрам", LATERAL ( SELECT coalesce(array_agg(src[i]) FILTER(WHERE get_bit(num_n, 64 - i) = 1), '{}') dst FROM generate_series(1, n) i ) Z;
Иерархия без рекурсии!
Теперь, вооруженные всеми приведенными выше алгоритмами, попробуем
найти решение нашей задачи сначала в общем виде, а затем разберем
один из типичных частных случаев.
Пути-дороги
Для начала воспользуемся тем фактом, что в качестве элементов пути,
который идентифицирует конкретную запись, можно использовать
уникальные ключи промежуточных записей в нашем случае это
id.
Но сортировать по такому пути, конечно, будет некорректно поэтому
для дальнейшей сортировки превратим
id записей в
соответствующее значение
data, которое использовали в
первом варианте.
Дано: газовая плита, чайник. Задача: вскипятить
воду.
Физик: Зажечь плиту, наполнить чайник водой и поставить на плиту,
ждать.
Математик: Аналогично.
Дано: зажженная газовая плита, наполненный водой чайник. Задача:
вскипятить воду.
Физик: Поставить чайник на плиту, ждать.
Математик: Выливаем воду из чайника на плиту. Огонь погас, чайник
пуст, задача сведена к предыдущей.
Народный анекдот
Но как найти путь до каждого из элементов без рекурсии? Вот здесь
нам и пригодятся алгоритмы выше.
Корректный путь от корня до конкретного элемента обладает
следующими свойствами:
- Правило #1: начинается и заканчивается нужными нам
элементами
path[1] = root AND path[array_length(path, 1)] =
id
- Правило #2: предок каждого элемента, кроме корневого, так же
присутствует в наборе
pid = ANY(path) OR pid = root
- Правило #3: из всех таких наборов искомый самой маленькой
длины
Иначе для id=3 наборы {1,2,3} и
{1,2,3,4} окажутся равноподходящими, поскольку предок
id=4 (pid=1) тоже присутствует.
- Правило #4: предок каждого элемента стоит ровно в предыдущей
позиции
pid = path[pos - 1]
Итак, намечаем план действий:
- генерируем все подмножества элементов, исключая
root и id, формируя тело пути по правилу
#1
- проверяем выполнение правила #2
- выбираем, согласно правилу #3, самый короткий набор
- генерируем все перестановки его элементов
- проверяем выполнение правила #4
- что осталось искомый путь
Полный вариант запроса, смотреть с
осторожностью
Я вас предупредил [
источник
картинки]
WITH src(id, pid, data) AS ( VALUES (1, NULL, 'A') , (2, 1, 'AA') , (3, 2, 'AAA') , (4, 1, 'AB') , (5, 2, 'AAB') , (6, 3, 'AAAA') , (7, 5, 'AABA') , (8, 4, 'ABA') , (9, 7, 'AABAA') , (10, 2, 'AAC'))-- кэшируем ID корневого элемента, root AS ( SELECT id FROM src WHERE pid IS NULL LIMIT 1)-- формируем уже известные пути и предварительные наборы, preset AS ( SELECT * , CASE -- для корневого элемента путь состоит только из него самого WHEN pid IS NULL THEN ARRAY[id] -- для ссылающегося на корневой - из пары WHEN pid = (TABLE root) THEN ARRAY[pid, id] END prepath , CASE WHEN pid IS NULL THEN NULL WHEN pid = (TABLE root) THEN NULL -- все ID, кроме корневого и собственного - EXCLUDE CURRENT ROW ELSE array_agg(id) FILTER(WHERE pid IS NOT NULL) OVER(ROWS BETWEEN UNBOUNDED PRECEDING AND UNBOUNDED FOLLOWING EXCLUDE CURRENT ROW) END preset FROM src)-- формируем "переборные" пути, prepath AS ( SELECT id , prepath FROM -- отбираем только элементы, чей путь еще не определили ( SELECT id , pid , preset src -- комбинируемый набор FROM preset WHERE prepath IS NULL ) data -- подмножества , LATERAL ( SELECT dst pathset FROM -- кэшируем размер набора LATERAL array_length(src, 1) n -- кэшируем границу интервала , LATERAL (SELECT (2 ^ n)::bigint l) X -- генерируем все числа на интервале , LATERAL generate_series(1, l - 1) num -- тут можно с 1, поскольку пустой набор нас заведомо не интересует -- кэшируем разложение числа в двоичной системе , LATERAL (SELECT num::bit(64) num_n) Y -- собираем элементы согласно "цифрам" , LATERAL ( SELECT coalesce(array_agg(src[i]) FILTER(WHERE get_bit(num_n, 64 - i) = 1), '{}') || data.id dst FROM generate_series(1, n) i ) Z -- проверяем наличие предка в наборе , LATERAL ( SELECT NULL FROM ( SELECT (SELECT pid FROM src WHERE id = dst[i] LIMIT 1) _pid FROM generate_subscripts(dst, 1) i ) T HAVING bool_and(_pid = (TABLE root) OR _pid = ANY(dst)) ) rule2 -- отбираем первый подходящий минимальной длины ORDER BY array_length(dst, 1) -- rule3 LIMIT 1 ) X -- перестановки , LATERAL ( SELECT dst prepath FROM -- исходный набор элементов (SELECT pathset) data(src) -- кэшируем размер набора , LATERAL array_length(src, 1) n -- кэшируем границу интервала , LATERAL (SELECT (n ^ n)::bigint l) X -- генерируем все числа на интервале , LATERAL generate_series(0, l - 1) num -- формируем разложение числа в N-ричной системе , LATERAL ( SELECT array_agg((num % (n ^ (pos + 1))::bigint) / (n ^ pos)::bigint ORDER BY pos DESC) num_n FROM generate_series(0, n - 1) pos ) Y -- фильтруем комбинации с неполным набором "цифр" JOIN LATERAL( SELECT count(DISTINCT unnest) = n cond FROM unnest(num_n) ) flt ON cond -- собираем элементы согласно "цифрам" , LATERAL ( SELECT array_agg(src[num_n[pos] + 1]) dst FROM generate_subscripts(num_n, 1) pos ) Z -- проверяем наличие предка в предыдущей позиции , LATERAL ( SELECT NULL FROM ( SELECT (SELECT pid FROM src WHERE id = dst[i] LIMIT 1) _pid , i FROM generate_subscripts(dst, 1) i ) T HAVING bool_and((i = 1 AND _pid = (TABLE root)) OR _pid = dst[i - 1]) ) rule4 ) Y)SELECT src.* -- восстанавливаем "путь" из прикладных ключей, ( SELECT array_agg(data ORDER BY i) FROM coalesce(X.prepath, ARRAY[(TABLE root)] || Y.prepath) p -- помним о необходимости добавить "корень" , LATERAL generate_subscripts(p, 1) i , LATERAL ( SELECT data FROM src WHERE id = p[i] LIMIT 1 ) T ) pathFROM srcLEFT JOIN preset X USING(id)LEFT JOIN prepath Y USING(id)ORDER BY path;
А попроще можно?..
Можно и попроще, если заранее известно, что порядок детей внутри
одного родителя определяется некоторым сквозным ключом. Например,
это может быть некоторый
монотонно возрастающий timestamp
сообщений в ветке форума или, как в нашем случае, первичный ключ
типа
serial (
id).
В таком случае, мы уже точно
знаем порядок следования
идентификаторов записей в нужном нам пути он совпадает с общей
сортировкой по этому ключу. И нам надо только выкинуть лишние id из
списка всех предстоящих:
WITH src(id, pid, data) AS ( VALUES (1, NULL, 'A') , (2, 1, 'AA') , (3, 2, 'AAA') , (4, 1, 'AB') , (5, 2, 'AAB') , (6, 3, 'AAAA') , (7, 5, 'AABA') , (8, 4, 'ABA') , (9, 7, 'AABAA') , (10, 2, 'AAC'))-- кэшируем ID корневого элемента, root AS ( SELECT id FROM src WHERE pid IS NULL LIMIT 1)-- собираем все предстоящие id в массив для текущего, prepath AS ( SELECT id , pid , array_agg(id) OVER(ORDER BY id /*!!! сортировка по тому самому ключу*/ ROWS UNBOUNDED PRECEDING EXCLUDE CURRENT ROW) src FROM src WHERE pid IS NOT NULL)-- находим пути, pre AS ( SELECT id , path FROM prepath -- подмножества , LATERAL ( SELECT dst path FROM -- кэшируем размер набора LATERAL array_length(src, 1) n -- кэшируем границу интервала , LATERAL (SELECT (2 ^ n)::bigint l) X -- генерируем все числа на интервале , LATERAL generate_series(0, l - 1) num -- кэшируем разложение числа в двоичной системе , LATERAL (SELECT num::bit(64) num_n) Y -- собираем элементы согласно "цифрам" , LATERAL ( SELECT coalesce(array_agg(src[i]) FILTER(WHERE get_bit(num_n, 64 - i) = 1), '{}') || id dst FROM generate_series(1, n) i ) Z -- проверяем наличие предка в предыдущей позиции , LATERAL ( SELECT NULL FROM ( SELECT (SELECT pid FROM src WHERE id = dst[i] LIMIT 1) _pid , i FROM generate_subscripts(dst, 1) i ) T HAVING bool_and((i = 1 AND _pid = (TABLE root)) OR (i > 1 AND _pid = dst[i - 1])) ) rule4 ) X)SELECT src.* -- восстанавливаем "путь" из прикладных ключей, ( SELECT array_agg(data ORDER BY i) FROM ( SELECT CASE -- для корневого элемента путь состоит только из него самого WHEN pid IS NULL THEN ARRAY[id] -- для ссылающегося на корневой - из пары WHEN pid = (TABLE root) THEN ARRAY[pid, id] ELSE ARRAY[(TABLE root)] || pre.path END p -- помним о необходимости добавить "корень" ) p , LATERAL generate_subscripts(p, 1) i , LATERAL ( SELECT data FROM src WHERE id = p[i] LIMIT 1 ) T ) pathFROM srcLEFT JOIN pre USING(id)ORDER BY path;
Понятно, что производительность таких экспоненциальных решений не
особо велика и применять в бою надо с большой осторожностью, но как
гимнастика для ума вполне.
04.08.2020 16:15:07 |
Автор: 
Категории: 
