비용 기반 질의 최적화

비용 기반 질의 최적화는 질의에 대한 동등한 실행 계획들의 공간을 탐색하고, 데이터에 대한 통계와 실행 비용 모델을 사용하여 추정된 비용이 가장 낮은 계획을 선택합니다.

Definition

비용 기반 질의 최적화는 데이터 통계와 비용 모델로부터 질의에 대한 대체 동등 계획들의 실행 비용을 추정하고, 추정된 비용이 가장 적은 계획을 선택하는 과정이며, 일반적으로 동적 프로그래밍에 의해 조인 순서가 선택됩니다.

Scope

이 주제는 최적화 프로그램이 계획을 선택하는 방법을 다룹니다: 관계 대수 등가성 및 대체 물리적 연산자에 의해 생성되는 계획 탐색 공간, 계획 점수를 매기는 비용 모델(주로 I/O 및 CPU), 통계 및 히스토그램을 통한 카디널리티 및 선택도 추정, 그리고 System R에 의해 도입된 조인 순서 열거를 위한 동적 프로그래밍 접근 방식. 연산자 자체의 구현과 계획 생성에 필요한 범위를 넘어서는 규칙 기반 논리적 재작성은 제외됩니다.

Core questions

• 동등한 실행 계획의 공간은 어떻게 생성되고 가지치기되는가?
• 최적화 프로그램은 연산의 카디널리티와 선택도를 어떻게 추정하는가?
• 동적 프로그래밍은 조인 순서를 어떻게 효율적으로 열거하는가?
• 비용 모델은 무엇을 고려하며, I/O 및 CPU 비용은 어떻게 결합되는가?
• 카디널리티 추정 오류가 왜 잘못된 계획 선택을 유발하는가?

Key concepts

• 계획 탐색 공간
• 비용 모델 (I/O 및 CPU)
• 선택도 및 카디널리티 추정
• 히스토그램 및 통계
• 조인 순서 열거
• 동적 프로그래밍
• 흥미로운 순서
• 변환 기반 최적화

Key theories

System R 동적 프로그래밍 최적화

Selinger의 최적화 프로그램은 동적 프로그래밍을 사용하여 조인 순서를 상향식으로 열거하며, 각 관계 부분집합(및 각 흥미로운 정렬 순서)에 대해 가장 저렴한 계획을 유지하여 대규모 조인 순서 공간 탐색을 다룰 수 있게 만듭니다.

카디널리티 및 선택도 추정

최적화 프로그램은 테이블 통계, 히스토그램 및 선택도 공식을 사용하여 각 연산이 생성하는 튜플 수를 추정합니다. 이러한 추정치는 비용 모델을 구동하며 최적화 오류의 주요 원인입니다.

비용 모델 및 탐색 전략

계획은 I/O, CPU 및 메모리 효과를 결합한 비용 모델에 의해 점수가 매겨집니다. System R의 동적 프로그래밍 외에도 변환 기반 최적화 프로그램은 재작성 규칙을 통해 계획을 탐색하여 더 풍부한 연산자와 분산 환경으로 최적화를 확장합니다.

Clinical relevance

최적화 프로그램은 사용자가 실행 방법을 지정하지 않고도 선언적 SQL을 작성할 수 있게 해주는 구성 요소입니다. 비용 추정 및 탐색의 품질은 대규모 데이터베이스에서 질의가 빠른지 여부를 직접적으로 좌우하므로, 비용 기반 최적화는 데이터베이스 시스템에서 가장 많이 연구되고 상업적으로 중요한 부분 중 하나입니다.

History

1979년 Selinger와 동료들이 개발한 System R 최적화 프로그램은 동적 프로그래밍 조인 순서 지정 및 선택도 기반 비용 추정을 통해 비용 기반 최적화를 도입하여 이 분야를 정의했습니다. 이후 Volcano 및 Cascades와 같은 변환 기반 최적화 프로그램은 탐색을 일반화했으며, 학습된 모델을 포함한 카디널리티 추정에 대한 지속적인 연구는 이 프레임워크의 주요 약점을 해결하고 있습니다.

Debates

카디널리티 추정 대 적응형 실행

비용 기반 최적화는 크기 추정만큼만 좋으며, 상관 관계가 있는 데이터의 경우 종종 잘못될 수 있기 때문에, 연구자들은 더 나은 통계 및 기계 학습된 추정기에 투자할지 아니면 실행 중에 잘못된 계획을 수정하는 적응형, 런타임 재최적화에 더 의존할지에 대해 논쟁합니다.

Key figures

• Patricia Selinger
• Goetz Graefe
• Surajit Chaudhuri

Seminal works

• selinger1979
• graefe1993

Frequently asked questions

최적화 프로그램이 때때로 잘못된 계획을 선택하는 이유는 무엇인가요?

비용 기반 최적화 프로그램은 각 연산이 생성할 행 수에 대한 추정치에 의존합니다. 데이터가 편향되거나 열이 상관 관계를 가질 때, 이러한 추정치는 크게 벗어날 수 있으며, 오류는 조인을 거치면서 누적됩니다. 잘못된 추정치는 최적화 프로그램이 서류상으로는 저렴해 보이는 계획임에도 불구하고 좋지 않은 조인 순서나 접근 경로를 선택하게 만들 수 있습니다.

조인 순서 지정을 위해 동적 프로그래밍을 사용하는 이유는 무엇인가요?

가능한 조인 순서의 수는 테이블 수에 따라 조합적으로 증가하므로, 완전 탐색은 불가능합니다. 동적 프로그래밍은 더 작은 부분집합에 대한 최적 계획으로부터 더 큰 관계 집합에 대한 최적 계획을 구축하여, 작업량을 극적으로 줄이면서도 일반적인 질의 크기에 대해 좋은(종종 최적의) 조인 순서를 찾습니다.