samkhya는 단 하나의 문장을 참으로 만들기 위해 존재합니다: 쿼리 옵티마이저 (query optimizer)는 머신러닝 (machine-learning) 모델이 계획을 망가뜨리지 않으면서도 모델로부터 숫자를 가져올 수 있어야 합니다.

그 메커니즘은 천장 (ceiling) 입니다. 즉, 증명 가능한 조인 카디널리티 (join-cardinality) 상한선이며, 수정된 추정치는 이 천장 아래로 제한됩니다. 모델은 천장 아래에서는 틀리는 것이 허용됩니다. 하지만 천장 위에서 틀리는 것은 허용되지 않습니다. 그 비대칭성이 전체 안전성 논거이며, 이 라이브러리를 사용할 가치가 있는 이유입니다.

지난 7월, 저는 926개의 조인 쿼리 (join queries)의 실제 출력을 구체화하여 각각을 라이브러리가 보고했던 천장과 비교하는 감사를 실시했습니다.

3,704번의 상한선 평가 중 2,179번에서 천장이 실제 정답보다 낮게 나타났습니다. 58.8%였습니다.

느슨하지도, 보수적이지도 않았습니다. 낮았습니다. 조인이 증명 가능하게 초과할 수 없었던 숫자가, 대부분의 경우 조인이 실제로 반환한 행 (rows)의 수보다 작았습니다. 이는 그것이 결코 상한선이 아니었음을 의미합니다. 그것은 단지 "증명 가능한"이라는 단어를 입은 또 하나의 추정치일 뿐이었습니다.

이 포스트는 무엇이 잘못되었는지, 어떻게 녹색 테스트 스위트 (green test suite)가 이를 숨겼는지, 위반 사항을 제로로 만든 수정 방법, 그리고 떠나는 길에 제가 철회해야 했던 모든 것에 대해 다룹니다.

옵티마이저의 가장 오래된 버그

머신러닝 이전에 더 단순한 문제가 있습니다. 조인 순서 (join order)를 선택하기 위해, 옵티마이저는 각 조인이 얼마나 많은 행을 반환할지 추측해야 합니다. 모든 엔진은 요약 통계 (summary statistics)와 완곡하게 표현하자면 낙관적인 독립성 가정 (independence assumptions)을 사용하여 이를 수행합니다.

오류가 그대로 유지된다면 살아남을 수 있을 것입니다. 하지만 그렇지 않습니다. 조인 트리 (join tree)는 곱해집니다: 하단에서 3배 틀린 추정치는 다음 조인으로 전달되어 거기서 다시 3배가 틀려지며, 6단계 위로 올라가면 중간 결과 (intermediate result)의 크기에 대해 1,000배(three orders of magnitude)나 틀리게 됩니다. 그 시점에 옵티마이저는 1만 개의 행이 있다고 생각하는 테이블에 대해 해시 조인 (hash join)과 메모리 예산 (memory budget)을 자신 있게 선택하지만, 실제로는 1,000만 개의 행이 있습니다.

단 한 번의 잘못된 추측, 6단계의 조인 (join)
조인 트리 (join tree)를 따라 곱셈적으로 누적되는 추정 오차 (illustrative)

• 3× 조인 1

10×
조인 2

32×
조인 3

100×
조인 4

320×
조인 5

1,000×
조인 6

하단의 추정치를 바탕으로 선택된 실행 계획 (plan)이 상단에서는 여전히 실행되고 있습니다.
예시입니다. 조인 트리 하단의 단 한 번의 잘못된 추정은 그 위의 모든 단계에서 곱해집니다.
이것이 바로 카디널리티 추정 (cardinality estimation) 분야에 머신러닝 (machine learning)이 주목받는 이유입니다. 학습된 모델은 이미 경험한 워크로드 (workload)에 대해 독립성 가정 (independence assumptions)보다 실제로 더 나은 성능을 낼 수 있습니다. 문제는 경험하지 못한 워크로드에서 어떤 일이 벌어지느냐 하는 것입니다.
여기서의 회귀 (regression)는 단순히 쿼리가 약간 느려지는 문제가 아닙니다. 그것은 결코 끝나지 않는 실행 계획을 의미합니다.

