데이터베이스 성능 최적화 때문에 밤을 새워본 경험, 개발자라면 누구나 한 번쯤 있을 겁니다. 저도 주니어 시절, 수십 줄에 달하는 복잡한 SQL 쿼리가 타임아웃을 내뱉을 때마다 식은땀을 흘리곤 했습니다. 당시 제가 할 수 있는 일이라곤 EXPLAIN 명령어를 쳐다보며 인덱스를 덕지덕지 붙이거나, 쿼리 순서를 이리저리 바꿔보는 게 고작이었죠. "옵티마이저가 알아서 잘 해주겠지"라고 믿으면서요. 하지만 데이터 규모가 커지고 조인(Join)해야 할 테이블이 늘어날수록, 기존의 방식으로는 한계에 부딪히는 순간이 옵니다. 오늘은 제가 최근에 흥미롭게 읽은 자료를 바탕으로, 조인이라는 익숙한 개념을 '그래프 이론'의 관점에서 바라보는 이야기를 해보려 합니다. 조금 딱딱하게 들릴 수 있겠지만, 이 원리를 이해하면 데이터베이스가 쿼리를 처리하는 근본적인 한계와 그 돌파구를 볼 수 있습니다.
우리가 흔히 접하는 복잡한 비즈니스 쿼리를 한번 떠올려 봅시다. 예를 들어 TPC-H 벤치마크의 5번 쿼리 같은 경우, 고객(Customer), 주문(Orders), 상품(LineItem), 공급자(Supplier), 국가(Nation), 지역(Region) 등 무려 6개의 테이블이 얽히고설켜 있습니다. 보통 우리는 이걸 "A 테이블과 B 테이블을 조인하고, 그 결과를 C와 조인한다"는 식의 선형적인 단계로 생각합니다. 그런데 이 쿼리를 그래프로 그려보면 어떨까요? 여기서 '노드(정점)'는 조인 조건이 되는 변수(예: custkey, orderkey)가 되고, '엣지(간선)'는 테이블 그 자체가 됩니다. 하나의 테이블이 여러 컬럼(변수)을 포함하므로, 이 그래프는 점 두 개만 잇는 단순한 선이 아니라 여러 점을 동시에 포함하는 '하이퍼그래프(Hypergraph)' 형태를 띠게 됩니다.
이 관점의 전환이 왜 중요할까요? 조인을 그래프로 치환하는 순간, 컴퓨터 과학의 오래된 난제들과 해결책들을 데이터베이스의 영역으로 끌어올 수 있기 때문입니다. 가장 직관적인 예로 '삼각형 찾기' 문제를 들 수 있습니다. 친구 관계 테이블이 있을 때, A와 B가 친구이고, B와 C가 친구이며, C와 A가 친구인 관계를 찾는 것은 SQL의 Self-Join 세 번과 같습니다. 이를 그래프 이론에서는 특정 패턴을 찾는 문제로 봅니다. 그래프 이론에서 말하는 '정점 커버(Vertex Cover)'는 쿼리의 모든 테이블과 연관된 조인 컬럼들의 집합이 되고, '엣지 커버(Edge Cover)'는 모든 조인 컬럼을 포함하는 테이블들의 집합이 됩니다. 단순히 용어만 바뀌는 게 아니라, 최적화의 힌트를 수학적으로 얻을 수 있게 되는 것이죠.
전통적인 데이터베이스 조인 방식은 '이진 조인(Binary Join)'을 기본으로 합니다. 두 테이블을 먼저 합치고, 그 중간 결과물을 다음 테이블과 합치는 식이죠. 여기서 치명적인 문제가 발생할 수 있습니다. 예를 들어 A, B, C 세 테이블을 조인한다고 합시다. 최종 결과는 10건밖에 안 되는데, A와 B를 먼저 조인한 중간 결과가 1억 건이 될 수도 있습니다. 우리는 이 중간 결과가 폭발하는 '최악의 경우(Worst Case)'를 막기 위해 실행 계획을 튜닝하느라 골머리를 앓습니다. 그런데 그래프 이론, 특히 '엣지 커버' 개념을 활용하면 이 쿼리의 결과 크기가 최대 얼마나 될지 수학적인 상한선(Bound)을 미리 계산할 수 있습니다. 이를 AGM(Atserias-Grohe-Marx) 상한이라고 부릅니다.
이론적으로 가장 흥미로운 지점은 여기서 '정수(Integer)' 제약을 '실수(Real Number)'로 완화했을 때 나타납니다. 기존에는 어떤 테이블을 "사용한다(1) 혹은 안 한다(0)"로만 판단하여 상한을 계산했습니다. 하지만 최신 연구인 'Worst-Case Optimal Join(WCOJ)' 알고리즘들은 이 제약을 0과 1 사이의 실수 값으로 확장합니다. 즉, 테이블을 부분적으로 가중치를 두어 계산함으로써 쿼리 결과 크기에 대해 훨씬 더 타이트하고 정확한 상한선을 찾아냅니다. 이렇게 되면 중간 결과가 불필요하게 폭발하는 실행 계획을 원천적으로 배제하고, 수학적으로 증명된 가장 효율적인 경로를 찾을 수 있게 됩니다.
물론 현업에서 당장 오늘부터 SELECT 문을 작성할 때 AGM 상한 공식을 대입해 보라는 뜻은 아닙니다. 하지만 우리가 사용하는 PostgreSQL이나 MySQL 같은 도구들이 왜 특정 쿼리에서 느려지는지, 그리고 차세대 데이터베이스들이 어떤 원리로 이 문제를 해결하려고 하는지(예: RelationalAI나 LogicBlox 같은 시스템)를 이해하는 데는 큰 도움이 됩니다. 개발자로서 10년을 보내며 느낀 건, 결국 기술의 깊이는 '어떻게 쓰느냐'를 넘어 '어떤 원리로 작동하느냐'를 파고들 때 생긴다는 점입니다. 조인을 단순히 테이블 붙이기가 아니라, 거대한 그래프 속에서 패턴을 찾아내는 과정으로 바라보는 상상력. 그 작은 시각의 차이가 엔지니어링의 질을 바꾼다고 생각합니다.
