PostgreSQL 안티패턴: 토끼굴은 얼마나 깊나요? 계층구조를 살펴보자

복잡한 ERP 시스템에서 많은 엔터티는 계층적 성격을 가지고 있습니다.같은 종류의 물체가 줄지어 늘어서 있을 때 조상-후손 관계의 나무 - 이것은 기업의 조직 구조(모든 지점, 부서 및 작업 그룹), 상품 카탈로그, 작업 영역, 판매 지점의 지리입니다...

사실은 하나도 없어요 비즈니스 자동화 영역, 결과적으로 계층 구조가 존재하지 않습니다. 그러나 "비즈니스를 위해" 일하지 않더라도 여전히 계층적 관계를 쉽게 접할 수 있습니다. 진부한 일입니다. 가계도나 쇼핑 센터 건물의 평면도도 동일한 구조입니다.

이러한 트리를 DBMS에 저장하는 방법은 여러 가지가 있지만 오늘은 한 가지 옵션에만 중점을 둘 것입니다.

CREATE TABLE hier(
  id
    integer
      PRIMARY KEY
, pid
    integer
      REFERENCES hier
, data
    json
);

CREATE INDEX ON hier(pid); -- не забываем, что FK не подразумевает автосоздание индекса, в отличие от PK

그리고 당신이 계층 구조의 깊이를 들여다보는 동안, 그러한 구조로 작업하는 "순진한" 방식이 얼마나 효과적이지 않을지 인내심을 갖고 기다리고 있습니다.

발생하는 일반적인 문제와 SQL에서의 구현을 살펴보고 성능을 개선해 보겠습니다.

#1. 토끼굴은 얼마나 깊나요?

명확성을 위해 이 구조는 부서, 사업부, 부문, 지점, 작업 그룹 등 조직 구조에서 부서의 종속성을 반영한다는 점을 인정하겠습니다.

먼저 10K 요소로 구성된 '트리'를 생성해 보겠습니다.

INSERT INTO hier
WITH RECURSIVE T AS (
  SELECT
    1::integer id
  , '{1}'::integer[] pids
UNION ALL
  SELECT
    id + 1
  , pids[1:(random() * array_length(pids, 1))::integer] || (id + 1)
  FROM
    T
  WHERE
    id < 10000
)
SELECT
  pids[array_length(pids, 1)] id
, pids[array_length(pids, 1) - 1] pid
FROM
  T;

가장 간단한 작업부터 시작해 보겠습니다. 특정 부문 내에서 또는 계층 구조 측면에서 일하는 모든 직원을 찾아보세요. 노드의 모든 자식 찾기. 자손의 "깊이"를 얻는 것도 좋을 것입니다... 예를 들어 일종의 것을 구축하려면 이 모든 것이 필요할 수 있습니다. 해당 직원의 ID 목록을 기반으로 한 복잡한 선택.

이러한 후손의 레벨이 몇 개만 있고 그 수가 십여 개 이내라면 모든 것이 괜찮겠지만, 레벨이 5개가 넘고 이미 자손이 수십 개라면 문제가 발생할 수 있습니다. 전통적인 하위 트리 검색 옵션이 어떻게 작성되고 작동하는지 살펴보겠습니다. 하지만 먼저 우리 연구에 가장 흥미로운 노드가 무엇인지 결정해 보겠습니다.

가장 좋은 "깊은" 하위 트리:

WITH RECURSIVE T AS (
  SELECT
    id
  , pid
  , ARRAY[id] path
  FROM
    hier
  WHERE
    pid IS NULL
UNION ALL
  SELECT
    hier.id
  , hier.pid
  , T.path || hier.id
  FROM
    T
  JOIN
    hier
      ON hier.pid = T.id
)
TABLE T ORDER BY array_length(path, 1) DESC;

 id  | pid  | path
---------------------------------------------
7624 | 7623 | {7615,7620,7621,7622,7623,7624}
4995 | 4994 | {4983,4985,4988,4993,4994,4995}
4991 | 4990 | {4983,4985,4988,4989,4990,4991}
...

가장 좋은 "넓은" 하위 트리:

...
SELECT
  path[1] id
, count(*)
FROM
  T
GROUP BY
  1
ORDER BY
  2 DESC;

id   | count
------------
5300 |   30
 450 |   28
1239 |   27
1573 |   25

이러한 쿼리에 대해 우리는 일반적인 재귀적 JOIN:


분명히 이 요청 모델을 사용하면 반복 횟수는 총 하위 항목 수와 일치합니다. (그리고 수십 개가 있습니다) 이는 상당한 리소스와 결과적으로 시간이 걸릴 수 있습니다.

"가장 넓은" 하위 트리를 확인해 보겠습니다.

WITH RECURSIVE T AS (
  SELECT
    id
  FROM
    hier
  WHERE
    id = 5300
UNION ALL
  SELECT
    hier.id
  FROM
    T
  JOIN
    hier
      ON hier.pid = T.id
)
TABLE T;

[explain.tensor.ru 참조]

