질의 처리와 질의 최적화를 위한 알고리즘

목차

SQL 질의를 관계대수로 번역

13.2 외부 정렬 알고리즘

13.3 실렉트와 조인 연산을 위한 알고리즘

13.4 프로젝트와 집합 연산을 위한 알고리즘

13.5 질단 연산과 외부 조인의 구현

13.6 파이프라인을 사용한 연산의 결합

13.7 경험을 사용한 질의 최적화

13.8 질의 최적화에서 선택률과 비용추정치 사용

13.9 ORACLE의 질의 최적화의 개요

13.10 의미적 질의 최적화

13.11 요약

본문내용

정렬-합병 알고리즘
주 화일을 런(run)이라고 하는 작은 부화일(subfile)들로 나누고 이들을 정렬한 후 정렬한 런들을 합병하여 더 큰 규모의 정렬된 부화일들을 생성하는 과정을 반복한다. 주기억 장치에 버퍼 공간을 필요로 하며 그 버퍼 공간에서 런들의 실제 정렬과 합병이 수행된다. 정렬 단계이용가능한 버퍼 공간에 들어갈 수 있는 화일의 런들을 주기억 장치로 읽어온 뒤, 내부 정렬 알고리즘을 이용하여 정렬한 후 이들을 임시 정렬된 부화일(또는 런)로서 디스크에 저장한다. Read RUN; Sort; Write RUN합병 단계
정렬된 런들이 한 번 이상의 패스(pass)를 거쳐 합병된다. 4-way 합병 (4개의 RUN들을 합병하여 하나의 RUN을 생성)하나의 RUN으로 될 때 까지 합병을 반복 수행함단순 선택(simple selection)을 위한 탐색 방법
화일 스캔S1. 선형 탐색(linear search)S2. 이진 탐색(binary search)
인덱스 스캔S3. 기본 인덱스나 해시 키를 사용하여 단일 레코드를 검색
S4. 기본 인덱스를 사용하여 여러 개의 레코드들을 검색S5. 클러스터링 인덱스를 사용하여 여러 개의 레코드들을 검색S6. 보조(B+-트리) 인덱스를 사용복합 선택(complex selection)을 위한 탐색 방법논리곱 조건(conjunctive condition)인 경우 : 여러 단순 조건들이 AND로 연결된 것
인덱스를 이용하여 레코드 포인터들을 구하고 이들을 통해 레코드들을 읽어서 다른 조건들을 비교함S7. 개별 인덱스를 사용하는 논리곱 선택(conjunctive selection)S8. 복합 인덱스를 사용하는 논리곱 선택
S9. 레코드 포인터들의 교집합에 의한 논리곱 선택논리합 조건인 경우 : 여러 단순 조건들이 OR로 연결된 것각 조건을 만족하는 레코드들의 합집합방법 1. 단순 조건들 중 어느 하나라도 접근경로를 가지지 않으면 선형 탐색 방법을 사용할 수 밖에 없음방법 2. 각 조건을 만족하는 레코드 포인터들의 합집합을 구하여 레코드들을 읽음Note. 선택률(selectivity)
조건을 만족하는 투플수를 릴레이션의 전체 투플수로 나눈 값: 0과 1 사이의 값선택률에 따라 인덱스를 선택함.

키워드

질의 처리와 질의 최적화를 위한 알고리즘,   외부 정렬 알고리즘,   실렉트와 조인 연산을 위한 알고리즘,   프로젝트와 집합 연산을 위한 알고리즘