Materialization 과 Pipelining

데이터베이스 쿼리 실행 기법

도출한 플랜으로 쿼리를 어떻게 실행할 수 있을까요 ?
보통 Entire expression tree 라는 트리를 통해, 실행해야 하는 연산들을 procedural 하게 처리할 수 있습니다.

π<name>(σ<building=“Watson”>(instructor))⋈dept)

다음과 같은 연산이 있다고 가정합시다.
위 내용을 expression tree 로 나타내면

다음과 같은 형식이 됩니다.
한눈에 봐도 직관적으로 실행 순서를 알아차릴 수 있습니다.
데이터베이스는 도출된 expression tree를 이용하여 쿼리를 실행합니다.

쿼리 실행 방법에는 크게 두가지 방식이 있습니다.

1. Materialized evaluation
2. Pipelined evaluation

순서대로 알아보겠습니다.

Materialization

Materialization , 번역하면 구체화입니다. 어떤 방식으로 구체화를 진행할까요 ?
위의 expression tree를 자세히 보시면, 가장 먼저 실행되어야 할 연산이 가장 아래쪽( child ) 에 존재하는 것을 확인할 수 있습니다.

Materialized evaluation 은 각 순서의 연산을 진행 후 임시 메모리에 저장하는 방식으로 순차적인 연산을 실행합니다.

위의 예시를 들어보겠습니다. π<name>(σ<building=“Watson”>(department))⋈instructor) 의 연산은

1. σ<building=“Watson”>(department) 의 결과를 temp 에 저장
2. temp ⋈instructor 의 결과를 temp 에 저장
3. π(temp)
   위와 같이, 계산된 중간 결과를 임시 메모리에 저장하는 방식으로 진행됩니다.

해당 방식은 단순하여 항상 적용 가능하다는 장점이 있습니다.
하지만 중간 결과를 항상 디스크에 작성해야 하기에, writing cost 가 발생하게 됩니다.
(Writing 은 기존 read 연산보다 비용이 더 발생)

종합하자면, 각 연산의 비용 + write cost 로, 전반적인 비용이 높은 처리 방식입니다.

Double Buffering

하나의 버퍼만 사용하여 연산을 진행하는 경우, output buffer가 모두 차서 디스크에 작성하는 경우, 입력을 받지 못하는 상황이 발생할 수 있습니다.
따라서 read Buffer 와 write Buffer 를 두어, 한 버퍼가 디스크 작업 중일 경우에도 입력받을 수 있도록 Double Buffering 기법을 사용할 수 있습니다. 하지만 다른 버퍼를 두어야 한다는 점에서
성능 효율은 올라가지만, 그만큼 메모리 사용량이 증가한다는 특징이 있습니다.

해당 용어는 비단 database 뿐만 아니라 다른 분야에도 통용되는 용어입니다.
Materialized evaluation 과 동일하게 데이터 처리의 효율성을 높이는 기법입니다.

Pipelining

Pipelined evaluation은 각 연산들을 동시에 병렬로 연산하는 방식을 말합니다.

위 그림과 같이, 밀어내기 방식으로 연산을 진행하는 것을 뜻합니다.

해당 방식은 materialized evaluation 과 다르게, 결과물을 임시로 저장하지 않습니다.
때문에 잘 동작한다면 훨씬 저렴한 비용에 연산 실행이 가능합니다.

하지만 언제나 그렇듯, 모든 방식에서 잘 작동하는 것은 아닙니다.
Sorting(runs), hash join(partitioning) 등과 같이, 결과를 즉각적으로 알 수 없는 Blocking 연산들에 대해서는 불가능 할 수도 있습니다.

해당 방식은 누가 주체가 되어서 실행시키는지에 따라 demand-driven 과 producer-driven 방식으로 나뉘어 질 수 있습니다.

demand-driven

Lazy evaluation , 지연 실행 방식이라고도 의미합니다. System 이 Top-level 부터 시작해서, 수요에 따라 데이터를 공급받는, 필요할 때만 선택적으로 공급받는 방식을 의미합니다.
내가 어떤 데이터가 필요한지가 나타나야 하기 때문에, 각 연산들은 자신의 상태를 유지해야 합니다.
(그래야 다음에 무엇을 반환받을지 알 수 있습니다)

producer-driven

Eager pipelining 이라고도 불립니다. 해당 방식은 bottom-up 방식으로써, 그때 그때 처리되는 데이터들을 수요에 상관 없이 밀어 올리는 방식으로 연산을 진행합니다. 따라서 각 연산자들 사이에는 buffer가 필요합니다.
결과를 받는 부모들은 buffer 의 값을 사용하고 지우는 , producer-consumer 패턴의 방식입니다.

요약하자면, Demand-driven 방식은 system이 자식에게서 당겨오는, Pull 방식의 연산이고,
Producer-driven 방식은 자식이 연산이 완료될 때마다 buffer에 밀어넣는, Push 방식의 연산이라고 할 수 있겠습니다.

언제나 틀린 부분은 댓글 달아주시면 감사히 수정하겠습니다 !