3-2/데이터베이스시스템

[DB16] Query Processing, Query Optimization

dotudy 2024. 12. 16. 21:45

* 12.18 업데이트

해당 게시물은 한양대학교 컴퓨터소프트웨어학부 김상욱 교수님 데이터베이스시스템 온라인 강의를 듣고 정리한 자료입니다.

오류가 있다면 언제든 알려주세요!

 

● 해당 강의의 목표

1. Algorithms for Query Processing

2. Query Optimization

 

query는 처리할 수 있는 방법이 굉장히 많다. 이를 execution plan이라고 한다. 어떠한 방법으로 처리할 것인가 결정하는 과정을 query optimization이라고 한다.

 

◆ Query optimizaiton

◆ 주어진 query를 처리하기 위한 적절한 execution plan을 고르는 과정이다.

query는 다양한 방법으로 처리될 수 있다. SQL이 declarative language이기 때문에 어떠한 절차를 걸쳐서 처리하라고 알려주는 것이 아니라 원하는 것이 무엇이라고 선언하는 것이다. 어떤 table을 조건에 맞게 골라내라 라는 식으로 선언하는데 이를 만족시키는 값들을 찾는 과정은 여러가지 방법들이 있다. 수백가지 수천가지 중에 가장 빨리 처리될 것 같은 plan을 찾는 과정을 query 최적화 과정이라고 한다.

주어진 query를 process하는 전체적인 과정이다.

1. 먼저 주어진 query를 훑어보면서 parsing, 올바른 query인지 validation까지 한다. 

이가 끝나면 query가 올바르고 무엇을 처리하는지 알게 된다. 아직 최적화는 되어있지 않고 처리하는 것이 무엇인지 올바른지만 알아낸다. (Immediate form of query) 

2. query optimizer가 돌아가서 이를 처리하기 위한 가장 효율적인 execution plan을 찾아낸다. 

3. Query code generator를 통해 query를 실행할 code를 찾아낸다.

4. Runtime databae processor가 query를 수행하고 결과가 사용자에게 보여진다. 

 

◆ Translatng SQL Queries into Relational Algebra

Query를 procedure한 language인 relational algebra로 변환하는 과정이 필요하다. 

◆ Query block

▪ processing의 기본적인 단위로 해당 단위로 SQL을 relational algebra operator로 바꾸고 그것을 최적화한다. 

▪ 하나의 block은 SELECT-FROM-WHERE절로 이루어져있고 당연히 GROUP BY, HAVING을 포함할 수 있다.

◆ Nested Query

▪ 중첩 query문은 두 개의 query block으로 인식한다. 각각 하나의 query block이 된다.

◆ Example

▪ 안쪽에 있는 큐리는 5번 부서에서 일하는 employee를 골라 연봉이 젤 높은 사람을 찾아내라.

▪ employee 중에서 5번 부서에서 일하는 사람의 최고 연봉보다 더 높은 연봉을 가진 사람의 이름을 골라내라.

▪ 두 query모두 query block이 된다. 이는 모두 relational algebra statement로 바꿀 수 있다. 5번인 것을 먼저 찾고 aggregate function을 적용해라. 연봉이 c보다 큰 employee를 찾아서 name으로 projection해라.

 

◆ Algorithms for External Sorting

▪ Internal sorting: sorting은 주어진 tuple들을 어떤 attribute값을 기준으로 순서화하는 것이다. 이는 전체 tuple들이 모두 main memory에 올라와있다고 가정하고 처리한다. 즉, 개수가 그렇게 많지 않다. main memory 안 쪽에서 하는 sorting이라서 internal sorting이라고 부른다.

◆ External sorting (main memory 바깥쪽에서 한다.)

▪ 들어있는 tuple 수가 너무 많아서 main memery에 다 저장될 수가 없어서 disk 또는 SSD에 저장된다.

▪ Size가 너무 커서 main memory에 fitting할 수 없는 상황을 위한 sorting algorithm이다. database 상황에서는 data가 굉장히 많기 때문에 대부분은 external sorting이 요구된다. ORDER BY, DISTINCT이 SQL에 사용될 때 external sorting이 사용된다. 

