04 — 실행 트리 순회 (Execution Tree Traversal)

질문: 쿼리 한 장이 응답 JSON 한 장이 될 때, 그 모양은 정확히 어떻게 만들어지는가? 한 줄 답: 실행은 깊이 우선 트리 순회다. 형제 노드는 parallel, 자식 노드는 부모가 끝나야 시작. 결과적으로 응답은 쿼리와 동형이다 — 이게 GraphQL의 가장 강력한 invariant다.

Why — 동형이라는 invariant

GraphQL이 REST·gRPC와 결정적으로 다른 한 가지가 있다.

응답은 쿼리와 같은 모양이다.

query {
  user(id: "1") {
    name
    posts {
      title
    }
  }
}

{
  "data": {
    "user": {
      "name": "Ada",
      "posts": [
        { "title": "First" },
        { "title": "Second" }
      ]
    }
  }
}

쿼리의 모든 필드가 응답의 같은 위치에 있다. 순서·중첩·이름까지 동일.

왜 이게 중요한가

결과	무엇이 가능해지는가
클라이언트가 응답 모양을 예측 가능	TypeScript 타입을 쿼리에서 자동 생성 (codegen)
응답이 그래프 구조의 부분 사진	클라이언트 정규화 캐시 (Apollo, Relay)
같은 필드 = 같은 응답 키	fragment 합성이 단순해진다
path가 결정적	에러 path가 응답상 정확한 좌표

이 invariant가 깨지면 GraphQL의 대부분의 장점이 사라진다. 그래서 실행 모델이 트리 순회로 강제된다.

How — 깊이 우선 트리 순회

1) 쿼리 AST = 실행 계획

쿼리가 파싱되면 트리가 된다.

query {
  users {
    name
    posts {
      title
    }
  }
}

executor는 이 트리를 깊이 우선으로 평가한다.

2) 깊이 우선 + 형제 parallel

ExecuteSelectionSet(Query):
  [parallel]
  └─ users → 리졸버 호출 → [u1, u2, u3]
     [for each user, parallel]
     ├─ u1
     │   [parallel]
     │   ├─ name  → "Ada"
     │   └─ posts → 리졸버 호출 → [p11, p12]
     │       [for each post, parallel]
     │       ├─ p11 { title → "First"  }
     │       └─ p12 { title → "Second" }
     ├─ u2 (같은 구조, 동시 진행)
     └─ u3 (같은 구조, 동시 진행)

부모-자식 관계는 순서 의존 (부모가 끝나야 자식 시작)
형제 관계는 무순서 (parallel)
리스트 안의 원소도 형제 — 각 원소가 독립 sub-tree

3) 응답 합성 — bottom-up

title(p11) = "First"   ←─ 리프
title(p12) = "Second"

posts(u1) = [{title:"First"}, {title:"Second"}]  ←─ 한 단계 위에서 합성
name(u1)  = "Ada"

u1 = { name: "Ada", posts: [...] }  ←─ 또 한 단계 위
u2, u3 similarly

users = [u1, u2, u3]  ←─ 최상위

{ data: { users: [u1, u2, u3] } }

리프(scalar)에서 시작해서 부모로 합성되어 올라간다. 트리 모양 그대로.

What — fan-out 비용

”리졸버는 형제 수만큼 호출된다”

query {
  users {            # 1번 호출 → 100명
    name             # 100번 호출 (default resolver, 사실상 무료)
    posts {          # ★ 100번 호출 — 각 user마다
      title          # posts 총합이 1000개면 1000번
      author {       # ★ 1000번 호출 — 다시 user 조회
        name
      }
    }
  }
}

users: 1 query
posts: 100 queries (user당 1개) → N+1 문제
author: 1000 queries (post당 1개) → 또 N+1

이게 03 챕터의 N+1 & DataLoader가 풀어야 할 문제다. 트리 순회는 공짜가 아니다.

비용 = 트리의 노드 수

total resolver calls = Σ (각 레벨의 노드 수)
                     = users(1) + posts(N) + author(N×M)

GraphQL의 cost analysis (07-security-governance)가 깊이 × 폭을 추정하는 이유가 여기다.

응답 = 쿼리의 깊이만큼 중첩

{ a { b { c { d { e { f { ... } } } } } } }

→ 응답 JSON도 6단계 중첩. 깊이 제한이 없으면 클라이언트가 서버를 골탕먹일 수 있다. depth limit이 등장하는 자리.

What-if — 잘못 이해하면

1) “한 쿼리는 한 번에 평가된다고 가정”

// ❌ 비효율 — 각 user마다 db hit
User: {
  posts: async (user) => db.posts.findMany({ where: { authorId: user.id } }),
}

