[db] query processing

https://codenme.tistory.com/22

데이터베이스 참고자료

위의 자료를 기반으로 작성한 내용입니다. 페이지 별로 관련 내용을 정리한 것이니, 해당 자료와 함께 보는 것을 권장 드립니다.

 

(update at 23-08-08)

 

Query Processing

데이터베이스에서 데이터를 가져오거나 데이터를 삽입할 때 사용하는 언어를 Query라고 한다.

쿼리는 실제 연산 속도에 큰 영향을 미친다.  

Query Processing이란 우리가 보낸 Query를 데이터베이스가 처리하는 과정을 말한다.

 

 

 

Query Processing 구조

 

1)    Parsing and translation: query를 internal form으로 바꾸고, relation algebra로 Translate //

Parser는 문법과 relation 체크

 

2)    Optimization: 다양한 플랜들 중에서 가장 비용이 낮은 플랜 찾기

 

3)    evaluate: 해당 플랜 실행

 

같은 요구(결과 데이터)도 다른 RA(Relation Algebra)로 표현 가능하기에, 동일한 결과를 반환하는 다양한 쿼리 방식 중, 최적의 방식을 찾는 것이 중요하다(optimization) .

 

Query Processing: Optimization 

dbms는 동시에 많은 사용자가 사용가능한 시스템. 같은 것도 시스템 자원을 조금 덜 사용하는 것이 유리하다.

Resource를 많이 사용하고 빨리 return하는 것은 사용자가 많은 환경에서 좋지 못한 선택이다. Cost를 어떤 식으로 책정할 것인가?

Db 구조상 시스템 resource를 가장 적게 사용하는 cost 모델을 사용한다. ( 동시 접근 관련)

 

 Query Cost 측정하기

query Cost   -> disk I/O ( seek, transfer(데이터 이동) ) 얼마나 일어났는가? 로 측정한다.( disk access time이 실행 시간에 제일 큰영향을 주는 요소이기에.)

 

Response time : query에 응답하기까지 시간.

Resource consumption: 리소스 차지하는 양.( 이걸 사용한다! Shared Db는 동시접근 빈번)

 response time은 측정이 어렵고, resource 소비량을 줄이는게 좋은 방식이다.

 

이번 글에선, CPU cost는 편의상 생략하겠다. (실제론 포함됨)
또한 Disk에 output을 작성하는 시간 역시 cost에 포함시키지 않겠다. 

 

 

어차피 쿼리의 cost를 정확하게 추정하는 것은 불가하다. 따라서 단순한 추정 모델 사용한다.

이 글에선 Block transfer from disk 횟수, number of seek 로 cost 추정을 수행할 것이다.

tT: 블록 1개 transfer time. ( write 와 read cost는 편의상 동일하다고 가정.)

tS: 1개 seek의 시간. (seek> 실린더에 헤드 놓는 시간)

 

Block b의 cost: ( transfer한 블록 수)b * tT+ (seek 수)S * tS

 

어디에 block이 저장되었는지 따라 tS,tT 달라지고, Magnetic disk, SSD 냐 따라 다르기에, 정확한 추산은 아니다. 

 

만약 disk 까지 넘어가지 않고 메모리에서 처리 가능 시, 정확한 쿼리 Cost 추정 더 어려워진다. (buffer를 위해 마련할수 있는 메모리 안의 공간량은 concurrent한 query 따라 다르고, 이건 실행 중에만 확인가능-> 추정 어렵다.)

-> 따라서 과거 기록으로 추정하는 것이 하나의 방법이다. ( Seek time 등의 정보를 가지고 있지 않기에)

Disk access time 측정(과거의 평균 Cost로)

1)    read할 block 수 * 블록 당 평균 read Cost

2)    write할 block 수 * 블록당 평균 write Cost

write가 평균적으로 더 큰 cost. Write 후에는 성공적인 write를 확인하기 위해 read 1번 수행하는 것도 포함한다.

Buffer로 in mem에 정보 저장하는 방식으로 disk I/O 줄이기 가능. Buffer을 제일 적게 사용하는게 worst case

 

 이제, 쿼리에서 'sort' 전략에 대해 알아보겠다.

 

알아두면 도움이 되는 용어
Index: Clustering vs non-clustering >  leaf들에서 파일의 같은 영역 내에 있는 인덱스?
non-clustering :실제 leaf node 에 모인 record 들이 실제 파일 블록 여러 군데 들어간다
secondary: index 상은 연속성 보장, but 실제는 보장 x
key: data 1개
non- key: data 여러 개 될 수 있다. ( 여러 block 에 흩어져 있을 수도)

 