▪ Disk를 한 번 access하는 것이 main memory를 한 번 access하는 것보다 훨씬 많은 time이 소비되기 떄문에 disk access 수가 굉장히 critical 하다. 이를 줄이는 데 초점을 맞춘 것이 해당 sorting이다.

 

◆ Sort-Merge strategy

▪ sorting을 해야 될 전체의 data를 같은 size의 크기로 자른다. 이 기준은 현재 쓸 수 있는 main memory size만큼 가급적 크게 나눈다. 각각의 덩어리를 run이라고 부르고 이 덩어리를 main memory에 올려서 internal sorting 하는 것이다. 전체 run에 이를 적용하면 각 run에 대해 sorting이 적용되어 있지만 전체적으로는 적용되어있지 않다. 

▪ 하나하나 비교하면서 sort 되어있는 run들을 merge한다. 1, 2, 3, 4, 5 의 run이 있으면 1, 2 / 3, 4 / 5 merge를 진행하고 다시 새롭게 생긴 6, 7 / 8 merge를 진행하고 마지막으로 merge를 한다. 점점 큰 size로 만들어나가는 것이다. 

 

<External sorting의 cost> 자세히 안 다룸~ 

 

 

◆ Algorithms for SELECT and JOIN Operation

◆ Implementing SELECT Operation

Examples

▪ (OP1): $\sigma$ SSN = '123456789' (EMPLOYEE)

▪ (OP2): $\sigma$ DNUMBER > 5 (DEPARTMENT)

▪ (OP3): $\sigma$ DNO = 5 (EMPLOYEE)

▪ (OP4): $\sigma$ DNO = 5 AND SALARY > 30000 AND SEX = F (EMPLOYEE)

▪ (OP5): $\sigma$ ESSN = 123456789 AND PNO = 10 (WORKS_ON)

 

 

▪ 위와 같이 record file에 하나의 relation이 있고 tuple들이 저장되어있다고 하자. 순서는 특별히 의미가 없이 무작위로 저장이 되어있다. 여기서 어떤 조건을 만족시키는 tuple들만 골라내야한다.

▪ S1 Linear search (brute force)

 - 처음부터 attribute value가 condition을 만족시키는지 확인한다. employee tuple을 하나씩 보면서 Dno = 5인지 확인하고 5이면 결과로 내보고 아니면 다음으로 넘어간다. 이렇게 처음부터 끝까지 다 확인하는 것이다. 아무 조건없이 사용할 수 있다.

▪ S2 Binary search

 - employee tuple들이 ssn으로 sorting되어 있다고 하자. 정렬이 되어있기 때문에 binary search를 하면 O(logn)의 시간복잡도를 가지고 찾을 수 있다. Linear search에 비해서 훨씬 효율적이다. 단지, 내가 찾으려는 atttribute에 대해서 sorting이 되어 있어야한다. 

▪ S3 Using a primary index or hash key to retrieve a single record

 - ssn에 대해서 index가 있다고 하자. 그러면 index를 이용해서 빠르게 leaf에 도달해서 해당되는 ssn을 찾아 record point로 갈 수 있고 바로 찾을 수 있다. record가 sorting이 되어있지 않더라도 index가 있으면 O(logn)의 시간복잡도를 가지고 해당되는 위치를 바로 찾을 수 있다. 만약 primary index가 있지않고 hash구조가 있다고 하더라도 빠르게 찾을 수 있다. hash는 O(1)이다.

 - 해당되는 attribute의 index가 있어야한다. O(logn)으로 index leaf까지 가면 해당되는 record point로 가서 원하는 정보를 찾을 수 있다. 

 

위와 같이 selection도 여러가지 방법을 통해 가능하다. query optimizer가 어떤 것이 가장 효율적인지 판단하여 selection을 진행하게 된다. 만약 세 가지 모두가 가능한 상황이면 linear search는 가장 기피될 것이다.

 