users 100명이면 100번 query. 트리의 각 노드가 독립 호출임을 잊은 결과다.

2) “응답 모양은 변할 수 있다”

응답 모양은 쿼리 AST에 의해 결정된다 — 절대로 서버 마음대로 키를 빼거나 더할 수 없다. 서버가 데이터가 없어서 빼고 싶다면? null로 둔다 (또는 NonNull이면 부모로 전파).

3) “트리는 평탄화할 수 있겠지”

{
  user(id: "1") { ...Fields }
}
fragment Fields on User { id name email }

fragment는 문법적 편의고, AST 레벨에서는 CollectFields가 펼친다. 그래서 응답 모양은 fragment 사용 여부와 무관 — 항상 동형.

4) “리스트 원소도 parallel 안 되겠지”

된다. 100명의 사용자에 대한 100개의 posts 리졸버는 동시에 호출된다 (Promise.all). 그래서 DataLoader가 그 100개를 한 batch로 묶을 수 있다 — single event loop tick 안에 모두 들어오니까.

5) “응답 키 == 필드 이름”

aliase를 쓰면 다르다.

{
  me: user(id: "1") { name }   # 응답 키는 "me"
  other: user(id: "2") { name } # 응답 키는 "other"
}

{ "data": { "me": {...}, "other": {...} } }

응답 키는 alias 우선, 없으면 fieldName. info.path도 alias를 따른다.

Insight — 동형성이 풀어주는 것들

”응답 ≅ 쿼리”라는 invariant가 만든 생태계

이 한 가지 사실이 GraphQL 생태계 전체를 가능하게 한다.

도구	이 invariant를 어떻게 활용?
GraphQL Codegen	쿼리 문자열에서 응답 TypeScript 타입을 정확히 생성
Apollo Client / Relay	응답을 트리째 정규화 — entity 단위로 캐시
GraphiQL / Apollo Studio	쿼리 입력만으로 응답 모양 프리뷰
persisted queries	쿼리 해시 → 항상 같은 응답 모양 → CDN 캐시 가능
federation	subgraph 응답들이 같은 트리 좌표에서 합성됨

REST는 엔드포인트마다 응답 모양이 다르고, 같은 엔드포인트라도 서버 마음대로 필드 추가/삭제가 가능하다. 그래서 클라이언트 타입 자동 생성이 어렵다 (OpenAPI도 가능하지만 수작업 스키마 동기화가 필요).

”Lee Byron이 2015년 React Confidence Talk에서 강조한 한 줄”

GraphQL 공동 창시자 Lee Byron의 원조 발표에서 가장 자주 인용되는 문장:

“The shape of the response matches the shape of the query.”

이게 단순한 디자인 선택이 아니라 전체 시스템의 invariant임을 보여준 게 GraphQL의 핵심 기여다.

”트리 vs 그래프 — 응답은 트리, 데이터는 그래프”

스키마는 그래프다 (User → Post → Author → User로 cyclic). 하지만 응답은 항상 트리다 — 쿼리가 방문 경로를 정한 순간 그래프가 트리로 unfold된다.

{
  user(id: "1") {
    posts {
      author {        # 같은 user를 다시
        posts {       # 같은 posts를 다시
          author { name }   # depth가 늘어남
        }
      }
    }
  }
}

응답에는 같은 user가 두 번 등장한다 (다른 좌표에). 클라이언트 정규화 캐시는 이걸 다시 그래프로 접어준다 — entity id로 dedup (05-cache-performance).

”왜 깊이 우선인가 — 너비 우선이면 안 되나”

bottom-up 합성이 필요하기 때문이다. 부모 응답이 모든 자식의 평가 결과를 담아야 하니, 자식이 먼저 끝나야 한다. 같은 레벨끼리는 parallel이지만, 한 가지(전체) 흐름은 DFS.

너비 우선이라면 응답 트리를 맨 마지막에 한꺼번에 합성해야 하는데, 그러면 streaming/incremental delivery(@defer, @stream)가 완전히 다른 모델이 된다. spec은 DFS를 골랐다.

요약

응답은 쿼리와 동형이다 — 깊이 우선 트리 순회 + 형제 parallel + bottom-up 합성. 이 invariant 위에 codegen·정규화 캐시·federation·persisted query가 모두 서 있다. 트리 순회는 공짜가 아니다 — 노드 수만큼 리졸버가 호출되고, 거기서 N+1이 태어난다.

다음: 05 — 에러와 부분 응답 — 트리 순회 중 한 노드가 실패하면 응답에 무슨 일이 일어나는가.

03 — Context와 Info 05 — 에러와 부분 응답 (Errors & Partial Response)