(논문) Rethink Query Optimization in HTAP Databases (5. Demain Model)

원본 논문

• 이 글은 Rethink Query Optimization in HTAP Databases, SIGMOD’24 논문을 읽고 정리한 글입니다.
• 별도의 명시가 없으면, 본 논문과 강의에서 그림을 가져왔습니다.

5.0. Prologue §

Arbitrary section

• 그냥 5.1. 직전의 내용이고, 논문에는 별도 section 으로 numbering 되어 있지는 않습니당

• Section 5 에서는 query plan selection 에 있어서 delta storage 가 미치는 영향 (즉, data dynimicity) 을 고려한 cost model 인 Demain (Delta Main) 에 대해 설명한다.
• 물론 여러 시스템마다 delta storage 를 어떻게 구성할지는 다르기 때문에, 이와 동일한 cost model 이 다른 시스템에도 곧바로 적용될 수 있다는 말은 아니다.
  • 다만, 본 논문에서 사용하고 있는 MetisDB 를 기반으로, delta storage 가 미치는 영향을 어떻게 모델링할 수 있는지에 대한 예시라고 할 수 있다.

5.1. Model Preliminaries §

• Modeling 에서는 위와 같은 약어를 사용한다.
  • 여기서 한가지 짚고 넘어갈 것은, disk 와 memory bandwidth 가 row store 와 column store 에 따라 구분되어 있다는 것이다.
  • 이것은 각각의 row / column store 가 별도의 machine 에서 작동하기 때문에 각각에 대해 bandwidth 가 다를 것이기 때문이다.
  • 또한, (뒤에서도 볼 수 있겠지만) random access 를 하냐 sequential access 를 하냐에 따라서도 bandwidth 가 달라지기 때문에 비록 위 표에는 적혀있지 않지만 이것들 또한 구분짓는다고 한다.
• 그리고 여기서 modeling 하는 query 는 range scan 이다. 즉,

SELECT col1
FROM table
WHERE col BETWEEN a AND b;

• 와 같은 형태의 query 에 대해 어떻게 cost 를 구할 것인지를 설명한다.
• 또한, MetisDB 에서는 row store 로써 LSM 을 사용하고 있기 때문에, 이에 대한 고려도 필요하다.
  • 우선 LSM 에서는 DELETE 를 tombstone 으로써 대신하고, 이것 이외에도 읽고 버려야 할 데이터들이 있을 수 있다 ¹. 하지만 이러한 tombstone 은 전체 data 들 중에서 그리 많지 않기 때문에 이놈들은 model 에 포함하지 않는다.
  • 또한, LSM 을 사용함으로 인해 발생하는 read amplification 이 있을 수 있는데 ², 이것은 $T$ 로 표시한다.
    • 즉, LSM 에 실제 저장된 entry 의 사이즈와 tuple 의 원래 사이즈 간의 크기 비율이 $T$ 인 것.
    • LSM 에 실제 저장된 entry 의 사이즈는 Global Meta Service 에서 추적한다고 한다.

5.2. Modeling Access Path In HTAP §

Arbitrary section

• 5.2.X 는 논문에 별도로 numbering 되어 있지는 않고, 주인장이 임의로 붙였습니다.

5.2.1. Network I/O Cost §

• 우선 storage node 에서 compute node 로 데이터를 땡겨와야 하기 때문에, Network I/O cost 가 당연히 있다. 이것에 대해 생각해 보자.

1. 우선 전체 record 의 개수를 $N$ 이라고 해보자.

$$N$$

2. 만약 이 query 의 selectivity (즉, 전체 record 중에 몇개의 record 를 고르느냐) 가 $sel$ 라면, MetisDB 에서는 predicate pushdown 으로 storage node 에서 filtering 을 하기 때문에, network 를 타고 와야 하는 record 의 개수는 다음과 같다.

$$sel\times N$$

3. 또한, 최종적으로 network 를 타고 전달되는 record 한개의 사이즈(byte) 를 $w_{res}$ 라고 한다면, network 를 타고 와야 하는 총 데이터 사이즈는 다음과 같다.