▪ S4 Using a primary index to retrieve multiple records

 - 조건에 >, >=, <, <= 가 있고 (여기서는 100~200이라고 하겠다) key에 붙은 index가 있으면 index를 통해서 100번에 해당되는 pointer를 찾는다. 그리고 그 pointer를 이용해서 해당되는 record를 찾는다. 그리고 연속적으로 traverse를 하면서 해당되는 record를 찾아나간다.

 - primary index 즉, key에 있는 index이기 때문에 같은 값이 허용하지 않는다. 

 

▪ S5 Using a clustering index to retrieve multiple records

 - key가 아니기 때문에 여러 값을 가질 수 있다. employee table안에서 Dno와 같이 key가 아닌 값에 clustering index가 있다면 따라 내려가서 3번을 찾으라고 하면 3번에 해당되는 record들을 다 pointer가 가리키고 있을 것이다. 이렇게 multiple record를 찾을 수 있다.

▪ S7 Conjunctive selection: (e.g., a > 3 AND b > 4)

 - 조건 2개 이상이 AND로 연결되어있는 경우이다. conjunctive condition안에 들어가 있는 attribute이 index가 있거나 sort 되어있으면 S2, S4방법대로 하면 된다. (a, b 중 b가 index가 있으면 b > 4인 record를 빠르게 찾는다.)

 - 여러 조건 중 하나를 binary search해서 해당되는 record를 가져온다. 

 - 둘 중 하나 빠르게 찾을 수 있는 것을 찾아서 나머지 조건을 체크한다. 각각의 가져온 tuple이 나머지 condition을 만족하는지 확인한다. 

▪ S9 Conjunctive selection by intersection of record pointers (e.g., a > 3 AND b > 4)

 - Record file이 Employee라고 하자. employee안에서 a, b 모두에 해당되는 index가 있다. 먼저 record file을 보지 말고 index file을 통해 3보다 큰 record들을 찾는다. 그러면 각각이 record를 가리키는 pointer를 가지고 있을 것이다. b가 4보다 것들을 찾으면 역시나 pointer들을 가지고 있을 것이다. 이 둘의 교집합을 구해 a, b 모두를 만족하는 pointer가 가리키는 tuple에 access해서 가져온다.

 - index가 양쪽에 다 있어야지 가능하다. 

 - 만약 condition 중에 일부만 secondary index를 가지고 있다면 일부에 대해서 만족하는 record를 index를 통해 찾고 그 찾은 record가 다른 조건을 만족하는지 확인한다. 

 

더보기

(1) 인덱스 기반 탐색

  • 각 속성 $a$와 $b$에 대해 인덱스 파일이 존재한다고 가정합니다.
  • 데이터 파일(Record File)을 바로 탐색하지 않고, 먼저 인덱스 파일을 통해 조건을 만족하는 레코드의 포인터를 가져옵니다.

예제:

  1. 조건: a > 3
    • 인덱스 파일 a>3a > 3을 만족하는 모든 레코드의 포인터를 찾습니다.
    • 결과: $P_a = \{p_1, p_2, p_3\}$
      ($P_a$는 a > 3을 만족하는 레코드의 포인터 집합).
  2. 조건: b > 4
    • 인덱스 파일 $b > 4$을 만족하는 모든 레코드의 포인터를 찾습니다.
    • 결과: $P_b = \{p_2, p_3, p_4\}$
      ($P_b$는 b > 4을 만족하는 레코드의 포인터 집합).

(2) 교집합 계산

  • 이제 $P_a$와 $P_b$의 교집합을 계산합니다: $P_{\text{result}} = P_a \cap P_b$
    • $P_a = \{p_1, p_2, p_3\}$
    • $P_b = \{p_2, p_3, p_4\}$
    • $P_{\text{result}} = \{p_2, p_3\}$
    • $P_{\text{result}}$는 a > 3 AND b > 4를 만족하는 레코드의 포인터입니다.

(3) 데이터 파일 접근

  • 교집합에 포함된 포인터를 따라가서 실제 데이터 파일(Record File)에서 레코드를 가져옵니다.
  • 결과: $P_{\text{result}}$가 가리키는 레코드들이 최종 결과입니다.

 

◆ Implementing JOIN Operation

