17. 12장 : OVERVIEW OF QUERY EVALUATION

컴퓨터에서 SQL이 어떻게 실행되는지 알아본다! (어떻게 구현됐는가!)

---

여기서 초반에 잠깐 언급했던건데,,, 이전 포스트

내가 작성한 SQL은 Query Parser & Optimizer를 통해 관계대수 (Relational Algebra)로 변경된다. (앞에서 배운것)

그리고 관계대수가 Query plan으로 변경되어 최종적으로 실행되게 된다.

=> 즉!! 관계대수에 나온 연산자들을 어떻게 컴퓨터내에 구현할것인가에 대해 배우는것이다.

각각의 연산자들 (select, join, project등등)은 iterator라는 형태로 구현된다.

Query Plan

쿼리플랜이란,,,? => 관계대수로 표현한 SQL을 약간 트리마냥 만들어준다.

dataflow graph

이런식으로 생겼다!! 아래부터 위로 올라가는 흐름으로 생각해보자면,,

• edge : 튜플의 "흐름"
• vertices(노드) : 관계대수
• source (맨 아래) : 테이블 접근 명령어 (요 노드에서 테이블로 접근해 실제 튜플을 가져온다)

각 노드에서 iterator가 일을 한다! (각 관계대수들이 iterator 인터페이스로 구현됨)

(옛날에,, 컴파일러에서 배운 eval eval eval 재귀호출 여러번했던 과제가 떠오른당... 대충 비슷한느낌 아니려나)

Iterator Interface

이터레이터는 어떤 메소드로 이루어져 있을까??

abstract class iterator{
    void setup(List<Iterator> inputs);
    void init(args);
    tuple next();
    void close();
}

• setup : dataflow graph를 그리는 단계 (각각의 이터레이터들을 연결하기)=> 즉 그래프가 어떤 모양으로 생겼는지 결정하기 위해 사용하는 메소드이다.
  그러니까 setup은 어떤 관계대수인지 상관없이 구현이 똑같다! (하는행동이 같음)
  지금 이터레이터의 자식노드가 무엇인지 정해준다 (input으로 들어오는게, 자식노드 리스트인것)
• init : 이터레이터 실행 전 초기화단계이 변수들을 초기화하는 역할을 해준다.
  이터레이터가 실행될 때 필요한 각종 멤버변수가 존재한다.
• next : 관계대수 구현이 들어간다. 반복적으로 호출된다. 튜플을 반환한다.여러번의 호출을 반복하여, 튜플을 하나씩 리턴하기때문에 인터페이스 이름이 "Iterator"가 되었다.
  한번의 호출에 "하나의 튜플"을 반환한다. 즉 릴레이션을 만들기 위해 반복적으로 호출된다.
• close : Iterator를 닫아준다.
  맨 마지막에 이터레이터를 종료하는 역할인듯 하다!

Pull-based computation model

pull system 참고자료

요청했을때 계산이 들어가는 방법이다!

그러니까.. 쿼리플랜을 기준으로 봤을 때, 호출순서가 아래에서 위로 올라가는게 아니라 위에 있는 노드에서, 아래의 자식노드에게 값을 요청하면 재귀호출처럼 타고타고 내려가는 방법이라는것 같다.

즉 루트에서 자식에서 튜플을 주거라,, 하면 자식이 또 next를 실행하면서 자식에게 튜플 내놔,,,,,,, 이렇게 재귀로 넘어간다!

streaming vs blocking

init, next를 구현할 때 스트리밍(즉시) 또는 블로킹(배치단위로)을 선택할 수 있다. (알고리즘을 선택하는것)

• streaming : 한번에 작은 작업만 처리, 튜플을 바로 반환함 -> select 구현에 사용
• blocking : 전체 입력을 처리한 다음에 결과를 반환함 -> sort 구현에 사용

Encapsulation

각각의 이터레이터들은 캡슐화되어있음!! (아무래도 클래스니까 그렇겠징...?)

그러니까 각각의 노드가 자식을 호출하고,, next로 결과를 반환하지만 자기랑 연결된 노드가 어떤 연산자인지는 알 필요가 없다

(그냥 또다른 이터레이터에게 내가 튜플을 주는구나! 튜플을 받는구나! 정도만 아는것)

State

각각의 이터레이터들은 private한 자기만의 상태를 가질 수 있다.

=> 페이지 크기만큼 클수도 있고, 아주아주 작을수도 있음!!

=> 뒤에 예시를 살펴보면서 하나씩 알아본다구 한다!

---

여러 연산자들이 어떻게 구현되는지 알아보자

Select

on-the-fly (streming) 방식이다.

// init(predicate)
{
    child.init();
    pred = predicate;
    current = NULL;
}