$$sel\times N\times w_{res}$$

4. 그럼 이놈을 network bandwidth 로 나누면, 이놈을 전송하는 데에 걸리는 시간 (즉, Transmission Delay) 가 나오게 된다.

$$\frac{sel\times N\times w_{res}}{B_{net}}$$

5. 그리고 network 에 기본적으로 깔려있는 latency (In-network Delay) ³ 인 $L_{net}$ 을 더하면 network cost 는 다음과 같다.

$$Cos{t}_{net}=\frac{sel\times N\times w_{res}}{B_{net}}+L_{net}$$

• 참고로, network 환경에서는 packet queing delay ⁴ 가 있을 수 있는데, 이놈들은 modeling 에서는 무시한다.

5.2.2. Row Scan §

• 우선, scan 을 할 때는 다음의 세 과정이 이루어 진다.
  1. 우선 disk 에서 읽어와 memory 로 올려야 하고
  2. Memory 에 있는 것을 cache 로 올려야 하고
  3. Cache 에 있는 것을 CPU cycle 을 소모해 scan 을 해야 한다.
• 당연히 이놈들은 pipelining 되기 때문에 가장 오래걸리는 놈인 disk I/O 에 bound 되게 된다. 따라서 row scan 뿐 아니라 앞으로의 modeling 에서 disk 에 접근해야 할 때는, disk I/O latency 를 기준으로 cost 를 산정한다.

1. 그럼 한번 계산해 보자. 우선 전체 record 개수인 $N$ 에 대해서,

$$N$$

2. 각 record 의 tuple size (byte) 인 $ts$ 를 곱하면 row store 에 있는 data size 가 나온다.
   • 다만 위에서 network cost 를 계산할 때는 $w_{res}$ 를 사용했는데, 왜 여기서는 $ts$ 를 사용하냐고 생각할 수 있는데, 저장되어있는 tuple 의 크기와 output 으로 나가는 tuple 의 크기가 항상 같을 수는 없기 때문으로 이해하자.

$$N\times ts$$

3. 그리고 row store 은 LSM 을 사용하기 때문에, 위에서 말한대로 $T$ 만큼의 read amplification 이 발생한다. 그럼 이놈을 곱해주면 다음과 같다.

$$T\times N\times ts$$

4. 그럼 여기에 row store 에 대한 disk sequential read bandwidth 를 나눠주면 row store read latency 가 나온다.

$$Cos{t}_{row}=\frac{T\times N\times ts}{D{B}_{row}^{seq}}$$

5.2.3. Index Scan §

• Index scan 을 할 때는 (1) 우선 index leaf node 에 대해 sequential scan 을 하고, (2) 읽어야 할 row id 를 추려서 disk 에서 읽어온다. 그럼 이때의 read latency 를 구해보자.

1. (1) 에서는, index leaf node 를 sequential scan 하므로, row scan 에서와 동일한 수식을 사용하되, index 의 key-value 만 읽으면 되므로 $ts$ 대신 key 의 크기인 $w_k$ 와 value 인 row id 의 크기인 $w_{id}$ 만큼만 읽으면 된다. 따라서,

$$\frac{T\times N\times (w_k+w_{id})}{D{B}_{row}^{seq}}$$

2. 그리고, index 를 통해 읽어야 할 row id 를 다 추렸다 하더라도 우선 모든 row 에 대해 row id 만을 읽어서 이게 원하는 row 인지 아닌지는 알아야 한다 ⁵. 따라서 모든 row 에 대한 row id 를 읽는 latency 는 다음과 같다.
   • 여기서 random I/O bandwidth ($D{B}_{row}^{rand}$) 인 이유는 row id 만을 읽기 때문에 sequential scan 이 아니기 때문이다 ⁶.

$$\frac{T\times N\times w_{id}}{D{B}_{row}^{rand}}$$

