(논문) The FastLanes Compression Layout - Decoding 100 Billion Integers per Second with Scalar Code, VLDB 2023 (2. FastLanes)

본 글은 논문 The FastLanes Compression Layout: Decoding > 100 Billion Integers per Second with Scalar Code (VLDB '23) 를 읽고 정리한 글입니다.

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

목차

• 1. Introduction
• 2. FastLanes (현재 글)
• 3. Evaluation
• 4. Related Work
• 5. Conclusion and Future Work

2. FastLanes §

Units

• $T$: Lane 하나의 길이
• $W$: BP 된 bit-width
• $S$: Lane 개수

2.1. Many SIMD widths §

2.1.1. Challenge §

• SIMD 는 처음에는 64bit register 로 시작했지만 지금은 8배나 늘어 512bit 을 지원한다.
  • 가령 x86 의 AVX512 등.
• 기존의 SIMD instruction 들은 특정 사이즈의 register 에만 집중해 왔다.
• 가령 SIMD-BP128 과 같은 4-way interleaving 방식은 128bit register 에 BP 된 값 4개를 할당해 처리한다 (int 는 32bit 이므로 $32\times 4$)
  • 이 방법을 이용해 bit 가 연속적으로 packed 되어 있으면 필요했을법한 cross-lane instructions 들 (PERMUTE, BITSHUFFLE) 을 우회해 왔다 ¹.
• 하지만 이것은 128bit register 에만 효과가 있고, 다른 사이즈의 register 에 대해서는 충분한 parallelism 이 되지 않는다고 한다.
  • 물론 그에 따라 8-way, 16-way 등의 방법도 소개되었지만 각자의 width 에 제한된다는 점은 동일하다.

2.1.2. Contribution §

• 따라서 FastLanes 에서는 미래의 언젠가는 출시될 1024bit register 를 가정하여 설계했다고 한다.
  • 이것이 FLMM1024 register 인것
• 이것은 다음과 같은 사실에서 기인한다:
  • 더 넓은 lane width 를 기반으로 디자인된 data layout 은 lane-cross instruction 을 사용하지 않는 한 더 좁은 lane width 에 적용시키는 것은 껌이라고 한다.
    • 그냥 넓은 lane width 에서 사용한 instruction 과 동일한 기능을 하는 좁은 lane width 버전의 instruction 을 사용하면 되기 때문.
  • 하지만 반대의 경우는 참이 아니다; 더 좁은 lane width 기반의 data layout 은 놀고 있는 lane 이 생기는 등의 병렬화 감소 혹은 PERMUTE (BITSHUFFLE) instruction 의 필요성 등의 부작용이 생기게 된다 ².
  • 그렇기 때문에 FastLanes 에서는 더 큰 크기의 register 를 기준으로 설계했고, 이것을 실제 register 사이즈에 맞게 scale-down 하는 것은 아무런 문제가 없을 것이라는 주장임
• 물론 다른 사이즈의 virtual register 를 사용할 수도 있다; 2048 이나 4096 같은 더 큰 애들을 사용할 수도 있음.
  • Register 의 사이즈는 Chunk size (chunk 에 담기는 value 의 개수) 에 영향을 준다.
    • 당연히 Register size 가 늘어나면 lane 도 많아지므로 chunk size 도 늘리는게 맞자나?
  • 근데 chunk size 가 커진다는 것은 그만큼 value range 가 커질 가능성이 있기 때문에 BP 시에 compression ratio 가 더 안좋아질 수 있다.
    • 물론 exception mechanism 으로 이러한 문제를 완화할 수는 있지만.

2.1.3. Interleaving Bit-packing §

• 위 그림이 interleaved BP 를 나타낸 그림이다.
  • 일단 각 value 들은 3bit 로 BP 되어있는 상태다. (파란색, 분홍색, 노란색이 각각 1bit 임)
  • 그리고 하나의 FLMM1024 word (SIMD 로 처리되는 단위) 는 1024bit 이고,
  • 이것으로 1024 개의 value 를 표현하기 위해서는 당연히 3개의 word 가 필요하다.
    • 1value = 3bit, 1024value = 3072bit = 3word
    • 위 그림에서는 빨간색 테두리 상자 하나가 1개의 word 이다. 따라서 세개의 word 가 그려져 있는 것을 볼 수 있음
  • Lane width 는 8bit 고, 따라서 총 128개의 lane 으로 하나의 word 가 구성된다.
  • 여기서 검은 상자 안의 숫자는 해당 value 에 대한 sequence number (logical position of the column) 이다.
    • 즉, 0이면 column 내에서 가장 첫번째 값이라는 것.
  • 이때 각 값들은 lane 들에 round-robin 식으로 분배된다.
    • seq no 를 0부터 쭉 따라가보면 알 수 있을 것이다; value[0] 은 lane[0] 에 배치되고, value[1] 은 lane[1] 에 배치되는 등
  • 근데 lane width 는 8bit 고 BP 는 3bit 이기 때문에 딱 들어맞지 않고 bit 가 좀 잘리게 된다.
    • value[256] 을 보자.
    • 이놈은 첫번째 word 의 lane[0] 에 비트 3개가 다 들어가지 못하고 하나 (파란색) 가 잘려서 두번째 word (그 다음줄) 로 떨어져 나간 것을 볼 수 있다.
    • value[640] 도 유사한 상황임; 이놈은 word[1], lane[0] 에 비트 1개만 들어갈 수 있어 하나 (노란색) 만 여기에 들어가고 나머지 (파란색, 분홍색) 은 word[2], lane[0] 로 튕긴 것을 볼 수 있다.

2.2. Heterogeneous ISAs §

2.2.1. Challenge §

• 새로운 SIMD 가 도입되면, instruction 의 관점에서 다음의 두가지 비대칭이 생긴다고 한다:
  • 일단 새로 도입된 instruction 이 기존에는 없는 기능이거나
  • 기존에 있던 instruction 이 새로운 SIMD 에서는 지원하지 않는 경우
• 이 두 가지 중 어느것이든 여기에 의존하고 있는 data layout 은 문제가 생기게 된다.
• 또한 ISA 호환성 문제는 점점 더 심각해지고 있다.
  • 가령 ARM 아키텍쳐를 차용한 server 인 AWS Graviton 과 PC 인 Apple Silicon 은 ARM 의 NEON 혹은 SVE instruction set 의 서로 다른 subset 을 도입하게 된다.

2.2.2. Contribution §

• 따라서 FastLanes 에서는 이런 호환성 문제를 없애기 위해, ISA 종류와 SIMD 크기 모두에 무관한 virtual instruction set 을 새로 정의하여 사용한다.
  • 즉, 모든 ISA, 그리고 모든 SIMD 크기에서 공통적으로 제공하는 간단한 기능만을 사용하여 FastLanes 를 구현했다는 것.
  • 이들을 기존의 ISA 를 이용해 구현하는 것은 아주 간단하다.
    • 그냥 동일한 기능을 하는 intrinsic 을 여러번 호출하면 되기 때문.
    • 가령 uint64 자료형을 $T=8$, $S=8$ 64bit register 로 생각해 uint64 자료형에 대한 연산으로 $T=8$, $S=8$ vectorized execution 을 대체하고,
    • uint64 연산을 16번 호출하는 것으로 $T=8$, $S=128$ 1024bit register (FLMM1024) 연산을 구현하는 것이다.
      • 이건 아래의 코드로 추가적으로 알아보자.

struct { uint64 val[16]; } FLMM1024; // 16*uint64 = FLMM1024
FLMM1024 AND<8>(FLMM1024 A, FLMM1024 B) {
	FLMM1024 R;
	for(int i=0; i<16; i++) R.val[i] = A.val[i] & B.val[i];
	return R;
}

• 위 코드는 $T=8$, $S=128$ FLMM1024 의 & 연산이다.
  • 논문에는 ”Scalar_T64 codepath” 라고 표현되어 있다.
• 이때 위의 코드를 보면 lane 8 개에 대한 & 연산을 uint64 & 로서 사용하고 있다는 것을 알 수 있다.
• 그리고 그것을 16번 반복해서 원하는 연산을 구현하고 있는 것.

2.2.3. List of virtual instructions §

• 그래서 FastLanes 에서 사용하고 있는 insruction (intrinsic) 은 다음과 같다.

• 딴놈은 그렇다 치고, AND_L(R)SHIFT 만 정리하고 가보자.
• AND_LSHIFT 는 MASK 를 이용해 몇개의 least significant bits 를 잘라낸 후 N 만큼 왼쪽으로 shift 를 하는 것이다.
  • 가령 1100101 에 MASK 가 111, N 은 2라면
  • 1100101 & 111 는 101 이고
  • 그것을 2만큼 left shift 하여 10100 가 그 결과가 되는 것.
  • 수식으로 표현하면 (INPUT & MASK) << N 이다.
• AND_RSHIFT 는 왼쪽부터 N 위치에서 MASK 만큼의 중간 bit 를 잘라내는 것이다.
  • 가령 위에서와 동일한 예시를 들자면
  • 1100101 에서 2번째 위치에 MASK 를 씌운 001 이 그 결과인 것.
  • 수식으로 표현하면 (INPUT & (MASK << N)) >> N 이다.
  • 즉, 111 << 2 는 11100 이고
  • 1100101 & 11100 은 00101 이며
  • 00101 >> 2 는 001 이 되는 것.
• 이놈은 이렇게 묶어놓은 이유는 대략 두가지로 정리할 수 있다.
  • BP 시에 AND 와 SHIFT 가 연달아 나오는 경우가 많기 때문이고
    • BP 에서는 packing 된 bit 들을 MASK 와의 AND 로 골라내고, 이것을 SHIFT 하여 원하는 위치로 보내는 연산이 요구된다.
    • 뒤에 예시가 나올테니 이따 보자고
  • 그리고 SHIFT 를 한다는 것은 원하지 않는 bit 들도 이동되기 때문이다.
    • SHIFT 로 bit 가 이동된다는 것은 어떤 bit 들은 다른 lane 에 할당된다는 것이고, 이건 SIMD instruction 들에서는 발생하지 않는 것이기 때문이다.
    • 즉, bit 가 lane 에 걸쳐 이동하는 것은 SIMD 에서는 허용되지 않기 때문.
    • 따라서 masking 을 통해 원하는 bit 만 골라내 다른 bit 들이 lane 을 넘어가는 일이 없도록 한다.

2.2.4. Usage example: Unpacking interleaving-BP §

• 그럼 이제 위의 예시 interleaved bit-packing layout 를 unpack 하는 코드 예시를 보자.
  • 즉, 이 예시는 $W=3$, $T=8$, $S=128$ 이다.
  • Listing 2 는 pseudo-code 이고, Figure 3 은 그에 대한 visual representation 이다.

• 간단히 살펴보고 가자.
  • 일단 value 0 ~ 127 까지는 lane 의 least significant bit 에 위치한다.
    • 따라서 이놈들은 AND_RSHIFT 로 LSB 3비트를 꺼내서 STORE 하면 될 것이다.
  • 그리고 value 128 ~ 255 까지는 (설명을 위해 각 lane 의 bit 들을 오른쪽부터 0-index 를 매기면) bit index 3 ~ 5 에 위치한다.
    • 이놈도 AND_RSHIFT 로 중간의 3비트를 꺼내서 LSB 로 shift 한 다음, STORE 하면 될 것이다.
  • 근데 256 ~ 383 까지는 1비트가 잘려 다른 FLMM1024 word 에 들어가 있다.
    • 이때는 일단 AND_RSHIFT 로 lane 의 MSB 2 비트를 꺼내서 LSB 로 shift 한 다음,
    • 다음 word 에서 AND_LSHIFT 로 lane 의 LSB 의 1비트를 꺼내서 bit index 2 로 shift 해주고,
    • 위 둘의 결과를 OR 로 합쳐주면 될 것이다.
• 이러면 10개의 instruction ³ 만으로 384 개의 value 를 꺼낼 수 있게 된다.
  • 이건 2GHz core, x86 AVX512 ISA 기준으로 1초에 1400억개의 value 를 unpacking 할 수 있는 수치라고 한다.
  • 물론 중간중간에 query execution pipeline 이 끼어드는 것까지 감안하면 100배정도 느려지긴 한다.
  • 그럼에도 불구하고 이건 매우 빠른 것이며, 따라서 unpack 에 소모되는 비용은 거의 없다고 해도 무방하다.
• 또한 저자들은 저런 code 를 모든 경우의 수에 대해 전부 static 하게 자동생성했다고 한다.
  • 즉, 위에 예시로 준 저 unpack 연산을 $T\in \{8,16,32,64\}$, $1\le W<T$ 의 모든 $T$, $W$ 경우의 수 (즉, $7+15+31+63=116$ 개) 에 대해 전부 static 하게 자동생성하여 pre-compiled function 을 만들어놨다고 한다.

2.3. Dealing with Sequential Data Dependencies §

2.3.1. Basic Transposition idea §

• DELTA 를 SIMD 로 처리하기에는 Data Dependency 문제가 있다.
  • 즉, DELTA 에서는 바로 이전의 값을 알아야 다음 값을 알아낼 수 있는데 SIMD 에서는 바로 이전의 값이 바로 옆의 lane 에 들어가기 때문.
• 아래 그림은 이 문제를 그림으로 보여준 것이다.

• 일단 legend 를 알아보자.
  • 위의 그림을 1-column, 2-row 박스 단위로 생각해 보자. 이때 각 박스의 위쪽 볼드체 글씨는 “값” 을 나타낸다.
    • 이 “값” 은 (a) 와 (b) 가 다르다; (a) 에서는 delta 값이고, (b) 에서는 delta 가 처리된 실제 값을 나타낸다.
  • 그리고 박스의 색깔이 노란색인 것은 base (즉, entry point) 이고, 초록색인 것은 intermediate 이다.
  • (a) 의 검은 화살표는 dependency 와 적용 순서를 나타낸다.
  • (b) 의 초록색 화살표는 마찬가지로 dependency 를 나타내는데, 적힌 숫자가 delta 값이다.
• 보면 뭐 어려울 것은 없다; 이전의 값에 delta 를 더해 현재의 값을 구하며 인접한 놈에게 dependency 가 걸려있는 모습이다.
• 이때 parallel 을 위해서 base 를 여러개 사용할 수 있을 것이다. 즉, base 를 여러개 사용하면 아래와 같은 그림으로 decoding process 가 바뀐다.

• 근데 여전히 data dependency 는 인접한 값에 엮여 있다. 이걸 아래와 같은 layout 으로 바꾸면, 인접하지 않도록 dependency 가 걸리게 할 수 있다.

• 즉, base 여러개를 각 lane 에 넣고, 그것과 동일한 순서대로 다음에 처리될 값들을 넣으면 인접하지 않은 값들에 dependency 가 생기기 때문에 SIMD 로 처리하는게 가능해진다.
• 이 layout 이 바로 Transposition 이다. 즉, 데이터의 위치를 병렬처리하기 좋게 바꾼다는 것.
  • 이때의 base 값들은 columnar foramt 의 header (아마 metadata) 에 들어가 있다.
• SIMD register 단위로 보자면, 이렇게 처리된다고 할 수 있다.

• 즉, 기존에 16번의 delta-addition 은 4번으로 확 줄어들게 된다.

2.3.2. FastLanes Transposition layout §

• 그럼 이제 실제로 FastLanes 에서 Transposing 은 어떻게 되나 알아보자.
• 일단 FastLanes 에서 chunk size 는 register size 와 동일한 1024 이다. 그럼 왜 이렇게 정한건지 생각해 보자.
  • 한번에 처리하는 chunk 의 tuple 개수를 $C$ 라고 해보자.
  • 그리고 register 의 bit-width 는 $R$, lane 의 bit-width 는 $T$ 라고 해보자.
  • 그럼 lane 의 개수 $S$ 는 $S=R/T$ 이 된다.
  • 이 $S$ 가 결국에는 base 의 개수가 되므로 한 lane 에서 처리하는 tuple 의 개수는 $C/S=(C\times T)/R$ 이 된다.
  • 이때 chunk 의 크기는 최소가 되는 것이 좋다. 위 에서 말한 것처럼, chunk 의 크기가 커지면 value range 가 넓어져 BP 를 적용하기 불리하기 때문이다.
  • 한 lane 에서 처리하는 tuple 의 개수는 $(C\times T)/R$ 이기에 이 값이 정수가 되는 최소의 $C$ 를 정해야 하는데, 이건 결국 $R$ 이다.
    • 왜냐면 FastLanes 에서는 모든 가능한 lane 개수에 대응하는 것이 목표이기에, $T$ 는 정수 변수이기 때문이다.
  • 따라서 chunk size $C$ 는 FastLanes 의 register size 와 동일한 1024 가 되는것.
• 결국, 아래의 그림과 같은 형태가 된다.

• 정리하자면, FastLanes 에서 Transposed-delta decoding 은
  • 한번에 1024개의 값이 chunk 로서 처리되고
  • $0$, $T$, $2T$, …, $(S-1)T$ 총 $S$ 개의 값이 base 로서 하나의 register 에 들어가며
  • 이 base 부터 시작해서 delta addition 이 병렬적으로 수행되는 것이다.

2.3.3. Discussion for not-preserving tuple order §

• 근데 한낱 data format 일 뿐인 FastLanes 에서 데이터의 순서를 막 바꿔도 괜찮을까? 결론은 문제가 없을 것이라는 주장이다.
  • 느낌상으로는 review 시에 공격들어와서 이 내용을 추가한게 아닌가 싶다.
• 왜냐면 일단 순서는 크게 중요하지 않을 수 있다:
  • Relational algebra 에는 “순서” 라는 개념이 없다. 집합 (Set) 기반이기 때문.
  • DBMS 의 query operator 는 순서에 의존하지 않는다.
    • 즉, 어떤 순서로 들어와도 정상적으로 처리된다는 것.
• 그리고 만일 순서가 중요한 경우에는, 충분히 복원될 수 있다.
  • Transposition 를 거꾸로 적용하면 원래의 순서가 나오기 때문.
  • 아니면 “Selection vector ⁴” 라는 놈을 사용하여 order 를 encoding 하는 방법도 있다고 한다.
    • 이 “Selection vector” 는 다소 operation 을 느려지게 할 수도 있다고 하긴 하지만
    • 에러의 여지가 없는 간단한 arithmetic 연산의 경우에는 동일한 selection vector 를 처리하지 않도록 vectorized executor 가 최적화되어 있기 때문에 이러한 overhead 가 무시되기도 한다고 한다 ⁵.

2.4. The Unified Transposed Layout §

2.4.1. Challenge §

• 근데 위 의 layout 에는 한가지 문제가 있다.
  • 이 layout 에 의하면, tuple 의 순서는 lane 의 개수 ($S$), 즉 lane 의 bit-width ($T$, $S=1024/T$ 이기 때문) 에 영향을 받는다.
  • 근데 안타깝게도 이 $T$ 값은 column 에 따라 달라질 수 있다. BP bit-width ($W$) 는 column 마다 다르기 때문.
• 따라서 위의 layout 을 그대로 사용하려면 다음의 두가지 선택지가 있다.
  • 첫번째는 column 별로 다른 순서를 가지게 하는 것이다.
    • 즉, 위에서 말한 “Selection vector” 를 사용해 순서를 복원하는 식으로 column 별 독립된 순서를 가지게 할 수 있다.
    • 하지만 당연히 selection vector 로 원래 순서를 알아내는 overhead 가 끼게 된다.
  • 두번째는 순서를 통일하는 방법이다.
    • 즉, base 의 개수를 $S$ 말고 고정값으로 박아놓자는 것.
    • 하지만 그럼 당연히 lane 이 비는 상황이 생기게 된다. 즉, base 개수보다 $S$ 가 더 크다면 그 차이만큼의 lane 은 버리게 되는 것이므로.
• 두번째 방법에 대한 문제점를 그림으로 예시를 들면 이렇게 된다.

• 위 의 예시는 128bit register 에 $T=32$, $S=4$ 로 처리하는 것이었다.
• 만약에 $T=16$ 의 더 좁은 lane 을 사용하면 당연히 $S=8$ 이므로 8개의 값을 병렬로 처리하기 원할 것이다.
• 근데 문제는 저 $S=4$ 기준 layout 에서는 값들이 0-4-8-12-1-5-9-13… 순서로 배치되므로 4개씩이 아닌 8개씩 register 에 넣으면 cross-lane data dependency 가 발생하게 된다.
• 결국에는 기존 layout 그대로 4개씩 넣어야 하고, 따라서 나머지 4개의 lane 을 버리게 되어 8개로 늘어난 이점이 사라지게 된다.

2.4.2. Basic idea §

• 따라서 모든 가능한 $T$ 에 대응할 수 있게 layout 을 수정할 필요가 있었다.
• 일단 위 에서의 예시 문제, 즉, $S=4$ 에서 $S=8$ 로 늘려도 아무 문제가 없도록 layout 을 고쳐보자.
• 다음처럼 하면 된다.

• 좀 빙글빙글 도는 식으로 바뀌었다 그쵸?
  • 일단 맨 왼쪽을 보면 $S=4$ 에 대해서도 잘 대응이 된다는 것을 알 수 있고,
  • 두번째를 보면 신기하게도 $S=8$ 에 대해서도 대응이 되는 것을 알 수 있다.
• 즉, lane 이 늘어나도 cross-lane data dependency 가 발생하지 않게 dependency 가 있는 놈을 더 멀리 보내버리는 아이디어라고 할 수 있다.
  • 0번 다음에 1번은 lane 이 8개가 될 때를 대비하여 왼쪽으로 8 만큼 떨어진 곳에 배치되고,
  • 2번은 1번보다 오른쪽에 배치하되 lane 이 4개일 때를 위해 오른쪽으로 4만큼 떨어진 곳에 배치되는 형태이다.

2.4.3. Unified Transposed Layout §

• 그럼 $T\in \{8,16,32,64\}$ 에 대한 transposition layout, Unified Transposed Layout 은 어떻게 구성되어 있을까.
• 한 chunk 의 1024 개의 값은 가로 16, 세로 8 사이즈 (즉, 총 128 개) 의 Tile 단위로, 총 8개의 Tile 로 분배된다.
  • 위 그림에서 점선으로 구분된 것이 하나의 Tile 이고, 파란색이 Tile index 이다.
• 왜 저 16 과 8이라는 숫자가 나왔는지 알아보자.
  • 한개 이상 Tile 의 한 row 단위로 register 에 들어간다. 그럼 한 Tile 의 row “크기”는 lane 개수의 최소로 정하면 될 것이다.
    • 즉, lane 개수가 가장 적은 것을 때는 $S=16$ ($T=64$) 일 때이므로 row 의 “크기” 는 16이 된다.
    • 이렇게 정해 놓고 $T$ 에 따라 lane 개수가 늘어나면 여러 Tile 에 걸친 row 를 한번에 register 에 넣으면 될 것이다.
  • Lane 개수가 가장 클 때는 $S=128$ ($T=8$) 이다. 따라서 chunk 하나를 위해서 Tile 은 8개가 필요하다. (Tile index 0~7)
    • 8개의 Tile 에 대한 row 의 “크기” 가 128이기 때문에, 이 row 가 딱 register 에 들어가는 사이즈가 되기 때문
  • 따라서 하나의 Tile 에 대한 세로 사이즈는 $ChunkSize/(TileRowSize\times TileCount)=1024/(16\times 8)=8$ 가 되는 것이다.
• 그럼 이 layout 을 토대로, 어떤 순서로 Tile 들이 배치되는지 알아보자.

• 보면 위 에서 설명한 idea 대로 빙글빙글 돌고 있고, 차근차근 읽어보면 순서를 바꾸지 않고 모든 $T$ 에 대응할 수 있다는 것을 알 수 있다.
• 그럼 이 순서여야 하는 이유에 대해 생각해 보자.
• 일단 맨 오른쪽을 0으로 두고, 나머지를 변수로 둔다.

G | F | E | D | C | B | A | 0

• $T=8$ 일 때는 모든 Tile 이 (의 한 row 가) register 에 들어가기 때문에 순서 관련 힌트를 얻을 수 없다.
• $T=16$ 일 때는 절반을 나눠 Tile 4 개 단위로 처리된다.
  • 즉, 오른쪽의 4개 ({C, B, A, 0}) 가 base 가 되고, 왼쪽의 4개 ({G, F, E, D}) 가 다음 순번으로 처리된다는 것.
  • 따라서 오른쪽 4개의 순서에 각각 1을 더한게 왼쪽 4개의 순서가 될 것이다.

C+1 | B+1 | A+1 | 1 | C | B | A | 0

• $T=32$ 일 때는 {A, 0} 이 base 에 들어가고, 그 다음에는 {A+1, 1}, 그리고 {C, B}, 마지막으로 {C+1, B+1} 로 처리된다.
  • 따라서 B = 1 + 1 = 2 이고, C = (A + 1) + 1 = A + 2 가 된다.
  • 여기서 다른 경우의 수는 없다; {A+1, 1} 다음에 {C+1, B+1} 이 처리될 수는 없다는 것.
    • 왜냐면 만약 그렇다면 A=C, B=0 이 되는데, Tile 의 처리 순서가 같을 수는 없기 때문이다.

A+3 | 3 | A+1 | 1 | A+2 | 2 | A | 0

• 그럼 A 는 4라는 결론을 내릴 수 있다. 왜냐면 “순서” 이기 때문에 연속된 숫자여야 하는데, 연속성을 유지하기 위해서는 A 가 4가 되어야 하기 때문.
• 결과적으로 다음과 같은 순서가 나오게 된다.

7 | 3 | 5 | 1 | 6 | 2 | 4 | 0

2.4.4. FastLanes RLE §

• 일단 전통적인 RLE 는 다음과 같다:

• 즉,
  • 새로운 run 이 시작되면 “Run Values” vector 에 해당 value 를 append 하고,
  • “Run Lengths” vector 에는 몇번 반복되었는지를 append 하는 것.
  • 따라서 하나의 run 에 대한 value 와 length 의 각 vector 에서의 index 는 동일하게 유지된다.
• 이 전통적인 RLE 를 decoding 하는 데에는 2-level nested loop 이 필요하다.
  • 하나는 “Run Values”, “Run Lengths” 두 vector 를 순회하는 loop (위에서 말한대로 한 index 값은 동일한 run 에 대한 value 와 length 를 참조하므로 하나의 loop 만 있으면 된다.)
  • 나머지 하나는 length 만큼 value 를 찍어내는데 사용되는 loop 이다.
• 하지만 이러한 구현법은 run length 가 짧을 때 decoding 시에 문제가 많다.
  • 일단 scalar 버전에서는 run length 가 짧아 inner loop 이 금방금방 끝나므로 pipeline branch misprediction 이 많이 뜬다.
  • Vectorize RLE 에서는 SIMD reg 에다가 value 를 전부 채워서 한번에 STORE 하는 식으로 처리되는데, 이 SIMD reg 크기보다 run length 가 더 길어야 효과가 있다.
    • 물론 overlapping 한다고 치면 run 개수만큼의 STORE 로 충분하지만, run length 가 짧으면 그만큼 run 개수는 많다는 의미이므로 vectorize 의 큰 이점은 없다고 할 수 있다.
• 따라서 본 논문에서는 FastLanes-RLE 라는 것을 제시한다.
  • 근데 뒤에 보면 알겠지만 RLE 라고 말하기 좀 애매하긴 하다. Run 을 활용하기는 하지만 length 로 꼼지락대지는 않기 때문.

• 여기서의 기본 아이디어는 RLE 에서의 “Run Values” vector 를 DICT 처럼 사용하여 값을 전부 치환하고, 그것에 DELTA + Unified Transposed Layout 을 먹이는 것이다.
• 즉, 위의 그림을 보면 “Run Values” vector 에 따라 치환된 Index Vector 가 있고 이것에 DELTA 를 먹여 Delta Encoded Vector 를 구성하는 것을 알 수 있다.
• 이 방법이 효과적인 이유는
  • RLE 의 “Run Values” vector 는 run 이 시작될 때마다 append 되기 때문에 항상 증가하는 값으로 치환되기에 DELTA 를 먹이기 아주 용이하고
  • 심지어 1씩만 증가하기 때문에 DELTA 를 먹였을 때 0 아니면 1 이어서 1bit 로 BP 되어 미친 compression ratio 를 갖게 되고
  • 또한 DELTA 는 위 에서 말한 Unified Transposed Layout 를 이용해 아주 빠르게 vectorized decoding 이 가능하다.
• 즉, 이건 RLE + DICT + DELTA + UTL 을 전부 짬뽕한 것이라고 할 수 있다. 차이점이라면:
  • RLE 에서는 run 의 “Length” 를 활용하지만 여기서는 이건 사용하지 않는다는 것
  • DICT 는 non-duplicated dictionary 를 이용해 치환하지만 여기서는 “Run Values” vector 를 이용하므로 duplicate 가 가능하다는 것이다.
• 몇가지 디테일은:
  • “Run Values” vector 는 avg. run length 가 짧은 경우 (즉, 짧은 run 들이 많이 있는 경우) 에는 16bit index 를 사용하고, 그렇지 않은 경우에는 8bit index 를 사용한다.
  • Base value 는 8bit 를 차지 ⁶ 하는데, 이건 3bit BP 가 가능하다고 한다. 따라서 전체적으로 보면 value 하나 당 0.375 bit ⁷ 를 소모하는 격이라고 한다.
• 이 방법을 이용하면 avg. run length 가 12 이하일 때 훨씬 더 좋은 compression ratio 가 나온다고 한다.
  • 만약 이것보다 더 큰 경우라면 0-bit DELTA 라는 것을 이용한다고 한다.
  • 간단하게 말하면 run 이 매우 길다면 Delta Encoded Vector 가 대부분 0 이고 가끔씩 1 이 되기 때문에
  • 별도의 Delta Encoded Vector 를 저장하지 않고 decoding 할 때만 0으로 memset 한 다음
  • 이 1들을 exception handling 으로 처리하는 방법이다.
  • 이건 근데 본 논문에서는 다루고 있지 않고, 추후에 별도의 논문으로 공개된다고 한다.
• RLE 의 문제점 중에서는 Overwrite 문제도 있는데, 이에 대해서는 만약에 decoding 시에 index vector 를 원본 value vector 로 치환한다면 마찬가지로 발생하긴 한다.
  • 근데 index vector 상태로 둬도 query processing 에는 아무런 문제가 없다. 그냥 query processing 할 때 대상이 되는 놈만 index 값을 value 로 바꿔서 사용하면 되기 때문.
  • 이렇게 원본으로 바꾸지 않는 것은 DuckDB 같은 DBMS 에서 사용하는 방법이며, 반대의 개념을 Full (혹은 eager) decompression 이라고 한다고 한다.

Footnotes §

1. Lemire 의 SIMD-* 인코딩의 원리를 알아야 이 문장이 이해될듯 ↩

2. 솔직히 잘 이해가 안된다. 뭐 좀 예시라도 들어주며 설명해주면 좋겠는데 ↩

3. 일단 Figure 3 에 그려진 것은 10개가 맞긴 한데, 각 AND_RSHIFT 나 OR 각각이 하나의 instrunction 이라고 한다면 Listing 2 에 있는건 10개가 훨씬 넘는다. 뭐 논리적인 문제는 없지만 수치적으로 맞나는 잘 모르겠음 ↩

4. 이게 뭐고 ↩

5. 이게 뭔소리고 원본 문장: vectorized query executors typically have an optimization where simple arithmetic operators (that cannot raise errors) will ignore (identical) selection vectors on all parameters, if many tuples are still in play, executing the operation on all values, at much lower per-value cost thanks to full sequential access (and SIMD). ↩

6. Base storage 가 왜 필요하지? Base 는 첫 run 의 index 이니까 무조건 0 이어야 하는 것 아닌기? ↩

7. 왜 이 수치가 나왔는지 모르겠음 ↩