Madison Digital Garden

Search

SearchSearch

(논문) Dremel: Interactive Analysis of Web-Scale Datasets, VLDB 2010 (4. Nested Columnar Storage)

Jan 09, 2025, 8 min read

원본 논문

4.0 Overview

Arbitrary section ( 4.0)

  • 내용 정리를 위해 임의로 구분지은 section 입니당. 논문에는 이런 section 은 없음
  • Section 3 에서 소개한 이 data model 을 columnar format 으로 바꾸기 위한 방법들에 대해 본 section 에서 설명한다.
    • Section 4.1. 에서는 data model 의 structure 를 표현하는 방법에 대해 설명하고,
    • Section 4.2. 에서는 columnar data 를 encoding 하는 방법에 대해 설명하며,
    • Section 4.3. 에서는 이러한 columnar data 에서 다시 record 의 형태로 바꾸는 방법에 대해 설명한다.

4.1. Repetition and Definition Levels

  • 일단 이 data model 을 columnar format 으로 바꾸면 value 그 자체로는 structure 를 추론하기 힘들다.
  • 가령 Repeated Field 의 데이터들에 대해서는, 이놈이 같은 record 에서 여러번 등장한건지, 아니면 다른 record 에서 등장한 것인지 알 수 없다.
  • 또한 Optional Field 에 대해서도 마찬가지로, 어떤 record 는 이 field 를 가지고 있고 어떤 record 는 그렇지 않은지 value 만 보고서는 알 수가 없다.
  • 따라서 이것에 대해 명시하는 Repetition Level 와 Definition Level 을 정의하여 이 정보로 columnar data 를 다시 structure 로 복원할 수 있게 한다.
  • 이 개념들을 이해하기 위해서는, 예시를 보면서 생각하는 것이 제일 좋다. 그래서 Section 3 에서 나온 예시와 이에 대한 Repetition Level, Definition Level 을 보여주는 다음의 예시를 보면서 이놈들에 대해 알아보자.
  • 일단 Section 3 에서 나온 record 예시는 다음과 같다.
    • 다만, 여기서 Repeated Field 들은 편의를 위해 [] 를 통해 등장 순서를 명시하였다.
DocID: 10
Links:
	Forward[0]: 20
	Forward[1]: 20
	Forward[2]: 20
Name[0]:
	Language[0]:
		Code: 'en-us'
		Country: 'us'
	Language[1]:
		Code: 'en'
	Url: 'http://A'
Name[1]:
	Url: 'http://B'
Name[2]:
	Language[0]:
		Code: 'en-us'
		Country: 'us'
DocID: 20
Links:
	Backward[0]: 10
	Backward[1]: 10
	Forward[0]: 80
Name[0]:
	Url: 'http://C'
  • 그리고 이때에 대한 Repetition Level 와 Definition Level 이다.

4.1.1. Repetition Level

  • 얘는 “어떤 repeated field 가 반복되었는지” 에 대한 level 을 의미한다.
  • 이거에 대해 이해하기 위해, Name.Language.Code field 를 살펴보자.
    • 일단 record 의 첫 value 에 대한 Repetition Level 은 0이다. 따라서 'en-us' 에 대해서는 해당 값이 0이 된다.
    • 그리고 그 다음 value 인 'en' 은 이전의 'en-un' 와 비교해 봤을 때, 동일한 Name[0] field 에 대해 Language field 가 반복되어 각각 Language[1] 와 Language[0] 에 속하는 값들이다.
      • 따라서 이것은 level 1 인 Name 에 대해서는 동일한 field (Name[0]) 에 속하지만, level 2 인 Language 에 대해서는 다른 field (Language[0], Langauge[1]) 에 속하는 것이라고 할 수 있다.
      • 그래서 이때의 Repetition Level 의 값이 2가 되는 것이다.
    • 다음 값인 NULL 에 대해 생각해 보자. 일단 Name[1].Language[0] field 는 보다시피 존재하지 않기 때문에 value 는 NULL 이다.
      • 이때 이 value 는 이전의 'en' 와 비교해 보면, Name field 가 반복되어 각각 Name[1] 와 Name[0] 에 속하게 된다는 것을 알 수 있다.
      • 따라서 반복되는 field 의 level 이 1이기 때문에 이 값의 Repetition Level 은 1 이 된다.
    • 다음 값인 'en-gb' 은 이전 값인 NULL 와 비교했을 때 다른 Name field 에 속하므로 (각각 Name[2] 와 Name[1]) 마찬가지로 Name field 의 level 인 1 이 이 value 의 Repetition Level 이 된다.
    • 마지막으로 다음의 NULL 은 이전 값인 'en-gb' 와 다른 record (각각 와 ) 에 속하므로, 첫 value 이기 때문에 0 이다.

4.1.2. Definition Level

  • 얘는 “어떤 level 에 해당 값이 명시되었는지” 에 대한 level 을 의미한다.
  • 이놈에 대해 이해하기 위해, Name.Language.Country field 를 살펴보자.
    • 일단 첫번째 값인 'us' 는 Name[0].Language[0].Country path 에 있는 값이다. 따라서 이놈의 level 은 3이다.
    • 그리고 두번째 값은 NULL 은 Name[0].Language[1].Country? 의 값이 존재하지 않기 때문에 NULL 값을 가지게 된 것이다. 이때, 해당 path 에서 존재하는 마지막 level 은 Name[0].Language[1] 이기 때문에 Definition Level 값이 2가 되는 것이다.
    • 세번째 값인 NULL 은 위와 마찬가지로 Name[1].Language?.Country? 의 값이 존재하지 않기 때문에 해당 값을 가지게 된 것이다. 이때 path 에서 존재하는 마지막 level 은 Name[1] 이기 때문에 Definition Level 이 1이 되는 것이다.
    • 네번째 값인 'gb' 는 Name[2].Language[0].Country 값이기 때문에 level 은 3이 된다.
    • 마지막으로 다섯번째 값인 NULL 은 의 Name[0].Language?.Country? 가 존재하지 않기 때문인 것이고, 따라서 path 에서 존재하는 마지막 level 이 Name[0] 이기 때문에 Definition Level 이 1 이 되는 것이다.
  • 단순히 IS_NULL 와 같은 boolean value 가 아닌 integer value 를 사용함으로써 structure 에 대한 correctness 을 보장한다고 한다. 이에 대해서는 Section 4.3. 에서 알아보자.

4.1.3. Encoding

  • 얘네는 Block 단위로 생성되어, 이 두 level data 뒤에 value data 가 뒤따르는 형태를 가진다.
  • NULL 은 definition level 을 통해 추론할 수 있기 때문에 value data 에는 포함되지 않는다.
    • Column 의 level 보다 작은 definition level 값은 모두 NULL 로 간주된다.
  • 이 level 들은 필요한 경우에만 존재한다.
    • 만약 어떤 column 이 not nullable 하다면, definition level 은 Block 에 포함되지 않는다.
    • 마찬가지로, definition level 이 0 이라면, repetition level 또한 0 일 것이기 때문에 이 경우에는 repetition level 은 Block 에 포함되지 않는다.
    • 따라서 위의 예시에서 DocId 는 not nullable 하고 repetition level 이 항상 0이기 때문에 definition, repetition level 모두 Block 에 포함되지 않는다.
  • 또한 level 은 bit packing 된다.
    • 즉, 만약 maximum definition level 이 3이라면, 2bit 만 사용되게 된다.

4.2. Splitting Records into Columns

#draft 나중에 정리할 예정입니다.

4.3. Record Assembly

#draft 나중에 정리할 예정입니다.

Graph View

Backlinks