쿼리 최적화

Query optimization

쿼리 최적화는 많은 관계형 데이터베이스 관리 시스템 및 그래프 데이터베이스와 같은 기타 데이터베이스의 기능입니다.쿼리 옵티마이저는 가능한 쿼리 [1]플랜을 고려하여 특정 쿼리를 실행하는 가장 효율적인 방법을 결정합니다.

일반적으로 쿼리 옵티마이저는 사용자가 직접 액세스할 수 없습니다.쿼리가 데이터베이스 서버에 송신되어 파서에 의해 해석되면 최적화가 [2][3]이루어지는 쿼리 옵티마이저로 전달됩니다.그러나 일부 데이터베이스 엔진에서는 쿼리 최적화 도구를 힌트로 안내할 수 있습니다.

쿼리는 데이터베이스에 대한 정보 요청입니다."사회보장번호 123-45-6789를 가진 사람의 주소를 찾아라"처럼 간단할 수도 있고, "배우자보다 수입이 적은 30-39세 캘리포니아의 모든 기혼 남성의 평균 급여를 찾아라"처럼 더 복잡할 수도 있다.쿼리 결과는 요청된 정보를 생성하는 방식으로 데이터베이스의 행을 처리하여 생성됩니다.데이터베이스 구조는 대부분의 경우 매우 단순하지 않은 쿼리의 경우 복잡하기 때문에 쿼리에 필요한 데이터는 다른 방법, 다른 데이터 구조 및 다른 [4]순서로 접근하여 데이터베이스에서 수집할 수 있습니다.일반적으로 각 방법마다 처리 시간이 다릅니다.동일한 쿼리의 처리 시간은 선택한 방법에 따라 몇 초에서 몇 시간까지 큰 차이가 있을 수 있습니다.자동화된 프로세스인 쿼리 최적화의 목적은 주어진 쿼리를 최소 시간 내에 처리하는 방법을 찾는 것입니다.가능한 시간의 큰 편차는 쿼리 최적화를 수행하는 것을 정당화하지만, 모든 가능성 중에서 정확한 최적의 쿼리 계획을 찾는 것은 일반적으로 매우 복잡하고 시간이 많이 걸리며 비용이 너무 많이 들 뿐만 아니라 실제로 불가능할 수도 있습니다.따라서 쿼리 최적화는 일반적으로 몇 가지 상식적인 대안을 비교하여 최적의 결과를 크게 벗어나지 않는 "충분히 좋은" 계획을 합리적인 시간 내에 제공함으로써 최적화를 시도합니다.

일반적인 고려 사항

최적의 쿼리 계획을 알아내는 데 소요되는 시간과 선택의 품질 사이에는 트레이드오프가 있습니다.최적화자가 스스로 최적의 답을 선택하지 않을 수도 있습니다.데이터베이스 관리 시스템의 품질에 따라 이 두 가지 균형을 맞추는 방법이 다릅니다.비용 기반 쿼리 옵티마이저는 다양한 쿼리 계획의 리소스 풋프린트를 평가하고 이를 계획 [5]선택의 기준으로 사용합니다.이들은 가능한 각 쿼리 계획에 추정된 "비용"을 할당하고 비용이 가장 적게 드는 계획을 선택합니다.비용은 필요한 I/O 작업 수, CPU 경로 길이, 디스크 버퍼 공간 양, 디스크 스토리지 서비스 시간, 병렬 장치 간 상호 연결 사용량 및 데이터 사전에서 결정된 기타 요인에 따라 쿼리 평가 런타임 비용을 추정하는 데 사용됩니다.검사된 쿼리 계획 세트는 가능한 액세스 경로(예: 프라이머리 인덱스 액세스, 2차 인덱스 액세스, 전체 파일 스캔)와 다양한 관계형 테이블 조인 기술(예: 병합 조인, 해시 조인, 제품 조인)을 검사하여 형성됩니다.검색 공간은 SQL 쿼리의 복잡도에 따라 상당히 커질 수 있습니다.최적화에는 두 가지 유형이 있습니다.이는 쿼리를 해결하기 위한 일련의 관계대수를 생성하는 논리적 최적화와 각 작업을 수행하는 방법을 결정하는 데 사용되는 물리적 최적화로 구성됩니다.

실행

