RDBMS에서 기간 쿼리 최적화하는 방법 소개 with 누적합, 비트셋

개요

비즈니스 요구사항에서 기간 단위 집계 쿼리가 등장하는 경우는 매우 흔하다.

기간 쿼리를 단순한 RDBMS 집계로 구성하면 기간에 포함된 모든 튜플을 읽어 집계해야 하므로, 기간이 길어질수록 스캔 대상이 선형적으로 증가하고 집계 비용이 $O(N)$으로 누적된다.

인덱스로 Range Scan이 보장되더라도 읽어야 할 튜플 수 자체는 줄어들지 않기 때문에, 장기 구간 조회에서는 결국 병목이 발생한다.

따라서 기간 쿼리에는 적절한 최적화 전략이 필요하다. 이번 포스트에서는 누적합과 비트셋을 활용한 기간 쿼리 최적화 기법을 살펴보고자 한다.

배경 지식

Prefix Sum

Prefix Sum(누적합)은 구간 $l$에서 $r$까지의 합을 구할 때, 임의의 시작 지점 $s$부터 값을 미리 누적해두고 다음과 같이 원하는 구간의 합을 구하는 기법이다.

$\text{sum}(l, r) = \text{prefix}[r] - \text{prefix}[l-1]$

• 누적합 배열 생성: $O(N)$
• 특정 구간 합 조회: $O(1)$

사전에 한 번의 $O(N)$ 비용을 지불하는 대가로, 이후의 모든 구간 조회를 상수 시간에 처리할 수 있게 된다.

누적합의 대수적 조건

누적합을 적용하려면 연산이 특정 대수적 조건을 만족해야 한다.

누적합 배열을 구성하는 것만이 목적이라면 결합법칙과 항등원을 갖는 모노이드로 충분하지만, 구간 추출(역연산)까지 필요하다면 여기에 역원까지 요구되는 군(Group)을 만족해야 한다.

덧셈은 군을 형성하기 때문에 누적합 → 구간합이 자연스럽게 성립하지만, 집합의 합집합(Union)처럼 멱등성을 갖는 연산은 역원이 존재하지 않아 누적합 방식으로는 구간 추출이 불가능하다. 이 차이가 뒤에서 비트셋이 등장하는 이유가 된다.

기간 쿼리 최적화

흔한 KPI 대시보드를 가정해 보자. 매출, 신규 가입자 수, 리텐션, DAU 등이 있겠다.

매출

매출은 일반적으로 정수의 합으로 구할 수 있다. 정수 집합은 덧셈에 대한 군을 형성하므로 누적합을 바로 활용할 수 있다.

RDBMS에서는 이벤트 발생 시간을 기준으로 정렬하고, 정렬된 값을 바탕으로 일(day) 혹은 시(hour) 단위로 사전 집계한 Pre-aggregation 테이블을 구성한다. 실제 조회 시에는 이 테이블에 대한 누적합과, 경계 구간에 대한 실시간 집계를 합성하는 방식이 일반적이다.

예를 들어 "3월 14일 오전 10시부터 4월 2일 오후 3시까지의 매출"을 구한다면,

• 3월 15일부터 4월 1일까지는 일 단위 Pre-aggregation 테이블의 누적합으로 $O(1)$에 조회
• 3월 14일 10시 이후, 4월 2일 15시 이전 구간만 원본 테이블에서 실시간 집계

이러한 Sliding Window 패턴을 적용하면 대부분의 쿼리 비용이 경계 구간의 작은 범위로 한정된다.

전제 조건은 매출 데이터에 시간 메타데이터가 존재해야 한다는 것이며, 대부분의 서비스에서는 이미 존재할 것이다.

신규 가입자 수

신규 가입자 수는 조금 까다롭다. 가입이라는 행위는 회원 데이터가 처음 생성되는 시점을 의미한다.

회원 데이터의 최초 생성 시점이 컬럼에 기록되어 있거나 추론할 수 있다면 카운팅 문제로 치환할 수 있다. 카운팅은 단순 덧셈이므로 군을 형성하고, 누적합을 그대로 적용할 수 있다.

탈퇴 개념을 추가하면 어떻게 될까?

탈퇴는 가입의 역연산으로 정의할 수 있고, 현재 회원 수는 다음과 같다.

$\text{현재 회원} = \text{전체 가입} - \text{탈퇴}$

여기까지는 단순한 뺄셈이므로 누적합으로 처리할 수 있다. 그런데 "특정 기간 동안 활동한 고유 회원 수"처럼 중복 제거가 필요한 지표가 등장하면 문제가 달라진다. 합집합과 차집합 연산은 멱등성을 가지며, 정수 덧셈과 같은 역원이 존재하지 않기 때문에 누적합을 직접 적용할 수 없다.

이때 비트셋을 도입하면 문제의 구조가 바뀐다. 각 회원을 비트 하나에 매핑하면, 집합 연산이 비트 연산으로 치환된다.

• 합집합: $A\ |\ B$
• 교집합: $A\ \&\ B$
• 차집합: $A\ \&\ \sim B$