▪ JOIN: 2개의 relation이 있는데 attribute들이 어떤 관계를 가지고 있는지 찾는 것

 - two-way join: relation이 2개를 join하는 것이다

.

 - multi-way joins: 3가지 이상의 table을 join하는 것이다.

▪ Example

 - (OP6): EMPLOYEE $\bowtie_{DNO=DNUMBER}$ DEPARTMENT (key와 foreign key가 관계 맺어짐)

 - (OP7): DEPARTMENT $\bowtie_{MGRSSN=SSN}$ EMPLOYEE 

 

▪ J1 Nested-loop join (brute force)

 - 어느 때다 다 사용할 수 있지만 아주 효과적이라고 볼 수는 없는 방법이다. 

 - 각각의 R의 tuple(outer loop)에 대해서 S의 tuple(inner loop)을 모두 조사한다. 

 - t[A] = s[B]인지 확인하면서 계속 test한다. 

 - n * m번 조사를 한다. 하지만 아무 조건이 없으니 항상할 수 있는 방법이다.

▪ J2 Single-loop join (Using an access structure to retrieve the matching records)

 - 둘 중에 하나가 index가 있는 구조이다.

 - S relation의 b attribute에 index가 있으면 R의 record t에 대해 S에서 record t[A]와 같은 S[B]를 찾으면 된다.

 - 따라서 R을 다 보는 것은 동일하지만 R과 match되는 S내의 tuple을 index를 통해 빠르게 찾을 수 있다. 

 

더보기

 

  • 을 하나씩 순회:
    • 의 각 튜플 t에 대해:
      • t[A]: R의 튜플에서 A 속성의 값.
  • S에서 인덱스를 사용해 빠르게 검색:
    • t[A] 값을 기준으로 S[B] 인덱스를 탐색.
    • 인덱스를 통해 S[B]=t[A]를 만족하는 튜플을 즉시 찾음.
  • 매칭된 튜플만 조인 결과로 추가:
    • t[A]=s[B] 조건을 만족하는 경우, R과 S 튜플을 조인해 결과에 추가.
    • S 전체를 스캔하지 않아도 되므로 효율적.

 

▪ J3 Sort-merge join

 - 2개의 relation이 join attribute A와 B로 sorting이 이미 되어있다면 앞에서부터 보면서(one scan) 원하는 Join을 하면 된다.

 - sorting이 되어있지 않다면 먼저 sort를 해야한다.

 - sorting이 되어있다면 각각 1 scan -> linear algorithm이 되고 되어있지 않다면 nlogn + nlogn + 1 scan으로 처리된다. 

▪ J4 Hash-join

 - hash는 특정 attribute 값을 기준으로 hash function을 적용해서 저장될 위치를 찾는 방법이다. Join attribute A에 대해서 원래 있었던 각 record를 hashing을 해서 hash bucket에 집어넣는다. hash function에 의해서 나온 hash value가 같은 tuple들끼리 같은 위치에 저장된다. S에 있는 record도 하나씩 scan하며 각 record의 attribute B에 대한 hash value가 있는 hash bucket만을 scan한다. hash function의 결과가 같아야지 같을 가능성이 생기는 것이다. join 될 수 있는 가능성이 있는 tuple들은 같은 hash bucket을 가지게 된다. 

 - R에 대해서 먼저 hashing을 하고 S에 있는 tuple에 대해서 같은 hash function을 적용하여 어느 bucket에 속하는지 알아낸다. 그리고 같은 bucket에 속하는 tuple끼리만 비교하여 join한다.

 

 

◆ Implementing PROJECT Operation (relation에서 해당되는 attribute만 보여줘라) $\pi _{<attribute list>}(R)$

▪ <attribute list>가 relation R의 key를 가지고 있다면

 - 즉, 해당되는 tuple들이 중복되는게 하나도 없다는 뜻이다. 단순히 R에서 속성을 추출하여 결과로 반환한다. project연산의 결과에 중복되는 것이 있으면 안 되기 때문에 확인해야한다. 

▪ <attribute list>가 relation R의 key를 가지고 있지 않다면

 - 중복된 tuple들이 있다는 뜻으로 결과에서 중복을 제거해야한다. 

