학습 기반 카디널리티 추정과 조인 샘플링을 위한 질의 최적화 연구

Learned Cardinality Estimation and Join Sampling for Query Optimization

연구 내용

조인 및 부분그래프 매칭에 필요한 카디널리티를 학습 모델과 샘플링으로 추정하여 질의 최적화의 비용 산정을 향상시키는 연구

대규모 데이터베이스에서 조인 질의와 부분그래프 매칭의 비용을 좌우하는 카디널리티를 정확도와 실행 효율을 함께 만족하도록 추정합니다. 테이블 단위 통계는 autoregressive model 기반으로 구성하고, join 키의 비독립성을 고려한 multi-dimensional statistics merging과 sampling 절차로 조인 결과 규모를 통합 추정합니다. 또한 필터링으로 샘플 공간을 축소한 뒤 adaptive tree sampling과 최악경우 보장형 stratified graph sampling을 결합하여 subgraph cardinality estimation의 정확도를 높입니다. 이를 통해 query optimizer 내부에서 재사용 가능한 추정치를 제공하는 데 중점을 둡니다.

관련 프로젝트

5건

연구 흐름

초기에는 조인에서 결과 개수 OUT을 추정하고 uniform sampling을 보장하는 이론적 기반을 마련했습니다. 이후 학습 기반 카디널리티 추정에서 per-table 통계를 생성하는 autoregressive model과 통합 과정의 효율을 조정하는 sampling 메커니즘을 결합하는 방향으로 연구를 확장했습니다. 2024년에는 다차원 통계 병합을 통해 join 키 독립 가정을 완화하고, 질의 최적화에서의 end-to-end 실행 시간과 더 넓은 질의 범위를 동시에 만족시키는 학습 추정기를 제안했습니다. 동시에 부분그래프 매칭의 카디널리티 추정을 위해 filtering-sampling 접근을 체계화하여 성능 격차를 분석하고 실용적인 추정 프레임워크로 발전시켰습니다.

활용 가능성

활용 가능성은 알앤디써클 특화 AI 에이전트가 생성한 내용으로, 실제 연구 가능 여부는 연구실과의 논의가 필요합니다.

learned cardinality estimator
join size estimation
subgraph counting estimation
uniform join sampling
adaptive sampling planning
query optimizer cost modeling
non-independence join estimation
sampling-based approximate query processing
multi-dimensional statistics merging
graph analytics workload estimation