Общая информация
В жизни разработчика периодически возникает задача каким-либо образом сохранить что-то древообразное. Это может быть оргструктура компании, каталог товаров, генеалогическое дерево и т.п.
И, соответственно, возникает задача как это хранить и использовать. Поскольку эта задача существует уже давно , то и подходы к решению этой задачи уже давно проработаны. Вот эти способы:
Adjacency List
Nested Sets
Closure Tab
Materialized Path.
Не буду расписывать в деталях всех из них, поскольку про них существует много материалов, но, по моему скромному мнению, Adjacency List и Materialized Path являются самыми приятными к использованию.
Adjacency List
Это простое хранение данных, когда для каждого узла дерева мы храним кто является его родителем.
Materialized Path
Этот подход при котором мы для каждого узла дерева храним полный путь от корневого элемента до узла.
Я умышленно в качестве разделителя в пути использовал '.' для того чтобы теперь перейти к теме ltree
ltree
Как говорится в документации к PostgreSQL тут :
ltree — тип данных для представления меток данных в иерархической древовидной структуре
Так же там же есть еще одно определение:
Путь метки — это последовательность из нуля или нескольких разделённых точками меток (например, L1.L2.L3), представляющая путь от корня иерархического дерева к конкретному узлу.
Из чего нам становится понятно, что ltree - это реализация подхода Materialized Path в PostgreSQL. И соответственно нам вместе с ltree достаются операторы и функции, которые весьмо полезны при работе с деревом и упрощают жизнь разработчик
Задача
Для того чтобы сравнить для подхода на практике в качеcтве примера работы возьмем получение списка узлов от заданного вверх по дереву.
И давайте сделаем это 3-мя способами:
Через рекурсивный SQL (Adjacency List)
Через ltree с использованием SQL
Через Specification
А также сравним оба подхода при исползовании микросервисов.
В прошлой своей статье я расказал на примере интервальных данных как нам подружить c JPA нестандартные типы данных Postres, поэтому здесь я не буду повторять все шаги прошлой статьи и сосредоточусь на основных моментах.
Код проекта и весь код, который привеведен ниже, можно найти тут : https://gitlab.com/pavel.s.gaev/ltree-demo
Поиск
Таблица БД
Простая таблица по хранению данных об узлах дерева для наших изысканий будет иметь следующий вид:
CREATE EXTENSION IF NOT EXISTS ltree; CREATE TABLE nodes ( id bigint NOT NULL, parent_id bigint, code varchar(6) NOT NULL, path ltree NOT NULL, depth integer NOT NULL GENERATED ALWAYS AS (nlevel(path)) STORED, CONSTRAINT nodes_pk PRIMARY KEY (id), CONSTRAINT nodes_parent_id_fk FOREIGN KEY (parent_id) REFERENCES nodes (id), CONSTRAINT nodes_code_unq UNIQUE (code) ); CREATE INDEX nodes_parent_id_idx ON nodes (parent_id); CREATE INDEX nodes_path_idx ON nodes USING GIST (path);
Как видим совмещение обоих подходов в рамках 1 таблицы ни коим образом не противоречит друг другу.
Entity
@Accessors(chain = true) @Getter @Setter @Entity @Table(name = "nodes") public class Node { @Id @Column(name = "id", nullable = false, updatable = false) private Long id; @ManyToOne(fetch = FetchType.LAZY) @JoinColumn(name = "parent_id") private Node parent; @Size(max = 6) @NotBlank @Column(name = "code", nullable = false, length = 6, updatable = false) private String code; @Type(PostgreSQLLTreeType.class) @NotBlank @Column(name = "path", columnDefinition = "ltree") private String path; @Generated(event = {EventType.INSERT, EventType.UPDATE}) @Column(name = "depth", insertable = false, updatable = false) private Integer depth; }
Кастомные функции
Зарегистрируем нашу функцию, которая будет посзволять находить все узлы вверх по дереву, включая исходный узел
public class PGDialect extends PostgresPlusDialect { public static final String LTREE_ANCESTORS = "ancestors"; public PGDialect() { super(); } @Override public void initializeFunctionRegistry(FunctionContributions functionContributions) { super.initializeFunctionRegistry(functionContributions); SqmFunctionRegistry functionRegistry = functionContributions.getFunctionRegistry(); BasicTypeRegistry basicTypeRegistry = functionContributions.getTypeConfiguration().getBasicTypeRegistry(); BasicType<Boolean> booleanType = basicTypeRegistry.resolve(StandardBasicTypes.BOOLEAN); functionRegistry.patternDescriptorBuilder( LTREE_ANCESTORS, "(?1::ltree @> ?2::ltree)" ) .setExactArgumentCount(2) .setArgumentTypeResolver(StandardFunctionArgumentTypeResolvers.ARGUMENT_OR_IMPLIED_RESULT_TYPE) .setInvariantType(booleanType) .register(); } }
Предикат
public class NodePredicateUtils { public static Predicate ancestors(From<?, Node> from, CriteriaBuilder builder, String path) { return builder.isTrue( builder.function(LTREE_ANCESTORS, Boolean.class, from.get("path"), builder.literal(path)) ); } }
Repostory
public interface NodeRepository extends JpaRepository<Node, Long>, JpaSpecificationExecutor<Node> { /** * Получить все записи начиная с узла (включая) до корневого элемента, используя рекурсивный SQL * Т.е. получаем список предков * * @param nodeId идентификатор узла * @return список объектов */ @Query(nativeQuery = true, value = """ WITH RECURSIVE tree AS ( SELECT n.* FROM nodes n WHERE n.id = :nodeId UNION ALL SELECT n.* FROM nodes n, tree WHERE n.id = tree.parent_id ) SELECT * FROM tree """) Collection<Node> getAncestors(Long nodeId); /** * Получить все записи начиная с узла (включая) до корневого элемента, используя ltree. * Т.е. получаем список предков * * @param nodeId идентификатор узла * @return список объектов */ @Query(nativeQuery = true, value = "select * from nodes n " + "where n.path @> (select path from nodes where id = :nodeId)") Collection<Node> getAncestorsByPath(Long nodeId); }
Примеры реализации поиска
@Test @DisplayName("Получение предков с помощью рекурсивного метода") public void testAncestorsRecursive() { Collection<Node> nodes = repository.getAncestors(50000L); assertNotNull(nodes); assertFalse(nodes.isEmpty()); nodes.forEach(node -> log.info("Node<id={}, parentId={}, code={}, path={}, depth={}>", node.getId(), Optional.ofNullable(node.getParent()).map(Node::getId).orElse(null), node.getCode(), node.getPath(), node.getDepth() )); } @Test @DisplayName("Получение предков через ltree") public void testAncestorsByPath() { Collection<Node> nodes = repository.getAncestorsByPath(50000L); assertNotNull(nodes); assertFalse(nodes.isEmpty()); nodes.forEach(node -> log.info("Node<id={}, parentId={}, code={}, path={}, depth={}>", node.getId(), Optional.ofNullable(node.getParent()).map(Node::getId).orElse(null), node.getCode(), node.getPath(), node.getDepth() )); } @Test @DisplayName("Получение предков с помощью Specification") public void testAncestorsSpecification() { Specification spec = (root, query, criteriaBuilder) -> ancestors(root, criteriaBuilder, "U8oj2J.rrKOti.puqgcl.Hy9rGW.5rbSLt.dIFwff.2dt02D.mqbNrE.tKha0j"); Collection<Node> nodes = repository.findAll(spec); assertNotNull(nodes); assertFalse(nodes.isEmpty()); nodes.forEach(node -> log.info("Node<id={}, parentId={}, code={}, path={}, depth={}>", node.getId(), Optional.ofNullable(node.getParent()).map(Node::getId).orElse(null), node.getCode(), node.getPath(), node.getDepth() )); }
Следует обратить особое внимание, что при поиске через Specification предварительно следует узнать path исходного узла. Что может в ряде случаев может чуть усложнить задачу исходного поиска и увеличить время исполнения поиска.
Производительность методов
В этот раз я решил сравнить методы поиска по их производительности.
@Test @DisplayName("Проверяем производительность получения 'предков' для различных способов") @Transactional(readOnly = true) public void testPerformance() { Set<Long> ids = new HashSet<>(); while (ids.size() < 1000) { ids.add(randomUtils.randomLong(0, ROWS_COUNT)); } StopWatch watch = new StopWatch(); watch.start(); for (long id : ids) { repository.getAncestors(id); } watch.stop(); log.info("Recursive method. Time: {}ms", watch.getTotalTimeMillis()); StopWatch watch2 = new StopWatch(); watch2.start(); for (long id : ids) { repository.getAncestorsByPath(id); } watch2.stop(); log.info("Path method. Time: {}ms", watch2.getTotalTimeMillis()); StopWatch watch3 = new StopWatch(); Collection<String> paths = new ArrayList<>(ids.size()); for (long id : ids) { paths.add(repository.getReferenceById(id).getPath()); } watch3.start(); for (String path : paths) { Specification spec = (root, query, criteriaBuilder) -> ancestors(root, criteriaBuilder, path); repository.findAll(spec); } watch3.stop(); log.info("Specification. Time: {}ms", watch3.getTotalTimeMillis()); }
Замечание: Для работы через Specification умышленно исключено время на получение. В обычном флоу для энд пойнта '/nodes/{id}/ancestors' мы сначала проверяем наличие исходного объекта по id. Поэтому условно считаем что 'path' нам известен.
Результаты:
Recursive method. Time: 1118ms
Path method. Time: 820ms
Specification. Time: 1083ms
Использование ltree при микросервисном подходе.
Для примера рассмотрим абстрактную задачу получения новостей пользователем, который работает в некотором филиале холдинга и он должен получить новости как своего подразделения, так и вышестоящих.
Соответственно, у нас будет 2 сервиса:
Сервис 1 - где хранится информация о структуре холдинга (наше дерево) и информация о том какому узлу этого дерева принадлежит пользователь
Сервис 2 - где хранится новость, какому подразделению эта новость принадлежит и разрешена выдача новостей этого подразделения или нет(например, не оплачены услуги Сервиса 2)
Давайте посмотрим как будут выглядеть запросы для случаев когда у нас в Сервисе 2 нет информации о положении узла в дереве(колонки path нет), и когда мы храним эту информацию
Общие выводы
Как видим переход (или расширение модели) на использование ltree способно привести к определенному росту производительности системы, дать больше гибкости в работе с иерахическими данными, снизить нагрузку на инфраструктуру