더 나은 추측이 아닌, 왜 상한선 (ceiling)인가

따라서 samkhya의 베팅은 결코 "모델이 정확할 것이다"가 아니었습니다. 그것은 "모델이 산술 (arithmetic)에 의해 감사 (audited)될 수 있다"였습니다.
이미 보유하고 있는 통계치를 통해, 데이터가 어떤 모습이든 조인이 초과할 수 없는 숫자를 계산합니다. 그런 다음 그래디언트 부스팅 트리 (gradient-boosted trees), TabPFN, 언어 모델 (language model) 등 원하는 어떤 교정기 (corrector)를 사용하여 추정치를 생성하게 하고, 그 숫지 아래로 제한 (clamp)합니다. 교정기가 잘못 보정되거나, 표류하거나, 완전히 환각 (hallucinating)을 일으키더라도, 산술이 제어하는 한계를 넘어 최적화 도구 (optimizer)를 밀어붙일 수는 없습니다.

상한선은 추정치가 아닙니다. 그것은 벽입니다.
조인이 증명 가능하게 초과할 수 없는 숫자 — 따라서 잘못된 모델이라 할지라도 그 아래에서만 틀릴 수 있습니다.

증명 불가능 (PROVABLY IMPOSSIBLE)
이 관계들(relations)에 대한 어떤 조인도 이만큼의 행을 반환할 수 없음

c
상한선 (ceiling)

실제 카디널리티 (true cardinality)

