[PostgreSQL] 재귀 CTE를 대체하는 계층 데이터 3가지 접근 — ltree vs connectby vs WITH RECURSIVE

설치·접속: PostgreSQL 설치와 접속

부제: 카테고리 트리에서 "이 노드 아래 전부"를 뽑아야 하는데, 매번 재귀 CTE를 짜기가 지겨울 때

같은 카테고리 트리를 세 가지 방식으로 저장·조회해 보고, 조회 편의와 성능이 어떻게 갈리는지 비교한다. 트리는 이렇게 생겼다.

Top
├─ Electronics
│  ├─ Computers
│  │  ├─ Laptops
│  │  └─ Desktops
│  └─ Phones
└─ Books
   ├─ Fiction
   └─ Tech

한 테이블에 adjacency-list용 parent_id와 ltree용 path를 같이 담아, 세 방식을 나란히 돌린다.

CREATE EXTENSION IF NOT EXISTS ltree;
CREATE EXTENSION IF NOT EXISTS tablefunc;

CREATE TABLE cat (
    id        int PRIMARY KEY,
    parent_id int REFERENCES cat(id),
    name      text NOT NULL,
    path      ltree
);
INSERT INTO cat(id, parent_id, name, path) VALUES
 (1, NULL, 'Top',        'Top'),
 (2, 1,    'Electronics','Top.Electronics'),
 (3, 2,    'Computers',  'Top.Electronics.Computers'),
 (4, 3,    'Laptops',    'Top.Electronics.Computers.Laptops'),
 (5, 3,    'Desktops',   'Top.Electronics.Computers.Desktops'),
 (6, 2,    'Phones',     'Top.Electronics.Phones'),
 (7, 1,    'Books',      'Top.Books'),
 (8, 7,    'Fiction',    'Top.Books.Fiction'),
 (9, 7,    'Tech',       'Top.Books.Tech');
CREATE INDEX cat_path_gist ON cat USING GIST (path);

접근 A — parent_id + WITH RECURSIVE

가장 표준적인 방법. parent_id만 있으면 되고, 확장도 필요 없다. 앵커(시작 노드)에서 출발해 자식을 계속 붙여 나간다.

WITH RECURSIVE tree AS (
    SELECT id, parent_id, name, 0 AS depth
      FROM cat WHERE name = 'Electronics'
  UNION ALL
    SELECT c.id, c.parent_id, c.name, t.depth + 1
      FROM cat c JOIN tree t ON c.parent_id = t.id
)
SELECT depth, repeat('  ', depth) || name AS node FROM tree ORDER BY depth, id;

 depth |     node     
-------+--------------
     0 | Electronics
     1 |   Computers
     1 |   Phones
     2 |     Laptops
     2 |     Desktops
(5 rows)

깊이(depth)는 재귀 항에서 직접 +1 해가며 계산한다. 어디서나 되고 유연하지만, 하위 트리를 뽑을 때마다 이 8줄짜리 CTE를 매번 손으로 써야 한다. 그리고 parent_id 조인을 노드 깊이만큼 반복하므로, 깊고 큰 트리에서는 조인 비용이 누적된다.

접근 B — tablefunc connectby

connectby는 adjacency-list를 루트부터 순회하며 level과 branch(경로 문자열)를 자동으로 붙여준다. 재귀 CTE의 뼈대를 함수 호출 한 줄로 대체한다.

SELECT level, keyid, branch
  FROM connectby('cat', 'id', 'parent_id', '2', 0, '.')
       AS t(keyid int, parent_keyid int, level int, branch text)
  ORDER BY branch;

 level | keyid | branch 
-------+-------+--------
     0 |     2 | 2
     1 |     3 | 2.3
     2 |     4 | 2.3.4
     2 |     5 | 2.3.5
     1 |     6 | 2.6
(5 rows)

connectby(테이블, keyid컬럼, parent_keyid컬럼, 시작키, 최대깊이, 구분자) 형태다. branch가 루트부터의 키 경로(2.3.4)를 문자열로 만들어 주는 게 재귀 CTE 대비 공짜로 얻는 이득이다. 이름을 붙이려면 결과를 원본 테이블에 다시 조인한다.

SELECT t.level, repeat('  ', t.level) || c.name AS node, t.branch
  FROM connectby('cat', 'id', 'parent_id', '2', 0, '.')
       AS t(keyid int, parent_keyid int, level int, branch text)
  JOIN cat c ON c.id = t.keyid
  ORDER BY t.branch;

 level |     node     | branch 
-------+--------------+--------
     0 | Electronics  | 2
     1 |   Computers  | 2.3
     2 |     Laptops  | 2.3.4
     2 |     Desktops | 2.3.5
     1 |   Phones     | 2.6
(5 rows)

컬럼 정의 리스트(AS t(...))를 반드시 붙여야 하고, keyid/parent_keyid 타입을 실제 컬럼과 맞춰야 한다. 순회 자체는 여전히 매 조회마다 트리를 훑는다.

접근 C — ltree 경로 타입 + GiST + lquery

경로를 값 자체로 저장한다. Top.Electronics.Computers.Laptops 같은 레이블 경로가 한 컬럼에 들어가고, 조상/자손 판정은 @>(조상)·<@(자손) 연산자 한 방이다. 재귀도 조인도 없다.

-- Electronics 아래 전부
SELECT id, name, path FROM cat WHERE path <@ 'Top.Electronics' ORDER BY path;

 id |    name     |                path                
----+-------------+------------------------------------
  2 | Electronics | Top.Electronics
  3 | Computers   | Top.Electronics.Computers
  5 | Desktops    | Top.Electronics.Computers.Desktops
  4 | Laptops     | Top.Electronics.Computers.Laptops
  6 | Phones      | Top.Electronics.Phones
