그 오랜 세월이 지났는데도 GROUP BY를 더 최적화할 수 있을까요?

요약

상위 K개만 뽑는 GROUP BY 쿼리에서 답이 나올 수 없는 파티션의 병합을 건너뛰어 1.6배 빨라졌습니다.

오픈소스 실시간 분석 데이터베이스 Pivot을 만드는 엡시오 랩스의 길라드 클라인만이 쓴 글입니다. 분석용 데이터베이스가 GROUP BY를 처리하는 방식을 설명하고, 그 위에 ORDER BY와 LIMIT이 붙은 쿼리를 빠르게 만든 방법을 소개했습니다.

왜 중요한가

ClickBench(분석 데이터베이스 성능 비교 벤치마크) 쿼리의 63%가 이런 형태라서 적용할 곳이 많습니다.
오래 다듬어진 GROUP BY에도 결과에 쓰이지 않는 작업이 아직 많이 남아 있다는 점을 보여 줍니다.
여러 노드에서 나눠 실행하는 기능이 붙으면 네트워크와 디스크 입출력까지 아껴 효과가 더 커질 것으로 봤습니다.

핵심 내용

파티션 안을 해시로 여러 슬롯에 나눠 합계를 따로 셉니다.
모든 슬롯 합계가 현재 상위 K개의 최솟값보다 작으면 그 파티션은 병합하지 않고 건너뜁니다.
ClickBench Q16은 35.6ms에서 22.2ms로 줄었고, 파티션의 70% 넘게 병합 없이 건너뛰었습니다.
상위 10개는 많아야 10개 파티션에만 있어서, 파티션이 4,096개면 4,086개 이상을 헛되이 병합하는 셈입니다.
값이 고르게 퍼진 데이터에서는 건너뛸 파티션이 없으므로 엔진이 이를 감지해 기능을 꺼야 한다고 했습니다.

HN 반응

일부 이용자는 슬롯 구조가 count-min sketch(적은 메모리로 빈도의 상한을 추정하는 자료 구조)와 같다고 짚었습니다.
35.6ms에서 22.2ms를 1.6배 빠르다고 한 것은 과장이라는 지적에, 처리량으로 보면 맞는 표현이라는 반론이 맞섰습니다.

27개 표시 · 전체 27개

SkiFire131일 전 HN

각 파티션에서 Top-K 집계를 병렬로 수행하지 않은 이유가 궁금합니다. 그러면 각 파티션의 원소 수도 줄고 파티션별 정확한 최댓값도 얻을 수 있어서, 그 값을 추가 가지치기에 쓸 수 있을 텐데요.
malisper1일 전 HN
쿼리는 이렇습니다.
```
  SELECT item_id, COUNT(*) AS c
  FROM orders
  GROUP BY item_id
  ORDER BY c DESC
  LIMIT 10;
```
가장 자주 나오는 item_id 상위 10개를 구하는 쿼리입니다. 어떤 item_id가 모든 파티션에서 11번째로 인기 있는 항목이라 10번째에는 들지 못할 수 있습니다. 그런데 모든 파티션의 개수를 합산하면 전체에서는 10번째로 많은 항목이 될 수 있습니다.
SkiFire1320시간 전 HN
그런데 모든 파티션의 개수를 합산하면 전체에서는 10번째로 많은 항목이 될 수 있습니다.

그 개수 합산은 최적화를 적용하기 전에 이미 하고 있습니다.

제가 보기에 "기본" 알고리즘은 이렇습니다.
```
    1. Get the data from disk, which will be partitioned by storage key.
    2. Parallelizing by storage key, aggregate each partition according to the grouping key. The result are many partitions by grouping key holding partially aggregated data.
    3. Parallelizing by grouping key, merge the partially aggregated results. The results are fully aggregated partitions (each item is present in one and only one partition)
    4. Merge these partitions into a global list of aggregated results
    5. Pick the top K of this list
```
글에 나온 최적화와 제 제안은 둘 다 4단계에 적용됩니다. 그 시점에는 한 항목의 집계 결과가 정확히 한 파티션에만 존재하는 것이 이미 보장되어 있으므로, 파티션 안에서는 11번째인데 전체 집계에서는 10번째가 되는 일은 있을 수 없습니다.
malisper14시간 전 HN
제가 알기로 기본 알고리즘에는 2단계가 없습니다. 이 사람들은 라딕스 파티셔닝 해시 테이블(radix-partitioned hash table)이라고 알려진 방식을 쓰고 있습니다. 기본 알고리즘은 이렇습니다.
```
  1. Get the data from disk, which will be partitioned by storage key
  2. Partition the data by grouping key (without aggregating it)
  3. In parallel, aggregate each partition
  4. Take the top K from each partition
  5. Take the top K overall
```
이 최적화를 쓰면 3~5단계를 전체 파티션이 아니라 일부 파티션에만 수행하면 되니까 그만큼 작업을 아낄 수 있습니다.
malisper2일 전 HN

