ltree in PostgreSQL mit JPA: Speichern von Bäumen

Hierarchische Daten in PostgreSQL mit ltree und JPA für Microservices speichern

Entwickler müssen häufig hierarchische Daten speichern: Organisationsstrukturen, Produktkataloge, Stammbäume. PostgreSQL bietet ltree – einen spezialisierten Typ für materialisierte Pfade, der Baumoperationen vereinfacht. Dieser Artikel untersucht die Kombination von ltree mit Adjazenzlisten in einer einzigen Tabelle und deren Integration mit JPA in einer Microservices-Architektur.

Zu den gängigen Ansätzen für die Speicherung von Bäumen gehören Adjazenzlisten (Elternreferenzen) und materialisierte Pfade (vollständige Pfade von der Wurzel). ltree implementiert Letzteres mit Punkt-Trennzeichen und bietet GIST-Indizes, Operatoren wie @> (enthält), <@ (enthalten in) und Funktionen wie nlevel().

Tabellenstruktur und Entity

Die Tabelle kombiniert beide Ansätze:

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);

JPA-Entity mit einem benutzerdefinierten Typ für ltree:

@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;
}

Benutzerdefinierte Funktionen und Prädikate

Registrieren einer Funktion für Vorfahrenprüfungen in einem PostgreSQL-Dialekt:

public class PGDialect extends PostgresPlusDialect {
    public static final String LTREE_ANCESTORS = "ancestors";

    @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();
    }
}

Prädikat für Vorfahren:

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))
        );
    }
}

Repository-Methoden

Repository mit nativen Queries und Specification-Unterstützung:

public interface NodeRepository extends JpaRepository<Node, Long>, JpaSpecificationExecutor<Node> {

    @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);

    @Query(nativeQuery = true, value = "select * from nodes n " +
            "where n.path @> (select path from nodes where id = :nodeId)")
    Collection<Node> getAncestorsByPath(Long nodeId);
}

Leistungsvergleich

Tests mit 1.000 zufälligen Knoten zeigten:

• Rekursives SQL (Adjazenzliste): 1118 ms
• ltree @> Operator: 820 ms
• JPA Specification: 1083 ms

ltree gewinnt aufgrund von GIST-Indizes und optimierten Operatoren. Specification erfordert das vorherige Abrufen des Pfads, was Overhead hinzufügt.

Testcode:

@Test
@DisplayName("Test der Leistung beim Abrufen von 'Vorfahren' mit verschiedenen Methoden")
@Transactional(readOnly = true)
public void testPerformance() {
    // ... Generieren von 1000 IDs
    // Zeitmessung für jede Methode
}

Anwendung in Microservices

In einem verteilten System wird die Struktur in einem Organisationsdienst gespeichert, während Nachrichten in einem Inhaltsdienst liegen. Ein Benutzer fordert Nachrichten aus seiner Abteilung und höheren Ebenen an.

Optionen:

• Nachrichtendienst ohne Pfad: Mehrere Abfragen an den Strukturdienst für jeden Nachrichtenbeitrag.
• Mit Pfad im Nachrichtendienst: Eine Abfrage für den Benutzerpfad, Filterung mit @> auf Datenbankseite.

Vorteile von ltree:

• Reduziert Netzwerkaufrufe zwischen Diensten.
• Schnelle hierarchische Filterung.
• Denormalisierung des Pfads minimiert den Datenverkehr.

Wichtige Erkenntnisse

• ltree lässt sich mit Adjazenzlisten in einer Tabelle kombinieren, ohne Konflikte.
• GIST-Index auf dem Pfad gewährleistet Leistung für @>, <@ Operationen.
• In Microservices reduziert das Duplizieren des Pfads dienstübergreifende Aufrufe.
• Rekursive CTEs sind bei großen Bäumen langsamer als ltree.
• JPA erfordert benutzerdefinierten Type und Dialect für ltree.

— Editorial Team