성능 모델 — 한 홉의 비용은 무엇으로 이루어지는가

이 문서가 답하는 질문

• 이 엔진에서 "한 홉"의 비용은 정확히 어떤 항목의 합인가?
• Apache AGE 대비 우리가 실제로 없앤 비용은 무엇이고, 그대로 남아 있는 비용은 무엇인가?
• 홉이 깊어질 때 비용은 어떤 함수로 늘어나는가?
• 이 모델에서 어디까지가 측정된 사실이고, 어디부터가 추정인가?

1. 사실 — 한 홉이 컴파일되는 실제 SQL

MATCH (a:P)-[:K]->(b:P) WHERE a.val = 7 RETURN count(b) 는 engine/src/cypher/compile.rs:900-906 이 만드는 다음 형태로 내려간다 (별칭 번호는 compile.rs:288-291 의 fresh() 규칙을 따른다).

SELECT jsonb_build_object('count(b)', t.c0) AS row FROM (
SELECT count(( jsonb_strip_nulls(jsonb_build_object(
                 '_id', n2.id, '_type', og_type_name(n2.type_id),
                 'name', to_jsonb(n2.p_name), 'val', to_jsonb(n2.p_val)))
             || COALESCE(n2.__ext,'{}'::jsonb) )) AS c0
  FROM og_data.v_2 n1
  CROSS JOIN LATERAL (SELECT u.nbr, u.eid
                        FROM og_data.og_adj adj3,
                             LATERAL unnest(adj3.nbr, adj3.eid) AS u(nbr, eid)
                       WHERE adj3.src = n1.id
                         AND adj3.dir = 'o'::"char"
                         AND adj3.etype = ANY(ARRAY[3]::int4[])) u4
  CROSS JOIN og_data.v_2 n2
 WHERE n2.id = u4.nbr
   AND (n1.p_val IS NOT DISTINCT FROM 7)
) t

세 가지를 이 SQL에서 바로 읽을 수 있다.

1. 라벨은 런타임 비용이 0이다. (a:P) 는 og_data.v_2 라는 구체 테이블들의 UNION ALL 뷰로 컴파일 시점에 확정된다 (engine/src/cypher/views.rs:93-138). 런타임에 계층을 걷는 코드는 없다.
2. 도착 노드 n2 는 별도 릴레이션으로 다시 조인된다. og_adj 가 이웃 id를 이미 들고 있음에도, 라벨 확인과 프로퍼티 접근을 위해 타입 뷰를 id로 재조회한다.
3. WHERE a.val = 7 은 = 가 아니라 IS NOT DISTINCT FROM 으로 내려간다 (compile.rs:1377). 같은 조건을 인라인 맵으로 쓴 (a:P {val: 7}) 은 push_prop_filters (compile.rs:803-815)를 지나 n1.p_val = 7 이 된다. 두 표기가 서로 다른 SQL을 만든다는 것은 코드에서 확인한 사실이고, 그것이 계획에 미치는 영향은 05_planner_interaction.md §4 와 PERF-01 에서 다룬다.

2. 사실 — 한 홉의 비용 항목

시작 노드 하나, 해당 관계 타입·방향의 차수를 d 라 할 때, 위 SQL이 하는 일은 다음 다섯 가지다.

og_adj 한 행은 이웃 최대 256개를 int8[] × 2 = 4 KB 로 들고 있고 STORAGE MAIN 으로 TOAST를 막아 놓았으므로 (bootstrap.sql:210-211), C2는 차수와 거의 무관한 상수다. C2가 이 설계의 핵심이다.

3. 사실 — AGE 대비: 없앤 비용과 남은 비용

Apache AGE에서 한 홉은 대략 이렇다 (docs/comparison.md "Traversing"):

즉 우리가 구조적으로 없앤 것은 첫 줄뿐이다. 두 번째 줄은 그대로 남아 있고, 1홉의 논리 페이지 접근이 두 시스템에서 거의 같은 이유가 이것이다.