예상대로 30개의 레코드를 모두 찾았습니다. 그러나 그들은 여기에 총 시간의 60%를 소비했습니다. 왜냐하면 그들은 인덱스에서 30번의 검색도 수행했기 때문입니다. 적게 하는 것이 가능한가요?

색인별 대량교정

각 노드에 대해 별도의 인덱스 쿼리를 만들어야 합니까? 아니요. 색인에서 읽을 수 있습니다. 한 번의 호출로 여러 키를 동시에 사용 를 통해 = ANY(array).

그리고 각 식별자 그룹에서 이전 단계에서 "노드"로 찾은 모든 ID를 사용할 수 있습니다. 즉, 다음 단계마다 우리는 특정 레벨의 모든 자손을 한번에 검색.

다만, 문제는 바로 이것이다. 재귀 선택에서는 중첩 쿼리에서 자체에 액세스할 수 없습니다., 하지만 이전 수준에서 찾은 것만 선택해야 합니다... 전체 선택 항목에 대해 중첩 쿼리를 만드는 것이 불가능하지만 특정 필드에 대해서는 가능하다는 것이 밝혀졌습니다. 그리고 이 필드는 배열이 될 수도 있습니다. 이것이 우리가 사용해야 하는 것입니다. ANY.

조금 이상하게 들리지만 다이어그램에서는 모든 것이 간단합니다.

WITH RECURSIVE T AS (
  SELECT
    ARRAY[id] id$
  FROM
    hier
  WHERE
    id = 5300
UNION ALL
  SELECT
    ARRAY(
      SELECT
        id
      FROM
        hier
      WHERE
        pid = ANY(T.id$)
    ) id$
  FROM
    T
  WHERE
    coalesce(id$, '{}') <> '{}' -- условие выхода из цикла - пустой массив
)
SELECT
  unnest(id$) id
FROM
  T;

[explain.tensor.ru 참조]

그리고 여기서 가장 중요한 것은 시간 내에 1.5배 승리, 인덱스에 대한 호출이 5개가 아닌 30개뿐이므로 더 적은 수의 버퍼를 뺍니다!

추가 보너스는 최종 unnest 후에도 식별자가 "레벨"별로 정렬되어 있다는 사실입니다.

노드 사인

성능 향상에 도움이 되는 다음 고려 사항은 다음과 같습니다. "잎"은 자식을 가질 수 없습니다즉, 그들에게는 전혀 "아래"를 볼 필요가 없습니다. 우리 작업의 공식화에서 이는 부서 체인을 따라 직원에게 연락하면 이 지점을 더 이상 볼 필요가 없음을 의미합니다.

우리 테이블에 들어가자 추가의 boolean-필드, 이는 트리의 이 특정 항목이 "노드"인지, 즉 하위 항목을 가질 수 있는지 여부를 즉시 알려줍니다.

ALTER TABLE hier
  ADD COLUMN branch boolean;

UPDATE
  hier T
SET
  branch = TRUE
WHERE
  EXISTS(
    SELECT
      NULL
    FROM
      hier
    WHERE
      pid = T.id
    LIMIT 1
);
-- Запрос успешно выполнен: 3033 строк изменено за 42 мс.

엄청난! 모든 트리 요소 중 30% 남짓만이 자손을 갖고 있는 것으로 나타났습니다.

이제 약간 다른 메커니즘을 사용해 보겠습니다. 즉, 다음을 통해 재귀 부분에 연결합니다. LATERAL이를 통해 재귀 "테이블"의 필드에 즉시 액세스하고 노드 기반 필터링 조건과 함께 집계 함수를 사용하여 키 세트를 줄일 수 있습니다.

WITH RECURSIVE T AS (
  SELECT
    array_agg(id) id$
  , array_agg(id) FILTER(WHERE branch) ns$
  FROM
    hier
  WHERE
    id = 5300
UNION ALL
  SELECT
    X.*
  FROM
    T
  JOIN LATERAL (
    SELECT
      array_agg(id) id$
    , array_agg(id) FILTER(WHERE branch) ns$
    FROM
      hier
    WHERE
      pid = ANY(T.ns$)
  ) X
    ON coalesce(T.ns$, '{}') <> '{}'
)
SELECT
  unnest(id$) id
FROM
  T;

[explain.tensor.ru 참조]

인덱스 호출을 한 번 더 줄일 수 있었고 양적으로 2배 이상 승리 교정하다.

#2. 뿌리로 돌아가자

이 알고리즘은 "트리 위"의 모든 요소에 대한 기록을 수집해야 하는 동시에 어떤 소스 시트(및 어떤 지표로)가 샘플에 포함되었는지에 대한 정보를 유지해야 하는 경우에 유용합니다(예: 요약 보고서 생성). 노드로 집계됩니다.

요청이 매우 번거롭기 때문에 다음 내용은 개념 증명으로만 받아들여야 합니다. 그러나 그것이 데이터베이스를 지배한다면 유사한 기술을 사용하는 것을 고려해야 합니다.

