원본 논문

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 으로써 대신하고, 이것 이외에도 읽고 버려야 할 데이터들이 있을 수 있다 1. 하지만 이러한 tombstone 은 전체 data 들 중에서 그리 많지 않기 때문에 이놈들은 model 에 포함하지 않는다.
    • 또한, LSM 을 사용함으로 인해 발생하는 read amplification 이 있을 수 있는데 2, 이것은 로 표시한다.
      • 즉, LSM 에 실제 저장된 entry 의 사이즈와 tuple 의 원래 사이즈 간의 크기 비율이 인 것.
      • 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 의 개수를 이라고 해보자.
  1. 만약 이 query 의 selectivity (즉, 전체 record 중에 몇개의 record 를 고르느냐) 가 라면, MetisDB 에서는 predicate pushdown 으로 storage node 에서 filtering 을 하기 때문에, network 를 타고 와야 하는 record 의 개수는 다음과 같다.
  1. 또한, 최종적으로 network 를 타고 전달되는 record 한개의 사이즈(byte) 를 라고 한다면, network 를 타고 와야 하는 총 데이터 사이즈는 다음과 같다.
  1. 그럼 이놈을 network bandwidth 로 나누면, 이놈을 전송하는 데에 걸리는 시간 (즉, Transmission Delay) 가 나오게 된다.
  1. 그리고 network 에 기본적으로 깔려있는 latency (In-network Delay) 3 을 더하면 network cost 는 다음과 같다.
  • 참고로, network 환경에서는 packet queing delay 4 가 있을 수 있는데, 이놈들은 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 개수인 에 대해서,
  1. 각 record 의 tuple size (byte) 인 를 곱하면 row store 에 있는 data size 가 나온다.
    • 다만 위에서 network cost 를 계산할 때는 를 사용했는데, 왜 여기서는 를 사용하냐고 생각할 수 있는데, 저장되어있는 tuple 의 크기와 output 으로 나가는 tuple 의 크기가 항상 같을 수는 없기 때문으로 이해하자.
  1. 그리고 row store 은 LSM 을 사용하기 때문에, 위에서 말한대로 만큼의 read amplification 이 발생한다. 그럼 이놈을 곱해주면 다음과 같다.
  1. 그럼 여기에 row store 에 대한 disk sequential read bandwidth 를 나눠주면 row store read latency 가 나온다.

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 만 읽으면 되므로 대신 key 의 크기인 와 value 인 row id 의 크기인 만큼만 읽으면 된다. 따라서,
  1. 그리고, index 를 통해 읽어야 할 row id 를 다 추렸다 하더라도 우선 모든 row 에 대해 row id 만을 읽어서 이게 원하는 row 인지 아닌지는 알아야 한다 5. 따라서 모든 row 에 대한 row id 를 읽는 latency 는 다음과 같다.
    • 여기서 random I/O bandwidth () 인 이유는 row id 만을 읽기 때문에 sequential scan 이 아니기 때문이다 6.
  1. 또한 이렇게 해서 선택된 row 들을 실제로 읽기 때문에, selectivity () 를 고려하면 선택된 row 를 읽는 latency 는 다음과 같다.
  1. 따라서 이것을 모두 종합하면 다음과 같다.

5.2.4. Column Scan on Column Store

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

5.2.5. Delta Scan

  • MetisDB 에서는 in-memory delta store 에 log 들이 append 가 되고, 이 log 들을 빠르게 찾아가기 위한 B+Tree 로 구성되어 있다.
  • 이때, 이 B+Tree 를 traversal 하는 latency 부터 살펴보자.
  1. 따라서, 개의 entry 가 들어 있는 delta store 에 대해, B+Tree 의 fanout 이 라면, 이 tree 의 height 는 다음과 같다.
  1. 그럼 이 tree 를 traversal 할 때 방문하는 node 는 (root node 를 고려하면) 다음과 같다.
  1. 그리고 node 내에 개의 child 가 있을 때, 이것을 binary search 로 탐색하여 child 를 선택한다면 probe 해야 할 child 의 수는 대략 일 것이다. 따라서,
  1. 다음에는 하나의 child 를 probing 할 때 소모되는 CPU latency 를 생각해 보자. 우선, CPU 1 cycle 에 걸리는 시간 (즉, CPU frequency 의 역수) 를 라고 하고, child probing 할 때 1 cycle 만에 실행되지는 않기 때문에 이때 소모되는 cycle 의 수를 라고 한다면 child probe 에 필요한 CPU latency 는 다음과 같다.
  1. 또한, child probe 에 필요한 memory access latency 는 memory bandwidth () 의 역수일 것이다. 따라서,
  1. 결과적으로 child probe 에 대한 CPU latency 와 memory access latency 를 더하면 child probe latency 가 나올 것이고, 따라서 모두 종합해 보면 다음과 같다.
  • 그리고, 이 B+Tree 에 있는 entry 에 대해 column store 에 적용을 해서 읽어야 할 것이다. 따라서, 우선 delta store 에 있는 개의 entry 에 대해, Index scan 에서와 비슷한 이치로 여기에 있는 애들애 대한 모든 row id 를 조회를 하고 selectivity 비율에 따라 tuple 에 접근할 것이다. 따라서,
    • 여기서 가 아니라 인 이유는 delta store 에는 columnar 로 저장되는게 아니라 full row 가 저장되기 때문이다 7.
  • 그래서 delta store 에 대한 총 latency 는 다음과 같다.

5.2.6. Column Scan in HTAP

  • 그래서 column scan 에 대한 cost 를 종합해 보면 다음과 같다.
  • 다만, 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 가 작다는 장점이 있다.
    • 위의 수식에서 을 비교해 보자.
    • 그럼 다른 점이 (대역폭을 제외하면) row store 에서 였던 것이 column store 에서는 가 된다.
    • 근데 는 당연히 1보다 크고, 는 record 전체 사이즈이기 때문에 당연히 column 하나의 사이즈인 보다 크므로 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. 이것 또한 주인장의 생각이다.