멋지네요! 참고로 글에서 설명하는 자료구조는 카운트-민 스케치(count-min sketch)예요. group by에 들어올 수 있는 원소의 상한을 정하는 데 쓰고, 그걸로 불필요한 작업을 상당수 건너뛰는 것 같아요.
ozgrakkurt2일 전 HN

클릭벤치(ClickBench) 결과가 정말 좋아 보여요.

https://benchmark.clickhouse.com/#system=+liH|Hoaus|DcD|ucqs|Pier|mb|U%20&type=-&machine=-ca4e|6t|ca2|6ax|g4e|gel|6ale|3al&cluster_size=-&opensource=-&hardware=+c&tuned=+n&storage=-&metric=cold&queries=-
eden-u41일 전 HN

Pivot과 DuckDB는 뭐가 다른가요? 꽤 비슷해 보이는데, 이 group by 구현을 다른 곳에서 가져다 쓰면 비슷한 벤치마크 결과를 낼 수도 있겠네요.
ntur13371일 전 HN

안녕하세요! Pivot 개발자 중 한 명입니다 :)

DuckDB도 Iceberg 같은 오픈 테이블 포맷을 질의할 수 있는 쿼리 엔진이 맞습니다. 하지만 Pivot은 ClickHouse 같은 "완전한 데이터베이스"의 경험을 오픈 데이터 포맷의 세계로 가져오는 것을 목표로 합니다. 클러스터를 띄우고, 여러 노드에 걸쳐 쿼리 하나를 실행하고, 수집(ingestion)과 컴팩션을 처리하고, 서버 모드로 돌면서 여러 클라이언트에 서비스하는 것까지 빠르고 효율적으로 해내려고 합니다.

저희도 DuckDB를 좋아합니다. 다만 ClickHouse는 독점 스토리지 포맷을 쓰는데도 많은 회사가 DuckDB 대신 ClickHouse를 택하고 있고, 그 이유는 DuckDB에는 없는 완결된 엔드투엔드 솔루션을 제공하기 때문이라고 봅니다.
eden-u418시간 전 HN

답변 감사합니다! 번거롭게 해서 죄송한데, 저는 ClickHouse를 잘 몰라서요. "클러스터를 띄우고, 여러 노드에 걸쳐 쿼리 하나를 실행하고..."라는 말이 무슨 뜻인지 이해해 보려는 중입니다. 데이터베이스 위에서 돌아가는 "스위트"의 "컴퓨트" 부분을 말씀하시는 건가요? Unity Catalog를 쓰면서도 Databricks의 클러스터 컴퓨트는 쓰지 않을 수 있는 것처럼요. 그러면 DuckDB나 MotherDuck과의 가장 큰 차이는 DB 솔루션과 그 DB를 쓰기 위한 "컴퓨트"가 서로 맞물려 있다는 점인가요?
lmeyerov1일 전 HN

이런 종류로는 Pivot이 MotherDuck과 더 비교될 것 같아요.

(그리고 아마존 건 때문에 앞으로 어떻게 될지는 저도 잘 모르겠어요.)
toddbandrowsky2일 전 HN

데이터셋을 통째로 네트워크로 보내는 게 그룹화된 결과만 보내는 것보다 어떻게 더 싸다는 건지 도무지 모르겠어요. 사실 그게 진짜 문제잖아요. 한 박스에서 group by가 100ns 걸리든 말든 무슨 상관이에요. 거기까지 데이터를 보냈다가 돌려받는 데 10배는 더 걸리는데요.

가장 빠른 group by는 그 박스에서 NVMe로 읽어 온 연속된 메모리 위에서 하는 거예요.

그러니까 group by 파티셔닝을 한다는 건 결국 그룹 자체를 서로 다른 박스에 나눠 놓고 그룹들을 다시 group by 하겠다는 얘기예요. 정말 어마어마한 데이터셋이라면 놓을 곳은 메인프레임이죠. 메인프레임은 터무니없이 큰 데이터셋에 group by를 하려고 만든 물건이나 다름없으니까요.
ozgrakkurt2일 전 HN