Sorting

 

인덱스 상에서 연속성 유지되었다고 disk 에서도 되있진 않다. >> index 상의 순서에 따라 예측하면 오류 발생하기에 별도의 sort 필요. 메모리보다 더 큰 데이터 저장하는게 일반적이고 DB에선 메모리가 성능에 큰 영향을 미친다.

Query Processing에서는, sort 를 2가지 방식을 통해 처리한다.

 

internal sort

main memory에 올려서 정렬할 수 있는 것

 

external sort merge 

제한된 메모리에서 메모리보다 더 큰 데이터

각 pass마다 M-1개 run

 

 

 

 

 disk의 table을 main memory에 올릴 수 있는 크기로 나누어서 internal sort를 하고 file로 저장한다. 이렇게 저장된 것을 run이라고 하며 run들을 merge를 하게 되면 특정한 칼럼에 대해 정렬할 수 있다. ( merge sort 와 유사. 메모리에 올라갈 때까지 쪼갠 뒤, 메모리에서 sort 하며 merge한다)

merge: run을 n개씩 정렬하며 합치기.

 

external sort Merge의 Merge phase에서 문제점

buffer block:1개 run을 read해도, 여러 I/O 발생가능 ( 해당 run 내에서, 메모리에 안 올라와있는 정보에 접근할 가능성이 있다.)

해결책:  run을  사용 가능한 버퍼 블럭의 개수만큼 쪼갠 뒤, read/write가 buffer block 당 1번씩만 발생하게 각각 할당한다.

 

이를 통해, 한번에 메모리 여유 공간만큼 데이터를 불러들이는 것이 가능하다. ( seek횟수 1회!)

 

 

 

Join Operation

각 relation(물리적으론 테이블)에서 가져온 데이터를 join 연산 수행해야 한다면, 특정 조건 가진 튜플들 가져와서

Join 연산으로 사용 가능한 알고리즘이 크게 3개 존재한다. (아래를 응용해서 다양한 join연산 수행하는 것이다.)

1)    Nested loop join

2)    Sort-merge join

3)    hash join

Nested-Loop Join

2개의 Table R,S를 Join할 때, 중첩 루프문을 통해, 모든 튜플 조합을 찾아서 Join하는 방식이다.

R: outer 루프, S inner 루프
Nr,Ns : r,s relation의 record 수
 Br,Bs: block 수

 

과정 예시

For R의 모든 record{
           For S의 모든 record{
                       만족하는 값 찾고 두 튜플 합쳐서 output에 기록
           }
}

 

Worst case: R,S 테이블 각각 1개 block만 memory에 올릴 수 있을 때

Transfer: (Nr * Bs+Br) block

Seek: Nr+Br   ( 모든 record와의 대조시마다 seek 발생. ( Nr을 S의 모든 블록과 대조> S relation block들 읽는건 한번 head 위치하고 쭉 읽으면 된다.

Transfer: (inner block transfer + outer block transfer)

Outer의 record 1개당 inner의 모든 block 과 대조>> inner에 1칸 뿐이기에 inner의 각 블록과 대조할 때마다 갱신된다.

Seek: outer의 record seek + inner의 block seek

Best case: 양 relation의 모든 block memory에 가능

Transfer: Br+Bs   >> R,S의 block 다 올려놓기

Seek : 2          -> R,S 각각 1번씩 쭉.

 

작은 relation만 mem에 전부 올릴 수 있을 때.

작은 relation을 inner로 두고 mem에 올린다.

Transfer: Br+Bs  (inner은 한번에 올려놓았다.) outer의 각 block 이랑 올라온 inner 대조후 outer 버림

Seek: 2

 

 

 

Block Nested-Loop Join

Nested-Loop-Join 과 유사하지만, 블록 단위로 수행한다. 실제 데이터를 가져오는 블록 단위로 수행되는 것이기에, 

어떠한 블록 중간까지만 가져와서 이후에 다시 가져와야하는 불상사가 생기지 않는다.

For R의 모든 블록Br 에 대해{
           For S의 모든 블록Bs에 대해{
                       For Br의 모든 튜플 tr 대해{
                                  For Bs의 모든 튜플 ts에 대해.{
                                  		만족하는 값 찾고 두 튜플 합쳐서 output에 기록
                                  }
                        }
           }
}

 

Worst case:

Transfer: Br*Bs+Br   ( Nr> Br로 변경!

Seek: 2*Br   (Nr+Br>> Nr이 Br 됨. ( outer의 block만큼만 seek하면 inner ok!)

 

하지만 여전히, Nested-Loop 를통한 Join 은 성능적으로 많은 문제가 있다.

(두 테이블 모두 메모리에 올리지 못할 경우, 계속해서 비효율이 생긴다.) 

 

개선방안

1)    block nested join 개선

Mem에서 사용 가능한 block 수가 M인경우

M-2를 outer relation에 할당하고, 남은 2개는 각각 inner, output 위해 할당

한번에 M-2개 씩 outer에서 읽어오고,  inner에서 1개 가져와서 대조.

Cost:

Transfer: up[ Br/ (M-2) ] *Bs +Br 

Seek: 2* up[Br/ (M-2) ]

 

2)    equi join에서(어떠한 값이 같을 시  join 하는 조건) attribute가 key를 구성하면(중복x), 매칭되는거 1개 찾고 바로 멈추기

3)    inner loop를 앞 뒤로 왔다갔다 스캔하기: LRU의 메커니즘으로 최근꺼는 아직 buffer에 남아있기에 I/O 절약할수도 있다. 

4)    Inner relation에 index 적용!  -> indexed Nested loop join

 

 여기까지, 가장 간단한 join 인 nested-loop-join 에 대해 살펴봤다.

