[SQL_Q] 3482. Analyze Organization Hierarchy (using recursive CTE)

https://leetcode.com/problems/analyze-organization-hierarchy/description/

what is Recursive CTE?

[SQL] RECURSIVE CTE 이해하기

문제

Table: Employees

+----------------+---------+
| Column Name    | Type    | 
+----------------+---------+
| employee_id    | int     |
| employee_name  | varchar |
| manager_id     | int     |
| salary         | int     |
| department     | varchar |
+----------------+----------+
employee_id is the unique key for this table.
Each row contains information about an employee, including their ID, name, their manager's ID, salary, and department.
manager_id is null for the top-level manager (CEO).
Write a solution to analyze the organizational hierarchy and answer the following:

Hierarchy Levels: For each employee, determine their level in the organization (CEO is level 1, employees reporting directly to the CEO are level 2, and so on).
Team Size: For each employee who is a manager, count the total number of employees under them (direct and indirect reports).
Salary Budget: For each manager, calculate the total salary budget they control (sum of salaries of all employees under them, including indirect reports, plus their own salary).
Return the result table ordered by the result ordered by level in ascending order, then by budget in descending order, and finally by employee_name in ascending order.

The result format is in the following example.

 

Example:

Input:

Employees table:

+-------------+---------------+------------+--------+-------------+
| employee_id | employee_name | manager_id | salary | department  |
+-------------+---------------+------------+--------+-------------+
| 1           | Alice         | null       | 12000  | Executive   |
| 2           | Bob           | 1          | 10000  | Sales       |
| 3           | Charlie       | 1          | 10000  | Engineering |
| 4           | David         | 2          | 7500   | Sales       |
| 5           | Eva           | 2          | 7500   | Sales       |
| 6           | Frank         | 3          | 9000   | Engineering |
| 7           | Grace         | 3          | 8500   | Engineering |
| 8           | Hank          | 4          | 6000   | Sales       |
| 9           | Ivy           | 6          | 7000   | Engineering |
| 10          | Judy          | 6          | 7000   | Engineering |
+-------------+---------------+------------+--------+-------------+
Output:

+-------------+---------------+-------+-----------+--------+
| employee_id | employee_name | level | team_size | budget |
+-------------+---------------+-------+-----------+--------+
| 1           | Alice         | 1     | 9         | 84500  |
| 3           | Charlie       | 2     | 4         | 41500  |
| 2           | Bob           | 2     | 3         | 31000  |
| 6           | Frank         | 3     | 2         | 23000  |
| 4           | David         | 3     | 1         | 13500  |
| 7           | Grace         | 3     | 0         | 8500   |
| 5           | Eva           | 3     | 0         | 7500   |
| 9           | Ivy           | 4     | 0         | 7000   |
| 10          | Judy          | 4     | 0         | 7000   |
| 8           | Hank          | 4     | 0         | 6000   |
+-------------+---------------+-------+-----------+--------+
Explanation:

Organization Structure:
Alice (ID: 1) is the CEO (level 1) with no manager
Bob (ID: 2) and Charlie (ID: 3) report directly to Alice (level 2)
David (ID: 4), Eva (ID: 5) report to Bob, while Frank (ID: 6) and Grace (ID: 7) report to Charlie (level 3)
Hank (ID: 8) reports to David, and Ivy (ID: 9) and Judy (ID: 10) report to Frank (level 4)
Level Calculation:
The CEO (Alice) is at level 1
Each subsequent level of management adds 1 to the level
Team Size Calculation:
Alice has 9 employees under her (the entire company except herself)
Bob has 3 employees (David, Eva, and Hank)
Charlie has 4 employees (Frank, Grace, Ivy, and Judy)
David has 1 employee (Hank)
Frank has 2 employees (Ivy and Judy)
Eva, Grace, Hank, Ivy, and Judy have no direct reports (team_size = 0)
Budget Calculation:
Alice's budget: Her salary (12000) + all employees' salaries (72500) = 84500
Charlie's budget: His salary (10000) + Frank's budget (23000) + Grace's salary (8500) = 41500
Bob's budget: His salary (10000) + David's budget (13500) + Eva's salary (7500) = 31000
Frank's budget: His salary (9000) + Ivy's salary (7000) + Judy's salary (7000) = 23000
David's budget: His salary (7500) + Hank's salary (6000) = 13500
Employees with no direct reports have budgets equal to their own salary
Note:

The result is ordered first by level in ascending order
Within the same level, employees are ordered by budget in descending order then by name in ascending order

정답 쿼리

내 쿼리

with recursive levels as (
    SELECT employee_id, 1 as level
    FROM Employees
    WHERE manager_id is NULL
    UNION ALL
    SELECT e.employee_id, l.level+1
    FROM levels l JOIN Employees e
    on l.employee_id = e.manager_id
), 
closure as (
    SELECT employee_id as ancestor, employee_id as descendant, salary as descendant_salary
    FROM Employees
    UNION ALL
    SELECT c.ancestor, e.employee_id, e.salary
    FROM closure c JOIN Employees e
    on c.descendant = e.manager_id
), tmp as (
    SELECT 
    ancestor,
    COUNT(*)-1 team_size,
    SUM(descendant_salary) as budget
    FROM closure
    GROUP BY ancestor
)
SELECT l.employee_id, e.employee_name, l.level, t.team_size, t.budget
FROM tmp t JOIN levels l JOIN Employees e
on t.ancestor = l.employee_id and l.employee_id = e.employee_id
order by 3, 5 DESC, 2

방식

• levels: 각 직원의 조직 내 level 계산 (단순 parent → child)
• closure: transitive closure 형태로 모든 ancestor–descendant 관계를 확장
  • 즉, 모든 경로를 materialize 함
• tmp: closure에서 group by 해서 team_size, budget 계산

장점

• 구조적으로 가장 직관적 (계층 level과 closure 분리)
• closure만 있으면 budget/team_size 집계는 단순 GROUP BY

단점

• closure 테이블 크기가 O(N²) 까지 커질 수 있음
  • 예: 100k 직원, depth 10 → closure 행 수 = 수백만 이상
• 대규모 조직에서는 temp table spill (디스크 사용) 가능성이 큼
• COUNT(*) - 1 보정이 필요 → 직관성은 떨어짐

다른 사람 쿼리 1

# Write your MySQL query statement below
with recursive leadership as(
    select employee_id,manager_id,employee_name,salary,1 as level 
    from Employees 
    where manager_id is null
    union all
    select e.employee_id,e.manager_id,e.employee_name,e.salary,level+1 as level
    from Employees e inner join leadership l
    on e.manager_id=l.employee_id
),
subordinate as(
    select employee_id,manager_id,salary from Employees
    union all
    select e.employee_id,s.manager_id,e.salary 
    from Employees e inner join subordinate s
    on s.employee_id=e.manager_id
)

select l.employee_id,l.employee_name,l.level,count(s.employee_id) as team_size,ifnull(sum(s.salary),0)+l.salary as budget from leadership l left join subordinate s on s.manager_id=l.employee_id group by 1,2,3,l.salary order by 3,5 desc,2

방식

• leadership: CEO부터 아래로 내려가면서 level 부여
• subordinate: manager_id 기반으로 recursive join → 각 manager가 가진 모든 부하직원 탐색
• 최종적으로 join 후 group by

장점

• closure보다 행 수가 조금 더 적음
• ifnull(sum(s.salary),0)+l.salary → 자신의 salary 포함 로직 깔끔

단점

• 사실상 closure와 유사하게 모든 manager–subordinate 관계 materialize
• subordinate CTE 크기 역시 O(N²) 위험 존재

다른 사람 쿼리 2

