계층 데이터 모델링

답글에 답글이 달립니다

표는 평평합니다. 행이 있고 열이 있을 뿐 위아래가 없습니다. 그런데 게시판의 글에는 위아래가 있습니다. 답글에 답글이 달리고, 그 답글에 또 답글이 달립니다.

이 구조를 표에 담는 방법은 하나가 아닙니다. 그리고 어느 것을 선택하느냐에 따라 조회와 삽입 가운데 어느 쪽이 비싸지는지가 갈립니다. 실습 데이터베이스가 어떤 선택을 했는지부터 봅니다.

SELECT num, parent_num, group_num, depth, sort_no, LEFT(title, 24) AS 제목
FROM Board.POSTS WHERE group_num = 6 ORDER BY sort_no;

parent_num 하나만 있어도 계층은 표현됩니다. 나머지 셋은 무엇 때문에 있는지가 이 단원의 물음입니다. 네 가지 방식을 차례로 보고 같은 화면을 내면서 읽은 페이지를 세어 봅니다.

인접 목록 — 부모만 가리킵니다

가장 단순합니다. 열 하나에 부모의 번호를 담고, 원글이면 NULL 입니다. 4바이트면 끝이고, 답글을 넣을 때 계산할 것이 없습니다.

문제는 읽을 때 드러납니다. 게시판 목록은 최신 원글부터, 덩어리 안에서는 차례대로 나와야 합니다. parent_num 만으로 그 순서를 내려면 2.5 의 재귀 CTE 로 전부 펼쳐야 합니다.

-- 원글에서 시작해 답글을 따라 내려가면서 정렬용 문자열을 만듭니다.
WITH T AS (
    SELECT num, board_num, title, num AS grp,
           CAST(RIGHT('0000000000' + CAST(num AS varchar(10)), 10) AS varchar(200)) AS ord
    FROM Board.POSTS WHERE parent_num IS NULL AND board_num = 2
    UNION ALL
    SELECT p.num, p.board_num, p.title, T.grp,
           CAST(T.ord + '/' + RIGHT('0000000000' + CAST(p.num AS varchar(10)), 10) AS varchar(200))
    FROM Board.POSTS p JOIN T ON p.parent_num = T.num
)
SELECT TOP (20) num, title FROM T ORDER BY grp DESC, ord;

20건만 필요한데 전부 펼쳐야 합니다. 재귀는 어디까지 내려가야 할지 미리 알 수 없어 중간에 멈출 수 없고, 정렬은 다 펼친 뒤에야 할 수 있습니다. 글이 늘면 이 비용이 그대로 늡니다.

인접 목록이 나쁜 것은 아닙니다. 부모를 따라 올라가거나 자식 한 단계를 찾는 데는 이보다 싼 방법이 없습니다. 실습 데이터베이스도 parent_num 을 그대로 두고 인덱스까지 걸어 두었습니다(IX_POSTS_parent). 목록 화면이 문제일 뿐입니다.

정렬 보조 열 — 실습 데이터베이스의 선택

순서를 조회할 때 계산하지 말고 미리 열에 담아 두자는 것입니다. 덩어리를 묶는 group_num, 덩어리 안의 차례 sort_no, 그리고 화면에 들여쓰기를 그릴 depth 입니다.

SELECT TOP (20) num, title FROM Board.POSTS
WHERE board_num = 2 ORDER BY group_num DESC, sort_no;

2장인 까닭은 3.5 에서 이미 보았습니다. IX_POSTS_list 가 (board_num, group_num DESC, sort_no) 순서로 놓여 있어 앞에서 20개를 끊어 내면 끝입니다. 정렬도 재귀도 없습니다.

인덱스 하나가 화면 하나를 그대로 담고 있는 셈입니다. 실습 스키마가 계층 열 넷을 둔 것은 이 한 장면을 위해서입니다.

조회를 산 값은 삽입으로 치릅니다

미리 담아 둔 순서는 새 답글이 끼어들 때 다시 매겨야 합니다. 덩어리 가운데에 답글이 달리면 그 뒤의 sort_no 를 전부 밀어야 합니다.

실습 데이터의 덩어리는 가장 큰 것이 3행이라 차이가 드러나지 않습니다. 답글 200개짜리 덩어리를 임시 표에 만들어 재 봅니다.

