q-error는 언제 Plan Regret을 예측하는가? Cardinality-Estimation Error의 세 가지 체제

Cardinality-estimation (CE, 카디널리티 추정) 연구는 q-error를 기준으로 추정기(estimator)의 순위를 매기지만, q-error가 쿼리 계획(query-plan) 품질을 나타내는 불완전한 대리 지표(proxy)라는 점은 잘 알려져 있습니다. 본 논문에서는 q-error가 언제 좋은 대리 지표가 되고 언제 그렇지 않은지, 그리고 그 이유가 무엇인지에 대해 측정 기반의 설명을 제공합니다. 계획 선택(plan selection)을 조각별 선형 비용 지형(piecewise-linear cost landscape)에서의 argmin 문제로 모델링함으로써, 우리는 계획 후회(plan regret, 실제 카디널리티 하에서 최적 계획 대비 선택된 계획의 비용)가 체제(regime)에 따라 계획 비용의 기하학적 구조(plan-cost geometry)에 의해 결정된다는 것을 발견했습니다. (i) 작은 오차의 경우, 실제 지점 조건수(true-point condition number) $\kappa$가 후회(regret)를 예측하며 q-error보다 더 나은 예측력을 보입니다. 국소 선형화(local linearization)가 그러하듯, 오차가 커짐에 따라 그 예측력은 0으로 감소합니다. (ii) 배포된 학습된 추정기들이 작동하는 영역인 큰 오차의 경우, 추정기와 무관한 평균 사례 하위 최적성(average-case sub-optimality) 측정 지표인 $ACS-\infty$가 어떤 쿼리가 후회에 취약한지를 예측합니다 (STATS-CEB 데이터셋에서 Spearman rho $\sim$ 0.54). 반면 q-error는 쿼리 수준에서 거의 정보력이 없습니다 (rho $\sim$ 0.05). (iii) 최악의 경우는 Haritsa의 최대 하위 최적성(MSO, maximum sub-optimality)입니다. 이 세 가지는 세 가지 가중치(weighting) 하에서의 하나의 비용 비율 스펙트럼입니다. 우리는 카디널리티와 무관한 조합론적 가중치를 갖는 극한 법칙 $ACS-\infty = \sum_k r_k \pi_k$를 증명하였으며, 사전 등록된 결정 규칙(decision rules)에 따라 공개된 4개의 추정기를 사용하여 STATS-CEB 및 JOB-light에서 모든 주장을 검증했습니다. 또한 실제 PostgreSQL 런타임에서 $ACS-\infty$가 q-error가 예측하지 못하는 후회를 예측함을 확인했습니다. 본 연구의 기여는 새로운 추정기를 제안하는 것이 아니라, 개념적이고 경험적인 측면—최악 사례 기반의 강건한 쿼리 최적화(robust query optimization)에 대한 평균 사례 대응물(average-case companion)을 제시하고, 정확도 지표가 언제 계획 품질을 추적하는지를 규명하는 것—에 있습니다. 코드와 전체 사전 등록 내용은 공개되어 있습니다.