적어도 이 글에는 쓸 만한 기술 정보가 들어 있어요. 저는 이런 블로그 글 읽는 게 정말 좋아요.

어차피 측정값이나 맥락은 상황마다 너무 달라서 써 봤자 쓸모가 없을 거예요.

하드웨어 한계와 비교한 벤치마크를 블로그에 올리는 DB 회사는 없잖아요. DuckDB는 지난번에 봤을 때 블로그에 "2026년에 데이터베이스에서 HTTP API를 안 쓰고 있다면 잘못하고 있는 것" 같은 문장이 있었어요.

저는 이 경우 오브젝트 스토리지도 좋지 않다고 생각해요. 그리고 이런 데이터베이스 프로젝트에는 Rust를 쓰면 안 돼요. Rust에서는 정적 할당이나 아레나 할당자를 쓰기가 편하지 않으니까요. Parquet도 압축 포맷 지원 같은 여러 이유로 성능 면에서는 쓰레기고요.
eru2일 전 HN

그리고 이런 데이터베이스 프로젝트에는 Rust를 쓰면 안 돼요. Rust에서는 정적 할당이나 아레나 할당자를 쓰기가 편하지 않으니까요.

요즘은 지루한 부분을 에이전트가 대신 써 주는데, 편의성이 그렇게까지 중요할까요?
ozgrakkurt1일 전 HN

제 경험상 코드가 단순한 상태라는 것은 에이전트의 효율에도 중요합니다.

편의성만의 문제가 아닙니다. Rust를 쓰는 이유는 탄탄한 추상화와 품질 좋은 라이브러리가 많다는 데 있습니다.

정적 할당과 아레나를 쓰면 이런 좋은 추상화를 쓸 수 없고, 라이브러리도 쓸 수 없고, 그 때문에 unsafe 코드를 잔뜩 써야 합니다. 그러면 Rust를 쓰는 게 오히려 발목을 잡으니 쓸 이유가 없습니다.
sagarm2일 전 HN

틀린 말씀은 아닙니다. 쿼리 하나에 필요한 메모리 크기를 알고 있고 데이터를 직접 연결된 SSD(AWS라면 임시 SSD)에 둘 수 있다면, 수직 확장이 가장 빠른 실행 시간을 줍니다.

하지만 수평 확장에는 장점이 있습니다. 규모를 조금씩 늘리고 줄이기가 쉽고, 분리된(disaggregated) 데이터에 접근할 때 집계 네트워크 대역폭이 더 커집니다. 분리형 구조에서는 컴퓨트와 스토리지를 독립적으로 확장할 수 있습니다. 또 머신 한 대를 잃어도 클러스터에 미치는 영향이 작아서 더 저렴한 스팟 자원을 쓸 수도 있습니다.

결국 복원력이 필요하다면 수평 확장을 전제로 설계한 시스템이 운영하기 더 쉬운 경우가 많습니다.
asdf889902일 전 HN

group by는 sum, max 같은 다른 집계 함수와 함께 쓸 때 유용합니다.
misiek081일 전 HN

22.2ms 대 35.6ms가 1.6배 빠른 거라고요? 그건 0.4배 빠른 거고, 최악의 계산법을 써도 0.62배 빠른 거예요.

IT 업계에서 속보니 우리 다 죽는다니 하는 선정적인 방식으로 소식을 전하는 건 정말 그만 둘 수 없나요?
Sesse__1일 전 HN

60% 빠른 겁니다(0.6배 빠르고, 1.6배의 속도). 처리량("단위 시간당 할 수 있는 일의 양")이 성능을 설명하는 유일하게 합리적인 방법입니다[1]. 그렇지 않으면 큰 속도 향상은 직관적으로 설명할 방법이 사실상 없습니다. (10초 걸리던 일이 이제 1초 걸리면 "0.9배 빨라졌다"가 아니라 "10배 빨라졌다"고 하는 게 맞습니다.)

[1] 지연 시간(latency)의 변화조차 처리량으로 설명하는 게 가장 좋습니다.
bollu1일 전 HN

지연 시간 변화를 어떻게 처리량으로 설명할 수 있나요? 파이프라이닝을 어떻게 하느냐에 따라 처리량은 같은데 지연 시간은 완전히 다를 수 있잖아요?
Sesse__1일 전 HN