CREATE TABLE Board.T_H (
    num int IDENTITY(1,1) PRIMARY KEY,
    parent_num int NULL, group_num int NOT NULL,
    depth smallint NOT NULL, sort_no int NOT NULL,
    title nvarchar(200) NOT NULL);
GO
-- 원글 하나에 답글 200개를 붙입니다(문장은 줄였습니다).
GO
-- (가) 정렬 열: 맨 앞에 끼우려면 뒤를 모두 밀어야 합니다.
BEGIN TRAN;
UPDATE Board.T_H SET sort_no = sort_no + 1 WHERE group_num = 1 AND sort_no >= 1;
INSERT INTO Board.T_H (parent_num, group_num, depth, sort_no, title)
VALUES (1, 1, 1, 1, N'끼워 넣은 답글');
SELECT database_transaction_log_record_count AS 로그레코드,
       database_transaction_log_bytes_used AS 로그바이트
FROM sys.dm_tran_database_transactions WHERE database_id = DB_ID();
ROLLBACK;

-- (나) 인접 목록: 그냥 넣습니다.

조회에서 1,000배를 얻고 삽입에서 100배를 잃었습니다. 게시판은 읽는 횟수가 쓰는 횟수보다 압도적으로 많으므로 이 거래가 남습니다. 목록은 방문자마다 열리고 답글은 가끔 달립니다.

반대인 자리도 있습니다. 답글이 초당 여러 건 달리고 목록은 관리자만 가끔 보는 표라면 이 거래는 손해입니다. 계층 모델은 자료의 모양이 아니라 화면의 모양을 보고 고릅니다.

경로 열거 — 조상을 문자열로 담습니다

/6/352/456/ 처럼 뿌리에서 자기까지의 번호를 이어 붙여 담습니다. 실습 데이터에 열을 하나 더해 채워 봅니다.

ALTER TABLE Board.POSTS ADD path varchar(200) NULL;
GO
-- 재귀 CTE 로 한 번만 계산해 채웁니다(2.5).
WITH T AS (
    SELECT num, CAST('/' + CAST(num AS varchar(10)) + '/' AS varchar(200)) AS p
    FROM Board.POSTS WHERE parent_num IS NULL
    UNION ALL
    SELECT c.num, CAST(T.p + CAST(c.num AS varchar(10)) + '/' AS varchar(200))
    FROM Board.POSTS c JOIN T ON c.parent_num = T.num
)
UPDATE P SET path = T.p FROM Board.POSTS P JOIN T ON T.num = P.num;
GO
CREATE NONCLUSTERED INDEX IX_POSTS_path ON Board.POSTS (path);
GO
SELECT num, parent_num, depth, path FROM Board.POSTS WHERE group_num = 6 ORDER BY sort_no;

하위 전체를 한 번에 가져오는 데 강합니다. 앞이 같은 문자열을 찾으면 되므로 인덱스 탐색이 됩니다.

-- (가) 인접 목록: 재귀로 내려갑니다.
WITH T AS (
    SELECT num FROM Board.POSTS WHERE num = 6
    UNION ALL
    SELECT p.num FROM Board.POSTS p JOIN T ON p.parent_num = T.num
)
SELECT COUNT(*) FROM T;

-- (나) 경로 열거: 앞이 같은 것을 찾습니다.
SELECT COUNT(*) FROM Board.POSTS WHERE path LIKE '/6/%';

LIKE '/6/%' 는 뒤에만 % 가 있어 인덱스를 사용합니다. '%/456/' 처럼 앞에 붙이면 그러지 못합니다. 조상을 찾는 것이 아니라 후손을 찾는 데 쓰는 구조입니다.

그런데 게시판 목록에는 맞지 않습니다

경로로 정렬해 봅니다.

SELECT TOP (8) num, path FROM Board.POSTS WHERE board_num = 2 ORDER BY path;

SELECT TOP (8) num, group_num, sort_no FROM Board.POSTS
WHERE board_num = 2 ORDER BY group_num DESC, sort_no;

문자열 정렬이므로 /1/ 다음에 /101/ 이 옵니다. 번호순도 아니고 게시판이 원하는 최신순도 아닙니다. 자리를 채워 /0000000001/ 처럼 만들면 번호순은 되지만, 최신 원글부터 내려면 번호를 뒤집어 담아야 합니다. 같은 화면을 내는 데 25장이 들었고 순서도 맞지 않았습니다.