▪ 중복을 제거하는 방법

 1. Sorting - 전체 attribute에 대해 sorting해서 중복을 판단한다. 

 2. Hashing - hash bucket 안에 각각의 tuple들을 집어 넣고 다음 tuple이 hashing 했을 때 같은 hash backet을 가진다면 중복이라고 판단하고 내보내지 않는다. 

 

◆ Implementing SET Operation

▪ Set operations: UNION, INTERSECTION, SET DIFFERENCE and CARTESIAN PRODUCT

 

▪ relation R, S에 대한 CARTESIAN PRODUCT

 - R, S에 있는 record들의 모두 가능한 조합. 모든 attribute이 concatenate되어 결과가 나온다.

 - R이 n개의 records, j개의 attribute가 있고 S가 m개의 records, k개의 attribute가 있으면 결과 relation은 n * m records, j + k attribute을 가지게 된다.

 - CARTESIAN PRODUCT operation은 굉장히 cost가 크고 최대한 avoid되어야한다.

 

▪ UNION

 - 두 relation안에 같은 attribute을 가져야한다. 즉, union compatible해야한다. 

 - R과 S안에 하나라도 있으면 결과로 나오게 된다. 먼저 두 relation을 sorting하고 merge하는 것처럼 처음부터 다르면 둘 다 내보내고  같으면 하나만 내보내야한다. 양쪽에 같은 tuple이 있을 때 결과를 하나만 내보내야한다. 

 

▪ INTERSECTION

 - 두 relation을 sort해서 양쪽에 모두 있는 결과만 내보낸다. 

 

▪ SET DIFFERENCE R-S

 - S-R과 다르다는 것을 기억하기! R에 있는 것들 중 S에 없는 것들을 내보낸다. 둘 다 sort 하고 순차적으로 보면서 R에 있는데 S에 없으면 답으로 내보내고 S에도 있으면 내보내지 않는다. 

 - S-R은 반대로 S에 있는데 R에 없으면 결과로 내보낸다.

 

◆ Implementing Aggregate Operation

▪ Aggregate operators: MIN, MAX, SUM, COUNT, and AVG

▪ Aggregate operator를 실행하는 방법

 1. Table Scan

    min, max를 기준으로 보자. S에 있는 record를 하나하나 보면서 가장 작거나 큰 값을 찾으면 된다. 

 2. Index

    만약 salary에 대해서 index가 있다고 하면 record file 전체를 다 보지 않고 index를 보면서 할 수도 있다.

▪ MAX and MIN example

 - SELECT MAX(SALARY)

    FROM EMPLOYEE;

 - 만약 (ascending) index가 있다면 이미 정렬이 되어있는 상태니 가장 오른쪽 subtree를 타고 내려가서 가장 오른쪽에 있는 값을 선택하면 MAX값이 된다. 가장 왼쪽에 있는 값을 선택하면 MIN 값이 된다. 만약 descending order라면 반대로 하면된다.

▪ SUM, COUNT, AVG

 - 만약 salary에 index가 있는 경우에는 전부 scan하면서 합을 구하면 되고 개수도 count하면 된다.

 - dense index: 하나의 record마다 index가 하나씩 반드시 있는 것이다. record마다 index entry가 있어서 index를 보고 모든 record의 salary에 대한 정보를 알 수 있는 상황을 말한다.

 - non-dense index(sparse index): record가 여러 개 저장된 block마다 entry가 하나씩 있는 경우를 뜻한다. 이 때는 index 하나를 따라가면 마지막에는 해당되는 record들이 여러 개 저장되어있다. index entry가 어느 block에 있는지, 몇 개가 안에 들어있는지 알려줄 수 있다. 예를 들어 record가 3개있고, salary가 3만이면 SUM에는 9만을 더하고 COUNT는 3을 더해주면 된다.

 - 만약 aggregate function 전에 GROUP BY가 되어있다면 attribute값이 같은 것 끼리 묶어서 묶어져있는 record들에 대해 aggregate function을 적용하면 된다. 이 경우에는 먼저 grouping attribute을 기준으로 전체 record를 sorting을 적용하면 group별로 묶이게 된다. 나눠진 각각의 group에 대해 그 그룹에 속하는 tuple에 대해서 aggregate function을 적용한다. 다만 group별로 묶여있기 때문에 index를 사용하면 안 되고 linear search를 통해 찾아야한다. 그래서 성능상의 overhead가 있다.

 

