2018. 4. 16. 19:46

Graph 구조 중 가장 단순하면서 흔히 사용되는 것이 Hierarchy, 즉 계층형 구조입니다.


이런 곳에 사용하죠.

  • 계층형 게시판
  • 카테고리
  • 조직도
  • 폴더 Tree
  • 추천인 Tree

먼저 기본 설계를 설명하고 다음으로 Materialized Path를 어떻게 적용할 수 있는 지 알아보겠습니다.


1. 계층형 설계의 기본 :  Adjacency List 


자신의 매니저를 `employee` 테이블에서 재귀 참조하는 예입니다.

정규화된 간결한 구조인데요.

이런 계층형 설계를 Adjacency List 라고 합니다.


그럼 테이블을 생성하고, 테스트 데이터를 입력해 봅니다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
CREATE DATABASE `graph_test` DEFAULT CHARACTER SET latin1 DEFAULT COLLATE latin1_general_cs;
 
USE `graph_test`;
 
CREATE TABLE `employee` (
    employee_id int UNSIGNED NOT NULL AUTO_INCREMENT PRIMARY KEY,
    manager_id int UNSIGNED NULL,
    INDEX `nix-employee-manager_id` (manager_id),
    CONSTRAINT `fk-employee-employee` FOREIGN KEY (manager_id)
        REFERENCES `employee` (employee_id)
ENGINE=InnoDB;
 
INSERT `employee` (employee_id, manager_id)
VALUES (1NULL), (21), (31), (41), (54), (62), (76), (83), (92), (108), (118), (127);
cs


이제 입력한 테스트 데이터를 아래와 같은 Tree Diagram 으로 나타낼 수 있도록 SELECT 문을 작성해야 하는데요.



방법 1 : MySQL 8.0 이상에서는 CTE (Common Table Expression)을 재귀 참조하는 방식을 사용할 수 있습니다.

1
2
3
4
5
6
7
8
9
10
11
12
WITH RECURSIVE C AS (
    SELECT employee_id, manager_id, CONVERT(employee_id USING latin1) AS path
    FROM employee FORCE INDEX FOR JOIN (`nix-employee-manager_id`)
    WHERE manager_id IS NULL
    UNION ALL
    SELECT E.employee_id, E.manager_id, CONCAT_WS(',', C.path, E.employee_id)
    FROM C
        STRAIGHT_JOIN employee E FORCE INDEX FOR JOIN (`nix-employee-manager_id`ON E.manager_id = C.employee_id
)
SELECT employee_id, manager_id, path
FROM C
ORDER BY path;
cs


방법 2 : MySQL 8.0 미만의 버전에서는 세션 변수를 사용한 Tricky 한 방법이 있는데 따로 소개하지 않겠습니다. (Stack Overflow에 많이 나옵니다.)


정리


Adjacency List 는 모델로만 보면 군더더기 없이 잘 정규화 되었습니다.

Rows 가 많지 않은 - 간단한 카테고리 구성과 같은 - 상황 이라면 이 모델로도 충분합니다.

하지만 조회가 빈번한 대용량 계층형 테이블이라면 Adjacency List 로는 부족합니다.

이 모델에서 만들 수 있는 SELECT 문으로는 계층을 위 / 아래로 탐색하는 성능에 한계가 있기 때문입니다.

Materialized Path 는 구현과 개념이 다소 어렵지만 성능 문제를 해결해 줄 수 있습니다.


잠깐!!! 그 동안 MySQL로 설계했던 대용량 계층형 설계와 이 포스트에서 소개하는 Materialized Path 가 다른 것인가요?


계층형 게시판을 설계한 예를 보면, 이런 컬럼 이름이 자주 사용됩니다.

bbs_id, bbs_group_id, seq, level

글이 추가될 때마다 seq 값을 update 해서 조회 속도를 높이는 방식인데, 아마 익숙하시리라 생각합니다.

굳이 표현하자면 이런 설계는 Nested Set 설계의 변형에 속합니다.

원래의 Nested Set 은 각 노드에 대한 left와 right의 seq 컬럼이 따로 있는데, 보통 사용되는 계층형 게시판의 설계에서는 left seq만 사용합니다.

Nested Set 에 대한 이야기는 기회가 닿으면 별도로 다루겠습니다.


2. 대용량 계층형 조회에 최적화된 설계 : Materialized Path


2-1. 개념 살펴보기

Materialized Path 번역하면 물리화된 경로 입니다.

이름에서 짐작할 수 있는 것처럼 계층형의 정렬 순서를 SELECT 시점에 결정하는 것이 아니라, Row 를 INSERT 할 때 물리적으로 저장하는 것입니다.


아래 표에서 the_path 컬럼에 들어있는 값을 관찰해 봅시다.


`employee` 테이블에 넣었던 데이터를 기억해 보면..

  • 6번 직원의 관리자는 2번 직원
  • 2번 직원의 관리자는 1번 직원

즉, 6번 직원까지 도달하는 계층형의 경로는 1번 > 2번 > 6번의 순서가 됩니다.


이것을 the_path 컬럼에 001/002/006 이라는 값으로 저장하는 것이 Materialized Path 의 핵심입니다.


어떤 잇점이 있을까요?


SELECT 문에서 단지 the_path 컬럼으로 정렬하면, 원하는 계층형 query 가 완성된다는 점입니다.


2-2. the_path 최적화 하기

이 설계의 가장 큰 단점은 depth (또는 level) 에 제한이 있다는 것입니다.


depth 제한이 큰 문제가 안되는 모델이라는 가정 아래.. 한 가지 문제가 더 있는데요.

계층 경로인 the_path 컬럼에 저장되는 값의 크기가 너무 커서 I/O 에 부담을 준다는 것입니다.


만약 employee_id가 integer라면 employee_id 당 최대 10글자이고, depth 제한이 30이라면..


the_path의 사이즈는 최대 (10 + 1) * 30 - 1 = 329 byte


따라서 the_path를 줄여 줄 필요가 있는데요.

depth 만큼 employee_id를 저장해야하는 건 피할 수 없지만, employee_id 값 자체의 길이는 줄일 수 있습니다.


ASCII 코드를 사용하면 1 ~ 127까지 한 개의 문자로 표현할 수 있습니다.

만약 확장 ASCII 코드를 사용하면 1 ~ 255까지 가능하죠.


여기서는 ASCII()함수와 역함수인 CHAR() 함수를 사용한 진법 변환 함수를 만드는 방법으로, the_path 컬럼을 최적화합니다.


단, 숫자를 문자열로 변환할 때 몇몇 글자는 제외해야 합니다!!

  1. 나중에 계층형 구조를 아래 방향으로 탐색할 때 LIKE 연산자를 사용해야하기 때문에, 와일드 카드 문자에 해당하는 %와 _ 를 뺍니다.
  2. CHAR(0)은 공백 문자라서 아무 것도 표현할 수 없으므로 뺍니다.
  3. MS-SQL에서 구분자를 사용하지 않아도 정렬에 문제가 없었는데, MySQL에서는 문자열의 끝을 나타내는 부분이 space로 취급되어 정렬되는 바람에.. 부득이 구분자로 사용할 문자 하나를 뺍니다. 아래의 코드에서는 CHAR(127)을 구분자로 사용했습니다.

이렇게 4개의 문자를 제외하면 최대 252진수를 만들 수 있으므로 varchar(4)로 표현할 수 있는 숫자의 범위는 0 ~ 4,032,758,015 가 됩니다.


데이터베이스의 Character Set 이 latin1 이라야 확장 ASCII를 사용할 수 있는데, 한국에서 latin1을 사용할리 없겠죠.


방법 1. 확장 ASCII를 포기하고 128 - 4 = 124진법을 사용한다.

방법 2. 이하에 소개하는 252진법 함수를 Character Set = latin1 인 별도의 데이터베이스에 넣고 사용한다.


252진법 변환 함수 (숫자 -> 문자)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
-- -----------------------------------------------------
-- FUNCTION usf_base252_ntos
-- -----------------------------------------------------
 
SET NAMES 'latin1';
SET COLLATION_CONNECTION = 'latin1_general_ci';
 
SET sql_mode = 'ONLY_FULL_GROUP_BY,STRICT_TRANS_TABLES,STRICT_ALL_TABLES,NO_ZERO_IN_DATE,NO_ZERO_DATE,ERROR_FOR_DIVISION_BY_ZERO,TRADITIONAL,NO_AUTO_CREATE_USER,NO_ENGINE_SUBSTITUTION';
 
DELIMITER $$
 
DROP FUNCTION IF EXISTS usf_base252_ntos$$
 
CREATE DEFINER=CURRENT_USER() FUNCTION usf_base252_ntos(
      pi_int_number int UNSIGNED -- 0 ~ 4,032,758,015 (252^4 - 1)
)
RETURNS char(4)
DETERMINISTIC
SQL SECURITY DEFINER
CONTAINS SQL
COMMENT '
author : doeyull.kim
e-mail : purumae@gmail.com
created date : 2017-12-06
description : encode base252 (number to string)
parameter :
      pi_int_number int UNSIGNED
'
BEGIN
    DECLARE v_iny_quotient tinyint UNSIGNED;
    DECLARE v_i tinyint UNSIGNED DEFAULT 1;
 
    SET @tmp = '';
 
    WHILE v_i <= DO
        SET v_iny_quotient = FLOOR(pi_int_number / POWER(252, (- v_i)));
        SET pi_int_number = pi_int_number % POWER(252, (- v_i));
 
        SET v_iny_quotient = 
            CASE -- skip CHAR(0), CHAR(37), CHAR(95), CHAR(127)
                WHEN v_iny_quotient <= 35 THEN v_iny_quotient + 1
                WHEN v_iny_quotient BETWEEN 36 AND 93 THEN v_iny_quotient + 2
                ELSE v_iny_quotient + 3
            END;
 
        SET @tmp = CONCAT(@tmp, CHAR(v_iny_quotient));
 
        SET v_i = v_i + 1;
    END WHILE;
 
    RETURN @tmp;
END$$
 
DELIMITER ;
 
cs


252진법 변환 함수 (문자 -> 숫자)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
-- -----------------------------------------------------
-- FUNCTION usf_base252_ston
-- -----------------------------------------------------
 
SET NAMES 'latin1';
SET COLLATION_CONNECTION = 'latin1_general_ci';
 
SET sql_mode = 'ONLY_FULL_GROUP_BY,STRICT_TRANS_TABLES,STRICT_ALL_TABLES,NO_ZERO_IN_DATE,NO_ZERO_DATE,ERROR_FOR_DIVISION_BY_ZERO,TRADITIONAL,NO_AUTO_CREATE_USER,NO_ENGINE_SUBSTITUTION';
 
DELIMITER $$
 
DROP FUNCTION IF EXISTS usf_base252_ston$$
 
CREATE DEFINER=CURRENT_USER() FUNCTION usf_base252_ston(
      pi_chr_string char(4)
)
RETURNS int UNSIGNED
DETERMINISTIC
SQL SECURITY DEFINER
CONTAINS SQL
COMMENT '
author : doeyull.kim
e-mail : purumae@gmail.com
created date : 2017-12-06
description : decode base252 (string to number)
parameter :
      pi_chr_string char(4)
'
BEGIN
    DECLARE v_a tinyint UNSIGNED;
    DECLARE v_b tinyint UNSIGNED;
    DECLARE v_c tinyint UNSIGNED;
    DECLARE v_d tinyint UNSIGNED;
    DECLARE v_int_number int UNSIGNED;
 
    SET v_a = ASCII(SUBSTRING(pi_chr_string, 41));
    SET v_b = ASCII(SUBSTRING(pi_chr_string, 31));
    SET v_c = ASCII(SUBSTRING(pi_chr_string, 21));
    SET v_d = ASCII(SUBSTRING(pi_chr_string, 11));
 
    SET v_int_number = 
        CASE
            WHEN v_d >= 96 THEN v_d - 3
            WHEN v_d BETWEEN 38 AND 95 THEN v_d - 2
            ELSE v_d - 1
        END * 16003008 +
 
        CASE
            WHEN v_c >= 96 THEN v_c - 3
            WHEN v_c BETWEEN 38 AND 95 THEN v_c - 2
            ELSE v_c - 1
        END * 63504 +
 
        CASE
            WHEN v_b >= 96 THEN v_b - 3
            WHEN v_b BETWEEN 38 AND 95 THEN v_b - 2
            ELSE v_b - 1
        END * 252 +
 
        CASE
            WHEN v_a >= 96 THEN v_a - 3
            WHEN v_a BETWEEN 38 AND 95 THEN v_a - 2
            ELSE v_a - 1
        END;
 
    RETURN v_int_number;
END$$
 
DELIMITER ;
cs


이제 the_path의 사이즈는 최대 (4 + 1) * 30 - 1 = 149 byte 로 줄게 되었습니다.


2-3. 기존 테이블을 Materialized Path 테이블로 Migration

처음 작성했던 `employee` 테이블을 마이그레이션 해 봅니다.


1. 컬럼을 추가합니다.

1
2
3
4
ALTER TABLE employee
    ADD COLUMN the_path varchar(149NOT NULL,
    ADD COLUMN depth tinyint UNSIGNED NOT NULL,
    ADD COLUMN has_child_flag tinyint UNSIGNED NOT NULL;
cs


2. has_child_flag 컬럼 (현재 노드를 기준으로 자식 노드가 존재하는 지 여부) 값을 마이그레이션 합니다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
CREATE TEMPORARY TABLE tmp_parent_rows (
    employee_id int UNSIGNED NOT NULL PRIMARY KEY
ENGINE=InnoDB;
 
INSERT tmp_parent_rows (employee_id)
SELECT P.employee_id
FROM employee P FORCE INDEX (PRIMARY)
WHERE EXISTS (
    SELECT *
    FROM employee C FORCE INDEX FOR JOIN (`nix-employee-manager_id`)
    WHERE C.manager_id = P.employee_id
);
 
UPDATE tmp_parent_rows S FORCE INDEX (PRIMARY)
    STRAIGHT_JOIN employee T FORCE INDEX FOR JOIN (PRIMARYON T.employee_id = S.employee_id
SET T.has_child_flag = 1;
 
DROP TABLE tmp_parent_rows;
cs


3. the_path와 depth 컬럼의 값을 처리하기 위해 아래와 같은 Stored Procedure 를 작성하고 실행합니다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
-- -----------------------------------------------------
-- PROCEDURE usp_set_materialized_path
-- -----------------------------------------------------
 
SET NAMES 'latin1';
SET COLLATION_CONNECTION = 'latin1_general_ci';
 
SET sql_mode = 'ONLY_FULL_GROUP_BY,STRICT_TRANS_TABLES,STRICT_ALL_TABLES,NO_ZERO_IN_DATE,NO_ZERO_DATE,ERROR_FOR_DIVISION_BY_ZERO,TRADITIONAL,NO_AUTO_CREATE_USER,NO_ENGINE_SUBSTITUTION';
 
DELIMITER $$
 
DROP PROCEDURE IF EXISTS usp_set_materialized_path$$
 
CREATE PROCEDURE usp_set_materialized_path ()
BEGIN
    DECLARE v_iny_depth tinyint UNSIGNED DEFAULT 1;
 
    UPDATE employee
    SET the_path = usf_base252_ntos(employee_id)
    WHERE manager_id IS NULL;
 
    UPDATE employee P FORCE INDEX FOR JOIN (`nix-employee-manager_id`)
        STRAIGHT_JOIN employee C FORCE INDEX FOR JOIN (`nix-employee-manager_id`ON C.manager_id = P.employee_id
    SET C.the_path = CONCAT_WS(CHAR(127), P.the_path, usf_base252_ntos(C.employee_id))
        , C.depth = 1
    WHERE P.manager_id IS NULL;
 
    CREATE INDEX `nix-employee-depth` ON employee (depth);
 
    main_loop: WHILE = DO
        UPDATE employee P FORCE INDEX FOR JOIN (`nix-employee-depth`)
            STRAIGHT_JOIN employee C FORCE INDEX FOR JOIN (`nix-employee-manager_id`ON C.manager_id = P.employee_id
        SET C.the_path = CONCAT_WS(CHAR(127), P.the_path, usf_base252_ntos(C.employee_id))
            , C.depth = P.depth + 1
        WHERE P.depth = v_iny_depth;
    
        IF ROW_COUNT() = THEN
            LEAVE main_loop;
        END IF;
 
        SET v_iny_depth = v_iny_depth + 1;
    END WHILE;
 
    DROP INDEX `nix-employee-depth` ON employee;
END$$
 
DELIMITER ;
cs


1
CALL usp_set_materialized_path ();
cs


4. 마지막으로 the_path 컬럼에 인덱스를 생성해 줍니다.

1
CREATE UNIQUE INDEX `uix-employee-the_path` ON employee (the_path);
cs


2-4. Materialized Path를 사용하여 Tree 탐색하기


1. 전체 탐색

1
2
3
SELECT * 
FROM employee FORCE INDEX FOR ORDER BY (`uix-employee-the_path`)
ORDER BY the_path;
cs






2 아래로 탐색 / employee_id = 8 기준

1
2
3
4
5
6
7
8
SELECT *
FROM employee FORCE INDEX FOR JOIN (`uix-employee-the_path`)
WHERE the_path LIKE (
    SELECT CONCAT(the_path, '%')
    FROM employee FORCE INDEX FOR JOIN (PRIMARY)
    WHERE employee_id = 8
)
ORDER BY the_path;
cs





3 위로 탐색


아래와 같이 정수만 들어 있는 - 보통 1,000개 ~ 10,000개 가량 - 테이블을 만들어 두면 유용한 경우가 많이 있습니다.

tree를 위로 탐색할 때도 이런 테이블을 만들어 참조하는 방식을 사용하면 query 작성이 수월해 집니다.


1
2
3
4
5
6
7
8
CREATE TABLE tally (
  n SMALLINT UNSIGNED NOT NULL PRIMARY KEY
)
ENGINE = InnoDB;
 
INSERT `tally`
VALUES (1),(2),(3),(4),(5),(6),(7),(8),(9),(10),(11),(12),(13),(14),(15),(16),(17),(18),(19),(20),(21),(22),(23),(24),(25),(26),(27),(28),(29),(30),(31),(32),(33),(34),(35),(36),(37),(38),(39),(40),(41),(42),(43),(44),(45),(46),(47),(48),(49),(50),(51),(52),(53),(54),(55),(56),(57),(58),(59),(60),(61),(62),(63),(64),(65),(66),(67),(68),(69),(70),(71),(72),(73),(74),(75),(76),(77),(78),(79),(80),(81),(82),(83),(84),(85),(86),(87),(88),(89),(90),(91),(92),(93),(94),(95),(96),(97),(98),(99),(100),(101),(102),(103),(104),(105),(106),(107),(108),(109),(110),(111),(112),(113),(114),(115),(116),(117),(118),(119),(120),(121),(122),(123),(124),(125),(126),(127),(128),(129),(130),(131),(132),(133),(134),(135),(136),(137),(138),(139),(140),(141),(142),(143),(144),(145),(146),(147),(148),(149),(150),(151),(152),(153),(154),(155),(156),(157),(158),(159),(160),(161),(162),(163),(164),(165),(166),(167),(168),(169),(170),(171),(172),(173),(174),(175),(176),(177),(178),(179),(180),(181),(182),(183),(184),(185),(186),(187),(188),(189),(190),(191),(192),(193),(194),(195),(196),(197),(198),(199),(200),(201),(202),(203),(204),(205),(206),(207),(208),(209),(210),(211),(212),(213),(214),(215),(216),(217),(218),(219),(220),(221),(222),(223),(224),(225),(226),(227),(228),(229),(230),(231),(232),(233),(234),(235),(236),(237),(238),(239),(240),(241),(242),(243),(244),(245),(246),(247),(248),(249),(250),(251),(252),(253),(254),(255),(256),(257),(258),(259),(260),(261),(262),(263),(264),(265),(266),(267),(268),(269),(270),(271),(272),(273),(274),(275),(276),(277),(278),(279),(280),(281),(282),(283),(284),(285),(286),(287),(288),(289),(290),(291),(292),(293),(294),(295),(296),(297),(298),(299),(300),(301),(302),(303),(304),(305),(306),(307),(308),(309),(310),(311),(312),(313),(314),(315),(316),(317),(318),(319),(320),(321),(322),(323),(324),(325),(326),(327),(328),(329),(330),(331),(332),(333),(334),(335),(336),(337),(338),(339),(340),(341),(342),(343),(344),(345),(346),(347),(348),(349),(350),(351),(352),(353),(354),(355),(356),(357),(358),(359),(360),(361),(362),(363),(364),(365),(366),(367),(368),(369),(370),(371),(372),(373),(374),(375),(376),(377),(378),(379),(380),(381),(382),(383),(384),(385),(386),(387),(388),(389),(390),(391),(392),(393),(394),(395),(396),(397),(398),(399),(400),(401),(402),(403),(404),(405),(406),(407),(408),(409),(410),(411),(412),(413),(414),(415),(416),(417),(418),(419),(420),(421),(422),(423),(424),(425),(426),(427),(428),(429),(430),(431),(432),(433),(434),(435),(436),(437),(438),(439),(440),(441),(442),(443),(444),(445),(446),(447),(448),(449),(450),(451),(452),(453),(454),(455),(456),(457),(458),(459),(460),(461),(462),(463),(464),(465),(466),(467),(468),(469),(470),(471),(472),(473),(474),(475),(476),(477),(478),(479),(480),(481),(482),(483),(484),(485),(486),(487),(488),(489),(490),(491),(492),(493),(494),(495),(496),(497),(498),(499),(500),(501),(502),(503),(504),(505),(506),(507),(508),(509),(510),(511),(512),(513),(514),(515),(516),(517),(518),(519),(520),(521),(522),(523),(524),(525),(526),(527),(528),(529),(530),(531),(532),(533),(534),(535),(536),(537),(538),(539),(540),(541),(542),(543),(544),(545),(546),(547),(548),(549),(550),(551),(552),(553),(554),(555),(556),(557),(558),(559),(560),(561),(562),(563),(564),(565),(566),(567),(568),(569),(570),(571),(572),(573),(574),(575),(576),(577),(578),(579),(580),(581),(582),(583),(584),(585),(586),(587),(588),(589),(590),(591),(592),(593),(594),(595),(596),(597),(598),(599),(600),(601),(602),(603),(604),(605),(606),(607),(608),(609),(610),(611),(612),(613),(614),(615),(616),(617),(618),(619),(620),(621),(622),(623),(624),(625),(626),(627),(628),(629),(630),(631),(632),(633),(634),(635),(636),(637),(638),(639),(640),(641),(642),(643),(644),(645),(646),(647),(648),(649),(650),(651),(652),(653),(654),(655),(656),(657),(658),(659),(660),(661),(662),(663),(664),(665),(666),(667),(668),(669),(670),(671),(672),(673),(674),(675),(676),(677),(678),(679),(680),(681),(682),(683),(684),(685),(686),(687),(688),(689),(690),(691),(692),(693),(694),(695),(696),(697),(698),(699),(700),(701),(702),(703),(704),(705),(706),(707),(708),(709),(710),(711),(712),(713),(714),(715),(716),(717),(718),(719),(720),(721),(722),(723),(724),(725),(726),(727),(728),(729),(730),(731),(732),(733),(734),(735),(736),(737),(738),(739),(740),(741),(742),(743),(744),(745),(746),(747),(748),(749),(750),(751),(752),(753),(754),(755),(756),(757),(758),(759),(760),(761),(762),(763),(764),(765),(766),(767),(768),(769),(770),(771),(772),(773),(774),(775),(776),(777),(778),(779),(780),(781),(782),(783),(784),(785),(786),(787),(788),(789),(790),(791),(792),(793),(794),(795),(796),(797),(798),(799),(800),(801),(802),(803),(804),(805),(806),(807),(808),(809),(810),(811),(812),(813),(814),(815),(816),(817),(818),(819),(820),(821),(822),(823),(824),(825),(826),(827),(828),(829),(830),(831),(832),(833),(834),(835),(836),(837),(838),(839),(840),(841),(842),(843),(844),(845),(846),(847),(848),(849),(850),(851),(852),(853),(854),(855),(856),(857),(858),(859),(860),(861),(862),(863),(864),(865),(866),(867),(868),(869),(870),(871),(872),(873),(874),(875),(876),(877),(878),(879),(880),(881),(882),(883),(884),(885),(886),(887),(888),(889),(890),(891),(892),(893),(894),(895),(896),(897),(898),(899),(900),(901),(902),(903),(904),(905),(906),(907),(908),(909),(910),(911),(912),(913),(914),(915),(916),(917),(918),(919),(920),(921),(922),(923),(924),(925),(926),(927),(928),(929),(930),(931),(932),(933),(934),(935),(936),(937),(938),(939),(940),(941),(942),(943),(944),(945),(946),(947),(948),(949),(950),(951),(952),(953),(954),(955),(956),(957),(958),(959),(960),(961),(962),(963),(964),(965),(966),(967),(968),(969),(970),(971),(972),(973),(974),(975),(976),(977),(978),(979),(980),(981),(982),(983),(984),(985),(986),(987),(988),(989),(990),(991),(992),(993),(994),(995),(996),(997),(998),(999),(1000);
 
cs


위로 탐색 / employee_id = 8 기준


1
2
3
4
5
6
7
SELECT STRAIGHT_JOIN P.*
FROM (
    SELECT usf_base252_ston(SUBSTRING_INDEX(SUBSTRING_INDEX(E.the_path, CHAR(127), - n), CHAR(127), 1)) AS employee_id
    FROM employee E FORCE INDEX FOR JOIN (PRIMARY)
        INNER JOIN tally T FORCE INDEX FOR JOIN (PRIMARYON T.n <= depth + 1
    WHERE E.employee_id = 8
) S INNER JOIN employee P FORCE INDEX FOR JOIN (PRIMARYON P.employee_id = S.employee_id;
cs





2-5. INSERT : 새 node 추가하기


employee_id 컬럼에 Auto Increment 속성을 사용하면 INSERT 한 다음 다시 the_path 값을 생성하여 UPDATE 해야하는 문제가 있습니다.

생각하기에 따라서 조삼모사로 보일 수 있지만, Auto Increment 대신 아래와 같은 sequence 테이블을 만들어 따로 채번하는 방식을 사용해 봅니다.


1 sequence 테이블 생성

1
2
3
4
5
6
7
8
9
CREATE TABLE sequence_employee_id (
  employee_id int UNSIGNED NOT NULL PRIMARY KEY
ENGINE=InnoDB;
 
INSERT sequence_employee_id (employee_id)
SELECT employee_id
FROM employee FORCE INDEX FOR ORDER BY (PRIMARY)
ORDER BY employee_id DESC
LIMIT 1;
cs


2 employee_id = 8을 manager로 하는 새 employee 추가

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
SET @manager_id = 8;
SET @has_child_flag = 0;
 
UPDATE sequence_employee_id
SET employee_id = LAST_INSERT_ID(employee_id + 1);
 
INSERT employee (employee_id, manager_id, the_path, depth, has_child_flag)
SELECT LAST_INSERT_ID(), employee_id, CONCAT_WS(CHAR(127), the_path, usf_base252_ntos(LAST_INSERT_ID())), depth + 10
FROM employee FORCE INDEX FOR JOIN (PRIMARY)
WHERE employee_id = @manager_id
    AND has_child_flag = (@has_child_flag := has_child_flag);
 
UPDATE employee FORCE INDEX FOR JOIN (PRIMARY)
SET has_child_flag = 1
WHERE @has_child_flag = 0
    AND employee_id = @manager_id;
 
SELECT * 
FROM employee FORCE INDEX FOR ORDER BY (`uix-employee-the_path`)
ORDER BY the_path;
cs






마치며

MySQL 에서 계층형 모델을 구현할 때 사용할 수 있는 Materialized Path 모델을 살펴봤습니다.

구조가 간단하지 않지만 막상 구현해보면 어렵지 않고 재미있습니다.


요즘은 Graph Database 가 있어서 이 보다 더 복잡한 형태의 Graph 모델도 빠르게 조회할 수 있다고 하니, 관심 있으신 분은 Graph Database 도 공부해 보시면 좋을 것 같습니다.

Posted by 르매

댓글을 달아 주세요

  1. ssaurabi 2018.04.25 13:32  댓글주소  수정/삭제  댓글쓰기

    오랫만에 포스팅하셨네요.

    SqlSafe를 비롯한 깊이있고 유용한 글에 항상 감사드립니다.

    MySql에서 버전관리는 어떻게 하시는지 궁금합니다.

    SqlSafe for MySql 에 관한 계획을 보았던 기억이 있는데 구축이 되셨는지요?

    • BlogIcon 르매 2018.04.25 13:43 신고  댓글주소  수정/삭제

      기억해 주시니 감사합니다~

      MySQL에서 general log를 수집해 비슷한 방식으로 sql safe를 만들어 사용하고 있습니다. ^^
      이번에는 웹개발자 분의 도움을 받아 ui를 입혔더니 도움이 많이 되더군요~

      다음 주 정도에 포스팅 하겠습니다. ^^

  2. ssaurabi 2018.04.25 15:34  댓글주소  수정/삭제  댓글쓰기

    정말 큰 기대가 됩니다. ^^

    여러차례 MySQL stored procedure 개발을 시도해보았지만, 결국은 익숙한 MS SQL로 귀환하게 되더군요 ㅡㅡ;

    르매님도 MySQL 전환 후 많은 고생을 하셨을 것으로 짐작됩니다.