ParadeDB, 포스트그레스SQL 'Top K' 쿼리 성능 대폭 개선...기존 대비 최대 100배 향상

[한국정보기술신문] 오픈소스 검색 특화 데이터베이스 스타트업 ParadeDB가 포스트그레스SQL(PostgreSQL)에서 'Top K' 쿼리를 최적화하는 자체 기술 방식을 공개했다. 이 회사는 기존 포스트그레스SQL의 인덱스 구조가 복합 필터와 전문 텍스트 검색이 결합된 환경에서 심각한 성능 저하를 보인다는 점을 지적하며, 독자적인 인덱스 설계와 알고리즘으로 이를 극복했다고 밝혔다.

Top K 쿼리란 데이터베이스에서 특정 기준으로 정렬했을 때 상위 K개의 행을 반환하는 연산이다. 예를 들어 "최근 게시물 10개"나 "점수 상위 10개 문서"와 같은 요청이 이에 해당한다. 단순해 보이지만, 실제 운영 환경에서는 필터 조건과 정렬 기준이 복잡하게 얽혀 성능 문제가 발생하기 쉽다.

포스트그레스SQL은 Top K 쿼리 최적화를 위해 주로 B-트리(B-Tree) 인덱스를 활용한다. B-트리는 정렬된 구조이기 때문에 단순한 Top K 검색에는 매우 효율적이다. 예를 들어 1억 건의 로그 데이터에서 최신 10건을 조회하는 쿼리는 인덱스 없이 약 15초가 걸리지만, timestamp 컬럼에 B-트리 인덱스를 생성하면 5밀리초(ms)로 단축된다.

그러나 WHERE severity < 3 같은 추가 필터가 붙는 순간 상황이 달라진다. 포스트그레스SQL은 정렬 인덱스를 따라 걸으면서 조건에 맞지 않는 행을 하나씩 버려야 하거나, 아니면 필터 조건에 맞는 행을 먼저 모아 정렬하는 방식을 택해야 한다. 어느 쪽이든 최악의 경우 다시 15초대로 돌아갈 수 있다.

이를 해결하기 위해 (severity, timestamp) 같은 복합 B-트리 인덱스를 만들 수 있지만, 필터와 정렬 기준의 조합이 늘어날수록 인덱스 수도 폭발적으로 증가한다. 인덱스가 많아지면 저장 공간 낭비, 쓰기 성능 저하, 쿼리 계획 복잡성 증가라는 부작용이 따른다.

포스트그레스SQL 네이티브 전문 검색과 범위 필터를 함께 쓰고 관련도 순으로 정렬하는 쿼리는 GIN 인덱스와 B-트리를 동시에 활용해야 한다. 그런데 GIN은 정렬 순서를 보존하지 않기 때문에 포스트그레스SQL 플래너는 쿼리를 여러 단계로 나눠 처리할 수밖에 없다.

GIN 인덱스로 매칭 행 ID를 추출하고, 해당 행을 테이블에서 가져온 뒤, 추가 필터를 적용하고, 살아남은 행을 정렬한 후, 최종적으로 상위 10건을 반환하는 방식이다. 문제는 GIN이 반환하는 후보 집합이 수백만 건에 달할 경우 테이블 히프 접근 비용이 폭증한다는 점이다. ParadeDB가 1억 건 데이터셋으로 실험한 결과, 최적화된 GIN 인덱스를 사용해도 해당 유형의 쿼리는 33~37초가 소요됐다.

ParadeDB는 이 문제를 근본적으로 다른 방식으로 접근한다. 특정 쿼리 형태에 맞게 인덱스를 미리 설계하는 대신, 검색·필터·정렬에 필요한 모든 필드를 하나의 복합 인덱스에 담는다. 이 인덱스는 반드시 정렬되어 있을 필요가 없으며, 목표는 특정 쿼리를 극한으로 최적화하는 것이 아니라 다양한 형태의 Top K 쿼리를 일관되게 빠르게 처리하는 것이다.

기반 자료구조는 두 가지다. 하나는 역색인으로, 각 검색어를 해당 단어가 포함된 문서 ID 목록(포스팅 리스트)에 매핑한다. 다른 하나는 컬럼형 배열로, 단일 필드를 연속된 배열에 저장하는 방식이다. 컬럼형 배열은 무작위 접근 비용이 O(1)이며, 최솟값·최댓값 메타데이터를 통해 조건에 맞지 않는 전체 컬럼 구간을 건너뛸 수 있다. SIMD(단일 명령 다중 데이터) 명령어를 활용해 여러 값을 한 번의 CPU 연산으로 평가하는 것도 가능하다.

관련도 점수 순으로 정렬하는 쿼리에서는 블록 WAND 알고리즘이 핵심 역할을 한다. 이 알고리즘은 문서 ID 블록 단위로 최고 점수 상한선을 유지하면서, 해당 블록의 최대 가능 점수가 현재 Top K 임계값보다 낮으면 블록 전체를 평가 없이 건너뛴다. 이를 통해 수억 건의 문서 중 실제로 채점이 필요한 블록만 선별적으로 처리하게 된다.

그 결과 동일한 1억 건 데이터셋에서 전문 검색과 필터가 결합된 Top K 쿼리의 응답 시간이 33초에서 300밀리초로 단축됐다.

ParadeDB는 최근 출시한 버전 0.21.0에서 특정 Top K 쿼리 성능을 추가로 최대 30% 향상시켰다. 핵심은 내부 검색 라이브러리 Tantivy의 부울 쿼리 처리 방식 개선이다.

기존에는 AND 조건을 평가할 때 각 이터레이터를 다음 매칭 문서로 실제로 이동시켜야 했다. 이 과정에서 두 이터레이터 사이에 간격이 클 경우 수많은 블록을 스캔해야 했다. 새 방식에서는 이터레이터를 실제로 이동하지 않고 특정 문서 ID의 존재 여부를 더 저렴하게 확인할 수 있게 됐다. 이를 통해 1억 건 데이터에서 해당 쿼리 유형의 응답 시간이 90밀리초에서 70밀리초로 줄었다.