제목
이론상 완벽한 코드가 운영 환경에서 배신할 때: Yannakakis 알고리즘의 역설
본문
스타트업에서 '생존'을 최우선으로 코드를 짜던 시절, 저는 "돌아가면 그만"이라는 생각으로 쿼리를 작성하곤 했습니다. 하지만 대규모 트래픽을 감당해야 하는 지금의 회사로 이직한 뒤, 성능 최적화는 선택이 아닌 필수 생존 기술이 되었습니다. 처음에는 컴퓨터 공학 전공 서적을 다시 뒤적이며 이론적으로 '완벽한' 알고리즘을 찾아 적용하는 데 몰두했습니다. Big-O 표기법이 보장하는 최적의 시간 복잡도만이 정답이라 믿었기 때문입니다. 하지만 최근 데이터베이스 이론에서 '완벽하다'고 칭송받는 Yannakakis 알고리즘(Yannakakis's algorithm)이 실제 현업에서는 단순한 Hash Join보다 2~3배 느릴 수 있다는 사실을 접하고, 개발자로서의 제 시야가 얼마나 좁았는지 뼈저리게 느꼈습니다. 오늘은 그 충격적인 배움과, 이를 통해 얻은 엔지니어링의 본질에 대해 이야기해 보려 합니다.
Yannakakis 알고리즘은 데이터베이스 이론 분야에서 'acyclic joins'를 처리하는 데 있어 사실상 완벽하다고 평가받습니다. 입력과 출력 크기에 비례하는 최적의 복잡도(Instance-optimality)를 가지기 때문입니다. 이론대로라면 불필요한 중간 결과를 생성하지 않으므로 가장 효율적이어야 합니다. 저 역시 복잡한 조인 쿼리 튜닝 과제를 맡았을 때, 중간 데이터 생성을 최소화하는 것이 능사라고 생각했습니다. 하지만 실제 벤치마킹 결과는 달랐습니다. 이 '완벽한' 알고리즘은 결과를 내기 전에 두 번의 세미조인(Semijoin) 패스를 요구합니다. 상향식(Bottom-up)으로 데이터를 축소하고, 다시 하향식(Top-down)으로 걸러낸 뒤, 마지막에 진짜 조인을 수행하는 구조입니다.
문제는 '오버헤드'였습니다. 예를 들어 4개의 테이블을 조인한다고 가정해 봅시다. 일반적인 Hash Join은 3개의 해시 테이블을 만들고 프로빙(Probing)하면 끝납니다. 반면 Yannakakis 알고리즘은 세미조인 과정에서 해시 테이블을 만들고 조회하고 삽입하는 과정을 반복합니다. 최악의 경우, 데이터가 거의 걸러지지 않는다면 일반 조인보다 3배나 많은 해시 조회와 삽입 연산을 수행하게 됩니다. 제가 겪었던 실수도 이와 비슷했습니다. 이론적으로 우아한 로직을 구현하느라, 실제 CPU가 메모리에 접근하는 비용과 해시 충돌 비용을 간과했던 것입니다. "이론상 O(N)이니까 빠르겠지"라는 안일한 생각이 운영 환경의 리소스를 낭비하는 결과를 초래했습니다.
그렇다면 우리는 이 아름다운 이론을 버리고 무식하게 Hash Join만 써야 할까요? 여기서 시니어 개발자의 통찰이 필요합니다. 문제의 핵심은 '메모리 접근 비용'에 있었습니다. 이를 해결하기 위해 등장한 실무적인 해법이 바로 '블룸 필터(Bloom Filters)'입니다. 블룸 필터는 "이 데이터가 집합에 존재하는가?"라는 질문에 대해 "아마도 예" 혹은 "확실히 아니요"를 아주 적은 메모리로 빠르게 답해주는 확률적 자료구조입니다. Yannakakis 알고리즘의 무거운 해시 테이블 연산 대신, CPU 캐시에 쏙 들어가는 가벼운 블룸 필터를 사용해 세미조인을 수행하면 상황은 역전됩니다. 메모리 접근(Locality) 효율이 극적으로 좋아지기 때문입니다. 이는 SQLite나 SQLServer 같은 상용 DB들이 이미 사용하고 있는 기법이기도 합니다.
더 나아가 비즈니스 요구사항을 깊이 파고들면 'Aggregate Pushdown'이라는 또 다른 최적화 지점을 발견할 수 있습니다. 우리가 쿼리를 날릴 때 수백만 건의 로우(Row) 자체를 전부 가져오는 경우는 드뭅니다. 대부분 `GROUP BY`를 통해 특정 카테고리의 최댓값이나 평균 같은 집계(Aggregate) 정보를 원합니다. 이 점을 활용해 조인을 수행하는 동시에 집계 연산을 미리 수행해 버리면(Push down), 데이터의 크기를 획기적으로 줄일 수 있습니다. Yannakakis의 복잡한 3단계를 단 한 번의 패스로 압축할 수 있는 것입니다. 이는 단순히 알고리즘을 개선하는 것을 넘어, "우리가 진짜 필요한 데이터가 무엇인가?"라는 비즈니스 본질을 꿰뚫었을 때 비로소 보이는 최적화입니다.
결국 "완벽한 알고리즘"이란 존재하지 않았습니다. 교과서에 나오는 Big-O 표기법은 하드웨어의 특성(캐시 히트율, 메모리 대역폭)과 실제 데이터의 분포를 반영하지 못합니다. 8년 차 개발자가 된 지금, 저는 주니어 시절처럼 화려한 이론이나 신기술에 맹목적으로 열광하지 않습니다. 대신 그 기술이 동작하는 바닥(Bottom) 레벨의 현실을 직시하고, 우리 서비스가 진짜 필요로 하는 가치에 집중하려 합니다. 코드는 논문 속에 사는 것이 아니라, 물리적인 서버 위에서 돌아가기 때문입니다. 혹시 지금 작성 중인 코드가 이론적으로 완벽하다며 안심하고 계신가요? 그렇다면 한 번쯤 의심해 보시길 권합니다. 그 완벽함이 실제로는 성능을 갉아먹는 주범일지도 모릅니다.
