Datalog를 GPU에서 돌리면 어떻게 될까: 선언형 쿼리의 새로운 가능성

Datalog가 뭐고, 왜 GPU에서 돌리는 게 흥미로운가

혹시 Datalog라는 언어 들어보셨어요? 이름은 좀 낯설지만, 사실 SQL의 사촌쯤 되는 선언형 쿼리 언어예요. 1980년대 데이터베이스 이론에서 출발했는데, 최근에 정적 분석(static analysis), 보안 취약점 탐지, 프로그램 검증 같은 분야에서 다시 각광받고 있어요. Facebook의 코드 분석 도구나 Soufflé 같은 오픈소스 분석기가 다 Datalog 기반이에요.

Datalog의 핵심 아이디어는 "규칙(rule)"을 정의하면 시스템이 알아서 모든 결론을 도출해준다는 거예요. 예를 들어 "A는 B의 부모다", "B는 C의 부모다"라는 사실(fact)이 있고, "X가 Y의 조상이다 IF X가 Y의 부모이거나, X가 누군가의 조상이고 그 누군가가 Y의 조상이라면"이라는 규칙(rule)이 있으면, 시스템이 자동으로 "A는 C의 조상이다"라는 결론을 끌어내요. 이런 걸 재귀적 추론(recursive inference) 이라고 해요.

최근 ACM(컴퓨터 학회)의 PPoPP 학회에 "Optimizing Datalog for the GPU"라는 논문이 발표됐어요. 이름 그대로 Datalog를 GPU에서 효율적으로 돌리는 방법을 다룬 연구예요. 왜 이게 흥미로운지 같이 풀어볼게요.

왜 GPU에 올리려고 할까

GPU는 원래 그래픽 처리용으로 만들어졌지만, 지금은 AI 학습이나 과학 계산의 핵심 도구가 됐어요. 이유는 단순해요. 수천 개의 작은 코어가 동시에 같은 작업을 병렬로 처리할 수 있기 때문이에요. CPU가 "한 번에 한 사람이 정성스럽게 요리하는 셰프 8명"이라면, GPU는 "단순한 작업을 동시에 하는 알바생 5,000명"인 셈이에요.

Datalog의 핵심 연산은 사실 GPU에 잘 맞아요. 가장 많이 쓰이는 연산이 조인(join) 인데, 이건 두 개의 큰 테이블을 합치는 작업이에요. SQL 써본 분이라면 익숙하실 거예요. 그리고 중복 제거(deduplication), 고정점 계산(fixpoint iteration) 같은 연산도 핵심이에요. 고정점 계산이 뭐냐면, 더 이상 새로운 사실이 생기지 않을 때까지 규칙을 계속 적용하는 과정이에요.

이런 연산들은 데이터가 많을 때 "같은 일을 수많은 행에 동시에 적용"하는 형태라서 GPU 병렬화의 좋은 후보예요. 다만 실제로 옮기는 건 쉬운 일이 아니에요. 왜냐하면 GPU는 메모리 접근 패턴과 분기 처리(branch divergence) 에 매우 민감하거든요.

논문이 풀어낸 핵심 최적화들

이 논문에서 다루는 주요 기법들을 풀어볼게요. 일단 GPU에서 조인을 효율적으로 하려면 데이터 구조부터 GPU 친화적으로 만들어야 해요. 일반적인 해시 테이블은 GPU에서 잘 안 돌아가요. 메모리 접근이 산발적(random access)이라서 캐시 효율이 떨어지거든요. 그래서 정렬 기반 조인(sort-merge join) 이나 GPU 최적화 해시 테이블을 쓰는 게 일반적이에요.

또 하나 중요한 게 증분 평가(incremental evaluation) 예요. Datalog는 규칙을 반복해서 적용하면서 새로운 사실을 만들어내는데, 매번 전체를 다시 계산하면 너무 비효율적이에요. 그래서 "이번 라운드에서 새로 생긴 사실"만 가지고 다음 라운드 계산을 하는 식으로 최적화해요. 이걸 세미나이브 평가(semi-naive evaluation) 라고 부르고요.

