질의 최적화
질의 최적화 또는 쿼리 최적화(Query optimization)는 수많은 관계형 데이터베이스 관리 시스템, 그리고 그래프 데이터베이스 등의 기타 데이터베이스의 기능이다. 쿼리 옵티마이저(query optimizer)는 잠재적인 쿼리 플랜을 고려함으로써 주어진 쿼리를 가장 효율적인 실행하는 방법을 정의하는 일을 시도한다.[1]
일반적으로 쿼리 옵티마이저는 사용자에 의해 직접 접근이 불가능하다. 쿼리가 데이터베이스 서버에 제출되고 파서에 의해 파싱이 되면 이것들은 최적화가 발생하는 쿼리 옵티마이저에 전달하게 된다.[2][3] 그러나 일부 데이터베이스 엔진은 힌트와 함께 쿼리 옵티마이저의 가이드를 허용한다.
질의는 데이터베이스에 정보를 요청하는 것이다. "사회 보장 번호가 123-45-6789인 사람의 주소를 찾아라"와 같이 간단할 수도 있고, "30세에서 39세 사이의 캘리포니아에 거주하는 기혼 남성 중 배우자보다 수입이 적은 모든 직장인의 평균 급여를 찾아라"와 같이 더 복잡할 수도 있다. 질의 결과는 요청된 정보를 산출하는 방식으로 데이터베이스의 로우를 처리함으로써 생성된다. 데이터베이스 구조는 복잡하기 때문에, 대부분의 경우, 특히 아주 단순하지 않은 질의의 경우 질의에 필요한 데이터는 서로 다른 데이터 구조를 통해, 그리고 서로 다른 순서로 데이터베이스에 액세스하는 다양한 방식으로 수집될 수 있다.[4] 각 방식은 일반적으로 서로 다른 처리 시간을 필요로 한다. 동일한 질의라도 선택된 방법에 따라 처리 시간이 1초 미만에서 몇 시간까지 큰 차이를 보일 수 있다. 자동화된 프로세스인 질의 최적화의 목적은 주어진 질의를 최소 시간에 처리할 수 있는 방법을 찾는 것이다. 가능한 시간 편차가 크다는 점이 질의 최적화 수행을 정당화하지만, 모든 가능성 중에서 정확한 최적의 질의 계획을 찾는 것은 일반적으로 매우 복잡하고 그 자체로 시간이 많이 걸리며 비용이 너무 많이 들거나 종종 실질적으로 불가능할 수 있다. 따라서 질의 최적화는 일반적으로 몇 가지 상식적인 대안을 비교하여 합리적인 시간 내에 최적의 결과와 크게 다르지 않은 "충분히 좋은" 계획을 제공함으로써 최적값에 근사하려고 시도한다.
일반적 고려 사항
[편집]최적의 질의 계획을 찾아내는 데 걸리는 시간과 선택의 품질 사이에는 트레이드오프가 존재하며, 최적화 프로그램이 스스로 최선의 답을 선택하지 못할 수도 있다. 데이터베이스 관리 시스템의 품질에 따라 이 두 가지의 균형을 맞추는 방식이 다르다. 비용 기반 질의 최적화 프로그램은 다양한 질의 계획의 리소스 사용량을 평가하고 이를 계획 선택의 기준으로 사용한다.[5][6] 이러한 방식은 가능한 각 질의 계획에 추정된 "비용"을 할당하고, 비용이 가장 적은 계획을 선택한다. 비용은 필요한 I/O 작업 수, CPU 경로 길이, 디스크 버퍼 공간 양, 디스크 저장소 서비스 시간, 병렬 처리 단위 간의 상호 연결 사용량 및 데이터 사전에서 결정된 기타 요인 측면에서 질의를 평가하는 런타임 비용을 추정하는 데 사용된다. 검토되는 질의 계획 세트는 가능한 액세스 경로(예: 기본 인덱스 액세스, 보조 인덱스 액세스, 전체 파일 스캔)와 다양한 관계형 테이블 조인 기술(예: 머지 조인, 해시 조인, 프로덕트 조인)을 검토하여 형성된다. 탐색 공간은 SQL 질의의 복잡성에 따라 상당히 커질 수 있다. 최적화에는 두 가지 유형이 있다. 질의를 해결하기 위한 관계대수 시퀀스를 생성하는 논리적 최적화와 각 작업을 수행하는 수단을 결정하는 데 사용되는 물리적 최적화로 구성된다.
구현
[편집]대부분의 질의 최적화 프로그램은 질의 계획을 "계획 노드"의 트리로 나타낸다. 계획 노드는 질의를 실행하는 데 필요한 단일 작업을 캡슐화한다. 노드들은 트리의 아래쪽에서 위쪽으로 중간 결과가 흐르는 트리 형태로 배열된다. 각 노드는 0개 이상의 자식 노드를 가지며, 자식 노드의 출력은 부모 노드의 입력으로 제공된다. 예를 들어, 조인 노드는 두 개의 조인 피연산자를 나타내는 두 개의 자식 노드를 갖는 반면, 정렬 노드는 단일 자식 노드(정렬할 입력)를 갖는다. 트리의 잎은 인덱스 스캔 또는 순차 스캔 등을 수행하여 디스크를 스캔하여 결과를 생성하는 노드이다.
조인 순서 결정
[편집]
질의 계획의 성능은 주로 테이블이 조인되는 순서에 의해 결정된다. 예를 들어 각각 10개, 10,000개, 1,000,000개 로우 크기를 가진 세 테이블 A, B, C를 조인할 때, B와 C를 먼저 조인하는 질의 계획은 A와 C를 먼저 조인하는 계획보다 실행하는 데 수십 배 더 많은 시간이 걸릴 수 있다. 대부분의 질의 최적화 프로그램은 IBM의 IBM 시스템 R 데이터베이스 프로젝트에서 개척한 동적 계획법 알고리즘을 통해 Join (SQL) 순서를 결정한다. 이 알고리즘은 두 단계로 작동한다.
- 먼저 질의의 각 관계에 액세스하는 모든 방법을 계산한다. 질의의 모든 관계는 순차 스캔을 통해 액세스할 수 있다. 질의의 술어에 응답하는 데 사용할 수 있는 인덱스가 관계에 있는 경우 인덱스 스캔도 사용할 수 있다. 각 관계에 대해 최적화 프로그램은 관계를 스캔하는 가장 저렴한 방법뿐만 아니라 특정 정렬 순서로 레코드를 생성하는 가장 저렴한 스캔 방법을 기록한다.
- 그런 다음 최적화 프로그램은 조인 조건이 존재하는 각 관계 쌍의 결합을 고려한다. 각 쌍에 대해 최적화 프로그램은 데이터베이스 관리 시스템에서 구현된 사용 가능한 조인 알고리즘을 고려한다. 각 관계 쌍을 조인하는 가장 저렴한 방법과 특정 정렬 순서에 따라 출력을 생성하는 각 관계 쌍을 조인하는 가장 저렴한 방법을 보존한다.
- 그런 다음 이전 단계에서 생성된 모든 두 관계 계획을 질의의 나머지 관계와 조인하여 모든 세 관계 질의 계획을 계산한다.
정렬 순서는 나중에 질의를 처리할 때 중복되는 정렬 작업을 피할 수 있게 해준다. 또한 특정 정렬 순서는 데이터를 특정한 방식으로 클러스터링하기 때문에 후속 조인 속도를 높일 수 있다.
중첩된 SQL 질의를 위한 질의 계획
[편집]현대적인 관계형 DBMS에 대한 SQL 질의는 단순한 선택과 조인 이상의 작업을 수행한다. 특히 SQL 질의는 group by, exists, not exists 연산자를 통해 여러 층의 SPJ 블록(Select-Project-Join)을 중첩하는 경우가 많다. 어떤 경우에는 이러한 중첩된 SQL 질의를 select-project-join 질의로 평탄화할 수 있지만 항상 그런 것은 아니다. 중첩된 SQL 질의에 대한 질의 계획도 조인 순서 결정에 사용되는 것과 동일한 동적 계획법 알고리즘을 사용하여 선택할 수 있지만, 이는 질의 최적화 시간의 엄청난 에스컬레이션을 초래할 수 있다. 따라서 일부 데이터베이스 관리 시스템은 질의 그래프 모델을 사용하는 대안적인 규칙 기반 접근 방식을 사용한다.[7]
비용 추정
[편집]질의 최적화에서 가장 어려운 문제 중 하나는 대안적인 질의 계획의 비용을 정확하게 추정하는 것이다. 최적화 프로그램은 질의 계획의 각 에지를 통해 흐르는 튜플의 수, 즉 카디널리티 추정에 크게 의존하는 질의 실행 비용의 수학적 모델을 사용하여 질의 계획의 비용을 책정한다. 카디널리티 추정은 다시 질의 술어의 선택 인자 추정에 의존한다. 전통적으로 데이터베이스 시스템은 히스토그램과 같이 각 컬럼의 값 분포에 대한 상당히 상세한 통계를 통해 선택도를 추정한다. 이 기술은 개별 술어의 선택도를 추정하는 데 잘 작동한다.
하지만 많은 질의는 select count(*) from R where R.make='Honda' and R.model='Accord'와 같은 술어의 논리곱을 포함한다.
질의 술어는 종종 밀접하게 연관되어 있으며(예를 들어, model='Accord'는 make='Honda'를 의미함), 일반적으로 연접의 선택도를 추정하는 것은 매우 어렵다. 부적절한 카디널리티 추정과 포착되지 않은 상관관계는 질의 최적화 프로그램이 좋지 않은 질의 계획을 선택하는 주요 원인 중 하나이다. 이것이 데이터베이스 관리자가 특히 대량의 데이터 로드/언로드 후에 데이터베이스 통계를 정기적으로 업데이트해야 하는 이유 중 하나이다.
확장
[편집]고전적인 질의 최적화는 질의 계획이 하나의 단일 비용 메트릭(일반적으로 실행 시간)에 따라 비교되며, 각 질의 계획의 비용이 불확실성 없이 계산될 수 있다고 가정한다. 실제로는 두 가정 모두 위반되는 경우가 있으며[8] 이러한 한계를 극복하는 고전적 질의 최적화의 여러 확장 기능이 연구 문헌에서 다루어졌다. 이러한 확장된 문제 변형은 단일 질의 계획의 비용을 모델링하는 방식과 최적화 목표 측면에서 차이가 있다.
매개변수적 질의 최적화
[편집]고전적인 질의 최적화는 각 질의 계획을 하나의 스칼라 비용 값과 연관시킨다. 매개변수적 질의 최적화[9]는 질의 계획 비용이 최적화 시점에 값을 알 수 없는 매개변수에 의존한다고 가정한다. 이러한 매개변수는 예를 들어 최적화 시점에는 완전히 지정되지 않았지만 실행 시점에 제공될 질의 술어의 선택도를 나타낼 수 있다. 따라서 매개변수적 질의 최적화는 각 질의 계획을 다차원 매개변수 공간에서 일차원 비용 공간으로 매핑되는 비용 함수와 연관시킨다.
최적화의 목표는 일반적으로 가능한 매개변수 값 조합 중 어느 하나에 대해 최적일 수 있는 모든 질의 계획을 생성하는 것이다. 이는 관련 질의 계획 세트를 산출한다. 런타임에 실제 매개변수 값이 알려지면 해당 세트 중에서 최상의 계획이 선택된다. 매개변수적 질의 최적화의 장점은 런타임에 최적화(일반적으로 매우 비싼 작업임)를 피할 수 있다는 것이다.
다목적 질의 최적화
[편집]질의 계획을 비교하는 데 실행 시간 외에도 관련이 있는 다른 비용 메트릭이 종종 존재한다. 예를 들어 클라우드 컴퓨팅 시나리오에서는 질의 계획을 실행에 걸리는 시간뿐만 아니라 실행 비용이 얼마나 드는지 측면에서도 비교해야 한다. 또는 근사 질의 최적화의 맥락에서, 실행 오버헤드를 줄이면서 대략적인 결과를 얻기 위해 입력 데이터의 무작위로 선택된 샘플에서 질의 계획을 실행할 수 있다. 이러한 경우 대안적인 질의 계획은 실행 시간뿐만 아니라 생성하는 데이터의 정밀도나 신뢰성 측면에서도 비교되어야 한다.
다목적 질의 최적화[10]는 질의 계획의 비용을 각 벡터 구성 요소가 서로 다른 비용 메트릭에 따른 비용을 나타내는 비용 벡터로 모델링한다. 고전적인 질의 최적화는 비용 공간의 차원(즉, 비용 벡터 구성 요소의 수)이 1인 다목적 질의 최적화의 특수한 경우로 간주될 수 있다.
서로 다른 비용 메트릭은 서로 충돌할 수 있다(예: 클라우드 컴퓨팅 시나리오에서 실행 시간이 최소인 계획과 금전적 실행 비용이 최소인 계획이 다를 수 있음). 따라서 최적화의 목표는 모든 비용 메트릭을 최소화하는 질의 계획을 찾는 것이 아니라, 서로 다른 비용 메트릭 사이에서 최선의 절충안을 구현하는 질의 계획을 찾는 것이어야 한다. 최선의 절충안이 무엇인지는 사용자 선호도에 따라 달라진다(예: 클라우드 시나리오에서 일부 사용자는 더 저렴한 계획을 선호하는 반면 다른 사용자는 더 빠른 계획을 선호할 수 있음). 따라서 최적화의 목표는 최적화 프로그램의 입력으로 제공된 사용자 선호도 사양을 기반으로 최상의 질의 계획을 찾거나(예: 사용자는 상대적 중요성을 표현하기 위해 서로 다른 비용 메트릭 사이의 가중치를 정의하거나 특정 메트릭에 대해 엄격한 비용 범위를 정의할 수 있음), 파레토 최적 질의 계획 세트(즉, 모든 메트릭에 대해 더 나은 비용을 갖는 다른 계획이 없는 계획)의 근사치를 생성하여 사용자가 해당 계획 세트에서 선호하는 비용 트레이드오프를 선택할 수 있도록 하는 것이다.
다목적 매개변수적 질의 최적화
[편집]다목적 매개변수적 질의 최적화[8]는 매개변수적 및 다목적 질의 최적화를 일반화한다. 계획은 여러 비용 메트릭에 따라 비교되며 계획 비용은 최적화 시점에 값을 알 수 없는 매개변수에 의존할 수 있다. 따라서 질의 계획의 비용은 다차원 매개변수 공간에서 다차원 비용 공간으로의 함수로 모델링된다. 최적화의 목표는 매개변수 값과 사용자 선호도의 가능한 각 조합에 대해 최적일 수 있는 질의 계획 세트를 생성하는 것이다.
여러 도구에서 어떤 작업의 처리 비용이 가장 높은지 보여주기 위해 질의 실행 계획을 표시한다. Microsoft SMS, ApexSQLPlan, Hana, Tableau 등이 그 예이다. 이러한 계획에서 발견된 문제를 해결하면 실행 시간을 수십 퍼센트 단축할 수 있으며, 경우에 따라서는 2차원 탐색을 선형 탐색으로 줄일 수도 있다.
가장 기본적이고 간단한 최적화 체크리스트 중 하나는 대부분의 RDBMS가 효율적으로 실행하도록 설계된 작업을 사용하는 것이다. Sargable을 참조할 것.
각주
[편집]- ↑ “IBM Knowledge Center”. 《www.ibm.com》.
- ↑ Ioannidis, Yannis (March 1996). “Query optimization”. 《ACM Computing Surveys》 28 (1): 121–123. doi:10.1145/234313.234367.
- ↑ Chaudhuri, Surajit (1998). 〈An Overview of Query Optimization in Relational Systems〉. 《Proceedings of the ACM Symposium on Principles of Database Systems》. 34–43쪽. doi:10.1145/275487.275492.
- ↑ Selinger, P. G.; Astrahan, M. M.; Chamberlin, D. D.; Lorie, R. A.; Price, T. G. (1979). 〈Access Path Selection in a Relational Database Management System〉. 《Proceedings of the 1979 ACM SIGMOD International Conference on Management of Data》. 23–34쪽. doi:10.1145/582095.582099. ISBN 089791001X.
- ↑ “Oracle SQL cost based optimization”. 《www.dba-oracle.com》.
- ↑ “NoSQL Architect: Data modeling/query optimization for DynamoDB”. 《volisoft.org》.
- ↑ “EXPLAIN QUERY PLAN”. 《www.sqlite.org》.
- 1 2 Trummer, Immanuel; Koch, Christoph (2015). “Multi-Objective Parametric Query Optimization”. 《ACM SIGMOD Record》 45: 221–232. doi:10.1145/2949741.2949748.
- ↑ Ioannidis, Yannis; Ng, Raymond T.; Shim, Kyuseok; Sellis, Timos K. (1997). “Parametric Query Optimization”. 《The VLDB Journal the International Journal on Very Large Data Bases》 6 (2): 132–151. CiteSeerX 10.1.1.33.696. doi:10.1007/s007780050037. S2CID 3060505.
- ↑ Trummer, Immanuel; Koch, Christoph (2014). 《Approximation Schemes for Many-Objective Query Optimization》. SIGMOD. 1299–1310쪽. arXiv:1404.0046.
| 유형 | |
|---|---|
| 개념 | |
| 객체 | |
| 구성 요소 | |
| 기능 | |
| 관련 주제 | |