// next()
{
    while(current != EOF && !pred(current)){
        current = child.next();
    }
    return current;
}

// close()
{
    child.close();
}

• init : predicate라는 선택조건을 받음 (select 조건?)

  일단 자식을 init해준다. (child.init) -> 여기서도 리프까지 재귀로 타고타고 갈것!

  그리고 멤버변수를 초기화해준다 (pred : 선택조건)

  로컬커서 current를 가진다 (초기값음 null)

• next : select연산자에서 next를 호출하면 본격적인 동작이 시작되는데...

  지금 (current)에 담겨져 있는게 EOF가 아니고, 조건에 False 일때 반복한다.

  -> pred가 false일 때 반복하는 이유 : 지금 받아온 튜플이 조건에 안맞는다면 next에서 반환해주면 안되기 때문에 while에 가둔것

  즉 조건에 True일 때 반복문에서 탈출할 수 있다.

• close : 자식의 close를 호출한다.

Heap Scan

자식을 갖지 않고, 쿼리플랜의 리프에 존재한다 (진짜 힙파일에 가서 튜플을 가져와주는 역할!)

// init(relation)
{
    heap = open heap file for this relation;
    cur_page = heap.first_page();
    cur_slot = cur_page.first_slot();
}

// next()
{
    if (cur_page == NULL) return EOF;

    current = [cur_page, cur_slot]
    cur_slot = cur_slot.next();

    if (cur_slot == NULL){
        cur_page = cur_page.next();
        if(cur_page != NULL){
            cur_slot = cur_page.first_slot();
        }
    }

    return current;
}

// close()
{
    heap.close();
}

• init : 릴레이션의 이름이 전달된다 (어떤 테이블에서 튜플을 가져와야 하는지 알려주는것)

  이 릴레이션이 저장되어있는 파일을 연다 (카탈로그를 참조한다!)

  그리고 이 파일의 (즉 이 릴레이션의) 첫번째 페이지를 참조하는 current page

  첫번째 슬롯을 참조하는 current slot을 초기화한다.

• next : 힙파일에서 튜플을 읽어서 반환한다.

  지금 페이지가 null이라는건 EOF라는 뜻이므로 EOF를 반환하고 끝낸다.

  그렇지 않으면 뭔가 있다는 뜻이니까 current를 정의한다! == recordID가 된다 (페이지ID, 슬롯ID)

  slot 커서를 미리 다음으로 옮겨둔다 (다음 next호출을 위한것)

  여기서 slot을 옮겼는데, null이라면? 페이지가 변한것이다!

  페이지를 다음페이지로 옮기고, 그 페이지의 slot을 가져온다.

  이렇게 다음 next호출을 위한 page, slot을 저장해줬으면

  current를 리턴해준다.

• close : heap을 닫아서 힙파일과 관련된 운영체제의 리소스를 해제한다

heap scan은 자식노드가 없다!! 재귀호출을 하지 않는다.

cur_page.next()같은것들은, 이터레이터가 아니라 디스크&파일 매니저의 next이다. (이터레이터 재귀호출이 아닌것)

Sort (2-pass)

정렬을 구현한다. 블로킹 알고리즘을 사용한다.

2 pass sort algorithm 참고글

2 pass sort algorithm 참고글 2

postgres에서는 "src/backend/executr/nodeSort.c" 파일에서 sort 구현코드를 확인할 수 있다.

// init(keys)
{
    child.init();
    repeatedly call child.next() and generate the sorted runs on disk, until child gives EOF

    open each sorted run file and load into input buffer for pass 1
}

// next()
{
    output = min tuple across all buffers
    if min tuple was last one in its buffer, fetch next page from that run into buffer

    return output (or EOF if no tuples remain)
}

// close
{
    deallocate the runs files
    child.close()
}

• init : pass 0, 정렬기준이 되는 key를 전달받는다.

  자식노드를 초기화한다 (재귀호출)

  자식노드가 EOF를 반환할때까지 child.next()를 반복호출한다.

  이렇게 가져온 튜플들은 메모리의 버퍼를 채운다.

  메모리에 있는 튜플들을 퀵소트하고, 디스크에 run으로 기록한다.

  => 즉 버퍼가 채워질때까지 튜플을 불러오고, 이걸 정렬해서 디스크에 기록하는걸 반복함!!

  => init이 끝나면 디스크에는 여러개의 정렬된 run이 저장된다.

  => pass1에서 이 정렬된 run 을 한 페이지씩 읽어서 merge를 한다.

• next : pass1, merge를 진행

  각각의 정렬된 run파일에서 한 페이지씩 읽어 입력버퍼에 저장하며 병합을 준비한다.

  이 시점에서 출력할 최소 튜플은 이미 메모리에 존재한다!! (0pass에서 각 버퍼를 저장할 때 정렬해서 저장함)

  모든 버퍼에서 최소튜플을 찾아서 출력하고 (return) 페이지가 끝나면, 다음페이지를 가져온다.

  모든 튜플이 출력되면 EOF를 반환한다.

