하위 트리 이동

클로저의 읽기가 빠른 대가는, 이동 한 번이 여러 경로를 바꾼다는 점입니다. Spring 하위 트리를 프론트엔드 아래로 옮기면, Spring뿐 아니라 그 자손인 데이터베이스가 바깥 조상과 이어진 경로도 모두 다시 계산해야 합니다.

인접 리스트와 클로저를 따로 커밋하면 어느 한쪽만 새 구조가 되어, 쿼리마다 다른 트리를 보여 줍니다. 그래서 이동은 순환 검사부터 두 모델의 갱신까지 하나의 트랜잭션이어야 합니다. 이 글은 14장 3편의 완전한 클로저(18행)와 처음 트리, 곧 Spring 5와 데이터베이스 7이 백엔드 2 아래에 있는 상태에서 계속 cs_db_lab으로 시작합니다.

일부 경로만 바꾼 이동

먼저 parent_id만 프론트엔드 3으로 바꾸고, 클로저가 여전히 백엔드 2를 바깥 조상으로 돌려주는 불일치를 만듭니다. 직속 부모의 조회는 새 부모를 보여 주지만, 클로저의 조상 조회는 이전 경로를 돌려줍니다.

UPDATE categories
SET parent_id = 3
WHERE category_id = 5;

SELECT parent_id
FROM categories
WHERE category_id = 5;

SELECT ancestor.category_id,
       ancestor.category_name,
       path.depth
FROM category_closure AS path
JOIN categories AS ancestor
  ON ancestor.category_id = path.ancestor_id
WHERE path.descendant_id = 7
ORDER BY path.depth;

parent_id
3

category_id | category_name | depth
7           | 데이터베이스  | 0
5           | Spring        | 1
2           | 백엔드        | 2
1           | 개발          | 3

인접 리스트의 부모는 3인데, 데이터베이스의 클로저에는 백엔드 2가 조상으로 남아 있고 프론트엔드 3은 없습니다. 14장 3편의 깊이 1 양방향 감사를 다시 실행하면 다음 두 행이 나옵니다.

mismatch       | ancestor_id | descendant_id
ADJACENCY_ONLY | 3           | 5
CLOSURE_ONLY   | 2           | 5

두 모델이 갈라졌지만 SQL 오류도 외래 키 위반도 없었습니다. 이 두 행은 깊이 1의 차이만 보여 준 것이며, 실제로 어긋난 간접 경로는 더 많습니다.

이동해도 하위 트리 안의 경로는 그대로입니다. 바뀌는 것은 이전 바깥 조상에서 하위 트리의 자손으로 가는 경로와, 새 부모의 모든 조상에서 하위 트리의 자손으로 가는 경로입니다. 새 부모가 하위 트리 안에 있으면 순환이므로 클로저에 (node, new_parent)가 있는지 한 번 조회해 거부할 수 있으며, 클로저가 이미 어긋난 상태라면 이동보다 재생성을 먼저 합니다.

내부 경로와 외부 경로의 구분

이전 조상 집합의 크기는, 클로저에서 자손이 그 노드인 행 가운데 노드 자신을 뺀 행의 수입니다. 하위 트리 집합의 크기는 조상이 그 노드인 모든 행의 수이고, 두 크기를 곱하면 지울 경로의 수가 됩니다.

새 경로의 깊이는 새 부모까지의 조상 깊이에, 부모에서 노드까지의 간선 하나와 노드 아래의 하위 트리 깊이를 더한 값입니다. 이 모든 쓰기는 인접 리스트의 UPDATE와 같은 트랜잭션에서 합니다.

정리하면 이동은 네 단계입니다. 이전 조상과 새 조상, 하위 트리의 자손 집합을 클로저로 구하고, 이전 조상과 하위 트리의 곱으로 만들어지는 경로만 지웁니다. 새 조상의 깊이 + 1 + 하위 트리의 깊이로 새 경로를 넣고, 커밋한 뒤 깊이 1의 차집합과 하위 트리의 행 수를 확인합니다.

