Как сделать вложенную сортировку в postgresql

Чтобы отсортировать строки в порядке DFS дерева, вы можете попробовать следующий запрос:

WITH RECURSIVE node(id, parent_id, position, position_array) AS (
    SELECT
        root.id,
        root.parent_id,
        root.position,
        ARRAY[ROW_NUMBER() OVER (ORDER BY root.position, root.id)] AS position_array
    FROM forest_node root
    WHERE root.parent_id IS NULL
UNION ALL
    SELECT
        child.id,
        child.parent_id,
        child.position,
        parent.position_array || ROW_NUMBER() OVER (PARTITION BY child.parent_id ORDER BY child.position) AS position_array
    FROM forest_node child
    INNER JOIN node parent ON parent.id = child.parent_id
)
SELECT
    n.id,
    n.parent_id,
    n.position,
    n.position_array,
    ROW_NUMBER() OVER (ORDER BY n.position_array) AS dfs_position
FROM node n
ORDER BY dfs_position;

Этот запрос начинается с корней (parent_id IS NULL) и рекурсивно (С РЕКУРСИВОЙ ) добавляет их дочерние элементы, создавая position_array с помощью оконной функции ROW_NUMBER() OVER () ( Учебное пособие по оконным функциям , Список оконных функций ). Сортировка, наконец, осуществляется путем упорядочивания по position_array на основе сравнения массивов ( Функции и операторы массивов).

Переименование forest_node в "course_content_entity" и id, parent_id и position в "id", "parentId" и "order" должно сделать это применимым к вашему случаю. Я выбрал разные имена по нескольким причинам, включая лучший общий пример и желание избежать идентификаторов в кавычках.

Предположения:

• Корневой узел может иметь или не иметь набор position. У некорневых узлов всегда установлена ​​позиция.
• В таблице может быть несколько корневых узлов (именно поэтому я использовал forest_node вместо tree_node в качестве имени таблицы). Мы заказываем их по position и разрываем связи по id. Все узлы одного дерева появляются рядом друг с другом в итоговом списке.

Примечание: если в таблице должен быть какой-то цикл, запрос будет игнорировать все записи этого цикла, поскольку нет пути, заканчивающегося корневым узлом.

Последнее замечание: если вы работаете с большой таблицей, возможно, было бы гораздо эффективнее написать функцию, которая просто обходит дерево узел за узлом, чтобы найти «соседей DFS». Предоставленный запрос всегда будет работать со всеми строками таблицы, которые могут стать узким местом.

Используется в целях тестирования:

CREATE TABLE forest_node (
    id text NOT NULL,
    parent_id text,
    position integer CHECK(position IS NOT NULL OR parent_id IS NULL),
    PRIMARY KEY(id),
    UNIQUE(parent_id, position)
);

INSERT INTO forest_node (id, parent_id, position)
VALUES
    ('root1', NULL, NULL),
    ('root2', NULL, NULL),
    ('root3', NULL, NULL),
    ('root1.1', 'root1', 1),
    ('root1.2', 'root1', 2),
    ('root3.2', 'root3', 2),
    ('root3.1', 'root3', 1),
    ('root2.1', 'root2', 1),
    ('root2.2', 'root2', 2),
    ('root2.1.1', 'root2.1', 1),
    ('root2.1.2', 'root2.1', 2),
    ('root2.4', 'root2', 4),
    ('root2.3', 'root2', 3);

Для подхода TypeORM к этой проблеме я вижу следующие возможности:

• жестко запрограммировать подготовленный оператор (параметризованный SQL-запрос)
• пройти по дереву, выбирая узлы один за другим
• используйте QueryBuilder.addCommonTableExpression() и заставьте его работать с WITH RECURSIVE (не уверен, что это возможно... возможно, нет, по крайней мере, не через QueryBuilder, а только с помощью жестко запрограммированного SQL, я полагаю)

Я бы предложил пройти по дереву и ниже приведу для этого некоторый обобщенный код.