경로 열거의 다른 대가는 옮길 때입니다. 어떤 글을 다른 부모 아래로 옮기면 그 아래 모든 후손의 경로를 다시 써야 합니다. 그리고 길이 제한이 있어 깊이가 깊어지면 넘칩니다.

hierarchyid — SQL Server 가 주는 형식

경로 열거와 생각은 같은데 문자열이 아니라 전용 형식으로 담습니다. 같은 계층을 훨씬 적은 바이트에 넣고, 계층을 다루는 메서드가 딸려 옵니다.

ALTER TABLE Board.POSTS ADD hid hierarchyid NULL;
-- 형제 사이의 순번으로 경로를 만들어 채웁니다(문장은 줄였습니다).
GO
SELECT num, depth, path, hid.ToString() AS hid문자열,
       DATALENGTH(hid) AS hid바이트, DATALENGTH(path) AS path바이트
FROM Board.POSTS WHERE group_num = 6 ORDER BY sort_no;

메서드가 붙어 있어 계층을 다루기 편합니다.

DECLARE @root hierarchyid = (SELECT hid FROM Board.POSTS WHERE num = 6);
SELECT COUNT(*) FROM Board.POSTS WHERE hid.IsDescendantOf(@root) = 1;

SELECT num, hid.GetLevel() AS 수준, hid.GetAncestor(1).ToString() AS 부모경로
FROM Board.POSTS WHERE group_num = 6 ORDER BY sort_no;

다만 SQL Server 전용 형식입니다. 다른 데이터베이스로 옮길 때 그대로 가져갈 수 없고, 응용 프로그램에서 다루려면 그쪽 드라이버가 이 형식을 알아야 합니다. 값을 눈으로 읽기도 어렵습니다 — ToString() 을 붙이지 않으면 이진 값이 나옵니다. 깊고 넓은 계층을 데이터베이스 안에서 주로 다루는 경우에 값어치가 있습니다.

무엇을 사고 무엇을 팔았습니까

507행 · 201행짜리 덩어리 기준. 논리적 읽기와 로그 레코드입니다.

숫자로 드러나지 않는 것도 있습니다.

• 옮기기 — 인접 목록은 부모 번호 하나만 고치면 끝입니다. 정렬 열은 두 덩어리의 차례를 다시 매겨야 하고, 경로 열거와 hierarchyid 는 후손 전체의 값을 다시 씁니다.
• 이식성 — hierarchyid 만 SQL Server 전용입니다. 나머지 셋은 어느 데이터베이스에서나 같은 방식으로 만듭니다.
• 깊이 제한 — 경로 열거는 열 길이가 곧 깊이 제한입니다. 나머지는 제한이 없습니다.

실습 데이터베이스가 정렬 열을 고른 까닭

게시판에서 가장 자주 열리는 화면이 목록이기 때문입니다. 그 화면을 2장에 내려고 나머지를 내주었습니다. 답글이 드물게 달리는 게시판에서는 남는 거래입니다.

그러면서 parent_num 도 함께 들고 있습니다. 정렬 열만으로는 누가 누구의 답글인지 알 수 없기 때문입니다. depth 는 몇 칸 들여쓸지만 알려 줄 뿐, 어느 글에 달린 답글인지는 말해 주지 않습니다. 그래서 넷을 다 두었습니다.

다른 자료라면 다른 답이 나옵니다. 조직도는 사람이 옮겨 다니고 "이 아래 전부" 를 자주 묻습니다 — 경로 열거나 hierarchyid 가 맞습니다. 댓글은 한 단계뿐이라 parent_num 하나로 충분합니다. 실습 데이터베이스가 COMMENTS 에 계층 열을 두지 않은 것이 그 까닭입니다.

직접 해보기

이 단원에서 더한 열과 표를 지웁니다.
DROP INDEX IX_POSTS_path ON Board.POSTS; DROP INDEX IX_POSTS_hid ON Board.POSTS;
ALTER TABLE Board.POSTS DROP COLUMN path, hid;
DROP TABLE Board.T_H;
ALTER INDEX PK_POSTS ON Board.POSTS REBUILD;