비트 OR 연산은 결합법칙과 멱등성을 만족하므로, 일 단위 비트셋을 사전 계산해두고 기간 조회 시 OR로 병합하는 방식으로 "고유 회원 수" 같은 카디널리티 지표를 효율적으로 구할 수 있다.

PostgreSQL은 bit varying 타입과 비트 연산자를 네이티브로 지원하며, 대규모 데이터에서는 RoaringBitmap처럼 압축된 비트셋 자료구조를 쓰는 것이 일반적이다. RoaringBitmap은 희소(sparse) 구간과 밀집(dense) 구간을 구분해 저장함으로써, 수억 단위 사용자 ID도 메모리 효율적으로 다룰 수 있다.

비트셋 용량조차 부담스럽다면 HLL(HyperLogLog)과 같은 확률형 자료구조를 고려할 수 있다. 포함-배제 원리를 응용해 Count(A ∪ B) = Count(A) + Count(B) - Count(A ∩ B) 같은 식으로 여러 집합의 카디널리티를 합성할 수 있으며, 메모리 사용량이 로그 스케일로 제한된다. 다만 일정 수준의 오차를 허용해야 한다.

응용 범위

수학에서 카디널리티(cardinality)는 집합에 포함된 고유한 원소의 개수를 의미하는데, 방금 다룬 문제가 바로 특정 집합의 카디널리티를 구하는 문제이다.

지금까지 누적합과 카디널리티를 살펴보았다. 동일한 방식으로 다음과 같은 지표도 처리할 수 있다.

• 평균, 성장률, 처리량
• 고유 방문자(Unique Visitor)
• 잔존율(Retention)
• 코호트 분석(Cohort Analysis)

User Journey 분석

더 복잡한 문제를 풀어보자.

요구사항: 프로모션 페이지를 본 사용자가 연관 상품을 경유해 특정 상품을 구매한 경우를 집계하고, 프로모션별로 상품 데이터를 구하고 싶다.

즉 User Journey를 기간 쿼리로 구하는 것이다. 이 역시 앞서 살펴본 카디널리티와 누적합 문제로 치환할 수 있다.

방법 1: Path Enumeration

간단하게 해결하는 방법은 Path Enumeration 기법이다. 모든 이벤트 경로를 다음과 같이 기록한다.

a
a -> b
a -> b -> c

a -> b -> c 이벤트를 시간 메타데이터와 함께 기록할 수 있다면, 곧바로 카운팅 문제로 치환된다.

문제는 쓰기 폭증이다. 단계가 $k$개라면 한 사용자의 단일 여정마다 최대 $k$개의 경로 레코드가 쌓이므로, 단계가 늘어날수록 저장 비용과 쓰기 QPS가 기하급수적으로 증가한다. 단계가 짧고 변형이 적은 도메인에서만 유효한 선택이다.

방법 2: Bitmask

각 단계를 비트 하나로 정의한다.

단계	행동	비트마스크
Step 1	프로모션 페이지 조회	001
Step 2	연관 상품 클릭	011
Step 3	특정 상품 구매	111

모든 단계를 완료한 111 값의 카운트만 집계하면 퍼널의 최종 전환 수가 된다. 비즈니스 요구사항에 따라 이전 비트가 켜져 있을 때만 다음 비트를 켤 수 있게 제약하면, "순서를 반드시 지켜야 하는 경로"라는 경로 의존성도 자연스럽게 표현된다.

Path Enumeration 대비 쓰기량이 사용자당 하나의 레코드로 고정되므로, 긴 퍼널에도 확장성이 좋다.

방법 3: 다른 도구에 위임하기

사실 이 모든 것을 꼭 RDBMS 쿼리로 해결할 필요는 없다.

User Journey 분석은 본질적으로 OLAP 성격의 질의이며, OLTP 서비스와 같은 RDBMS에서 수행하면 서비스 트래픽에 영향을 줄 수 있다. 이러한 종류의 분석은 GA4와 같은 제품 분석 도구에 위임하거나, CDC(Change Data Capture)를 통해 변경 이벤트를 분석 전용 저장소로 흘려보낸 뒤 DuckDB, ClickHouse, BigQuery와 같은 OLAP 특화 엔진에서 처리하는 것이 일반적인 선택이다.

즉, 쿼리 최적화의 마지막 단계는 "더 나은 쿼리를 짜는 것"이 아니라 "이 질의를 어느 저장소에 맡길 것인가"를 재설계하는 것일 수 있다.

맺으며

기간 쿼리는 단순해 보이지만, 그 아래에는 "어떤 연산이 대수적으로 누적 가능한가"라는 대수적 구조의 문제와 "어떤 자료구조로 집합을 표현할 것인가"라는 자료구조의 문제가 동시에 깔려 있다.

덧셈으로 충분한 지표는 누적합으로, 중복 제거가 필요한 지표는 비트셋으로, 오차를 감당할 수 있는 대규모 지표는 HLL로, 그리고 쿼리 자체의 성격이 OLAP이라면 저장소 자체를 분리하는 것이 합리적인 선택이다.