[MySQL] Materialized Path를 사용한 계층형 모델

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

 

이런 곳에 사용하죠.

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

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

 

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

 

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

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

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

 

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

CREATE DATABASE `graph_test` DEFAULT CHARACTER SET utf8mb4 DEFAULT COLLATE utf8mb4_general_ci;
 
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 (1, NULL), (2, 1), (3, 1), (4, 1), (5, 4), (6, 2), (7, 6), (8, 3), (9, 2), (10, 8), (11, 8), (12, 7);

 

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

 

 

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

WITH RECURSIVE C AS (
    SELECT employee_id, manager_id, CONVERT(LPAD(employee_id, 3, '0'), char(30)) 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, LPAD(E.employee_id, 3, '0'))
    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, CAST((LENGTH(path) + 1) / 4 - 1 AS SIGNED) AS depth
FROM C
ORDER BY path;

 

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

 

정리

 

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

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

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

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

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

 

일반적으로 사용하는 대용량 계층형 설계와 이 포스트에서 소개하는 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 코드를 사용하면 0 ~ 127까지 한 개의 문자로 표현할 수 있습니다.

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

 

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

 

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

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

이렇게 5개의 문자를 제외하면 최대 251진수를 만들 수 있으므로 char(4)로 표현할 수 있는 숫자의 범위는 0 ~ 3,969,126,001이 됩니다.

 

주의!!
the_path 컬럼은 latin1_bin 으로 설정해야 합니다.

 

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

-- -----------------------------------------------------
-- FUNCTION usf_base251_ntos
-- -----------------------------------------------------
 
SET sql_mode = 'STRICT_ALL_TABLES,TRADITIONAL,NO_ENGINE_SUBSTITUTION,ONLY_FULL_GROUP_BY';
 
DELIMITER $$
 
DROP FUNCTION IF EXISTS usf_base251_ntos$$
 