(5 rows)

lquery로 "어느 깊이든 Computers 노드와 그 아래"처럼 레벨 인식 패턴도 표현한다. LIKE로는 못 하는 지점이다.

SELECT name, path FROM cat WHERE path ~ '*.Computers.*' ORDER BY path;

   name    |                path                
-----------+------------------------------------
 Computers | Top.Electronics.Computers
 Desktops  | Top.Electronics.Computers.Desktops
 Laptops   | Top.Electronics.Computers.Laptops
(3 rows)

깊이는 nlevel(path)로, "직계 자식만"은 깊이 조건으로 뽑는다. 조상 경로(breadcrumb)는 @>를 뒤집어 쓰면 된다.

-- Electronics의 직계 자식만
SELECT name, nlevel(path) AS depth FROM cat
 WHERE path <@ 'Top.Electronics' AND nlevel(path) = nlevel('Top.Electronics') + 1
 ORDER BY path;

   name    | depth 
-----------+-------
 Computers |     3
 Phones    |     3
(2 rows)

성능: GiST 인덱스가 갈림길이다

9행짜리 장난감 트리에서는 셋 다 순식간이라 차이가 안 보인다. 그래서 10만 행 트리로 path <@ ... 하위 트리 조회를 GiST 인덱스가 있을 때와 없을 때로 비교했다.

EXPLAIN (ANALYZE, COSTS OFF, SUMMARY OFF)
SELECT count(*) FROM cat_big WHERE path <@ 'Top.Electronics.C5';

-- GiST 인덱스 사용
 Aggregate (actual time=0.210..0.211 rows=1 loops=1)
   ->  Bitmap Heap Scan on cat_big (actual rows=1000 loops=1)
         Recheck Cond: (path <@ 'Top.Electronics.C5'::ltree)
         Heap Blocks: exact=13
         ->  Bitmap Index Scan on cat_big_gist (actual rows=1000 loops=1)
               Index Cond: (path <@ 'Top.Electronics.C5'::ltree)

-- 인덱스 없이 (seqscan)
 Aggregate (actual time=5.716..5.717 rows=1 loops=1)
   ->  Seq Scan on cat_big (actual rows=1000 loops=1)
         Filter: (path <@ 'Top.Electronics.C5'::ltree)
         Rows Removed by Filter: 99000

같은 1000행을 뽑는데 GiST는 13개 힙 블록만 만지고 0.21ms, seq scan은 9만 9천 행을 걸러내며 5.72ms. 하위 트리 조회가 잦은 읽기 위주 트리라면 ltree가 압도적이다.

결론: 언제 무엇을 쓰나

• WITH RECURSIVE: 확장이 없거나 트리가 자주 바뀌는 곳. 이미 parent_id 스키마가 있고 조회 빈도가 낮으면 그대로 둔다. 가장 이식성이 높다.
• connectby: parent_id 스키마를 유지한 채 level·branch 경로 문자열이 공짜로 필요할 때. 재귀 CTE를 함수 호출로 줄이는 중간 선택지.
• ltree: 하위 트리·조상 조회가 읽기 위주로 빈번하고, GiST 인덱스로 밀어붙일 때. 대신 노드를 옮기면 그 아래 모든 path를 갱신해야 하므로 이동이 잦은 트리에는 쓰기 비용이 붙는다.

정리하면, 쓰기가 잦으면 parent_id 계열, 읽기가 잦고 하위/조상 조회가 핵심이면 ltree. connectby는 스키마를 안 바꾸고 재귀 CTE의 손맛만 덜고 싶을 때다.

이렇게도 쓴다

adjacency-list와 ltree path를 서로 변환한다. connectby의 branch나 재귀 CTE로 경로를 만들어 ltree 컬럼을 채운다. (조합: connectby → ltree 마이그레이션)

UPDATE cat SET path = t.branch::ltree
  FROM connectby('cat','id','parent_id','1',0,'.')
       AS t(keyid int, parent_keyid int, level int, branch text)
 WHERE cat.id = t.keyid;  -- 키 경로를 ltree로 저장(레이블 경로로 바꾸려면 name으로)

 

재귀 CTE로 조상 경로(breadcrumb)를 문자열로 뽑는다. ltree 없이도 경로가 필요할 때. (조합: WITH RECURSIVE + string_agg)

WITH RECURSIVE up AS (
    SELECT id, parent_id, name FROM cat WHERE id = 4
  UNION ALL
    SELECT c.id, c.parent_id, c.name FROM cat c JOIN up ON c.id = up.parent_id
)
SELECT string_agg(name, ' > ' ORDER BY id) AS breadcrumb FROM up;

 

ltree @>로 조상 목록(breadcrumb)을 한 방에 뽑는다. 재귀 없이.

SELECT name, path FROM cat
 WHERE path @> 'Top.Electronics.Computers.Laptops' ORDER BY path;

 

connectby에 최대 깊이를 걸어 N단계까지만 순회한다.

SELECT * FROM connectby('cat','id','parent_id','1', 2, '.')  -- 루트에서 2단계까지
  AS t(keyid int, parent_keyid int, level int, branch text);

 

WITH RECURSIVE에 방문 배열을 얹어 순환을 방어한다. 데이터가 오염돼 사이클이 생겨도 무한루프를 막는다. (조합: CYCLE 대용 배열)

WITH RECURSIVE tree AS (
    SELECT id, parent_id, ARRAY[id] AS visited FROM cat WHERE id = 2
  UNION ALL
    SELECT c.id, c.parent_id, t.visited || c.id
      FROM cat c JOIN tree t ON c.parent_id = t.id
     WHERE c.id <> ALL(t.visited)
)
SELECT * FROM tree;