3. 또한 이렇게 해서 선택된 row 들을 실제로 읽기 때문에, selectivity ($sel$) 를 고려하면 선택된 row 를 읽는 latency 는 다음과 같다.

$$\frac{T\times N\times sel\times ts}{D{B}_{row}^{rand}}$$

4. 따라서 이것을 모두 종합하면 다음과 같다.

$$Cos{t}_{index}=\frac{T\times N\times (w_k+w_{id})}{D{B}_{row}^{seq}}+\frac{T\times N\times (w_{id}+sel\times ts)}{D{B}_{row}^{rand}}$$

5.2.4. Column Scan on Column Store §

• Column store 에서 column scan 을 할 때는, 크기 $w_a$ 인 column 에 대해 $N$ 개를 sequential 하게 읽어야 하므로, 이에 대한 latency 는 다음과 같다.
  • 이때에는 LSM 을 읽는 것이 아니므로, 당연히 read amplification 인 $T$ 은 당연히 빠진다.

$$Cos{t}_{col}^{\ast }=\frac{N\times w_a}{D{B}_{col}^{seq}}$$

5.2.5. Delta Scan §

• MetisDB 에서는 in-memory delta store 에 log 들이 append 가 되고, 이 log 들을 빠르게 찾아가기 위한 B+Tree 로 구성되어 있다.
• 이때, 이 B+Tree 를 traversal 하는 latency 부터 살펴보자.

1. 따라서, $N_d$ 개의 entry 가 들어 있는 delta store 에 대해, B+Tree 의 fanout 이 $b$ 라면, 이 tree 의 height 는 다음과 같다.

$$\lceil lo{g}_b(N_d)\rceil$$

2. 그럼 이 tree 를 traversal 할 때 방문하는 node 는 (root node 를 고려하면) 다음과 같다.

$$1+\lceil lo{g}_b(N_d)\rceil$$

3. 그리고 node 내에 $b$ 개의 child 가 있을 때, 이것을 binary search 로 탐색하여 child 를 선택한다면 probe 해야 할 child 의 수는 대략 $b/2$ 일 것이다. 따라서,

$$(1+\lceil lo{g}_b(N_d)\rceil )\times \frac{b}{2}$$

4. 다음에는 하나의 child 를 probing 할 때 소모되는 CPU latency 를 생각해 보자. 우선, CPU 1 cycle 에 걸리는 시간 (즉, CPU frequency 의 역수) 를 $p$ 라고 하고, child probing 할 때 1 cycle 만에 실행되지는 않기 때문에 이때 소모되는 cycle 의 수를 $f_p$ 라고 한다면 child probe 에 필요한 CPU latency 는 다음과 같다.

$$f_p\times p$$

5. 또한, child probe 에 필요한 memory access latency 는 memory bandwidth ($M{B}_{col}^{rand}$) 의 역수일 것이다. 따라서,

$$\frac{1}{M{B}_{col}^{rand}}$$

6. 결과적으로 child probe 에 대한 CPU latency 와 memory access latency 를 더하면 child probe latency 가 나올 것이고, 따라서 모두 종합해 보면 다음과 같다.

$$Cos{t}_{TreeTraversal}=(1+\lceil lo{g}_b(N_d)\rceil )\times \frac{b}{2}\times (f_p\times p+\frac{1}{M{B}_{col}^{rand}})$$

• 그리고, 이 B+Tree 에 있는 entry 에 대해 column store 에 적용을 해서 읽어야 할 것이다. 따라서, 우선 delta store 에 있는 $N_d$ 개의 entry 에 대해, Index scan 에서와 비슷한 이치로 여기에 있는 애들애 대한 모든 row id 를 조회를 하고 selectivity 비율에 따라 tuple 에 접근할 것이다. 따라서,
  • 여기서 $w_a$ 가 아니라 $ts$ 인 이유는 delta store 에는 columnar 로 저장되는게 아니라 full row 가 저장되기 때문이다 ⁷.

$$Cos{t}_{DataTraversal}=\frac{N_d\times (w_{id}+sel\times ts)}{D{B}_{col}^{rand}}$$