◆ Using Heuristics in Query Optimization

◆ Process for heuristics optimization 

▪ 경험적 지식에서 이렇게 하면 좋다라고 증명하는 것이다. 과학적으로 증명할 수는 없다.

▪ 처음에 high-level query가 있으면 parser를 통해서 해석하고 점검하고 initial internal representation한다. 아주 simple하게 relational algebra로 바꾼다.

▪ internal representation을 (어떤 형태로 되어있는 relational algebra sequence를) 좀 더 빠르게 처리할 수 있도록 heuristic rule을 통해 optimize한다.

▪ 그 결과가 execution plan이 되어 operation들을 실행한다. 

 

◆ heuristic의 가장 기본은 중간 결과의 size를 줄이는 방식으로 최적화하는 것이다.

▪ relational algebra의 결과는 operation의 sequence로 표현된다. 여기서 기본은 적용한 결과의 size를 줄이는 것을 먼저 적용하는 식으로 순서를 바꾸는 것이다.

 - 이를 위해서는 먼저 SELECT, PROJECT operation을 먼저 적용해야한다. SELECT를 적용하면 전체 중 조건을 만족하는 tuple만 골라지게 되고 PROJECT를 적용하면 원래 relation에서 원하는 attribute만 보여주게 된다. size가 줄면 이후에 operation을 할 때 cost가 줄어들어 자원을 절약할 수 있다.

 

◆ Query Tree

▪ Query를 tree 형태로 표현한 것이다.

 - tree 형태의 data structure로 이는 relational algebra expression과 대응된다.

employee와 works_on을 cartesian product하고 그 결과를 다시 project와 cartesian product한다. 결과로 3개의 table이 모두 cartesian product된 굉장히 큰 table이 나온다. 거기서 Pname = 'Aquarius', Pnumber = Pno, Essn = ssn, Bdate > '1957-12-31'( 더 뒤에 나온 사람들 ) 이 조건을 만족시키는 것을 SELECT하고 Lname으로 project한다는 뜻이다. 즉, project name이 Aquarius인 project에 참여하는 employee 중 1957년 12월 31일 이후에 태어난 사람들의 이름을 알려달라는 뜻이다. 보통 이 query tree에 leaf node에 해당되는 것이 input relation이 된다. 가운데 나오는 internal node에 해당되는 것이 relational algebra operator이다. 이러한 query tree의 수행은 밑에서부터 relation이 있어야지만 처리할 수 있다. 

 

▪ Query tree의 execution

 - internal node에 해당되는 것을 수행하는 것은 그것의 operand(피연산자)가 연산 가능할 때이다.

 - 이후 internal node를 operation을 실행 후 나온 결과 relation으로 대체한다.

 

▪ Example

 - For every project located in ‘Stafford’, retrieve the project number, the controlling department number, and the department manager’s last name, address, and birthdate

 - Relation algebra:

SQL은 declarative language이기 때문에 원하는 것을 명시하고 어떤 순서로 처리하는지 모른다. relation algebra는 procedure language이기 때문에 순서가 존재한다. 1 selection -> 2 department와 join -> 3 employee와 join -> 4 projection

하지만 우리가 수행해야할 것은 SQL이고 해당 statement를 어떤 순서로 처리해야할지는 아직 결정되어 있지 않다. 이를 처리하는 방법도 굉장히 다양하다.

 

(a)는 relational algebra를 표현한 것이다. 이를 query tree라 한다.

(b)는 같은 tree를 다르게 표현한 것이다. 

모두 결과는 같지만 (b)가 시간이 훨씬 많이 걸린다. cartesian product를 수행하기 때문이다. 정말 많은 tuple들이 생성된다. 따라서 (a)가 훨씬 효율적이다.