• close : 런 파일을 해제하고 재귀적으로 close 호출

Group By on Sorted input

입력으로 들어오는 튜플이 정렬된 입력 이라고 가정하고 구현한다.

-> 옵티마이저가 입력이 정렬되어있는지 확인한다.

아무튼 구현 자체는 정렬된 입력 이라고 가정하고 구현한다.

집계함수

agg_type	state	init	merge(x)	final
COUNT	count	0	count++	count
SUM	sum	0	sum += x	sum
AVG	[count, sum]	[0, 0]	[count++, sum += x]	sum / count
MIN	min	+infinity	min > x ? x : min	min

각각의 집계함수들은 state를 유지한다.

• count : 현재까지의 개수를 유지. merge가 호출될때마다 (새로운 튜플을 볼떄마다) 카운트를 증가한다. 최종적으로 지금까지의 총 개수를 반환함

• sum : 누적합을 계산

• AVG : 평균을 계산한다. count, sum 두가지 상태변수를 저장하고, 마지막에 평균을 반환한다.

• MIN : 지금까지의 최소값을 유지한다. 새로운 튜플을 보면, 기존 min값과 비교해 업데이트한다.

// init(group_keys, aggs)
{
    child.init();
    cur_group = NULL;
}

// next()
{
    result = NULL;

    do{
        tup = child.next();

        if(group(tup) != cur_group){
            if(cur_group != NULL{
                result = [cur_group, final() of all aggs];
            }

            cur_group = group(tup);
            call init() on all the aggs
        }

        call merge(tup) on all the aggs

    } while (!result);

    return result;
}

// close()
{
    child.close();
}

• init : group_by절의 key와 select에서 사용하는 집계함수 리스트를 입력으로 받는다.

  재귀로 자식노드를 초기화한다.

  현재 그룹은 NULL로 지정한다.

• next : 자식으로부터 같은 Group BY값을 가진 튜플들을 가져온다. 이걸 합쳐서 출력으로 보낸다.

  정렬된 입력 이라고 가정했으니까, 처음 봤던 튜플의 그룹과 "다른" 그룹의 튜플이 들어오면, 지금 그룹을 다 찾은것이다!

  즉 child.next로 현재 그룹의 튜플들을 가져오고, 다음 그룹의 튜플을 만나면 루프를 중단하고 리턴한다.

  근데, 맨 처음에 현재그룹을 NULL로 초기화했기 때문에 첫번째 반복문에 대한 처리가 필요하다

  (NULL이면 group(tup) != cur_group에 무조건 걸리니까)

  일단, 가져온 튜플이랑 지금 그룹이 다르고 && cur_group도 NULL이 아니면, 리턴시그널이다!! result를 채워주어 반복문을 탈출할 수 있게 해준다.

  반대로, cur_group이 NULL이면, resul를 채울게 아니라 집계함수를 초기화해서 그룹채울 준비를 해주는게 맞다!

• close : 자식을 재귀적으로 close 호출

broup by알고리즘은 메모리 효율적이다.

특정 튜플의 값을 집계함수에 병합한 다음에 다음 튜플을 가져온다. 즉 하나의 그룹에 대해 여러 튜플을 메모리에 동시에 저장하지 않는다.

단순히 merge를 반복하면서 집계함수를 유지하고, 마지막에 final로 각 집계함수 값을 돌려준다.

---

쿼리플랜

이런식으로 heapscan위에 select, sort, groupby를 사용할 수 있다.

쿼리플랜은 single-thread 방식이다.

위 그림으로 보면, 제일 위에 있는 스레드는 group by의 init을 호출한다. (작업 시작)

-> 이터레이터에서 (heap scan을 제외하면) init에서는 자식노드의 init을 재귀적으로 실행한다.

이후 이 스레드는 EOF를 받을때까지 group by에 대해 반복적으로 next를 호출한다

-> 이 또한, next에서 자식의 next를 재귀호출하며 아래아래로 내려가게된다.

중요한점은, 각 이터레이터의 출력결과는 디스크에 저장하지 않는다!

대신 콜 스택을 통해 반환된다.

next가 튜플을 return하고, 이게 다음 이터레이터로 전달된다.

(sort가 구현중 run을 위해 디스크를 사용하긴 하지만!!)

전체 쿼리플랜에서 보면, 각 튜플들이 노드를 타고 돌아다닐 때 디스크에 저장되지 않는다는걸 기억해야 한다!!

결론 : 이터레이터는 메모리활용이 매우 간결하다! (적은 메모리를 사용함)