대댓글 기능 데이터 모델링 #2 (Path Enumeration)

Path Enumeration

Tree data structure illustration

Adjacency Lists(대댓글 기능 데이터 모델링 #1 (Adjacency List) 참고)는 트리에서 주어진 노드의 여러 계층의 부모/자식 노드를 한 번에 검색하는데 비용이 많이 든다. Path Enumeration은 이러한 문제를 문자열을 이용해 각 노드의 속성으로 저장함으로써 해결할 수 있다.

CREATE TABLE Comments (
  comment_id SERIAL PRIMARY KEY,
  path VARCHAR(1000),
  post_id BIGINT UNSIGNED NOT NULL,
  author BIGINT UNSIGNED NOT NULL,
  comment_date DATETIME NOT NULL,
  comment TEXT NOT NULL,
  FOREIGN KEY (post_id) REFERENCES Posts(post_id),
  FOREIGN KEY (author) REFERENCES Accounts(account_id)
);

 

Path Enumeration 방법은 Comments 테이블에서 parent_id 컬럼 대신 VARCHAR 타입의

path라는 칼럼을 정의한다. 이 칼럼에 저장된 문자열은 UNIX path처럼 트리의 root부터 현재 노드의 comment_id를 순서대로 나타낸다.

 

그럼 댓글의 부모 댓글들을 찾아보는 쿼리를 작성해 보자.

현재 노드의 경로를 다른 노드의 경로와 비교하는 방식으로 부모 노드들을 조회할 수 있다. 예를 들어 7번 댓글의 부모 댓글들을 찾기 위해 다음 쿼리를 사용할 수 있다.

SELECT comment_id, path, author, comment
  FROM Comments AS c
 WHERE '1/4/6/7/' LIKE c.path || '%' AND c.path <> '1/4/6/7/';

 

조회 결과는 1/4/6/%, 1/4/%, 1/%의 부모 노드 경로 패턴과 일치한다.

 comment_id |  path  | author |              comment
------------+--------+--------+-----------------------------------
          1 | 1/     | J.H    | What's the cause of this bug?
          4 | 1/4/   | Rula   | We need to check for valid input.
          6 | 1/4/6/ | J.H    | Let's add a check.

 

Path Enumeration은 트리의 서브 트리를 조회하거나 서브 트리에서 노드 수를 단순하게 조회하는 쿼리들을 쉽게 수행할 수 있다. 예를 들어 4번 댓글에서 시작하는 서브트리에서 작성자별 댓글 수를 구하려면 다음과 같은 쿼리를 사용할 수 있다.

SELECT c.author, COUNT(*)
  FROM Comments AS c
 WHERE c.path LIKE '1/4/' || '%'
 GROUP BY c.author;

 author | count
--------+-------
 J.H    |     1
 Oula   |     1
 Rula   |     2

 

Path Enumeration에서의 노드 삽입 과정은 Adjacency Lists 모델에서의 삽입과 비슷하다. 다른 레코드들을 수정할 필요 없이 non-leaf 노드를 삽입할 수 있다.

 

새로 추가할 노드의 부모 path를 복사하고, 이 문자열에 새 노드 ID (comment_id)를 추가한다. comment_id가 자동으로 생성되는 경우에는 추가된 comment_id 값을 알고 난 뒤에 path를 업데이트해야 할 수도 있다. MySQL의 경우 내장 함수 LAST_INSERT_ID()는 현재 세션에서 삽입된 행에 대해 가장 최근 id 값을 반환한다. (PostgreSQL에서는 CURRVAL('comments_comment_id_seq')를 이용할 수 있다.)

INSERT INTO Comments (author, comment) VALUES ('Ollie', 'Good job!');

UPDATE Comments
   SET path = CONCAT((SELECT path FROM Comments WHERE comment_id = 7), 
       LAST_INSERT_ID(), '/')
 WHERE comment_id = LAST_INSERT_ID();

SELECT * FROM Comments;

 comment_id | author  |    path    |              comment
------------+---------+------------+-----------------------------------
          1 | J.H     | 1/         | What's the cause of this bug?
          2 | hotamul | 1/2/       | I think it's a null point.
          3 | J.H     | 1/2/3/     | No... That's not
          4 | Rula    | 1/4/       | We need to check for valid input.
          5 | Oula    | 1/4/5/     | Yeah...
          6 | J.H     | 1/4/6/     | Let's add a check.
          7 | Rula    | 1/4/6/7/   | That fixed it.
          8 | Oula    | 1/4/6/7/8/ | Good job!

 

Path Enumeration oddity

Path Enumeration은 몇 가지 단점이 있다. (Database 디자인에서 다대다 관계를 위해 Insertsection Table 생성을 대신해서 때때로 콤마(,)로 구분된 칼럼을 사용하는 경우가 있다. 이러한 패턴을 SQL Antipattern 중 하나인 Jaywalking이라고 한다. Jaywalking에 대한 내용은 다음에 다뤄볼 예정이다.)

 

RDBMS에서는 path가 올바르게 형성되었는지 또는 path 값이 기존 노드에 해당하는지에 대한 validation 체크를 할 수 없다. path의 문자열 유지는 애플리케이션 코드에 의존하며, 이를 관리하기 위해서는 많은 비용이 들 수 있다.

 

그리고 VARCHAR 타입의 컬럼을 길게 만들더라도 길이 제한이 있어, 제한 없는 깊이의 트리를 생성할 수 없다.

 

그럼에도 Path Enumeration은 구분자 사이의 값들이 일관된 길이를 가지고 트리의 깊이가 어느 정도 예상할 수 있다면, 쉽게 저장된 댓글들을 쉽게 관리할 수 있는 방법이다.