[CMU 15-445 Intro to DB Sys] Lec12 Query Execution(1)

Query Processing Models

Iterator Model

• 각 operator는 open(), next(), close() 함수를 갖고 있음.
  • next()를 통해 다음 single tuple을 반환하거나, 더 이상 없을 경우 EOF를 반환함. 일종의 iterator 작동과 동일하다고 생각하면 됨.
  • open(), close()는 C++의 constructor, destructor와 유사한 역할로 생각하면 됨.

• 우선 쿼리의 윗부분부터 시작해서 아래로 가기까지 operator들을 open해준다. 그리고 next() 함수는 child operator가 반환한 값을 iterate하는 형식으로 되어 있다. root node에서 child에 대해 next()를 호출하면, child는 또 마찬가지로 child에 대해 next()를 호출하여, emit된 값을 single tuple 단위로 반환받는다.
  • 즉 emit될 때마다 현재 돌고 있는 함수를 빠져나가서 parent에게 반환하는 것처럼 생각할 수 있음. 하지만 일반적인 for문과의 차이는 iterator이기 때문에 어디까지 돌았는지 알고 있다는 점이다.
• 이와 같이 tuple 하나가 가능한 많은 operator를 거치기 때문에 pipelining이 가능하다.
• 어떤 operator(e.g. join, subquery, order)들은 children이 모든 tuple을 emit할 때까지 기다려야 한다(pipeline breaker).
• output control(LIMIT)은 비교적 용이한데, 원하는 타이밍에 next()를 더 이상 부르지 않으면 되기 때문이다.
• tuple을 하나 가져올 때 leaf에서 root까지 전부 다 이동해야 하기 때문에, 너무 많은 function call이 필요할 수 있다. 그리고 함수가 너무 많은 것은 cache의 코드 영역(instruction cache)에 좋지 못하다.

Materialization Model

• input 전체를 한번에 처리하고, output 전체를 한번에 내보낸다. 즉 결과가 single result로 "materialize"된다.
• iterator model과의 차이는 scan한 결과물을 어딘가에 따로 저장한 뒤에 그 전체를 한 번에 반환해서 올려보낸다는 데에 있다.

• OLTP 쿼리는 대체로 비교적 적은 수의 tuple만을 이용하기 때문에 OLTP에 유리하다. 중간에 나오는 결과값들이 많은 OLAP 쿼리의 경우 그 내용을 disk에 써야 할 수도 있어서 적합하지 않다.

Vectorization Model

• iterator model에서처럼 next() 함수를 사용하지만, 한번에 single tuple이 아니라 batch of tuples를 emit하게 한다.

Plan Processing Direction

• top-to-bottom: root에서 시작해서 children으로부터 데이터를 "pull"하며, function call을 통해 tuple이 넘어간다
• bottom-to-top: children에서 parent로 데이터를 "push"한다. cache/register의 tighter control을 가능하게 한다.

Access Methods

• table 내에 있는 데이터를 어떤 식으로 접근할지에 대한 문제다.

Sequential Scan

• page 순서대로 불러들여서 tuple을 순서대로 체크함. 이를 위한 internal cursor가 필요함.
• prefetching, buffer pool bypass, parallelization, late materialization, heap cluster, data skipping 등 optimization 방법들이 있다.
• Data Skipping
  • 1) Approximate Queries(lossy!): 전체 테이블의 sampled subset에 대해서만 쿼리를 해서 결과를 approximate한다.
  • 2) Zone Maps(lossless): 각 페이지에 있는 tuple attribute에 대해 미리 aggregation 값들을 계산하여 zone map에 저장해 둔다. page access가 필요한지를 판단하기 위해 먼저 zone map을 본다.

Index Scan

• selectivity에 따라서 적절한 index를 골라서 한다.
• multi-index scan이 지원되는 경우, 각각 index에 부합하는 record ID의 집합을 구한 뒤에 이를 합칠 수 있다. bitmap, hash table, bloom filter 등으로 효율적으로 교집합을 구할 수 있다.

Modification Queries

• INSERT를 하는 데에 있어서는 1) operator 내에서 tuple들을 materialize하거나 2) child operator로부터 넘어온 tuple을 삽입하는 방식으로 구현할 수 있다.

Halloween Problem

• update를 실시하는 과정에서 tuple의 physical location이 변경됨에 따라서, operator가 동일한 tuple을 여러 차례 방문하는 현상이다.
• 따라서 operator들은 tuple의 record ID를 pass해서 올려야 하고, 이미 본 tuple들을 기록해서 다시 방문하지 않게 해야 한다.

Expression Evaluation

• DBMS는 expression tree를 만들어 두고, context handle을 유지(current tuple, query parameters, table schema 등 필요한 metadata를 포함)하다가 tree를 따라서 값을 계산할 수 있음.
• 하지만 이는 느리기 때문에, 그냥 expression을 directly evaluate하는 게 나음(JIT compilation과 유사함)

Scheduler

• 기본적으로 query processing model에서는 data flow에 집중하여 설명하고 있는데, scheduler는 data flow와 control flow를 분명하게 구별한다.
• top-to-bottom 방식의 트리를 만드는 대신에, work order를 큐에 넣고 worker threads가 이를 수행하게 한다.