대부분의 쿼리 옵티마이저는 쿼리 계획을 "계획 노드" 트리로 나타냅니다.계획 노드는 쿼리를 실행하는 데 필요한 단일 작업을 캡슐화합니다.노드는 트리로 배열되어 있으며, 중간 결과는 트리의 하단에서 상단으로 흐릅니다.각 노드에는 0개 이상의 자 노드가 있습니다.자노드는 부모 노드에 입력으로 출력이 공급되는 노드입니다.예를 들어, 결합 노드에는 2개의 결합 오퍼랜드를 나타내는2개의 자 노드가 있는 반면, 정렬 노드에는 1개의 자 노드가 있습니다(정렬할 입력).트리의 잎은 인덱스 스캔 또는 순차 스캔을 수행하는 등의 방법으로 디스크를 스캔하여 결과를 생성하는 노드입니다.

조인 순서

쿼리 계획의 성능은 주로 테이블이 결합되는 순서에 따라 결정됩니다.예를 들어 크기가 각각 10행, 10,000행 및 1,000,000행인 3개의 테이블 A, B, C를 결합할 때 B와 C를 먼저 결합하는 쿼리 계획은 A와 C를 먼저 결합하는 쿼리 계획보다 몇 배 더 오래 걸릴 수 있습니다.대부분의 쿼리 옵티마이저는 IBM의 System R 데이터베이스[citation needed] 프로젝트에서 개척한 동적 프로그래밍 알고리즘을 통해 조인 순서를 결정합니다.이 알고리즘은 2단계로 동작합니다.

  1. 먼저 쿼리의 각 관계에 액세스하는 모든 방법이 계산됩니다.쿼리의 모든 관계는 순차 스캔을 통해 액세스할 수 있습니다.쿼리의 술어에 응답하는 데 사용할 수 있는 관계에 인덱스가 있는 경우 인덱스 스캔도 사용할 수 있습니다.각 관계에 대해 옵티마이저는 특정 정렬 순서로 레코드를 생성하는 관계를 스캔하는 가장 저렴한 방법뿐만 아니라 관계를 스캔하는 가장 저렴한 방법도 기록합니다.
  2. 그런 다음 옵티마이저는 결합 조건이 존재하는 각 관계 쌍의 결합을 고려합니다.각 쌍에 대해 옵티마이저는 DBMS에 의해 구현된 사용 가능한 결합 알고리즘을 고려합니다.또한 특정 정렬 순서에 따라 출력을 생성하는 각 관계 쌍을 결합하는 가장 저렴한 방법뿐만 아니라 각 관계 쌍을 결합하는 가장 저렴한 방법을 유지합니다.
  3. 그런 다음 이전 단계에서 생성된 각 2개의 관계 계획을 쿼리의 나머지 관계와 결합함으로써 모든 3개의 관계 쿼리 계획이 계산됩니다.

정렬 순서를 지정하면 나중에 쿼리를 처리할 때 중복 정렬 작업을 피할 수 있습니다.둘째, 특정 정렬 순서는 특정 방식으로 데이터를 클러스터링하기 때문에 후속 조인 속도를 높일 수 있습니다.

중첩된 SQL 쿼리에 대한 쿼리 계획

최신 관계형 DBMS에 대한 SQL 쿼리는 단순히 선택과 결합만을 수행하는 것이 아닙니다.특히 SQL 쿼리는 SPJ 블록의 여러 레이어(Select-Project-Join)를 그룹화 기준으로 포함하거나 존재하거나 존재하지 않는 연산자를 통해 중첩하는 경우가 많습니다.경우에 따라서는 이러한 중첩된 SQL 쿼리를 select-project-join 쿼리로 평탄화할 수 있지만 항상 그런 것은 아닙니다.중첩된 SQL 쿼리에 대한 쿼리 계획도 조인 순서와 동일한 동적 프로그래밍 알고리즘을 사용하여 선택할 수 있지만 쿼리 최적화 시간이 크게 늘어날 수 있습니다.따라서 일부 데이터베이스 관리 시스템에서는 쿼리 그래프 [6]모델을 사용하는 대체 규칙 기반 접근 방식을 사용합니다.

비용 견적