• 그래서 delta store 에 대한 총 latency 는 다음과 같다.

$$Cos{t}_{delta}=Cos{t}_{TreeTraversal}+Cos{t}_{DataTraversal}$$

5.2.6. Column Scan in HTAP §

• 그래서 column scan 에 대한 cost 를 종합해 보면 다음과 같다.

$$Cos{t}_{col}=Cos{t}_{col}^{\ast }+Cos{t}_{delta}$$

• 다만, plan selection 에는 위에서 말한 Row scan, Index scan, Column scan 셋을 비교한다. 왜냐하면 predicate pushdown 을 하기 때문에 결국에 compute node 로 전달되는 data 의 사이즈는 세 방법 모두 동일하기 때문에 network IO cost 는 동일하기 때문.

5.3. Access Path Selection §

• 위에서의 수식들을 기반으로, 어떤 access path 가 어떨 때 유리할지 생각해 보자.
• 일단 column store 는 row store 에 비해 I/O size 가 작다는 장점이 있다.
  • 위의 수식에서 $Cos{t}_{row}$ 와 $Cos{t}_{col}^{\ast }$ 을 비교해 보자.
  • 그럼 다른 점이 (대역폭을 제외하면) row store 에서 $T\times ts$ 였던 것이 column store 에서는 $w_a$ 가 된다.
  • 근데 $T$ 는 당연히 1보다 크고, $ts$ 는 record 전체 사이즈이기 때문에 당연히 column 하나의 사이즈인 $w_a$ 보다 크므로 column store 로 가면 I/O 는 당연히 줄어든다.
  • 따라서 이 효과는 table 에 column 의 개수가 많고, query 에 포함된 column 의 수가 적을수록 극대화된다.
• 그리고 index scan 은 selectivity 가 작을수록 강점을 가진다.
  • Selectivity 가 작으면 필요한 row 가 적고, 어떤 row 를 봐야하는지를 index 를 통해 빠르게 알 수 있으므로 이런 경우에는 column scan 보다 훨씬 좋은 성능을 낸다.
  • 반대로 selectivity 가 크다면, 많은 양의 row 를 tuple 전체에 대해 읽어야 하고, 또한 index 접근의 overhead 도 있기 때문에 row scan 이나 column scan 보다도 훨씬 안좋아진다.
  • 따라서 전통적으로는 특정한 threshold 를 두어 selectivity 가 이것보다 작을 경우에만 index scan 을 하게 한다.
• 그럼 row scan 은 언제 좋을까. 위의 Demain 에서 알 수 있다시피, column scan 에는 delta scan 비용이 포함되어 있다.
  • 그렇다는 것은 만약에 delta scan overhead 가 커진다면, 즉, write heavy 상황이어서 delta 의 양이 엄청 많아진다면, column scan 보다 row scan 을 하는 것이 오히려 더 좋다는 것이다.
• 그래서 종합해 보면 다음과 같다.
  • 만약에 selectivity 가 작다면, index scan 을 선택하는 것이 합리적이다.
  • 만약에 selectivity 가 크고 delta 의 양이 많아 이것으로 인한 overhead 가 columnar 의 I/O 감소를 압도한다면, row scan 을 선택하는 것이 합리적이다.
  • 만약에 그렇지 않다면, column scan 을 하는 것이 합리적이다.

Footnotes §

1. 구체적으로 어떤건지는 설명 안해준다. LSM 의 internal structure 를 알고 있다면 누구나 이해할 수 있는 내용일지도 모르지만, 주인장은 모르기 때문에 패스 ↩

2. 이것도 LSM internal structure 를 몰라서 패스 ↩

3. 이게 뭔지는 구체적으로는 모른다. ↩

4. 논문에는 stack delay 라고 표시되어 있다. ↩

5. 논문에는 이런 설명은 없다. 주인장의 생각이다. ↩

6. 이것도 논문에는 설명에 없고 주인장의 생각이다. ↩

7. 이것 또한 주인장의 생각이다. ↩