(논문) BtrBlocks - Efficient Columnar Compression for Data Lakes, SIGMOD 2023 (7. Related work and conclusion)

본 글은 논문 BtrBlocks - Efficient Columnar Compression for Data Lakes (SIGMOD '23) 를 읽고 정리한 글입니다.

별도의 명시가 없는 한, 본 글의 모든 그림은 위 논문에서 가져왔습니다.

목차

• 1. Abstract, Intro
• 2. Background
• 3. Scheme selection and compression
• 4. Pseudodecimal encoding (BtrBlocks, SIGMOD 23)
• 5. Fast decompression
• 6. Evaluation
• 7. Related work and conclusion (현재 글)

7. Related Work §

7.0. Overview §

Tip Section 7.0. Overview

• 마찬가지로 논문에는 없는 section 이고, 형식상 주인장이 끼워 넣은 것이다.
• Column store 과 관련된 것들이 많이 있지만, 여기서는 BtrBlock 과 관련된 애들만 추려서 살펴볼 예정이다.

7.0.1. SQL Server. §

참고

• MS SQL Server Columnstore Index
• SIGMOD’10

• MS 의 SQL Server 에서 제공하는 columnar data format 을 Columnstore Index 라고 한다.
• 여기서는 table 의 최대 1,048,576 개의 row 를 모아 Rowgroup 을 만들고, 이때의 각 column data 들을 Column Segment 라고 한다.
• 이 Column Segment 단위로 compression 을 진행하는데, 다음과 같은 순서로 진행한다고 한다:

1. 모든 값을 정수로 표현하기
   • 각 자료형별로는 이렇게 정수로 바꾼다고 한다:
   1. String: 이놈은 dictionary 를 사용한다.
      • 최근 버전에서는 4byte int 로 변환하는 것이 아닌 short string 을 사용해서 더욱 최적화했다고 한다 ¹.
   2. Double: 이놈에게는 smallest common exponent 를 찾아 그것을 곱하여 정수로 바꾼다고 한다.
      • 가령 $123\ast 2^{-3}$ 과 $456\ast 2^{-5}$ 두 값이 있을 때, $2^5$ 를 곱해서 $492$ 와 $456$ 로 만든다.
   3. Integer: 이놈은 leading zero ($12300$ 에서 $00$) 를 지우고, FOR 를 적용한다.
2. Rowgroup 내의 row 들을 재배치하여 compression 하기 쉽게 변환
   • Row 를 재배치하는 이유는 RLE 를 위해서이다; compression scheme 를 적용할 때에는 순서를 바꿔 run length 가 최대가 되게 하면 좋기 때문.
   • 또한 column 단위가 아니고 row 단위로 재배치하는 이유는 column data 들을 재배치할 경우 row 방향으로 읽었을 때 다른 값이 읽일 수 있기 떄문이다.
   • RLE 말고 Bit-packing 를 적용하기도 한다.
3. Compress

• 구체적인 과정은 공개되어있지 않고, MS 내부 데이터로 실험한 결과 5.1배 더 compression ratio 가 좋았다고 한다.

7.0.2. DB2 BLU. §

참고

• VLDB’13

• IBM 의 DB2 에는 columnar store compression 을 위해 BLU 라는 방법이 추가되었다.
• 이놈은 대략 다음과 같이 한다:
  • 여러 Column Segment 들을 하나의 고정된 크기의 page 에 저장한다.
    • 참고로 SQL Server 에서는 이렇게 안한다고 하네.
  • 각 Column Segment 들은 Frequency encoding 으로 압축된다.
  • 이후에 data distribution 에 따라 한번 더 local dictionary ² 나 offset-coding ³ 으로 압축될 수도 있다고 한다.
• 이놈의 장단점은 다음과 같다.
  • 우선 장점은, (SQL Server 도 마찬가진데) decompression 하지 않고 range query 가 가능하도록 디자인 되어 있다.
  • 하지만 단점은, bitwise-operation 이 되어 있기 때문에 point acccess 는 decompression 을 동반한다고 한다.

Tip Point Access 란?

• 그냥 Random access 라고 생각하면 된다.
• 특정 (혹은 적은 수의) tuple 에 접근하는 것을 일컫는다.

7.0.3. SIMD decompression and selective scans. §

• SIMD 를 이용해 연산을 최적화 하는 것은 BtrBlock 뿐 아니라 이전에도 많이 연구되어 왔었다고 한다.

1. 이 논문 에서는 흔한 자료구조들에 대한 연산을 SIMD 로 바꾸고, 이때의 성능 향상에 대해 연구했었다.
2. 이 논문 과 이 논문 에서는 column store 에 대한 predicate evaluation, decompression 을 SIMD 로 바꿨을 때를 연구했고,

Tip Predicate 란?

• 간단하게 말하면 SQL 에서 WHERE 절을 의미한다고 생각하면 된다.
• CMU-15445 를 참고하자.

3. 이 논문 과 이 논문 에서는 세로로 값을 저장하고 SIMD 를 적용해 더 빠르게 predicate evaluation 을 했다고 한다.
   • 저 “세로로 값을 저장” 하는 것은 64bit 값을 하나의 address 가 아닌 64개의 address 에 저장해, 여러 값들에 대한 $k$ 번째 bit 가 하나의 address 에 들어오도록 한 것을 의미한다 [^kth-bit-adjacent].
4. 이 논문 에서는 predicate 에서 일반적으로 여러 column 이 evaluation 된다는 생각에, 여러 column 에 대한 값들을 하나의 “word” 에 집어넣고 이 “word” 에 대해 SIMD 로 최적화한 operation 을 돌리는 방식을 제안했다.

7.0.4. Compressed data processing in BtrBlocks. §

• Section 7.0.2 에서 말한 것 처럼, 어떤 포맷들은 compression 상태에서도 어느 정도의 query 를 할 수 있도록 디자인 되어있다.
• 하지만 얘네들의 경우에는 computing 과 storage 가 통합되어 있는 proprietary system 에서나 유용하고, Data Lake 에서는 이것보다는 decompression speed 가 더 유의미하다고 한다 ⁴.
  • Decompression speed 가 빠르면 query 를 바꾸지 않고도 성능 향상을 이뤄낼 수 있기 때문.
• 물론 근데 사용된 scheme 이 그것을 지원하기만 한다면, 이론적으로는 compressed data 에서 query 를 하는 것이 가능하기는 하다고 한다.

7.0.5. HyPer Data Blocks. §

• HyPer 이라는 인메모리 HTAP 시스템에서는 cold data 접근을 최적화하기 위해 Data Block 이라는 것을 제안했다. (논문)
• HTAP 이라는 것은 OLTP 와 OLAP 를 모두 제공해 줘야 한다는 소리이고, 이것은 OLTP 의 hot data point access 와 OLAP 의 all data range access 를 모두 충족해야한다는 소리이다.
• 따라서 Data Block 에서는 다음과 같은 최적화를 진행했다.

1. 일단 point-access 를 위해 byte-addressable 한 compression scheme 만을 사용했는데 여기에는:
   1. One Value
   2. Ordered Dictionary Encoding
      • 얘는 dictionary 와 유사한데 dictionary 를 정렬해 압축된 상태에서도 range query 가 가능한 방법이다.
      • 그리고 dictionary size 에 따라 code 의 bit length 를 동적으로 정한다고 한다.
   3. Truncate
      • 얘는 FOR 과 유사한데 이때의 기준치가 block 내 값들의 최소값인 방법이다.
   • 이 scheme 들을 선정하는 것은 statistics 를 이용한다고 한다.
2. 각 block 에는 lightweight index 와 SMA (Small Materialized Aggregate) 를 담고 있어, point access 를 돕는다고 한다.

Small Materialized Aggregate (SMA) 란?

• 작은 사이즈의 Data Cube 라고 생각하자.
• 이 논문 에서 제시된 것이다.

• 뭐 결과는 5배 정도의 compression ratio 향상이 있었다고 한다.

7.0.6. SAP BRPFC. §

• SAP 이 제시한 string encoding 은 Block-based Re-Pair Front Coding (BRPFC) 이다.
  • 이건 SAP HANA 의 dictionary string pool 이 전체 메모리의 28% 나 차지하기에 이것을 줄이기 위해 제시된 것이다.
• 우선 이놈은 string dictionary 를 최적화하는 것으로, 두 개념으로 쪼개볼 수 있다.

1. Block-based Front Coding: 이건 정렬된 dictionary 가 주어졌을 때, 앞선 문자열과의 공통된 prefix 를 prefix length 로 교체하는 것이다.
   • 가령 [SIGMM, SIGMOBILE, SIGMOD] 는
   • 각 원소를 이전 원소와 비교하면 [SIGMM, (SIGM)OBILE, (SIGMO)D] 와 같이 되기 때문에,
   • 결과적으로 [SIGMM, (4)OBILE, (5)D] 가 된다.
2. Re-Pair: 이건 각 block 에 대해 동적으로 생성된 grammar 를 이용해 substring 을 치환하는 방법 ⁵ 이다.

• 여기에서도 SIMD 를 이용해 decompression 을 최적화했는데, BtrBlock 의 저자들은 그래도 너무 느려서 BtrBlock 에는 이 방법을 추가하지 않았다고 한다.

7.0.7. Latency on data lakes. §

• BRPFC 는 SAP HANA 와 같은 인메모리 상황에서 per-string access latency 를 최소화하기 위함이었다.
• 하지만 Data Lake 에 데이터가 저장되고 이것을 네트워크에 태워 한꺼번에 가져오는 상황은 이와는 꽤 다르고, 따라서 BRPFC 기법은 별로 도움이 안됐다.
• 결과적으로 throughput 과 decompression latency 를 줄이는 것이 access latency 보다 더 중요해 이것을 중점적으로 최적화했다고 한다.

8. Conclusion §

• 드디어 BtrBlock 의 결론을 내려보자.
• BtrBlock 은 Data Lake 를 위한 Columnar compression format 이고,
• PBI 를 이용해 evaluation 하며 compression scheme pool 을 선정하였으며,
• Floating point encoding 을 위한 새로운 방법인 PDE 또한 scheme pool 에 추가하였으며,
• Sample-based selection 을 통해 decompression speed 와 compression ratio 모두 월등한 새로운 compression 방법을 제시할 수 있었다고 한다.

Footnotes §

1. 구체적으로 어떻게 되는지는 모르겠지만, 별로 중요한건 아니니 나중에 궁금하면 찾아보자. ↩

2. 이게 뭔지 (그냥 Dictionary 와는 뭐가 다른지) 정확히는 모르겠다. ↩

3. 이것도 뭔지 모르겠다. 느낌으로는 FOR. 원본 논문 읽어보면 더 정확하게 알 수 있긴 한데, 일단 패스. ↩

4. 근거는 제시하지 않는다. 그냥 의견을 주장하는 것이다. ↩

5. 몰?루 일단은 넘어가고 나중에 다시 보자. ↩