DAY 28개념·실험속성 그래프 모델

테이블 JOIN과 그래프 순회

같은 ‘친구의 친구’ 질문을 관계형 테이블과 그래프 저장소가 어떻게 따라가는지 비교하고, 그 차이가 어디서 커지고 어디서 작아지는지 봅니다.

약 20분조작형 실험 확인 퀴즈

01 / UNDERSTAND

핵심 개념

관계형 데이터베이스에서는 사람 표 person과 친분 표 knows(from_id, to_id)를 따로 둡니다. ‘민수의 친구의 친구’를 찾으려면 knows 표를 홉마다 한 번씩 JOIN합니다. 각 JOIN에서 엔진은 보통 B-트리 같은 인덱스를 찾아 ‘이 사람이 from_id인 행’을 고릅니다. 홉이 늘수록 JOIN과 인덱스 탐색이 함께 늘어납니다.

네이티브 그래프 저장소는 노드 레코드가 자신에게 연결된 관계를 직접 가리키도록 저장합니다. 이웃으로 갈 때 전역 인덱스를 찾지 않고 저장된 참조를 따라가므로 이를 인덱스 없는 인접(index-free adjacency)이라고 부릅니다. 한 홉의 비용은 표 전체 크기보다 그 노드에 실제로 붙은 관계 수에 좌우됩니다. 그래서 한 시작점에서 여러 홉을 따라가는 국소 순회에 유리합니다.

차이를 과장해서는 안 됩니다. 인덱스 탐색 비용은 표 크기 N에 대해 log N 정도로 천천히 늘고, 관계형 엔진은 해시 조인 같은 다른 전략도 씁니다. Stonebraker와 Pavlo(2024)는 그래프를 노드 표와 엣지 표로 담은 관계형 시스템이 그래프 DBMS보다 빠르게 나온 성능 연구들을 소개하고, SQL:2023에 그래프 질의 확장(SQL/PGQ)이 들어간 점도 짚습니다.

정리하면 그래프 저장소의 이점은 ‘특정 시작점에서 깊게 따라가는’ 질문에서 두드러지고, ‘모든 행을 읽어 묶어 세는’ 집계나 대량 스캔에서는 작거나 없습니다. 이런 일에는 관계형·컬럼형 엔진이 강할 수 있습니다. 또 시작 노드를 찾을 때는 그래프에서도 인덱스가 필요합니다(DAY 46). 실험의 숫자는 차이를 보기 위한 교육용 단순 비용 모델이며, 실제 성능은 엔진과 데이터에 따라 다릅니다.

그래프 저장소는 깊고 국소적인 순회에서 JOIN보다 유리할 수 있지만, 전체 스캔과 집계에서는 그 이점이 작습니다.

02 / WORKED EXAMPLE∑

작은 예제로 따라가기

모든 사람이 친구 3명을 가진다고 합시다. 민수에서 2홉을 가면 그래프는 관계 3+9=12개를 따라갑니다.

관계형은 knows 표를 2번 JOIN하며 인덱스 탐색을 1번(민수)+3번(친구들)=4번 합니다. 표가 1,048,576행(2^20)이면 탐색 하나가 이진 탐색 근사로 약 20단계라서 대략 4×20=80단계에 행 읽기 12개가 더해집니다.

‘연구실별 논문 수’처럼 모든 행을 한 번씩 읽어 묶는 질문은 두 방식 모두 전체를 훑어야 하므로 인접 참조의 이점이 거의 없습니다.

03 / EXPLORE

직접 실험해 보기

홉 수를 1에서 4로 올리며 관계형의 JOIN 횟수·인덱스 탐색 수와 그래프의 포인터 수 막대를 비교하고, 사람 수를 바꿔도 어느 쪽 막대가 덜 변하는지 확인하세요. 노트의 ‘교육용 비용 모델’ 문구도 함께 읽으세요.

LIVE EXPERIMENT · JOIN VS TRAVERSAL

홉이 늘 때 JOIN과 포인터 따라가기 비교

민수에서 시작해 KNOWS를 2홉 따라가 닿는 사람을 찾는다. 1인당 친구는 5명이라고 가정한다.

홉 수2홉사람 수10,000명

관계형: 인덱스 탐색 + 행 읽기126

그래프: 포인터 따라가기30

JOIN2회홉마다 knows 자기 조인

인덱스 탐색6번한 번에 16단계 (log₂ 50,000행)

그래프 포인터30전체 사람 수와 무관

SELECT DISTINCT k2.dst AS friend_id
FROM person p
JOIN knows k1 ON k1.src = p.id
JOIN knows k2 ON k2.src = k1.dst
WHERE p.name = '민수';

MATCH (:Person {name: '민수'})
      -[:KNOWS*2]->(f:Person)
RETURN DISTINCT f.name;

홉별 계산 — 프런티어는 그 홉에서 출발하는 사람 수
홉	프런티어	관계형 인덱스 단계	그래프 포인터
1	1	1×16 = 16	1×5 = 5
2	5	5×16 = 80	5×5 = 25

교육용(학습용) 단순 비용 모델이다. 관계형은 사람 수가 늘면 인덱스 깊이(log₂)가 커지고, 그래프는 저장된 인접 포인터를 따라가므로 만진 부분만큼만 일한다(index-free adjacency). 실제 성능은 엔진·캐시·데이터 분포에 따라 다르며, 전체 집계·스캔은 관계형이 더 유리할 수 있다.

04 / RECALL & PRACTICE

이번에는 직접 풀어 보세요

정답을 보기 전에 계산과 이유를 적어 보세요. 해설과 비교하고 확인 표시를 남기면 완료할 수 있습니다.

문제 1

모든 사람이 친구 4명을 가진다고 할 때, 한 사람에서 3홉 순회를 하면 그래프가 따라가는 관계 수, 관계형의 JOIN 횟수, 인덱스 탐색 횟수를 각각 구하세요(중복 방문은 무시).

힌트 보기

홉마다 사람 수가 4배가 됩니다. 인덱스 탐색은 각 홉에서 출발하는 사람 수만큼 일어납니다.

풀이와 비교하기

관계는 4+16+64=84개입니다. JOIN은 홉마다 1번씩 3번이고, 인덱스 탐색은 1+4+16=21번입니다. 결과가 4배씩 늘어나는 것은 두 방식이 같고, 차이는 탐색 하나하나의 비용에서 생깁니다.

내 풀이를 해설과 비교하고 다른 점을 확인했어요.

풀이와 확인 표시는 이 브라우저에 저장됩니다.

YOUR NOTES

오늘 이해한 것과 다시 볼 것

계산이 달라진 이유, 헷갈린 개념, 다음에 확인할 질문을 남겨 보세요.

메모는 이 브라우저에 저장됩니다. 홈에서 전체 기록을 내려받을 수 있습니다.

05 / CHECK YOURSELF

오늘의 이해 확인

인덱스 없는 인접(index-free adjacency)의 핵심 아이디어로 맞는 것은?

완료 조건: 확인 퀴즈 정답 · / 직접 풀기 0/1

더 깊이 읽기

예제와 실험 데이터는 이 과정을 위해 만든 것입니다. 원문은 선택 자료이며, 강의와 직접 풀기만으로도 다음 회차를 이어갈 수 있습니다.

What is a graph databaseNeo4j Getting Started What Goes Around Comes Around... And Around...Stonebraker & Pavlo (2024), SIGMOD Record Survey of graph database modelsAngles & Gutierrez (2008)

이 자료는 개념 학습용입니다. 실제 데이터베이스·라이브러리·플랫폼의 동작과 설정은 제품과 버전마다 다를 수 있습니다.