Сущность:

import {
    Check,
    Column,
    Entity,
    Index,
    JoinColumn,
    ManyToOne,
    OneToMany,
    PrimaryGeneratedColumn,
} from "typeorm";

@Entity()
@Check("parent_id IS NULL OR position IS NOT NULL")
@Index(["parent", "position"], { unique: true })
@Index(["name"], { unique: true })
export class ForestNode {
    @PrimaryGeneratedColumn("uuid")
    id?: string; // ? because id will only get assigned on save, not already in constructor

    @Column()
    name: string; // added property to easily identify nodes

    @ManyToOne(() => ForestNode, (parent) => parent.children, { nullable: true })
    @JoinColumn()
    parent?: ForestNode | null; // ? because relation might not be loaded when record is fetched from DB

    @Column({ nullable: true, type: "int" })
    position: number | null;

    constructor(
        name: string,
        parent: ForestNode | null,
        position: number | null,
    ) {
        this.name = name;
        this.parent = parent;
        this.position = position;
    }

    @OneToMany(() => ForestNode, (child) => child.parent)
    children?: ForestNode[]; // ? because relation might not be loaded when record is fetched from DB - and no value assigned in constructor
}

Результаты в такой таблице БД (с использованием SnakeNamingStrategy из typeorm-naming-strategies):

                        Table "public.forest_node"
  Column   |       Type        | Collation | Nullable |      Default
-----------+-------------------+-----------+----------+--------------------
 id        | uuid              |           | not null | uuid_generate_v4()
 name      | character varying |           | not null |
 position  | integer           |           |          |
 parent_id | uuid              |           |          |
Indexes:
    "PK_3249a860f2197601caa2e20f3a9" PRIMARY KEY, btree (id)
    "IDX_b809a8da806808ab77c47a0e95" UNIQUE, btree (name)
    "IDX_c6597116d3f149e5889c912e8d" UNIQUE, btree (parent_id, "position")
Check constraints:
    "CHK_e53d2fb9afed95a164b1b04a3b" CHECK (parent_id IS NULL OR "position" IS NOT NULL)
Foreign-key constraints:
    "FK_db6b2f9beaeb26ff7a41a16f220" FOREIGN KEY (parent_id) REFERENCES forest_node(id)
Referenced by:
    TABLE "forest_node" CONSTRAINT "FK_db6b2f9beaeb26ff7a41a16f220" FOREIGN KEY (parent_id) REFERENCES forest_node(id)

Пример того, как пройти по дереву, чтобы найти предшественника DFS:

async function getDfsPredecessorNode(
    forestNodeRepo: Repository<ForestNode>,
    node: ForestNode,
) {
    const { parent, position } = node;

    if (parent === undefined) {
        throw new Error("parent relation not loaded");
    }
    if (parent === null) {
        return null; // root has no predecessor
    }

    if (position === null) {
        throw new Error("non-root cannot have null position");
    }

    const predecessorSibling = await forestNodeRepo.findOne({
        where: {
            parent,
            position: LessThan(position),
        },
        order: { position: "DESC" },
        relations: { parent: true },
    });

    if (!predecessorSibling) {
        return parent;
    }

    // we want now to find the last node in the subtree rooted in predecessorSibling
    let subtreeRoot = predecessorSibling;

    while (true) {
        const lastChild = await forestNodeRepo.findOne({
            where: {
                parent: subtreeRoot,
            },
            order: { position: "DESC" },
        });

        if (!lastChild) {
            return subtreeRoot;
        }

        subtreeRoot = lastChild;
    }
}

Чтобы найти преемника DFS, вы можете реализовать аналогичный подход (если у узла есть дочерние элементы, верните первого дочернего элемента; в противном случае начните с текущего узла и проверьте, есть ли у него брат-преемник, если да, верните его, иначе повторите этот шаг с родительский узел в качестве текущего узла — если родительского узла больше нет, верните ноль).