쿼리 최적화에서 가장 어려운 문제 중 하나는 대체 쿼리 계획의 비용을 정확하게 추정하는 것입니다.Optimizer는 쿼리 계획의 각 에지를 통과하는 카디널리티 또는 튜플 수의 추정치에 크게 의존하는 쿼리 실행 비용의 수학적 모델을 사용하여 쿼리 계획을 비용화합니다.카디널리티 추정은 질의에 포함된 술어의 선택 팩터 추정치에 따라 달라집니다.전통적으로 데이터베이스 시스템은 히스토그램과 같은 각 열의 값 분포에 대한 매우 상세한 통계를 통해 선택성을 추정했습니다.이 기술은 개별 술어의 선택성을 추정하는 데 효과적입니다.그러나 많은 쿼리에는 다음과 같은 술어가 결합되어 있습니다.select count(*) from R where R.make='Honda' and R.model='Accord'쿼리 술어는 많은 경우 높은 상관관계가 있습니다(예를 들어,model='Accord'암시하다make='Honda'일반적으로 결막의 선택성을 추정하는 것은 매우 어렵다.빈약한 카디널리티 추정치와 파악되지 않은 상관관계는 쿼리 최적기가 빈약한 쿼리 계획을 선택하는 주요 이유 중 하나입니다.이는 데이터베이스 관리자가 특히 주요 데이터 로드/언로드 후 데이터베이스 통계를 정기적으로 업데이트해야 하는 이유 중 하나입니다.

내선번호

기존 쿼리 최적화는 쿼리 계획이 단일 비용 메트릭(일반적으로 실행 시간)에 따라 비교되고 각 쿼리 계획의 비용이 불확실성 없이 계산될 수 있다고 가정합니다.두[7] 가정 모두 실제로 위반되는 경우가 있으며, 이러한 한계를 극복한 연구 문헌에서 고전적인 쿼리 최적화의 여러 확장이 연구되었다.이러한 확장된 문제 변형은 단일 쿼리 계획의 비용을 모델링하는 방법과 최적화 목표 측면에서 다릅니다.

파라미터 쿼리 최적화

기존 쿼리 최적화에서는 각 쿼리 플랜을 1개의 스칼라 비용 값에 관련짓습니다.파라미터 쿼리[8] 최적화에서는 쿼리 계획 비용이 최적화 시 값을 알 수 없는 파라미터에 따라 결정된다고 가정합니다.예를 들어 이러한 파라미터는 최적화 시 완전히 지정되지 않았지만 실행 시 제공되는 쿼리 술어의 선택성을 나타낼 수 있습니다.따라서 파라메트릭 쿼리 최적화는 각 쿼리 계획을 다차원 파라미터 공간에서 1차원 비용 공간으로 매핑하는 비용 함수와 관련짓습니다.

최적화의 목적은 일반적으로 가능한 매개 변수 값 조합에 최적인 모든 쿼리 계획을 생성하는 것입니다.이를 통해 일련의 관련 쿼리 계획이 생성됩니다.실행 시 실제 파라미터 값이 확인되면 해당 세트 중에서 최적의 계획이 선택됩니다.파라미터 쿼리 최적화의 장점은 런타임에 최적화(일반적으로 매우 비용이 많이 드는 작업)를 피할 수 있다는 것입니다.

다목적 쿼리 최적화

쿼리 계획 비교와 관련된 실행 시간 외에도 다른 비용 메트릭이 있는 경우가 많습니다.예를 들어 클라우드 컴퓨팅 시나리오에서는 쿼리 계획을 실행하는 데 소요되는 시간뿐만 아니라 실행 비용도 비교해야 합니다.또는 근사 쿼리 최적화의 맥락에서 실행 오버헤드를 줄인 근사 결과를 얻기 위해 무작위로 선택된 입력 데이터의 샘플에 대해 쿼리 계획을 실행할 수 있다.이러한 경우, 대체 쿼리 계획은 실행 시간뿐만 아니라 생성되는 데이터의 정밀도 또는 신뢰성 측면에서도 비교되어야 합니다.

다목적 쿼리[9] 최적화는 쿼리 계획의 비용을 비용 벡터로 모델링합니다.여기서 각 벡터 구성요소는 다른 비용 메트릭에 따라 비용을 나타냅니다.고전적인 쿼리 최적화는 비용 공간의 차원(즉, 비용 벡터 구성요소의 수)이 1인 다목적 쿼리 최적화의 특별한 경우로 간주될 수 있다.

서로 다른 비용 지표가 서로 충돌할 수 있습니다(예: 클라우드 컴퓨팅 시나리오에서는 실행 시간이 최소인 하나의 계획과 실행 비용이 최소인 다른 계획이 있을 수 있습니다).따라서 최적화의 목표는 모든 비용 메트릭을 최소화하는 쿼리 계획을 찾는 것이 아니라 서로 다른 비용 메트릭 간에 최적의 타협을 실현하는 쿼리 계획을 찾는 것입니다.최적의 절충안은 사용자 선호도에 따라 달라집니다(예: 클라우드 시나리오에서 더 저렴한 요금제를 선호하는 사용자도 있고 더 빠른 요금제를 선호하는 사용자도 있습니다).따라서 최적화의 목표는 최적화 도구에 입력으로 제공된 사용자 선호도의 일부 사양을 기반으로 최적의 쿼리 계획을 찾거나(예: 사용자는 상대적 중요성을 표현하기 위해 다른 비용 메트릭 간의 가중치를 정의하거나 특정 메트릭에 대한 하드 비용 한계를 정의할 수 있음) 파레토 세트의 근사치를 생성하는 것이다.최적의 질의 계획(즉, 모든 지표에 따라 다른 계획이 더 나은 비용을 갖지 않도록 하는 계획)을 통해 사용자가 해당 계획 집합에서 원하는 비용 트레이드오프를 선택할 수 있습니다.

다목적 파라미터 쿼리 최적화

다목적 파라미터 쿼리[7] 최적화는 파라미터 및 다목적 쿼리 최적화를 일반화합니다.계획은 여러 비용 지표에 따라 비교되며, 계획 비용은 최적화 시 값을 알 수 없는 매개변수에 따라 달라질 수 있습니다.따라서 쿼리 계획의 비용은 다차원 매개변수 공간에서 다차원 비용 공간까지의 함수로 모델링된다.최적화의 목적은 매개 변수 값과 사용자 기본 설정의 가능한 각 조합에 최적일 수 있는 쿼리 계획 세트를 생성하는 것입니다.

많은 툴이 쿼리 실행 계획을 표시하여 처리 비용이 가장 높은 작업을 보여줍니다.Microsoft SMS, ApexSQLPlan, Hana, Tableau가 그 예입니다.이러한 계획에서 발견된 문제를 수정하면 실행 시간을 수십 % 단축할 수 있으며 경우에 따라 2차원 검색을 선형 검색으로 줄일 수 있습니다.

가장 중요하고 간단한 최적화 체크리스트 중 하나는 대부분의 RDMS가 효율적으로 실행하도록 설계된 작업을 사용하는 것입니다.'Sargable' 참조.

「 」를 참조해 주세요.

레퍼런스

  1. ^ "IBM Knowledge Center". www.ibm.com.
  2. ^ Ioannidis, Yannis (March 1996). "Query optimization". ACM Computing Surveys. 28 (1): 121–123. doi:10.1145/234313.234367.
  3. ^ Chaudhuri, Surajit (1998). "An Overview of Query Optimization in Relational Systems". Proceedings of the ACM Symposium on Principles of Database Systems. pp. 34–43. doi:10.1145/275487.275492.
  4. ^ 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. pp. 23–34. doi:10.1145/582095.582099. ISBN 089791001X.
  5. ^ "Oracle SQL cost based optimization". www.dba-oracle.com.
  6. ^ "EXPLAIN QUERY PLAN". www.sqlite.org.
  7. ^ a b Trummer, Immanuel; Koch, Christoph (2015). "Multi-Objective Parametric Query Optimization". VLDB: 221–232.
  8. ^ Ioannidis, Yannis; Ng, Raymond T.; Shim, Kyuseok; Sellis, Timos K. (1997). "Parametric Query Optimization". VLDB. 6 (2): 132–151. CiteSeerX 10.1.1.33.696. doi:10.1007/s007780050037.
  9. ^ Trummer, Immanuel; Koch, Christoph (2014). Approximation Schemes for Many-Objective Query Optimization. SIGMOD. pp. 1299–1310. arXiv:1404.0046.