모델의 가공되지 않은 추정치 (model's raw estimate)

제한됨 (clamped)

이 보증은 벽이 실제로 당신이 주장하는 위치에 있을 때에만 가치가 있습니다.
상한선은 더 나은 추측이 아닙니다. 그것은 교정된 추정치가 제한되는 벽입니다.
그것은 좋은 설계입니다. 다만 그 벽이 실제로 당신이 말하는 위치에 있을 때에만 좋은 설계가 됩니다.

감사 (The audit): 진실을 구체화하고, 확인하라

v1.1 테스트 스위트(test suite)는 통과(green) 상태였습니다. 하지만 그것이 확인하고 있었던 것은 내부적 일관성(internal consistency) — 즉, 경계값(bounds) 간의 관계, 스케치 출력물(sketch outputs)에 대한 경계값, 그리고 모두 문제의 동일한 측면에 존재하는 불변량(invariants)들이었습니다. 그 안의 어떤 것도 조인(join)을 실행하여 결과로 나온 행(row)의 수를 세지는 않았습니다.

그래서 그것이 바로 감사(audit)가 수행한 작업입니다. 1,080회의 시행 — 4개의 조인 토폴로지(join topologies) × 3개의 크기 × 3개의 $\ell_p$ 체제(regimes) × 30회의 반복. 154회는 구체화된 진실(materialized truth)이 u64를 초과하여 제외되었고, 926회의 감사 대상 시행이 남았습니다. 각 시행마다 4개의 경계값을 평가했습니다: 총 3,704회의 경계값 평가(bound-evaluations)가 이루어졌으며, 각각은 실제로 생성된 행 수(row count)와 비교되었습니다.
4개의 경계값 중 3개가 실패했습니다.

4개의 경계값 중 3개는 경계값이 아니었습니다
v1.1 경계값당 위반율 — 각 926회의 감사 대상 시행
ProductBound

0.0%
0 / 926
ChainBound

96.0%
889 / 926
LpJoinBound

76.7%
710 / 926
AgmBound

62.6%
580 / 926

ProductBound는 유지되었습니다. 하지만 이는 네 가지 중 가장 느슨하고(loosest) 유용성이 가장 낮습니다.
v1.1 경계값당 위반율, 각 926회의 감사 대상 시행. 네 가지 중 가장 느슨한 ProductBound만이 유지되었습니다.
ChainBound는 시행의 96%에서 부정확(unsound)했습니다. LpJoinBound는 77%, AgmBound는 63%였습니다. ProductBound는 0%로 유지되었는데 — ProductBound는 관계 크기의 단순 곱(straight product)인 자명한(trivial) 경계값이며, 세트 내에서 가장 느슨하고 유용성이 가장 낮습니다. 살아남은 유일한 것은 가장 적은 일을 수행하던 것이었습니다.

천장을 그대로 뚫고 지나간 다섯 가지 조인

집계(Aggregates)는 이 내용을 추상적으로 들리게 만듭니다. 개별 사례들은 그렇지 않습니다.

천장을 그대로 뚫고 지나간 다섯 가지 조인
구체화된 진실(Materialized truth) vs 이를 제한하기로 되어 있었던 v1.1 천장
외래 키 조인 (foreign-key join)
orders(10) ⋈ lineitem(100)

100

10
두 개의 관계, 하나의 키
단일 공유 키

20

4
세 관계 체인 (three-relation chain)
R ⋈ S ⋈ T

27

3
왜곡된(skewed) 20 × 20
헤비 히터(heavy-hitter) 키

260

20
네 관계 스타 (four-relation star)
하나의 허브, 세 개의 포인트

128

2
실제 행 (true rows)

v1.1 "provable" ceiling (증명 가능한 상한선)
감사(audit)를 통해 발견된 다섯 가지 반례. 각 사례에서 "증명 가능한" 상한선은 그것이 제한하려던 실제 정답보다 더 작았습니다.
가장 당혹스러우면서도 교훈적인 첫 번째 사례를 살펴보겠습니다. 전형적인 외래 키 조인(foreign-key join)입니다: 10개의 행을 가진 orders 테이블과 100개의 행을 가진 lineitem 테이블, 그리고 모든 lineitem이 하나의 order를 가리키고 있습니다. 실제 출력 결과는 100개의 행입니다. SQL을 작성해 본 사람이라면 누구나 이것이 100개의 행이라는 것을 압니다.
v1.1은 10이라는 증명 가능한 상한선을 보고했습니다.
만약 교정기(corrector)가 이 상한선 아래로 값을 고정(clamp)했다면, 옵티마이저(optimizer)에게 100개의 행을 반환하는 조인이 최대 10개만을 반환한다고 강제로 말해야 했을 것이며, 이 고정 작업은 마치 안전 기능이 제 역할을 다하는 것처럼 보였을 것입니다. 네 관계 스타(four-relation star)는 비율 면에서 더 심각합니다: 실제 값은 128인데, 상한선은 2였습니다.

어떻게 녹색 테스트 스위트(green suite)가 세 개의 깨진 경계(bounds)를 숨겼는가

각 실패에는 구체적이고 지루한 원인이 있었으며, 일단 살펴보기 시작하면 그 중 어느 것도 미묘하지 않았습니다:
LpJoinBound — 분수 에지 커버(fractional-edge-cover) 선형 계획법(LP)에 속성별 제약 조건(per-attribute constraints)이 누락되었습니다. 이 방식은 술어(predicate)당 커버리지는 확인했지만 프라이빗 컬럼(private columns)은 조용히 무시했기에, 해결하겠다고 주장한 문제보다 더 작은 문제를 해결하고 있었습니다.

• AgmBound — min(product, |R_min| · |R_max|)를 계산했습니다. 두 개 이상의 관계를 조인하는 경우, 이 식은 두 개를 제외한 모든 관계를 버려버립니다. 이것은 쿼리에 대한 경계(bound)가 아니라, 아무도 요청하지 않은 서브쿼리(sub-query)에 대한 경계입니다.
• ChainBound — 상한선(ceiling)이 필요한 곳에 균등 분포(uniform-distribution) 추정기(estimator)를 적용했습니다. 균등성(uniformity)은 데이터에 대한 사실이 아니라 데이터에 대한 가정일 뿐이며, 왜곡(skew)은 이를 즉시 무너뜨렸습니다.

마지막 사례는 이 모든 교훈을 축약해 보여줍니다. 추정기(estimator)와 경계(bound)는 서로 다른 의무를 가진 서로 다른 객체입니다. 추정기는 양방향 모두에서 틀릴 수 있으며, 바로 그 점이 그것을 추정기로 만듭니다. 경계는 단 한 방향으로 단 하나의 작업만을 수행하며, 금지된 방향에서 틀린 경계는 느슨한 경계(loose bound)가 아니라 거짓된 진술(false statement)입니다. v1.1의 어딘가에서 추정기가 경계로 호출되었고, 타입 시스템(type system)은 이에 대해 아무런 의견도 내지 않았습니다.

제가 주의를 기울여서 이를 잡아냈다고 말하고 싶습니다. 저는 마침내 시스템 외부의 무언가와 비교함으로써 이를 잡아냈습니다.

수정 사항: 신장 트리(spanning tree)를 따라 차수(degree) 곱하기

v1.2.0에서의 수정 사항은 그 모든 것을 단일 차수 기반 구조(degree-based construction)로 대체하는 것이며, 제가 이 방식에서 마음에 드는 점은 새로운 통계 정보가 필요하지 않다는 것입니다.

조인 그래프(join graph)를 가져와서, 임의의 신장 트리(spanning tree)를 선택하고, 아무 곳에나 루트(root)를 설정합니다. 루트 관계(root relation)의 기수(cardinality)부터 시작합니다. 각 트리 에지(tree edge)를 따라 이동하며 해당 에지에 걸친 최대 차수(maximum degree)를 곱합니다. 여기서 최대 차수란, 근처 쪽(near side)의 임의의 단일 행이 건너편 쪽(far side)에서 매칭될 수 있는 가장 큰 행의 수입니다. 그 곱셈 결과가 상한선(ceiling)이 되며, 이는 머릿속으로 이해할 수 있는 이유로 인해 상한선이 됩니다. 즉, 모든 출력 행은 트리(tree)를 따라 확장된 어떤 루트 행이며, 각 확장은 해당 에지의 최대 차수에 의해 제한되기 때문입니다.

수정 사항: 신장 트리(spanning tree)를 따라 차수(degree) 곱하기
루트 기수(Root cardinality) × 트리 에지당 최대 차수(max degree per tree edge) — 모든 입력은 이미 사이드카(sidecar)에 있음

• maxdeg maxdeg maxdeg maxdeg

Rr
root

R1

R2

R3

R4
tree edge

unused

|Q| ≤ |Rr| · Π maxdeg(Rv, a_uv)
차수(Degrees)는 Puffin 사이드카에 이미 있는 HLL(HyperLogLog) 고유 카운트(distinct counts)와 Count-Min 스케치(sketches)에서 가져옵니다 — 새로운 통계는 필요 없습니다.
v1.2.0: 루트 기수에 각 신장 트리 에지를 따른 최대 차수를 곱합니다. 트리 에지가 아닌 에지(Non-tree edges)는 오직 도움만 될 뿐입니다.
트리 에지가 아닌 에지는 무시되며, 이는 안전합니다. 추가적인 조인 술어(join predicates)는 필터링만 할 뿐, 결코 추가할 수는 없기 때문입니다. 그리고 차수는 이미 Puffin 사이드카에 자리 잡고 있는 통계, 즉 samkhya가 어차피 작성하고 있던 HyperLogLog 고유 카운트와 Count-Min 스케치에서 가져옵니다.
10이라는 상한선을 생성했던 외래 키(foreign-key) 조인의 경우, 새로운 구조는 100을 반환합니다. 안전하게 추정한 100이 아닙니다. 정확히 100입니다. 즉, 해당 쿼리에 대해 존재하는 가장 타이트하고 건전한(tightest sound) 상한선인 실제 출력값입니다.
동일한 테스트 환경(harness)과 동일한 실험(trials)으로 감사를 다시 실행합니다:

3,704회의 경계 평가(bound-evaluations) 중 건전성 위반(Soundness violations)
동일한 테스트 환경, 동일한 실험, 단 한 번의 릴리스 차이

v1.1

2,179
58.8%

v1.2.0

0
0.0%
오른쪽의 막대는 작지 않습니다. 그것은 0입니다 — 녹색 표식이 축(axis)입니다.
동일한 하네스(harness), 동일한 시행(trials), 단 한 번의 릴리스 차이. 아래쪽 막대의 녹색 표식은 값이 아니라 축입니다.

그와 함께 무엇이 내려왔는가

자신의 실패를 감지하지 못하는 측정치를 단 하나라도 발견한다면, 다른 측정치들도 그러할 것이라고 가정해야 합니다. 저도 그랬습니다.
40.95× 경계 엄격도 (bound-tightness) 수치는 철회되었습니다. 이는 불완전(unsound)한 것으로 판명된 경계(bounds)를 기준으로 계산되었으므로, 틀린 숫자가 얼마나 엄격한지를 측정하고 있었던 셈입니다.
1.038× JOB-Slow 속도 향상 (speedup) 수치와 그 뒤에 있었던 캠페인 전체도 철회되었습니다. 감사(audit) 결과, "수정됨(corrected)"라고 표시된 암(arm)에는 수정기(corrector)가 포함되어 있지 않았음이 밝혀졌습니다 — 애초에 벤치마크에 훈련된 수정기를 부착할 플래그(flag)가 없었습니다. 네 번의 시행 모두 113개 중 55번째 쿼리에서 OOM-kill(Out Of Memory kill)되었습니다. 실행 순서 혼란(Run-order confound)이 존재했던 3.8% 효과의 약 3분의 2를 차지합니다. 그리고 근본적인 카디널리티(cardinality)는 항상 1이었으며, 이는 해당 하네스에서 검증 지표로서 q-error를 무의미하게 만듭니다. 실제로 출판된 것은 카디널리티 교정(cardinality-correction)이라는 헤드라인 아래의 휴대 가능한 통계(portable-statistics) 결과였습니다.
TabPFN-2.5 q-error 주장은 15% 개선으로 사전 등록(pre-registered)되었습니다. 측정된 값은 7.84%였습니다. 방향성은 유지되었으나, 제가 사전에 약속했던 크기 임계값(magnitude threshold)은 유지되지 않았습니다. 사전 등록은 예측 실패를 보고할 때만 가치가 있습니다. 따라서, 결과는 실패했습니다.
그리고 제가 진정으로 유용하다고 생각하는 부분은 — 홀드아웃 쿼리(held-out queries)에서 수정기가 추정치를 오히려 _악화(worse)_시켰다는 점입니다. 기하평균(geomean) q-error가 13.46에서 26.41로 증가했습니다. 이는 모델이 개선하기 위해 추가된 대상을 능동적으로 저하시키고 있음을 의미합니다. 또한 이는 상한선(ceiling)이 존재하는 바로 그 시나리오이며, 실제 환경에서, 저의 벤치마크에서, 저의 모델을 대상으로 관찰되었습니다.

감사에서 살아남은 것과 살아남지 못한 것
각주가 아닌, 원본 데이터와 함께 리포지토리(repo)에 게시됨

유지됨 (KEPT)
0건의 위반 / 3,704건의 경계 평가 (bound-evaluations)
외래 키 조인 상한선 (foreign-key join ceiling) = 100, 정확히 실제 출력값과 일치
HLL p=14, n=10⁶ — RSE 0.676%, BCa CI [0.535, 0.848]
TabPFN-2.5 P95 추론 (inference) 31.15 ms, CI [29.39, 35.32]
혼합 워크로드 페널티 (mixed-workload penalty) 0.949× — samkhya가 약 5% 손실
84 KB WASM 번들, TypeScript 타입 포함

철회됨 (WITHDRAWN)
40.95× 경계 엄격도 (bound-tightness) — 철회됨
1.038× JOB-Slow 속도 향상 (speedup) — 철회됨
JOB-Slow 캠페인 — "교정된 (corrected)" 실험군 내에 교정기 (corrector) 없음
TabPFN q-오차 (q-error): 사전 등록 15%, 측정치 7.84%

여전히 미결 (STILL OPEN)
§4 상한선 (ceiling)이 실제 쿼리 계획 (query plan) 내부에서 측정된 적 없음
§7 문서화된 재현 (repro) 명령어가 작성된 대로 실행되지 않음
§3/5/6/8 신뢰할 수 있으나 출처 (provenance)가 원본 데이터로 추적되지 않음
전체 회계 내역은 원본 데이터와 함께 리포지토리(repo)에 게시됨.

내가 현재 실제로 믿고 있는 것