Logfire에서 span_name = 'tool called'처럼 일치하는 행이 적은 조건으로 데이터를 찾을 때는 수십억 행 가운데 일부만 조회하는 점 조회(point lookup)가 이뤄진다. Pydantic은 Apache Arrow의 Rust 구현에 블룸 필터 접기(folding) 최적화를 기여했다. 이 방식은 별도 튜닝 없이 필터 크기를 줄이고, Parquet에서 관련 없는 데이터를 더 효과적으로 건너뛰도록 한다.

블룸 필터와 Parquet의 방식

블룸 필터는 값이 집합에 있는지 확인하는 작은 자료 구조다. 결과는 ‘확실히 없음’ 또는 ‘있을 가능성이 있음’으로 나뉜다. 거짓 음성은 없으므로 ‘없음’이라고 답하면 해당 데이터를 읽지 않아도 된다. 반면 거짓 양성은 있을 수 있어 불필요한 읽기를 일으키지만, 잘못된 답을 내지는 않는다.

Parquet은 각 행 그룹의 각 열에 블룸 필터를 둔다. 질의 엔진은 열 데이터를 읽기 전에 행 그룹별 필터를 확인하고, 값이 없다고 판정된 그룹은 압축 해제나 입출력 없이 건너뛴다. 트레이스 ID, 스팬 이름, 사용자 ID처럼 값의 종류가 많은 열을 선별적으로 조회할 때는 데이터의 99%를 건너뛸 수도 있다. DuckDB는 블룸 필터를 이용한 점 조회에서 50배, InfluxData는 최대 30배의 속도 향상을 보고했다.

Parquet은 캐시 효율을 높인 Split Block Bloom Filter(SBBF)를 사용한다. 푸체(Putze), 잔더스(Sanders), 징글러(Singler)가 소개한 이 방식은 한 값의 비트를 256비트 블록 하나에 모은다. 각 값은 한 블록 안의 8개 비트를 설정하며, 조회할 때는 그 비트가 모두 설정됐는지 확인한다. 따라서 일반 블룸 필터처럼 여러 메모리 위치를 무작위로 읽는 대신 한 블록을 확인한다. Parquet 형식 문서와 관련 논문에 설명돼 있다.

데이터에 맞춰 필터 크기 조정

블룸 필터는 담을 서로 다른 값의 수(NDV)에 따라 적정 크기가 달라진다. 너무 작은 필터에 값이 많이 들어가면 비트 대부분이 설정돼 거의 모든 값을 ‘있을 가능성이 있음’으로 판단한다. SBBF 블록의 거짓 양성 확률은 대략 비트가 설정된 비율의 8제곱(fill⁸)에 따라 커지므로, 필터가 차면 효과가 급격히 떨어질 수 있다. 반대로 필요 이상으로 크게 만들면 파일마다 비어 있는 비트 배열에 공간을 낭비한다.

행 그룹마다 값의 수가 다르기 때문에 쓰기 전에 NDV를 정확히 알기는 어렵다. 기존 Rust Parquet 구현인 arrow-rs는 고정 크기를 사용했지만, 그 결과 필터가 불필요하게 크거나 포화되는 경우가 있었다. 일부 시스템은 쓰기 전에 데이터를 살펴 NDV를 추정하며, DuckDB도 이 방식을 쓴다. 여러 크기의 필터를 만든 뒤 하나를 고르는 방법도 있지만, 메모리와 쓰기 작업이 더 필요하다.

이번 최적화는 넉넉한 크기의 필터에 값을 모두 기록한 뒤 실제로 얼마나 찼는지 측정하고, 필요한 만큼 줄인다. 이를 접기라고 한다. 인접한 블록 두 개를 비트 OR 연산으로 합치면 블록 수가 절반이 된다.

block[i] = block[2i] | block[2i + 1]

블록 선택에 사용하는 식은 i = ((h >> 32) * z) >> 32다. 블록 수 z를 절반으로 줄이면 기존 블록 2i와 2i+1이 새 블록 i로 합쳐진다. OR 연산은 설정된 비트를 지우지 않으므로, 접은 뒤에도 삽입된 값의 비트가 남아 거짓 음성이 생기지 않는다. 결과는 처음부터 작은 필터에 기록한 경우와 수학적으로 동등하다고 Pydantic은 설명한다.

구현은 쓰기를 마친 뒤 블록 전체의 평균 비트 설정률을 측정하고, 목표 거짓 양성 확률을 넘지 않는 선에서 가능한 한 많이 접는다. 각 접기 단계에서 블록당 유효 값 수가 대략 두 배가 되며, 그에 따라 거짓 양성 확률도 달라진다. 처리 순서는 다음과 같다.

1. Allocate a generously large filter (sized from the row group's max row count). 2. Write every value — the filter fills up, often far below capacity. 3. Measure the real fill rate across all blocks. 4. Fold (OR adjacent pairs) as many times as possible while FPP ≤ target. 5. Serialize the right-sized filter into the file.

Pydantic에 따르면 값이 적은 열은 필터가 크게 줄고, 값이 많은 열은 목표 거짓 양성률을 유지하는 크기로 조정된다. NDV를 추정하거나 매개변수를 설정할 필요가 없으며, 이 동작이 새 기본값이다.

비용과 적용 범위

접기에는 쓰기 시점에 필터를 메모리에 보관하는 비용이 든다. 보수적으로 크게 만든 블룸 필터 하나당 약 1MiB이며, 열 데이터와 다른 쓰기 버퍼에 비하면 무시할 만한 수준이라고 Pydantic은 설명한다. 계산에는 필터를 훑어 설정률을 측정하는 작업과, 블록을 접는 OR 연산이 들어간다.

기여한 PR의 벤치마크에서 100K개의 값을 실제로 받은 필터를 대상으로, 1M NDV에 맞춰 만든 필터를 접는 데 약 27µs가 추가됐다. 삽입 작업 약 190µs에 비해 약 14%의 추가 시간이다. Pydantic은 이를 열 인코딩과 압축 비용에 견주면 작은 부담이라고 설명한다.

Pydantic은 트레이스, 스팬, 로그를 Parquet에 저장하는 Logfire에서 이 최적화를 활용한다. 트레이스 ID나 스팬 이름을 찾는 점 조회는 행 그룹을 더 많이 건너뛰고 읽는 데이터가 줄어들 수 있으며, 적정 크기의 필터는 파일 크기도 줄일 수 있다는 설명이다. 앞서 공개한 동적 셰딩 작업은 속성에 전용 열을 부여해 속성 질의를 빠르게 했고, 이번 최적화는 해당 열의 점 조회에서 행 그룹을 건너뛰도록 한다.

Pydantic은 이 변경을 자체 포크가 아니라 Apache Arrow에 기여했다. 따라서 Rust Parquet 구현을 쓰는 다른 프로젝트에도 기본으로 적용된다. Parquet Java 유지보수진도 이 방식을 이식하는 데 관심을 보였다. 관련 논의에서 확인할 수 있다.