몇 가지 간단한 문장으로 시작해 보겠습니다.

• 데이터베이스의 동일한 레코드 한 번만 읽어보는 것이 가장 좋습니다..
• 데이터베이스의 레코드 일괄적으로 읽는 것이 더 효율적입니다.혼자보다.

이제 필요한 요청을 구성해 보겠습니다.

1 단계

분명히, 재귀를 초기화할 때(재귀가 없으면 어디에 있을까요!) 초기 식별자 세트를 기반으로 리프 자체의 레코드를 빼야 합니다.

WITH RECURSIVE tree AS (
  SELECT
    rec -- это цельная запись таблицы
  , id::text chld -- это "набор" приведших сюда исходных листьев
  FROM
    hier rec
  WHERE
    id = ANY('{1,2,4,8,16,32,64,128,256,512,1024,2048,4096,8192}'::integer[])
UNION ALL
  ...

"세트"가 배열이 아닌 문자열로 저장된다는 것이 누군가에게 이상하게 보인다면 이에 대한 간단한 설명이 있습니다. 문자열에 대한 집계 "접착" 기능이 내장되어 있습니다. string_agg, 그러나 배열에는 해당되지 않습니다. 비록 그녀는 스스로 구현하기 쉽다.

2 단계

이제 더 읽어야 할 섹션 ID 세트를 얻게 됩니다. 거의 항상 원본 세트의 다른 레코드에 복제됩니다. 그룹화, 소스 잎에 대한 정보는 보존합니다.

그러나 여기서는 세 가지 문제가 우리를 기다리고 있습니다.

1. 쿼리의 "하위 재귀" 부분에는 다음과 같은 집계 함수가 포함될 수 없습니다. GROUP BY.
2. 재귀적 "테이블"에 대한 참조는 중첩된 하위 쿼리에 포함될 수 없습니다.
3. 재귀 부분의 요청에는 CTE가 포함될 수 없습니다.

다행히도 이러한 모든 문제는 해결하기가 매우 쉽습니다. 끝부터 시작합시다.

재귀 부분의 CTE

여기 그렇게 아니 공장:

WITH RECURSIVE tree AS (
  ...
UNION ALL
  WITH T (...)
  SELECT ...
)

그래서 작동합니다. 괄호가 차이를 만듭니다!

WITH RECURSIVE tree AS (
  ...
UNION ALL
  (
    WITH T (...)
    SELECT ...
  )
)

재귀적 "테이블"에 대한 중첩 쿼리

흠... 재귀 CTE는 하위 쿼리에서 액세스할 수 없습니다. 하지만 CTE 내부에 있을 수도 있습니다! 그리고 중첩된 요청은 이미 이 CTE에 액세스할 수 있습니다!

GROUP BY 내부 재귀

불쾌하지만... 다음을 사용하여 GROUP BY를 에뮬레이트하는 간단한 방법이 있습니다. DISTINCT ON 그리고 창 기능!

SELECT
  (rec).pid id
, string_agg(chld::text, ',') chld
FROM
  tree
WHERE
  (rec).pid IS NOT NULL
GROUP BY 1 -- не работает!

그리고 이것이 작동하는 방식입니다!

SELECT DISTINCT ON((rec).pid)
  (rec).pid id
, string_agg(chld::text, ',') OVER(PARTITION BY (rec).pid) chld
FROM
  tree
WHERE
  (rec).pid IS NOT NULL

이제 숫자 ID가 텍스트로 변환된 이유를 살펴보겠습니다. 이를 통해 쉼표로 구분하여 서로 결합할 수 있습니다.

3 단계

결승전에는 아무것도 남지 않았습니다.

• 그룹화된 ID 세트를 기반으로 "섹션" 레코드를 읽습니다.
• 뺀 부분을 원본 시트의 "세트"와 비교합니다.
• 다음을 사용하여 설정 문자열을 "확장"합니다. unnest(string_to_array(chld, ',')::integer[])

WITH RECURSIVE tree AS (
  SELECT
    rec
  , id::text chld
  FROM
    hier rec
  WHERE
    id = ANY('{1,2,4,8,16,32,64,128,256,512,1024,2048,4096,8192}'::integer[])
UNION ALL
  (
    WITH prnt AS (
      SELECT DISTINCT ON((rec).pid)
        (rec).pid id
      , string_agg(chld::text, ',') OVER(PARTITION BY (rec).pid) chld
      FROM
        tree
      WHERE
        (rec).pid IS NOT NULL
    )
    , nodes AS (
      SELECT
        rec
      FROM
        hier rec
      WHERE
        id = ANY(ARRAY(
          SELECT
            id
          FROM
            prnt
        ))
    )
    SELECT
      nodes.rec
    , prnt.chld
    FROM
      prnt
    JOIN
      nodes
        ON (nodes.rec).id = prnt.id
  )
)
SELECT
  unnest(string_to_array(chld, ',')::integer[]) leaf
, (rec).*
FROM
  tree;

[explain.tensor.ru 참조]

출처 : habr.com