50,000 노드 / 974,936 엣지, 1홉 논리 페이지 접근 (bench/results/bench-50000-20260806T042833Z.json):

README도 이 점을 명시한다 — "a single indexed hop through AGE reads about as many pages as we do" (README.md:41-42). 저장 구조의 이득은 실제로 존재하지만(389 대 1,707), Cypher 표면을 지나면 대부분 사라진다(1,742). 그 차이가 어디에서 오는지는 03_hot_paths.md 에서 단계별로 센다.

4. 사실 — k홉으로 갈 때의 비용 함수

세 가지 서로 다른 함수가 있고, 어떤 것이 적용되는지는 04_deep_traversal_mechanics.md 의 전환 판정이 정한다.

og_vlp 의 곡선이 정확히 평균 차수라는 것은 측정으로 확인되어 있다: dense 픽스처(50,000 노드 / 999,784 엣지, 평균 차수 20)에서 0.51 → 6.85 → 106.72 → 2,300 → 49,334 ms 로 홉당 13, 16, 22, 21배 (docs/deep-traversal.md, bench/csr/results/deep-dense-20260817T021522Z.json).

중요한 비대칭: og_reach 로 바뀌어도 C4·C5는 사라지지 않는다. BFS는 노드 id만 돌려주지만, Cypher는 그 id마다 다시 타입 뷰를 조인하고 jsonb를 만든다. 50,000 노드 4홉에서 측정된 페이지 수가 그 값이다 (bench/results/bench-50000-20260817T033001Z.json):

4홉에서 도달 노드는 약 50,000개이므로, 노드 하나당 약 3.6 페이지가 C4+C5에 쓰인다(추정 — 179,032 / 50,000). 이것이 이 코드베이스에서 가장 큰 단일 최적화 여지다 (PERF-02, PERF-03).

5. 사실 — 쓰기 한 건의 비용 구성

읽기와 달리 쓰기는 SQL 한 문장이 아니라 Rust에서 행 단위로 SPI를 호출하는 절차다 (engine/src/cypher/mod.rs:236-243 의 per-env 루프).

정확한 횟수는 03_hot_paths.md §3 에서 코드를 세어 산출한다. W6의 append는 SET nbr = a.nbr || $4 형태의 UPDATE (adjacency.rs:22-31)이므로, 이웃 1개를 추가할 때 MVCC 규칙상 최대 4 KB짜리 튜플 전체가 새 버전으로 다시 쓰인다. 이것이 이 설계가 읽기에서 얻은 이득의 대가다.

6. 결정 — 이 모델이 담고 있는 설계 결정

7. 사실 — "access.sql은 전부 인라인된다"는 주장의 정확한 범위

access.sql:1-9 의 주석은 모든 함수가 인라인되어 "플래너가 순회 스캔 자체를 본다"고 말한다. 코드를 읽고 확인한 정확한 범위는 다음과 같다.

• og_expand 의 실제 호출자는 portal/server/index.js:262,266 와 하네스의 ontological_raw 행(bench/harness.py:398-401)뿐이다.
• og_nodes / og_edges / og_subtype_ids 는 engine/src/ 어디에서도 호출되지 않는다 (grep 으로 확인). 즉 브리핑이 우려한 type_id IN (SELECT og_subtype_ids(...)) 형태는 Cypher 계획에 등장하지 않는다. 라벨 스캔은 항상 타입 뷰의 UNION ALL 이다.
• LANGUAGE sql SRF의 인라인 여부는 PostgreSQL의 inline_set_returning_function() 이 결정하며, CTE를 포함한 본문은 인라인되지 않는 것으로 알려져 있다. 이 문서는 그 동작을 소스로 확인하지 않았다. 확인 방법: EXPLAIN 출력에 Function Scan on og_vlp 노드가 나타나면 인라인되지 않은 것이다.

8. 사실 vs 추정 — 이 문서의 신뢰도 구분