GPU에서는 이걸 한 단계 더 발전시켜서, GPU 메모리에 상주하는 자료구조를 유지하면서 호스트(CPU)와의 데이터 전송을 최소화하는 게 핵심이에요. PCIe 버스를 통한 데이터 전송이 GPU 계산보다 훨씬 느리기 때문에, 한 번 GPU로 보낸 데이터는 거기서 끝까지 처리하는 게 좋아요.

어디에 쓸 수 있나

이 연구의 실용적 의미를 알려면 Datalog가 어디에 쓰이는지 봐야 해요. 가장 큰 분야가 정적 코드 분석(static analysis) 이에요. 큰 코드베이스에서 보안 취약점이나 버그를 찾을 때, "이 변수가 사용자 입력에서 출발해서 SQL 쿼리에 도달하는 경로가 있는가?" 같은 질문을 Datalog로 표현해요. 이걸 Taint Analysis(오염 분석) 라고 하죠.

Facebook의 코드 분석 도구 Infer, Doop이라는 Java 분석 도구, Soufflé 같은 도구들이 Datalog를 쓰고 있어요. 그런데 코드베이스가 커지면 Datalog 쿼리 실행 시간이 너무 길어지는 게 문제였어요. 회사 전체 코드를 분석하는 데 몇 시간씩 걸리니까요. 여기서 GPU 가속이 엄청난 의미를 가지는 거예요.

또 그래프 분석, 소셜 네트워크 분석, 지식 그래프 추론 같은 분야에도 응용 가능해요. 이런 분야들은 모두 "관계를 따라가면서 새로운 사실을 도출하는" 작업이라서 Datalog와 잘 맞거든요.

비슷한 흐름의 프로젝트들

Datalog 기반의 대표 도구로 Soufflé가 있어요. C++로 컴파일해서 빠르게 돌아가는 Datalog 엔진이에요. 그리고 Differential Datalog(DDlog) 라는 프로젝트도 있는데, 이건 데이터가 변할 때 결과를 점진적으로 업데이트하는 데 특화돼 있어요. VMware 같은 회사가 네트워크 설정 관리에 쓰고 있어요.

GPU 데이터베이스 쪽으로는 HeavyDB(구 OmniSci) 나 BlazingSQL 같은 프로젝트들이 있어요. SQL을 GPU에서 돌리는 시도들이죠. Datalog의 GPU 가속 연구는 이런 흐름의 연장선에 있다고 볼 수 있어요.

한국 개발자에게 주는 시사점

당장 실무에서 Datalog를 쓸 일은 많지 않을 수 있어요. 하지만 알아두면 시야가 넓어지는 도구예요.

첫째, 선언형 사고방식을 익히는 데 좋은 훈련이 돼요. "어떻게 계산할지"가 아니라 "무엇이 참인지"를 정의하는 방식인데, 이건 SQL을 더 잘 쓰게 만들고 함수형 프로그래밍에도 도움이 돼요.

둘째, 보안이나 코드 품질 관련 일을 한다면 Datalog 기반 도구들을 한 번씩 써보세요. CodeQL(GitHub의 보안 분석 도구)도 Datalog와 비슷한 선언형 쿼리 언어를 써요. 회사 코드베이스의 보안 취약점을 찾는 데 실제로 도움이 돼요.

셋째, GPU 병렬 컴퓨팅의 응용 범위가 점점 넓어지고 있다는 걸 보여주는 사례예요. AI 학습뿐 아니라 데이터베이스, 그래프 분석, 정적 분석까지 GPU가 들어오고 있어요. CUDA나 OpenCL을 한 번쯤 공부해두면 미래에 도움이 될 거예요.

마무리

Datalog의 GPU 최적화 연구는 "오래된 아이디어가 새로운 하드웨어를 만나 다시 빛나는" 좋은 사례예요. 1980년대 데이터베이스 이론이 2020년대 GPU와 만나서 코드 보안 분석을 빠르게 만들어주는 거죠.

여러분은 학교에서 배우거나 옛날에 잠깐 써봤던 기술이 최근 다시 부상하는 걸 본 경험이 있으세요? 함수형 프로그래밍이 다시 뜨고, Rust가 시스템 프로그래밍을 새로 정의하는 것처럼요. 어떤 "오래되고 새로운" 기술이 다시 주목받을 만하다고 생각하세요?