[CMU 15-445 Intro to DB Sys] Lec13 Query Execution(2)

Parellel Execution

• 같은 HW 자원을 가지고 더 많은 퍼포먼스를 낼 수 있다(higher throughput, lower latency)
• 시스템의 responsiveness 향상(한 worker가 stall된 동안 다른 worker가 일함에 따라 외부에서 보기에 stall이 적어 보임)
• lower total cost of ownership(TCO)(HW, SW, labor overhead, energy 등을 아낄 수 있음)

Parallel vs. Distributed

• 어플리케이션이 겉으로 보기에는 모두 single logical database로 보이게 된다.
• Parallel DBMS에서는 자원들이 physically 서로 가까이 있고, high-speed interconnect로 소통하게 된다. communication이 cheap, reliable한 것으로 가정된다.
• Distributed DBMS에서는 자원들이 서로 멀리 있을 수 있고, slow(er) interconnect로 소통한다. 그리고 communication cost와 reliability를 무시할 수 없다.

Process Models

• DBMS의 process model은 multi-user application으로부터의 concurrent request를 어떻게 다룰 지를 결정하고 있다.
• worker란 클라이언트를 위해 task를 실행하는 DBMS의 구성요소이다.

Process per DBMS Worker

• 각 worker가 separate OS process로 존재한다.
• 따라서 OS scheduler에 따라 움직임에 따라 통제력이 줄어들고, global data structure를 위해서는 shared memory를 사용하므로 overhead가 크다.
• 하지만 별도의 프로세스에서 구동되고 있기 때문에 crash가 발생하더라도 전체 시스템을 교란시키지는 않는다.
• pthread가 보편화되기 전에 있던 오래된 DBMS들(postgres, IBM DB2, Oracle)은 이 방식을 사용한다.

Thread per DBMS Worker

• 각 worker가 thread로 존재함에 따라, DBMS는 single process with multiple worker threads가 된다.
• 따라서 DBMS가 자체적으로 스케줄링을 관리할 수 있고, context switch에 드는 overhead도 적다. shared memory를 관리할 필요도 없다.
• 최근 20여년 간 만들어진 DBMS들은 모두 이 방식을 사용하고 있다. 오직 Postgres와 그 계열의 DB들만이 여전히 프로세스 기반 방식을 사용한다.
  • 그러나 thread per worker라고 해서 intra-query parallelism을 지원한다는 의미는 아니다. 이를테면 MySQL에서 여러 스레드를 쓰기는 하지만 하나의 쿼리는 하나의 스레드로 실행될 뿐이다.

    Scheduling

• 각각의 query plan에 대해서 DBMS는 언제, 어디서, 어떻게 실행할 지를 결정한다. DBMS는 언제나 OS보다 더 많은 것을 알고 있다.
• MS SQLServer에서는 SQLOS를 사용한다. 이는 user-level OS layer로 DBMS 내에서 구동되며, 할당된 HW 자원을 관리한다.
  • 여기서는 quantum이 4ms인데, 4ms마다 yield를 통해 다시 schedule하도록 한다.

Embedded DBMS

• 보통의 DBMS는 client-server 모델로서 어플리케이션과 독립적인 형태지만, embedded DBMS는 application과 동일한 address space 내에서 구동된다. 그래서 application이 스레드나 스케줄링을 관리한다.

Inter- vs. Intra-query Parallelism

• inter-query: multiple disparate queries를 동시에 실행하여 throughput을 높이고 latency를 낮춤. 단순히 read-only query라면 크게 어렵지 않음.
• intra-query: single query의 operator들을 병렬적으로 실행하여 성능을 향상시킴. latency를 낮추는 효과가 있음.
  • producer/consumer 패러다임으로 생각하면 operator들이 data를 생산하는 한편 소비함.

Intra-Query Parallelism

Intra-Operator(Horizontal)

• operator를 서로 다른 data subset에 대해 동일한 함수를 수행하는 independent fragments로 나눈다.
• 이를 위해서 exchange operator라는 것을 query plan에 넣어서 여러 operator들로부터의 결과를 합치거나 나누어준다. 이는 여러 child operator들에 동시에 next를 불러서 결과를 받아온다.
  • Gather(여러 worker의 결과를 합쳐서 single output stream으로 보낸다)
  • Distribute(하나의 input stream을 multiple output streams로 보낸다)
  • Repartition(multiple input streams를 multiple output streams로 보낸다)

Inter-Operator(Vertical)

• 주로 stream processing system에 많이 쓰인다. 그래서 계속 들어오는 데이터를 처리하기 위해 계속 돌아가야 하는 것이다.
• materialization을 하지 않고 data를 pipeline하기 위해 사용되므로 pipelined parallelism이라고도 불린다.

Bushy Parallelism

• hybrid of intra- and inter-operator parallelism

I/O Parallelism

• 위에서 살펴본 parallelism은 기본적으로 CPU에 대한 것이었는데, 병목이 디스크에서 발생할 수도 있다.
• 그래서 DBMS를 여러 storage device로 나누어서 disk bandwidth latency를 향상시킨다.
• 어떤 DBMS들은 이를 native하게 제공하지만, 어떤 경우에는 DBMS 외부에서 별도로 관리해야 할 수도 있다.

Multi-Disk Parallelism

• OS/HW를 통해 여러 multiple storage device에 나누어 저장한다(e.g. RAID).
• 같은 내용을 여러 device에 중복하여 저장하게 되면 I/O가 빨라지고 reliable해진다.

Database Partitioning

• DBMS 차원에서 저장할 디스크 위치를 지정할 수 있다.
• 하나의 logical table을 여러 disjoint physical segments에 저장하는 방식인데, 어플리케이션 입장에서는 이를 신경쓰지 않고 logical table만을 신경쓸 수 있게 하는 게 이상적이다.