CREATE DEFINER=CURRENT_USER() FUNCTION usf_base251_ntos(
      pi_int_number int UNSIGNED -- 0 ~ 3,969,126,000 (251^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 base251 (number to string)
parameter :
      pi_int_number int UNSIGNED
'
BEGIN
    DECLARE v_iny_quotient tinyint UNSIGNED;
    DECLARE v_i tinyint UNSIGNED DEFAULT 1;
    DECLARE v_result char(4) DEFAULT '';
 
    WHILE v_i <= 4 DO
        SET v_iny_quotient = FLOOR(pi_int_number / POWER(251, (4 - v_i)));
        SET pi_int_number = pi_int_number % POWER(251, (4 - v_i));
 
        SET v_iny_quotient = v_iny_quotient +
            CASE -- skip CHAR(0), CHAR(32), CHAR(37), CHAR(95), CHAR(127)
                WHEN v_iny_quotient BETWEEN 0 AND 30 THEN 1
                WHEN v_iny_quotient BETWEEN 31 AND 34 THEN 2
                WHEN v_iny_quotient BETWEEN 35 AND 91 THEN 3
                WHEN v_iny_quotient BETWEEN 92 AND 122 THEN 4
                ELSE 5
            END;
 
        SET v_result = CONCAT(v_result, CONVERT(CHAR(v_iny_quotient) USING latin1));
 
        SET v_i = v_i + 1;
    END WHILE;
 
    RETURN v_result;
END$$
 
DELIMITER ;

 

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

-- -----------------------------------------------------
-- FUNCTION usf_base251_ston
-- -----------------------------------------------------
 
SET sql_mode = 'STRICT_ALL_TABLES,TRADITIONAL,NO_ENGINE_SUBSTITUTION,ONLY_FULL_GROUP_BY';
 
DELIMITER $$
 
DROP FUNCTION IF EXISTS usf_base251_ston$$
 
CREATE DEFINER=CURRENT_USER() FUNCTION usf_base251_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 base251 (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(CONVERT(SUBSTRING(pi_chr_string, 4, 1) USING latin1));
    SET v_b = ASCII(CONVERT(SUBSTRING(pi_chr_string, 3, 1) USING latin1));
    SET v_c = ASCII(CONVERT(SUBSTRING(pi_chr_string, 2, 1) USING latin1));
    SET v_d = ASCII(CONVERT(SUBSTRING(pi_chr_string, 1, 1) USING latin1));
 
    SET v_int_number = 
        CASE
            WHEN v_d BETWEEN 128 AND 255 THEN v_d - 5
            WHEN v_d BETWEEN 96  AND 126 THEN v_d - 4
            WHEN v_d BETWEEN 38  AND 94  THEN v_d - 3
            WHEN v_d BETWEEN 33  AND 36  THEN v_d - 2
            WHEN v_d BETWEEN 1   AND 31  THEN v_d - 1
        END * 15813251 +
 
        CASE
            WHEN v_c BETWEEN 128 AND 255 THEN v_c - 5
            WHEN v_c BETWEEN 96  AND 126 THEN v_c - 4
            WHEN v_c BETWEEN 38  AND 94  THEN v_c - 3
            WHEN v_c BETWEEN 33  AND 36  THEN v_c - 2
            WHEN v_c BETWEEN 1   AND 31  THEN v_c - 1
        END * 63001 +
 
        CASE
            WHEN v_b BETWEEN 128 AND 255 THEN v_b - 5
            WHEN v_b BETWEEN 96  AND 126 THEN v_b - 4
            WHEN v_b BETWEEN 38  AND 94  THEN v_b - 3
            WHEN v_b BETWEEN 33  AND 36  THEN v_b - 2
            WHEN v_b BETWEEN 1   AND 31  THEN v_b - 1
        END * 251 +
 
        CASE
            WHEN v_a BETWEEN 128 AND 255 THEN v_a - 5
            WHEN v_a BETWEEN 96  AND 126 THEN v_a - 4
            WHEN v_a BETWEEN 38  AND 94  THEN v_a - 3
            WHEN v_a BETWEEN 33  AND 36  THEN v_a - 2
            WHEN v_a BETWEEN 1   AND 31  THEN v_a - 1
        END;
 
    RETURN v_int_number;
END$$
 
DELIMITER ;

 

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

 

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

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

 

1. 컬럼을 추가합니다.

ALTER TABLE employee
    ADD COLUMN the_path varchar(149) CHARACTER SET latin1 COLLATE latin1_bin NOT NULL,
    ADD COLUMN depth tinyint UNSIGNED NOT NULL,
    ADD COLUMN has_child_flag tinyint UNSIGNED NOT NULL;

 

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

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 (PRIMARY) ON T.employee_id = S.employee_id
SET T.has_child_flag = 1;
 
DROP TABLE tmp_parent_rows;

 

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

-- -----------------------------------------------------
-- PROCEDURE usp_set_materialized_path
-- -----------------------------------------------------
 
SET sql_mode = 'STRICT_ALL_TABLES,TRADITIONAL,NO_ENGINE_SUBSTITUTION,ONLY_FULL_GROUP_BY';
 
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_base251_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, CONVERT(usf_base251_ntos(C.employee_id) USING latin1))
        , C.depth = 1
    WHERE P.manager_id IS NULL;
 
    CREATE INDEX `nix-employee-depth` ON employee (depth);
 
    main_loop: WHILE 1 = 1 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, CONVERT(usf_base251_ntos(C.employee_id) USING latin1))
            , C.depth = P.depth + 1
        WHERE P.depth = v_iny_depth;
    
        IF ROW_COUNT() = 0 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 ;

 

CALL usp_set_materialized_path ();

 

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

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

 

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

 

1. 전체 탐색

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

 

 

 

 

 

 

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

SELECT CONCAT(the_path, '%')
INTO @v_the_path
FROM employee FORCE INDEX FOR JOIN (PRIMARY)
WHERE employee_id = 8;
 
SELECT *
FROM employee FORCE INDEX FOR JOIN (`uix-employee-the_path`)
WHERE the_path LIKE @v_the_path
ORDER BY the_path;

 

 

 

 

3 위로 탐색

 

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

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

 

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);
 

 

위로 탐색 / employee_id = 8 기준

 

WITH P (employee_id) AS (
    SELECT usf_base251_ston(SUBSTRING_INDEX(SUBSTRING_INDEX(E.the_path, CHAR(127), - n), CHAR(127), 1))
    FROM employee E FORCE INDEX FOR JOIN (PRIMARY)
        INNER JOIN tally T FORCE INDEX FOR JOIN (PRIMARY) ON T.n <= depth + 1
    WHERE E.employee_id = 8
)
SELECT STRAIGHT_JOIN E.*
FROM P
    INNER JOIN employee E FORCE INDEX FOR JOIN (PRIMARY) ON E.employee_id = P.employee_id;

 

 

 

 

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

 

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

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

 

1 sequence 테이블 생성

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;

 

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

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, CONVERT(usf_base251_ntos(LAST_INSERT_ID()) USING latin1))
    , depth + 1
    , 0
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;

 

 

 

 

 

마치며

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

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

 

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