요약:  2개의 테이블에서 조건에 맞는 튜플들을 모은다.

• 각 테이블의 모든 튜플에 대해 조건을 확인해보고 join을 수행한다. 흔히 생각하는 2중 for 문과 같이 동작하기에, 직관적이고 구현하기 쉬운 장점이 있다.
• 하지만 성능상 조금 나쁘다.

예를들어 R(oiuter) 과 S(inner)가 join 시,  모든 r,s 가짓수 2중 루프로. 이 때 매번 저장장치를 가져와서 IO가 많이 발생된다. (매번 outer에 대한 inner의 모든 block을 찾기 때문)

 

해결책

•  block nested loop: nested loop 에서 테스트하는 튜플을 block 단위로 모으고 해당 block 들에 대해서만 nested loop 돌려 찾는 방법 
•  index nested-loop join: inner table에 index 사용 가능시, 굳이 inner에 테이블 두지 않고 index 통해 찾는 것으로 메모리에 inner 테이블 전체를 올리지 않아도 된다. 모든 튜플 가져와서 비교 연산하는 것이 아닌, inner table에 index 사용해서 full-scan 피하는방식으로 대처가 가능하다.

 

 

Merge join

merge join은 우리가 알고리즘에서 흔히 접하는 merge Sort와 유사하게 동작한다.

마찬가지로, 각 테이블이 "Sorted" 상태여야한다.

각각 테이블이 모두 정렬 되어 있다면 각각 포인터를 두고, 포인터를 각각 1개씩 이동해가며 튜플들을 찾아 나간다. 

outer 테이블의 포인터를 pr, inner 테이블의 포인터를  ps 로 두고 설명하겠다.

pr과 ps가 가르키는 값이 같다면 (equal), 두 튜플을 join하고, 만약 다르다면, pr,ps의 값을 비교한다.만약 pr이 더크다면 ps의 포인터를 1증가 시키고, ps가 더 크다면 pr의 포인터를 1 증가 시키면 된다.

이렇게 하는 것으로, 기존의 Nested-loop join에서와 같이 모든 가짓수를 비교하는 것이 아닌, 대소 비교에 따른 중복 비교를 배제하는 것으로 성능을 향상시켜나갈 수 있다. 

 

또한, Nested loop 가 여러번 IO 접근을 수행하는 것에 반하여, Merge는 한번의 접근으로 전부 받아올 수 있다!

 

Merge Join 요약

• 정렬 시간이 추가로 필요해짐.
• Equi, nat Join 에서만 가능.( R.a==S.a 와 같은 동치 조건에서만 사용 가능) 
• IO 시간 감소

 

Sort 대한 cost 제외하면 각 테이블이 가지고 있는 블록만큼만 읽어 들이면 된다.

또한, Inner table의 block과 outer table의 block 에서 매번 랜덤하게 1개의 블록씩을 가져오는 것이 아닌,

한번에 많은 블록을 읽어들일 확률이 높기에 seek time 감소 역시 가능하다. (pr<ps일 시,  ps>=pr이 될때까지 R 테이블의 데이터 블록을 쭉 읽어 들일 수 있다.)

 

 

Hybrid join

Merge: 내가 어떤 key를 지나면, 이후로는 해당 key보다 큰 값만 나온다는 것을 보장해야.

하지만 이게 적절치 않은 경우가 존재한다.

