데이터 특성에 따른 최적 구조 선택으로 중복 제거 성능 최대 94배 향상

Context

std::unordered_set 중심의 보편적 중복 제거 방식이 데이터 분포와 키 특성에 따라 심각한 성능 저하를 유발하는 문제 분석. 특히 Dense Integer나 Long String 같은 특정 데이터셋에서 Hashing과 Pointer Chasing으로 인한 불필요한 오버헤드 발생.

Technical Solution

• Dense Bounded Integer 처리 시 Hashing 과정을 생략하고 인덱스 기반의 Bitset을 활용한 멤버십 확인 구조 설계
• Long String 처리 시 전체 문자열 비교 대신 Fingerprinting 기반 정렬을 수행하여 Comparison 비용 최적화
• Sparse 64-bit Integer 대응을 위해 메모리 효율과 검색 속도를 절충한 Roaring Bitmap 도입
• Unbounded Stream 환경에서 Durable 저장소가 필요한 경우 Single Transaction 오버헤드 제거를 위한 Batched Write 전략 적용
• 데이터의 범위와 분포에 따라 Bitset, Sorting, Bitmap 중 최적의 데이터 구조를 동적으로 선택하는 전략 수립