중앙 집중식 시스템의 쿼리 최적화
관계형 대수식 계산을위한 대체 액세스 경로가 파생되면 최적의 액세스 경로가 결정됩니다. 이 장에서는 중앙 집중식 시스템에서 쿼리 최적화를 살펴보고 다음 장에서는 분산 시스템에서 쿼리 최적화를 살펴 보겠습니다.
중앙 집중식 시스템에서 쿼리 처리는 다음과 같은 목적으로 수행됩니다.
질의 응답 시간 최소화 (사용자 질의에 대한 결과 생성에 소요되는 시간)
시스템 처리량 (주어진 시간 동안 처리되는 요청 수)을 최대화합니다.
처리에 필요한 메모리 및 스토리지 양을 줄이십시오.
병렬 처리를 늘리십시오.
쿼리 구문 분석 및 번역
처음에는 SQL 쿼리가 스캔됩니다. 그런 다음 구문 오류 및 데이터 유형의 정확성을 찾기 위해 구문 분석됩니다. 쿼리가이 단계를 통과하면 쿼리가 더 작은 쿼리 블록으로 분해됩니다. 그런 다음 각 블록은 동등한 관계형 대수식으로 변환됩니다.
쿼리 최적화를위한 단계
쿼리 최적화에는 쿼리 트리 생성, 계획 생성 및 쿼리 계획 코드 생성의 세 단계가 포함됩니다.
Step 1 − Query Tree Generation
쿼리 트리는 관계형 대수 표현식을 나타내는 트리 데이터 구조입니다. 쿼리 테이블은 리프 노드로 표시됩니다. 관계형 대수 연산은 내부 노드로 표시됩니다. 루트는 쿼리 전체를 나타냅니다.
실행 중에 내부 노드는 피연산자 테이블을 사용할 수있을 때마다 실행됩니다. 그런 다음 노드는 결과 테이블로 대체됩니다. 이 프로세스는 루트 노드가 실행되고 결과 테이블로 대체 될 때까지 모든 내부 노드에 대해 계속됩니다.
예를 들어, 다음 스키마를 고려해 보겠습니다.
종업원
| EmpID | EName | 봉급 | 부서 번호 | DateOfJoining |
학과
| D 아니 | DName | 위치 |
예 1
쿼리를 다음과 같이 생각해 봅시다.
$$ \ pi_ {EmpID} (\ sigma_ {EName = \ small "ArunKumar"} {(EMPLOYEE)}) $$
해당 쿼리 트리는-
예 2
조인과 관련된 다른 쿼리를 고려해 보겠습니다.
$ \ pi_ {EName, Salary} (\ sigma_ {DName = \ small "Marketing"} {(DEPARTMENT)}) \ bowtie_ {DNo = DeptNo} {(EMPLOYEE)} $
다음은 위 쿼리에 대한 쿼리 트리입니다.
Step 2 − Query Plan Generation
쿼리 트리가 생성 된 후 쿼리 계획이 작성됩니다. 쿼리 계획은 쿼리 트리의 모든 작업에 대한 액세스 경로를 포함하는 확장 쿼리 트리입니다. 액세스 경로는 트리에서 관계형 작업을 수행하는 방법을 지정합니다. 예를 들어, 선택 작업에는 선택을위한 B + 트리 인덱스 사용에 대한 세부 정보를 제공하는 액세스 경로가있을 수 있습니다.
또한 쿼리 계획에는 한 연산자에서 다음 연산자로 중간 테이블을 전달하는 방법, 임시 테이블을 사용하는 방법 및 작업을 파이프 라인 / 결합하는 방법도 나와 있습니다.
Step 3− Code Generation
코드 생성은 쿼리 최적화의 마지막 단계입니다. 쿼리의 실행 가능한 형식이며, 그 형식은 기본 운영 체제의 유형에 따라 다릅니다. 쿼리 코드가 생성되면 Execution Manager가이를 실행하고 결과를 생성합니다.
쿼리 최적화에 대한 접근 방식
쿼리 최적화를위한 접근 방식 중 대부분은 철저한 검색 및 휴리스틱 기반 알고리즘이 사용됩니다.
철저한 검색 최적화
이러한 기술에서는 쿼리에 대해 가능한 모든 쿼리 계획이 처음에 생성 된 다음 최상의 계획이 선택됩니다. 이러한 기술이 최상의 솔루션을 제공하지만 솔루션 공간이 크기 때문에 시간과 공간이 기하 급수적으로 복잡해집니다. 예를 들어, 동적 프로그래밍 기술입니다.
휴리스틱 기반 최적화
휴리스틱 기반 최적화는 쿼리 최적화를 위해 규칙 기반 최적화 접근 방식을 사용합니다. 이러한 알고리즘은 다항식 시간 및 공간 복잡도를 가지며 이는 철저한 검색 기반 알고리즘의 지수 복잡도보다 낮습니다. 그러나 이러한 알고리즘이 반드시 최상의 쿼리 계획을 생성하는 것은 아닙니다.
일반적인 휴리스틱 규칙 중 일부는 다음과 같습니다.
조인 작업 전에 선택 및 프로젝트 작업을 수행합니다. 이 작업은 선택 및 프로젝트 작업을 쿼리 트리 아래로 이동하여 수행됩니다. 이렇게하면 조인에 사용할 수있는 튜플 수가 줄어 듭니다.
다른 작업보다 먼저 가장 제한적인 선택 / 프로젝트 작업을 수행합니다.
중간 테이블 크기가 매우 커지므로 교차 제품 작업을 피하십시오.