GraphQL 신입 개발자 코딩·알고리즘 면접

N+1 문제는 부모 데이터 N개를 조회한 후, 각각의 관련 데이터를 가져오기 위해 추가로 N번의 쿼리가 발생하는 문제입니다. 예를 들어 사용자 10명의 게시글을 조회할 때, 사용자 조회 1번 + 각 사용자별 게시글 조회 10번으로 총 11번의 쿼리가 발생합니다. DataLoader는 요청을 배치(batch)로 모아서 한 번에 처리하는 방식으로 이를 해결합니다. 시간 복잡도는 O(N)번의 개별 쿼리에서 O(1)번의 배치 쿼리로 개선되며, 전체 응답 시간이 크게 단축됩니다.

중첩된 쿼리는 트리 구조로 표현되며, 깊이가 d이고 각 레벨에서 평균 b개의 자식을 조회한다면 시간 복잡도는 O(b^d)로 지수적으로 증가합니다. 예를 들어 user -> posts -> comments -> replies 같은 4단계 중첩 쿼리는 데이터량에 따라 수천 번의 조회가 발생할 수 있습니다. Query Depth Limiting은 AST(Abstract Syntax Tree)를 재귀적으로 순회하며 깊이를 측정하는 방식으로 구현합니다. 재귀 함수에서 현재 깊이를 매개변수로 전달하고, 최대 허용 깊이를 초과하면 에러를 반환하는 방식으로 O(n) 시간에 검증할 수 있습니다.

Resolver는 대부분 데이터베이스나 외부 API를 호출하는 I/O 작업을 수행하므로, 동기 처리 시 블로킹으로 인해 전체 응답 시간이 길어집니다. 비동기 처리를 사용하면 I/O 대기 시간 동안 다른 작업을 수행할 수 있습니다. 예를 들어 user, posts, comments 세 필드를 조회할 때, 각각 100ms가 걸린다면 순차 처리는 300ms가 소요됩니다. 하지만 Promise.all을 사용한 병렬 처리는 가장 긴 작업인 100ms만 소요되어 O(max(t1, t2, t3))의 시간 복잡도를 가집니다. 순차 처리의 O(t1 + t2 + t3)에 비해 최대 3배 빠른 응답이 가능합니다.

Offset-based Pagination은 SKIP N, TAKE M 방식으로 동작하며, 데이터베이스는 N개의 레코드를 건너뛰기 위해 실제로 N개를 스캔해야 하므로 시간 복잡도가 O(N+M)입니다. 페이지 번호가 커질수록 성능이 저하됩니다. Cursor-based Pagination은 특정 커서(보통 ID나 타임스탬프) 이후의 데이터를 인덱스로 직접 조회하므로 O(log N + M)의 시간 복잡도를 가집니다. 또한 실시간으로 데이터가 추가되는 상황에서 Offset 방식은 중복 조회나 누락이 발생할 수 있지만, Cursor 방식은 고유한 커서를 기준으로 하므로 이런 문제가 없습니다.

정규화 없이 캐싱하면 같은 User 객체가 여러 쿼리 결과에 중복 저장되어 공간 복잡도가 O(N*M)으로 증가합니다(N은 쿼리 수, M은 평균 객체 수). 정규화를 사용하면 각 객체를 ID 기반으로 한 번만 저장하고 참조하므로 O(N+M)으로 개선됩니다. 또한 User 정보가 업데이트되면 정규화된 캐시는 한 곳만 수정하면 모든 쿼리 결과에 반영되지만, 비정규화 캐시는 중복된 모든 곳을 찾아 수정해야 하므로 업데이트 시간 복잡도가 O(1)에서 O(N)으로 차이납니다.