1개 테이블은 sort(physically) 되어있고, 남은 1개 테이블은 second index(index로 순차 접근 가능,

즉 logical하게 sort되있는 경우( secondary 인덱스의 경우, 인덱스 순서 != 실제 데이터 순서이기에 physical sort와는 무관하다.) 

 

Outer table은 physicaly sort 되있는 테이블로 두고, inner table은 logical하게 sort되어있는 테이블로 둔다.

이후, inner table의 테이블을 실제로 가져오지 않고, address만 가져와서 join 결과를 만든다.

• Merge step에서 어느정도 위치에 있다는 것만 가지고 온다.
• Outer은 실제 값, inner은 그에 매칭되는 주소값만 가져온다. 
• Merge 이후에 추가적인 sort를 사용해서 주소값만 가져온 것들의 실제 값들 정렬하여 제대로 가져온다.

이런 Merge Sort 종류는 각테이블 sort 시간이 너무 크면 필연적으로 성능이 나빠진다는 점을 주의하자.

 

 

 

 

 

Hash Join

같은 hash value 가지는 튜플끼리 grouping을 통하여 Join이 같은 값을 찾는 연산이 효율적으로 일어난다.

원리: inner, outer table에 hash attribute가 있다면 hash 함수를 통해 같은 값을 가지는 것 끼리 partition 한다.

Ex
outer에서 hash func이 0~4 의 값을 나타난다고 하면 ( 같은 hash 값을 같는 것 끼리 grouping 할 수 있다)

 

 

 

각 hash partition 된 tuple 들은 sort되있지 않기에, nested loop 로 비교해야 하지만, Nested-loop join은 앞서 설명했듯이 성능이 별로이기에 Inner table에 또다른 hash func 통해 hash index를 만든다.

 

Inner table:  hash index를 build 하는 쪽이라서 build input 라고도 함

Outertable: 하나씩 레코드를 찾는 역할이라 probe input 라고도 함.

 

hash테이블의 개수( 그룹의 가짓수라고 생각해보 된다)는 메모리 상황을 고려해서 책정되어야 한다.

 

메모리에서 사용할 수 있는 버퍼보다 파티션 개수가 늘어나면 일부 파티션은 메모리에 존재하지 않게 되어 매우 나빠진다. (disk에서 가져와서 쓰고 다시 넣고… 배보다 배꼽이 크다)
따라서 주어진 메모리 사이즈 개수 따라 파티션 개수를 정해야한다. ( 메모리 버퍼 블록 – 파티션 1대1 매칭 전부 되게!)
N 개의 버퍼 블록 공간이 남아있으면, input block 1개 제외한 n-1 way 로 partion 나눠야한다.

하지만, 제한된 공간(way수)로 인하여, 데이터의 개수가 많아지더라도, Partion의 '개수'는 한정되 있기에  Partition의 크기가 점점 커지게 된다.

 

해결책: recursive partition 

파티션에 있는 튜플들을 또다른 hash 함수를 통해 세분화해서 진행하는 것으로 제한된 공간 내에서 최대한 세분화를 진행할 수 있다. ( Multi-Level-index를 통해 메모리에 최대한 테이블 전체를 커버하는 인덱스를 한번에 올리는 것 과 유사한 해결 방안이다.) 

 

 

Hash Join에는 이 외에도 또다른 문제점이 존재한다.

아무리 Hash Function을 잘 만든다 하더라도, 각 모든 tuple들을 hash 파티션 했을 때 각 파티션이 동일 크기가 아닌 경우가 많다는 것이다. ( unbalance) 

 

이처럼 partition의 크기가 한쪽에 몰릴 것을 감안해서 hash partition 기술을 적용할 수 도 있지만,

(이 기술 적용하려면 hash table이 전부 memory에 올라와 있어야 하기에, 올라와있지 않은 hash Table이 있다면 Disk에서 꺼내와야하는데, 이를 위해 Disk I/O가 발생하는 것 역시 별로이기에, 자주 사용하지는 않는다.)

 

각 Join 방식의 선택 방법

여기 까지 3가지 Join 방법을 알아봤다. 그럼 각각의 Join은 언제 사용할까?

hash, Merge는 확실히 Nested-loop에 비해 최적의 상황에서 우월한 성능을 자랑하지만, 아래와 같은 제약조건이 있다.

 

1) Hash, Merge Join 는 Equi Join( 동치 조건의 join), 그리고 Natrual Join에서만  사용할 수 있다.

2) Merge Join은 두 테이블이 정렬 되어있어야한다.

3) hash Join은 Hash Table 을 따로 구성해야한다.

 

따라서, 보통 테이블이 매우 작아서, Join을 수행하는 양쪽 테이블 모두 한번에 Memory에 올라갈 수 있다면, 단순히 nested-loop Join을 통해 수행하는 것이 좋은 해결책일 수 있다.

 