안전한 하위 트리 이동

먼저 처음 트리의 부모 관계를 되돌리고 클로저를 다시 만듭니다. 이 복구 구간의 UPDATE와 DELETE, INSERT는 한 트랜잭션이 아니므로, 다른 읽기와 쓰기를 멈춘 유지보수 상태를 전제로 하며, 트리 전체가 백필의 깊이 상한 20 안에 들어와야 합니다.

이동 프로시저는 오류 처리기로 롤백하고, 대상의 존재와 순환을 검사한 뒤 경로와 부모를 함께 바꿉니다. 프로시저가 자체의 START TRANSACTION과 COMMIT을 가지므로, 호출하는 쪽은 열린 트랜잭션 밖에서 호출해야 합니다. MySQL의 START TRANSACTION은 열려 있던 트랜잭션을 암묵적으로 커밋할 뿐 중첩 트랜잭션을 만들지 않습니다.

UPDATE categories
SET parent_id = 2
WHERE category_id = 5;

DELETE FROM category_closure;

INSERT INTO category_closure
  (ancestor_id, descendant_id, depth)
WITH RECURSIVE paths (ancestor_id, descendant_id, depth) AS (
  SELECT category_id, category_id, 0
  FROM categories
  UNION ALL
  SELECT p.ancestor_id, c.category_id, p.depth + 1
  FROM paths AS p
  JOIN categories AS c
    ON c.parent_id = p.descendant_id
  WHERE p.depth < 20
)
SELECT ancestor_id, descendant_id, depth FROM paths;

DROP PROCEDURE IF EXISTS move_category_subtree;
DELIMITER //
CREATE PROCEDURE move_category_subtree(
  IN p_node_id BIGINT UNSIGNED,
  IN p_new_parent_id BIGINT UNSIGNED
)
procedure_body: BEGIN
  DECLARE v_node_count INT DEFAULT 0;
  DECLARE v_parent_count INT DEFAULT 0;
  DECLARE v_cycle_count INT DEFAULT 0;
  DECLARE EXIT HANDLER FOR SQLEXCEPTION
  BEGIN
    ROLLBACK;
    RESIGNAL;
  END;

  START TRANSACTION;

  SELECT COUNT(*) INTO v_node_count
  FROM categories
  WHERE category_id = p_node_id
  FOR UPDATE;

  IF v_node_count = 0 THEN
    SIGNAL SQLSTATE '45000' SET MESSAGE_TEXT = 'node not found';
  END IF;

  IF p_new_parent_id IS NOT NULL THEN
    SELECT COUNT(*) INTO v_parent_count
    FROM categories
    WHERE category_id = p_new_parent_id
    FOR UPDATE;

    IF v_parent_count = 0 THEN
      SIGNAL SQLSTATE '45000' SET MESSAGE_TEXT = 'new parent not found';
    END IF;

    SELECT COUNT(*) INTO v_cycle_count
    FROM category_closure
    WHERE ancestor_id = p_node_id
      AND descendant_id = p_new_parent_id;

    IF v_cycle_count > 0 THEN
      SIGNAL SQLSTATE '45000' SET MESSAGE_TEXT = 'cycle-producing move';
    END IF;
  END IF;

  DELETE path
  FROM category_closure AS path
  JOIN category_closure AS old_ancestor
    ON old_ancestor.ancestor_id = path.ancestor_id
   AND old_ancestor.descendant_id = p_node_id
   AND old_ancestor.ancestor_id <> p_node_id
  JOIN category_closure AS subtree
    ON subtree.ancestor_id = p_node_id
   AND subtree.descendant_id = path.descendant_id;

  IF p_new_parent_id IS NOT NULL THEN
    INSERT INTO category_closure
      (ancestor_id, descendant_id, depth)
    SELECT new_ancestor.ancestor_id,
           subtree.descendant_id,
           new_ancestor.depth + 1 + subtree.depth
    FROM category_closure AS new_ancestor
    JOIN category_closure AS subtree
      ON subtree.ancestor_id = p_node_id
    WHERE new_ancestor.descendant_id = p_new_parent_id;
  END IF;

  UPDATE categories
  SET parent_id = p_new_parent_id
  WHERE category_id = p_node_id;

  COMMIT;