(c)는 query graph이다. 순서없이 SQL에 의해서 declare한 것이다. 다만 많이 다루지는 않을 것이다.

 

◆ Heuristic Optimization of Query Trees

▪ 같은 SQL query는 여러 개의 relational algebra expression으로 될 수 있다. 따라서 여러 query tree가 나온다.

▪ Heuristic을 이용한 query optimization은 수행하는데 있어서 빠른 final query tree를 찾는 과정이다.

SQL에는 순서가 없다. query optimizer가 전적으로 결정한다.

 

(a) 가장 단순 무식! 다 cartesian product해서 selection 진행

(b) selection operation을 밑으로 내렸다. 이렇게만 해도 전체적인 성능을 높일 수 있다.

(c) 좀 더 크기를 작게 만드는 selection을 먼저 했다. project의 size가 employee보다 작기 때문이다.

(d) cartesian product과 selection 연산을 join으로 바꾼다.

(e) Project operation을 먼저 수행한다. 이를 통해 table의 size를 줄여 놓자. Lname을 미리 projection했다. Ssn도 같이 해야함을 기억하자.

 

◆ General Transformation Rules

1. Cascade of $\sigma$

$\sigma_{c1 AND c2 AND … AND cn​}(R) $ = $\sigma_{c1​}(\sigma_{c2​}(\cdots (\sigma_{cn​}(R))\cdots ))$

relation에 대해 selection을 하는데 조건이 여러 개 있고 conjunctive form으로 되었다. 이는 각각의 조건에 대한 individual selection operation의 sequence로 표현할 수 있다. 왜 이렇게 쪼개는게 도움이 될까? 왼쪽처럼 하기 위해서는 relation안에 각각의 tuple에 대해 해당 조건을 한번에 확인해야한다. 하지만 만약 다 나뉘어있다면 cn에 대한 index가 있다면 이 조건을 만족하는 것은 굉장히 빠르게 찾아서 tuple의 수를 크게 줄일 수 있다. 그러면 이후의 selection operation들을 빠르게 처리할 수 있다.

 

2. Communtativity of $\sigma$

$\sigma_{c1​}(\sigma_{c2​}(R)) = \sigma_{c2}(\sigma_{c1}(R))$

selection에 대한 교환법칙이다. c1을 먼저 찾고 c2를 찾는 것도 가능하다. 만약 c2에 해당되는 attribute가 index가 없고 c1이 index가 있다면 c1에 해당되는 것을 먼저 찾아서 굉장히 빠르게 tuple의 수를 줄여놓을 수 있다.

 

3. Cascade of $\pi$

R에 대해 listn에 대해 projection하고 그 결과를 List2에 대해 projection하고 계속 진행하여 list1에 대해 projection한다면 결국 R에서 최종적으로 남을 attribute에 대해서 projection한 것과 같다.

 

4. Commuting $\sigma$ with $\pi$

R에 대해 selection을 먼저하고 그 결과에 대해 projection하는 것은 projection을 먼저하고 그것을 대상으로 selection하는 것과 결과가 같다. 물론 c(condition)에 들어있는 attribute이 A1~An에 들어있는 List에 포함되어있을 때 가능한 일이다. projection을 통해 먼저 size를 줄이는 것이다.

 

5. Commutativity of $\bowtie$ (and x)

교환법칙이 모두 성립한다. nested loop을 할 때 무엇을 outer loop에 넣고 무엇을 inner loop에 넣을지 할 때 해당 교환법칙이 잘 사용된다. R에 index가 있고 S에 index가 없다면 S를 outer에 넣고 R을 inner에 넣으면 S의 각 tuple에 대해서 그 tuple의 join attribute 값과 같은 attribute값을 가지는 R의 tuple을 index를 통해 빠르게 찾을 수 있다. Cartesian product도 size가 다를 때 S가 작으면 R * S로 해서 각 R을 한 번 scan하는 동안 S가 작기 때문에 main memory에 올라갈 수 있어서 disk access를 크게 줄일 수 있다. 만약 S * R으로 해서 S를 outer로 하면 R에 접근하기 위해서 disk access가 발생하여 S의 tuple의 수만큼 disk access가 발생하게 된다.

 