만약 그렇지 않다면, Join하는 두 테이블의 Physical, Logical Sort가 수행되었는지 여부에 따라 merge 조인을 고려하고,\

두 테이블 모두 아무런 Sort가 수행되지 않은 상태라면, hash Join 을 사용하자. 

 

 

Evaluation of Expression

여태까지는 Select, Join, Sort 등 각 절차를 측정, 수행하는 방법에 대해 알아봤다.

이와 다르게, 전체 Expression을 측정하는 방법은 Join을 수행 시에 join 에 필요한 2개의 input 데이터가 준비 되어있어야 한다. 이 2개의 input 데이터를 어떤 방식 쓰냐 따라 아래와 같이 2가지 방법으로 구분된다.

• Materialization evaluation
• Materialization evaluation

 

Materialization evaluation

전체 쿼리(expression)에서, 각 단계가 "완벽히" 끝난 이후에 다음 단계로 넘어간다.

RA

수행

이전 연산의 데이터를 파일 형태로 저장하고, 다음연산에서 읽어서 사용한다.  Step by step. 모든 step의 내용을 materialize on disk한다. 바닥에서부터 데이터가 준비되고, 파일 형태로 만들어 윗(다음) 단계로 넘긴다.

 

장점

안전하다.

 

단점

• step by step 으로 진행되어, select하지 않을 쓸데없는 값들을 불러들여오고 다시 버리는 temporary 데이터 에 대한 비용이 생긴다.
• 기다리는 동안 아무런 동작도 수행하지 않고 가만히 있는 비효율적인 경우가 발생할 수 있다.

Ex
버퍼가 1개 있는 상황을 가정했을 때, 만약 버퍼에 이전 데이터 넣어 놨는데, 다 읽어 들이지 못하면 해당 버퍼의 값 다 읽을 떄 까지 write 불가. -> 버퍼 개수를 늘리는 것으로 해결 가능

 

 

 

• Pipelined evaluation

 데이터가 준비되면 일부라도 넘겨서 윗단계 연산에서 해당 데이터를 사용할 수 있게 한다.

(이전 단계 완벽하게 끝난거 아니어도 필요한거만 적절하게 넘겨서)  어느정도 준비되면 memory 상에서 input으로 넘긴다.

여러 연산들이 동시에 진행하는 것 처럼 보여진다.

 

Selection 이름=Watson 
(department)

위와 같이, 이름 =watson인 값을 Join된 테이블에서 가져와야할 경우, select 하면서 join 도 조금씩 진도 나간다.

 

예시
어떠한 튜플을  department 테이블에서 가져온 뒤, 완전히 불러들여오기 전에 이름=watson 인지 이름 값만 빼와서 확인해보고 아니면 다음 스텝 안하고,  맞으면 실제로 불러들여온다

 

만약 이전 단계의 모든 데이터가 준비되지 않으면 다음 단계가 전혀 시행되지 않는 Case가 존재하면 PipleLine 이 의미 없기에 별로다!!

Ex
sort, Hash 연산들은 한번 전체를 훑어야 유효한 데이터가 된다. ( sort하다가 말면, Sort된 데이터가 아니기에 안하는 거나 다름 없다..) 이 외의 연산들은 PipeLine을 통해서 성능 향상을 얻어낼 수 있다.

 

 

Demand driven pipeline(Lazy evaluation):

시스템에서 필요한 만큼 데이터(다음 튜플)를 상위 레벨에 요구 후 가져와서 사용하는 PipeLine 매커니즘이다.

(그때 그때 필요한 걸 요구하는 방식)

각 오퍼레이션: 자신의 children 오퍼레이션에게 또 다시 요구……. Top bottom 처럼 맨 하위에서 다 처리하고 재귀함수 리턴하는 것처럼 최상위로 전달하며 조립한다. 필요거만 그때 그때 빼오기 때문에 불필요한 정보까지 가져오지 않아도 되지만, 필요한 시점에서야 가져오기에, 이 시점에선 성능이 느릴 수 있다.

 

Producer driven pipeline(Eager evaluation):

상위 레벨에서 연산에서 필요한 데이터를 하위 레벨에서 미리 만들어서 전달. (필요한 걸 미리 모두 완성해 놓는 것)

각 연산 유닛에 별도의 worker thread 존재. 데이터가 준비되면 전달.

미리 A to Z 다 만들어놓기 때문에, 필요 없는 것도 전부 가져올 수 있지만, 실제 사용 시점에서 매우 성능이 좋아진다.