END//
DELIMITER ;

CALL move_category_subtree(1, 7);
CALL move_category_subtree(5, 3);

ERROR 1644 (45000): cycle-producing move

첫 CALL은 루트 개발을 자손 데이터베이스 아래로 옮기려 했으므로, 클로저에 (1, 7)이 있어 순환으로 거부됩니다. 오류 처리기가 ROLLBACK한 뒤 RESIGNAL로 같은 오류를 호출자에게 다시 던지므로, 아무것도 바뀌지 않습니다.

둘째 CALL에서 지우는 경로는 이전 조상 {1, 2}와 하위 트리 {5, 7}의 곱인 (1, 5, 2), (1, 7, 3), (2, 5, 1), (2, 7, 2)의 네 행입니다. 넣는 경로는 새 부모 3의 조상인 자신 3과 개발 1에 하위 트리를 곱한 (3, 5, 1), (3, 7, 2), (1, 5, 2), (1, 7, 3)의 네 행입니다. 예를 들어 개발에서 데이터베이스까지의 새 깊이는 개발에서 3까지의 1, 3에서 Spring까지의 1, Spring에서 데이터베이스까지의 1을 더한 3입니다.

공통 조상 1의 두 경로는 최종 결과가 같지만, 이 일반적인 SQL은 이전 바깥 경로를 먼저 지우고 다시 넣으므로 쓰기 행의 수에는 들어갑니다. 내부 경로 (5, 5, 0), (5, 7, 1), (7, 7, 0)은 그대로이고, 클로저는 18 - 4 + 4 = 18행입니다.

하위 트리가 크고 깊으면 지우고 넣는 행이 많아져 잠금과 리두 로그가 늘어납니다. 그래서 옮기기 전에 영향받는 경로의 수를 계산하고, 트랜잭션의 예산을 넘으면 유지보수 시간대나 비동기 재생성을 씁니다. 애플리케이션에 프로시저의 실행 권한만 주어도 DBA의 직접 UPDATE는 여전히 가능하므로, 정기적인 불일치 검사와 재생성 절차가 우회와 과거의 버그, 복구 실수까지 다룹니다.

더 깊이: 같은 테이블을 읽으면서 지우는 DELETE

위 프로시저의 DELETE는 category_closure를 세 별칭으로 조인해 지울 행을 고르는 여러 테이블 DELETE(multiple-table DELETE)입니다. 이 문법에서는 FROM 앞에 적은 별칭 path의 테이블에서 조인 조건에 맞은 행만 지워집니다. 별칭을 선언했다면 지울 대상도 별칭으로 적어야 하고, 별칭의 선언은 테이블 참조 부분에서만 할 수 있습니다. 또 여러 테이블 DELETE에는 ORDER BY와 LIMIT을 쓸 수 없으므로, 큰 하위 트리의 경로를 나누어 지우려면 조건의 범위로 나누어야 합니다.

같은 조건을 서브쿼리로 쓰면 이야기가 달라집니다. MySQL은 한 테이블을 수정하면서 같은 테이블을 서브쿼리에서 읽는 것을 일반적으로 허용하지 않으므로, DELETE FROM category_closure WHERE ... (SELECT ... FROM category_closure ...) 꼴의 문장은 거부됩니다. 예외는 같은 테이블을 파생 테이블로 감싸고 그 파생 테이블이 바깥 쿼리에 합쳐지지 않고 임시 테이블로 구체화되는 경우인데, 옵티마이저가 합치기로 하면 이 예외가 성립하지 않으므로 NO_MERGE 힌트로 구체화를 유도해야 합니다. 조인으로 쓴 이 글의 DELETE는 이런 우회 없이 같은 테이블을 읽으며 지웁니다.