6. Commuting $\sigma$ with $\bowtie$ 

두 table을 join 한 후 c 조건을 만족시키는 것을 selection 한다는 것은 R에 대해서 c 조건을 만족하는 것을 선택한 다음에 S와 join하는 것과 같다. selection을 통해서 size를 먼저 줄이고 join해서 성능에 도움이 된다.

비슷하게 S에 대한 조건을 또 적용해서 size를 줄이고 join을 하면 훨씬 cost가 낮아진다.

 

7. Commuting $\pi$ with $\bowtie$ (or x)

R과 S를 join한 다음에 projection하는 것이다. R, S 각각에 대한 attribute으로 projection을 먼저하고 그 결과를 join 하면 훨씬 빠르게 처리할 수 있다. 만약 join condition에 먼저 projection한 attribute외의 attribute이 사용된다면 미리 해당 attribute을 projection시에 같이 project해야한다.

 

8. Commutativity of set operations

$\cap$과 $\cup$는 교환법칙이 성립되지만 set difference는 성립하지 않는다.

 

9. Associativity of $\bowtie$, x, $\cap$, $\cup$

결합법칙이 모두 가능하다. $\theta$를 위의 기호들 대신 표현하였다.

( R $\theta$ S ) $\theta$ T = R $\theta$ ( S $\theta$ T )

 

10. Commuting $\sigma$ with set operations

$\cap$, $\cup$, -에 대해서 set operation을 하고 selection을 하는 것은 각각에 대해서 selection을 한 후 set operation을 하는 것과 같다. selection을 먼저하면 size를 줄일 수 있어서 유리하다.

 

11. $\pi$ Commutes with $\cup$

union 후 projection하는 것은 projection을 각각에 대해서 해서 size를 줄이고 union 한 것과 같다.

 

12. Converting a ($\sigma$, x) sequence into $\bowtie$

Cartesian product 한 후에 selection하는 것은 selection을 join condition으로 하는 join을 바로 하는 것이 유리히다.

 

이와 같은 것들은 모두 selection과 projection을 가급적 미리해서 대상이 되는 operand에 해당되는 relation의 size를 줄이는 것이 유리하다. 

 

◆ Using Selectivity and Cost Estimates in Query Optimization

◆ Cost-based query optimization

▪ 각각의 query에 대해서 서로 다른 execution plan이 있을 수 있다. 각각의 execution plan에 대해 cost를 예측하고 가장 적은 것을 고르는 전략이다. 

▪ Heuristic query optimization과 경쟁하는 관계이다. DBMS는 둘 중 하나만 쓴다.

◆ Issues

▪ Cost function 마련이 되어야한다. 정확도가 높아야되는데 실질적으로 어렵다.

▪ Number of execution strategies to be considered

위의 부분이 잘 design된다면 Heuristic query optimization보다 더 높은 성능을 보이지만 어렵다.

 

◆ Cost components for Query Execution

1. disk로 부터 읽는데 걸리는 시간 (disk IO 시간)

2. storage cost (disk에 결과를 쓰는 시간)

3. computation cost (main memory에서 계산을 하거나 정렬하거나 등의 CPU cost)

4. Memory usage cost (main memory에 올라왔을 때 CPU가 이를 계산하기 위해서 memory를 access하는 데 드는 cost)

5. Communication cost (machine 간의 communication)

 

main cost은 disk에 대한 IO cost가 가장 크다. 분산 환경에서는 5번도 크다.

 

database system이 처한 환경이 다르다면 당연히 cost component가 달라진다. secondary storage로 disk / SSD .. 등..

 

◆ Summary

0. Introduction to Query Processing

1. Translating SQL Queries into Relational Algebra

2. Algorithms for External Sorting

3. Algorithms for SELECT and JOIN Operations

4. Algorithms for PROJECT and SET Operations

5. Implementing Aggregate Operations

6. Using Heuristics in Query Optimization

 

DBMS 내부에서 SQL Query를 어떻게 처리하는가.