똑같은 방식으로 설명합니다. 지연 시간이 10초에서 1초로 바뀌면 지연 시간 기준으로 10배 빨라진 것입니다(900% 빨라졌다고 해도 됩니다). 전에는 초당 0.1건을 처리했고 이제는 초당 1.0건을 처리하는 셈입니다. 지연 시간과 처리량의 유일한 실질적 차이는 작업 인스턴스를 겹쳐 실행할 수 있느냐 없느냐이고, 두 값의 변화를 같은 언어로 말할 수 있습니다.

물론 지연 시간에서 처리량을, 또는 그 반대를 _계산_할 수는 없습니다(한쪽이 다른 쪽의 한계가 된다는 점을 빼면요). 두 값은 서로 다르니까요. 하지만 둘 다 "단위 시간당 일의 개수"라는 (아주 단순하고 아주 직관적인) 틀로 설명할 수 있습니다.

문제가 지저분해지는 건 "N% 느려졌다"라고 말할 때입니다. 이것도 쓸모는 있지만 N이 0에 가깝지 않으면 금세 모호하고 골치 아파집니다.
lcnPylGDnU4H9OF1일 전 HN

(If something that took 10s now takes 1s, that's “ten times as fast”, not “zero point nine times faster”.)

(10초 걸리던 일이 이제 1초 걸리면 "0.9배 빨라졌다"가 아니라 "10배 빨라졌다"고 하는 게 맞습니다.)

속도를 기준으로 해도 여전히 성립합니다("0.9"가 아니라 그냥 "9"로요). 관계를 뒤집어서 생각하면 됩니다. 10초에서 1초가 된 것은 여전히 "9배 빨라졌다"고 할 수 있는데, 말씀하신 대로 덜 직관적이긴 해도 "빠르다"는 것이 1초를 10초와 비교한다는 뜻이기 때문입니다(즉 "9(1초) + 1초 = 10초"). 반대로 "9(10초) + 10초 = 1초"는 당연히 틀립니다. 1초가 10초보다 짧은 시간이라는 걸 아니까 이렇게 해석되는 것입니다. 시간은 늘어나면 본질적으로 "느려진다"는 뜻이라서 "빠르다"는 말은 수치 관계를 뒤집습니다. 실제로 둘의 차이는 x = 1일 때 9x입니다. 그리고 10초에서 0.1초가 되면 99배 빨라진 것인데, x = 0.1일 때 99x가 9.9이기 때문입니다(처리량으로 재면, 속도만 변했다고 가정할 때 99배 더 많은 일을 하는 것이고 100배의 양을 하는 것이기도 합니다).

(모르셔서 드리는 말씀이 아니라 그냥 사소한 트집을 잡아 본 겁니다.)
d1sxeyes1일 전 HN

문제는 "더 빠르다", "더 느리다"가 속도를 비교하는 말이라는 점입니다. 속도는 단위 시간당 x개의 일을 뜻하는데, 여기서는 시간만 비교하고 있습니다. 어느 정도 설득력 있는 해석은 "한 건이 22.2ms 걸린다면 35.6ms 동안 몇 건을 끝낼 수 있나"인데, 실제로 그 답이 글에서 말하는 1.6이라는 숫자입니다.

선정적인 게 아니라 "빠르다"라는 단어를 좀 느슨하게 쓴 것뿐입니다.
_zoltan_1일 전 HN

자연어에서는 "1.6배 빠르다"는 표현도 충분히 받아들일 수 있어요.
seritools1일 전 HN

오해가 생겨도 신경 쓰지 않는다면 받아들일 수 있겠죠.
shikck2002일 전 HN

그보다 더 중요한 건, 왜 MySQL의 GROUP BY는 아직도 기본값이 망가진 상태냐는 거예요. MySQL은 데이터베이스계의 PHP인데, 버그를 고칠 계획이 아예 없어 보여요.
Sesse__1일 전 HN

MySQL의 GROUP BY는 기본값이 망가져 있지 않아요(표준에 맞는 선택인 ONLY_FULL_GROUP_BY가 10년 넘게 기본값이에요). 다만 MySQL 옵티마이저 팀은 연이은 감원 끝에 사실상 남아 있지 않아요. 40명쯤이던 게 3명 정도로 줄었거든요. Postgres를 써 보세요 :-)
holoduke1일 전 HN

LLM을 쓰면 쿼리 전략을 더 잘 분석하고 세울 수 있을지 궁금합니다. 사용 패턴에 따라 데이터 모델을 실시간으로 재구성하는 것도 가능할지 모르겠네요.

Hacker News에서 보기 ↗