여러 테이블을 한꺼번에 지울 때의 주의점도 있습니다. MySQL 8.4 매뉴얼에 따르면 외래 키로 이어진 InnoDB 테이블들을 여러 테이블 DELETE로 함께 지우면, 옵티마이저가 부모와 자식의 관계와 다른 순서로 처리해 문장이 실패하고 롤백될 수 있습니다. 매뉴얼은 이럴 때 한 테이블에서만 지우고 InnoDB의 ON DELETE 동작에 맡기라고 권하며, 이 글의 DELETE는 클로저 테이블 하나에서만 지우므로 여기에 해당하지 않습니다.

이동 전후의 경로 검증

데이터베이스의 조상과 Spring의 자손, 깊이 1의 불일치를 함께 확인합니다. 내부의 자기 경로와 Spring에서 데이터베이스로 가는 경로는 이동 뒤에도 같아야 합니다.

SELECT a.category_name AS ancestor_name,
       p.depth
FROM category_closure AS p
JOIN categories AS a
  ON a.category_id = p.ancestor_id
WHERE p.descendant_id = 7
ORDER BY p.depth;

SELECT d.category_name AS descendant_name,
       p.depth
FROM category_closure AS p
JOIN categories AS d
  ON d.category_id = p.descendant_id
WHERE p.ancestor_id = 5
ORDER BY p.depth;

SELECT c.category_id
FROM categories AS c
LEFT JOIN category_closure AS p
  ON p.ancestor_id = c.parent_id
 AND p.descendant_id = c.category_id
 AND p.depth = 1
WHERE c.parent_id IS NOT NULL
  AND p.ancestor_id IS NULL;

SELECT p.ancestor_id, p.descendant_id
FROM category_closure AS p
LEFT JOIN categories AS c
  ON c.parent_id = p.ancestor_id
 AND c.category_id = p.descendant_id
WHERE p.depth = 1
  AND c.category_id IS NULL;

ancestor_name | depth
데이터베이스  | 0
Spring        | 1
프론트엔드    | 2
개발          | 3

descendant_name | depth
Spring          | 0
데이터베이스    | 1

데이터베이스의 조상은 이제 7, 5, 3, 1이고, Spring의 하위 트리는 자신과 데이터베이스의 두 행 그대로입니다. 깊이 1의 두 불일치 쿼리는 빈 결과이므로 인접 리스트와 클로저의 직속 간선이 다시 일치합니다. 다만 깊이 1이 일치한다고 자기 경로와 모든 간접 경로, 깊이까지 옳다는 증명은 아니므로, 필요하면 14장 3편의 전체 집합 대조를 함께 실행합니다.

쓰기의 증폭과 삭제

노드를 새 루트로 옮기면 이전 바깥 경로만 지우고 새 경로의 삽입은 건너뜁니다. 노드의 자기 경로와 하위 트리 안의 경로는 남으므로, 그 노드가 독립된 트리의 루트로 동작합니다(연습 문제 1).

하위 트리를 물리적으로 지울 때는, 가장 깊은 노드부터 인접 리스트를 지우기 전에 외래 키 CASCADE와 클로저 경로의 삭제 순서를 먼저 검토합니다. 보통은 보관하거나 RESTRICT로 막은 뒤 명시적인 하위 트리 명령을 씁니다.

이동마다 하위 트리의 노드 수와 지운 경로, 넣은 경로의 수, 잠금 시간, 롤백의 수를 기록합니다. 깊이 1의 불일치가 0인지, 자기 경로의 수가 노드의 수와 같은지, 클로저의 최대 깊이가 얼마인지는 배치의 건전성 검사로 유지합니다.