with recursive lvl_cte as (
    select employee_id, manager_id, 
    1 as level, salary
    from employees 
    union all
    select a.employee_id, b.manager_id, level+1, a.salary 
    from lvl_cte a join employees b 
    on b.employee_id = a.manager_id
)
,employee_lvl as (
    select a.employee_id, a.employee_name, a.salary, b.level 
    from employees a, (
        select employee_id, level 
        from lvl_cte 
        where manager_id is NULL) b
    where a.employee_id = b.employee_id
)
select a.employee_id, a.employee_name, 
a.level, coalesce(b.team_size, 0) as team_size,
a.salary+coalesce(b.budget, 0) as budget 
from employee_lvl a left join (
    select manager_id as employee_id, 
    count(*) as team_size, 
    sum(salary) as budget
    from lvl_cte 
    where manager_id is not NULL 
    group by manager_id) b
on a.employee_id = b.employee_id 
order by level, budget desc, employee_name

방식

• lvl_cte: employee → manager 체인 전개 (직원별로 위쪽 manager_id까지 추적)
• employee_lvl: CEO 기준 level만 추출
• 최종 집계: manager_id 단위로 team_size, budget 구함

장점

• 불필요한 모든 ancestor–descendant 쌍 materialization 방지
• 필요한 정보만 join해서 aggregate
• 따라서 O(N·depth) 복잡도 (closure보다 훨씬 작음)

단점

• 쿼리 구조가 복잡하고 읽기 어려움
• 특정 DB 엔진 최적화 여부에 따라 실행계획이 불안정할 수 있음

성능 비교 (대규모 환경 가정)

쿼리	접근 방식	CTE 크기 복잡도	확장성	장점	단점
사용자 쿼리	closure (ancestor–descendant)	O(N²)	낮음	구조적 명확, 집계 쉬움	closure 폭발
다른 사람 쿼리 1	leadership + subordinate	O(N²)	낮음	로직 직관적	subordinate 폭발
다른 사람 쿼리 2	lvl_cte 기반 upward traversal	O(N·depth)	높음	확장성 좋음	쿼리 복잡
다른 사람 쿼리 3	쿼리 1과 유사	O(N²)	낮음	읽기 쉬움	성능 문제 동일

내 쿼리 수정본

with recursive
-- 1) upward 방식: level 계산
up_chain as (
    select employee_id, manager_id, 1 as level
    from employees
    union all
    select u.employee_id, e.manager_id, u.level+1
    from up_chain u
    join employees e on u.manager_id = e.employee_id
),
levels as (
    select employee_id, max(level) as level
    from up_chain
    where manager_id is null   -- CEO까지 도달한 경우
    group by employee_id
),

-- 2) downward 방식: 팀/예산 계산
down_chain as (
    select employee_id as ancestor, employee_id as descendant, salary
    from employees
    union all
    select d.ancestor, e.employee_id, e.salary
    from down_chain d
    join employees e on e.manager_id = d.descendant
),
agg as (
    select ancestor as employee_id,
           count(*) - 1 as team_size,   -- 자기 제외
           sum(salary) as budget
    from down_chain
    group by ancestor
)

-- 3) 조합
select e.employee_id, e.employee_name,
       l.level,
       a.team_size,
       a.budget
from employees e
join levels l on e.employee_id = l.employee_id
join agg a on e.employee_id = a.employee_id
order by l.level, a.budget desc, e.employee_name;

1. upward CTE (up_chain)

   • row 수가 직원 수 × 트리 높이 정도로만 증가
   • manager_id is null 조건으로 조기에 recursion 종료 → 효율적

2. downward CTE (down_chain)

   • 팀/예산 계산용으로만 사용
   • 하지만 ancestor 중심으로 확장되므로 aggregation 한 번으로 모든 상사 서브트리를 커버

3. 결과 조합 단계

   • upward로 얻은 level + downward로 얻은 team_size/budget을 조인