예외도 정해 둡니다. 새 부모가 지금의 부모와 같으면 변경 없이 끝낼지 버전을 남길지 정하고, 서로 다른 테넌트의 트리 사이의 이동은 프로시저의 첫 단계에서 막습니다. 겹치는 하위 트리의 동시 이동은 이 예제의 범위 밖이며, 잠금 순서를 통일하는 것은 교착 상태를 줄일 뿐이므로 검사하는 경로 전체의 경쟁을 배제하는 직렬화 정책이 더 필요합니다. DAG의 클로저에서는 바깥 경로의 삭제가 단일 부모의 트리보다 복잡하고, 경로가 겹친 수를 보존해야 합니다.

클로저의 빠른 읽기는 완전한 쓰기 명령이 있을 때만 안전합니다. 경로의 일부만 고치는 SQL을 여러 호출자가 복사해 쓰게 두지 않습니다.

정리

• 하위 트리의 이동은 바깥 조상과 이어진 경로만 바꾸고, 내부 경로는 그대로 둡니다.
• 순환은 클로저의 조상 조회 한 번으로 판단할 수 있습니다.
• 인접 리스트의 변경과 경로의 삭제, 삽입은 한 트랜잭션입니다.
• 지울 경로의 수는 이전 조상 수와 하위 트리 크기의 곱이므로, 실행 전에 계산합니다.

연습 문제

1. 새 루트로 떼어 내기

처음 트리와 완전한 클로저(18행)로 되돌린 뒤, CALL move_category_subtree(5, NULL);로 Spring을 새 루트로 옮겼고 다른 작성자는 없었다고 합시다. 지우는 행과 넣는 행은 각각 몇 개이고, 클로저는 모두 몇 행이 되나요? 루트는 무엇이고, 내부 경로 (5, 7, 1)은 남아야 하나요?

2. 경로까지 만드는 노드 추가

새 분류를 부모 아래에 더하면서, 자기 경로와 모든 조상과의 경로를 함께 만드는 프로시저를 작성해 보세요. 부모가 NULL인 새 루트도 지원해야 합니다.

DROP PROCEDURE IF EXISTS add_category_closure;
DELIMITER //
CREATE PROCEDURE add_category_closure(
  IN p_category_id BIGINT UNSIGNED,
  IN p_category_name VARCHAR(100),
  IN p_parent_id BIGINT UNSIGNED,
  IN p_sort_order SMALLINT UNSIGNED
)
procedure_body: BEGIN
  DECLARE EXIT HANDLER FOR SQLEXCEPTION
  BEGIN
    ROLLBACK;
    RESIGNAL;
  END;

  START TRANSACTION;

  IF p_parent_id IS NOT NULL AND NOT EXISTS (
    SELECT 1
    FROM categories
    WHERE category_id = p_parent_id
  ) THEN
    SIGNAL SQLSTATE '45000' SET MESSAGE_TEXT = 'parent not found';
  END IF;

  INSERT INTO categories
    (category_id, category_name, parent_id, sort_order)
  VALUES
    (p_category_id, p_category_name, p_parent_id, p_sort_order);

  INSERT INTO category_closure
    (ancestor_id, descendant_id, depth)
  VALUES (p_category_id, p_category_id, 0);

  IF p_parent_id IS NOT NULL THEN
    INSERT INTO category_closure
      (ancestor_id, descendant_id, depth)
    SELECT ancestor_id, p_category_id, depth + 1
    FROM category_closure
    WHERE descendant_id = p_parent_id;
  END IF;

  COMMIT;
END//
DELIMITER ;

CALL add_category_closure(8, '라우팅', 3, 30);
CALL add_category_closure(9, '없는 부모', 999, 10);

ERROR 1644 (45000): parent not found

다음 장은 다시 board_lab에서 진행하므로, 실습을 마쳤다면 USE board_lab;으로 돌아갑니다. 다음 글 변경 이력 모델에서는 구조의 이동뿐 아니라 게시글의 값이 누가, 왜, 언제 바뀌었는지를 현재 행과 이력 행의 시간 축으로 보존합니다.