BigQuery에서 Nested Data의 처리: Dremel 논문으로 이해하기①🕵️‍♀️

들어가며

 빅쿼리로 수집되는 서비스의 데이터를 보면 <ARRAY<STRUCT (...)>> 와 같은 데이터 타입을 자주 볼 수 있습니다. 복잡한 데이터 구조를 효율적으로 저장하고 처리하기 위해 이러한 타입이 사용되는데요, 지난주에도 평소와 같이 데이터를 조회하다가 문득 이런 생각이 들었습니다.

컬럼 기반 스토리지에서는 중첩된 데이터를 어떻게 처리할까?

 

컬럼 기반 스토리지는 각 컬럼을 따로 저장해서 압축률을 높이고 조회 성능을 최적화하는데요, STRUCT나 ARRAY와 같이 중첩되고 반복되는 데이터는 단순한 구조가 아니어서 궁금증이 생겼습니다. 이를 이해하기 위해 BigQuery의 기반이 되는 Dremel이 어떻게 Nested Data를 다루는지 알아보았습니다.

 

Dremel의 등장 : Nested Data를 다루는 방법

 Dremel은 구글이 2010년 발표한 논문에서 소개된 기술로, 대규모의 데이터를 분석할 수 있도록 설계된 확장 가능한 대화형 쿼리 시스템입니다[1]. 당시 구글에서는 웹 데이터와 같은 다양한 데이터를 처리하기 위해 컬럼 기반 데이터 모델에서 더 나아가 중첩된 데이터를 처리할 수 있어야만 했습니다. 

 

 

 그림 1을 보면 중첩 데이터를 컬럼 기반으로 표현했을 때 필드의 값이 연속적으로 저장됩니다(오른쪽 트리 형태). 이 아이디어를 사용하면 r1 레코드의 A.B.C 컬럼을 조회할 때 A.B.D나 A.E를 읽지 않고도 원하는 데이터만을 가져올 수 있게 됩니다. 이를 구현하기 위해 나온 것이  Repetition Level(이하 반복 레벨)과 Definition Level(이하 정의 레벨)입니다.

 

반복 레벨과 정의 레벨

 Nested Data를 효율적으로 저장하고 읽기 위해서는 (1) 값이 어떤 레코드에서 반복되고 있는지와 (2) NULL값이 있는지 여부를 구분할 수 있어야합니다. Dremel에서는 반복 레벨과 정의 레벨이라는 값을 사용해 이를 구분합니다. 논문의 Document 라는 예시 데이터를 통해 이를 이해해 보겠습니다.

 

✅ 반복 레벨 (Repetition Level)

 중첩된 필드 내에서 값이 반복되는지 여부를 나타냅니다. 0은 해당 필드에서 반복이 없는 첫 번째 값을 의미하며, 이후 중첩된 필드의 단계에 따라 반복 레벨이 결정됩니다.

• r1의 Name.Language.Code 반복 레벨을 예로 들면
  • Code: 'en-us'는 첫번째 Name.Language.Code 값입니다. 반복 레벨은 0입니다.     
  • Code: 'en'은 Name.Language 필드가 반복된 Code값입니다. 반복 레벨은 2입니다.
  • Code: 'en-gb'는 Name 필드가 반복된 Code값입니다. 반복 레벨은 1입니다.

 

✅  정의 레벨 (Definition Level)

 중첩된 필드 내에서 값이 실제로 존재하는지 여부를 나타냅니다. 해당 필드가 실제로 존재하는지와 그 상위 필드가 정의되었는지에 따라 정의 레벨이 결정됩니다.  

• r1의 Links.Backward 정의 레벨을 예로 들면
  • Links.Backward 필드가 존재하지 않지만 Links 필드는 정의되어 있습니다. 정의 레벨은 1입니다.
• r2의 Links.Backward 정의 레벨을 예로 들면
  • Links 필드가 정의되어 있고 Links.Backward 값이 존재합니다. 정의 레벨은 2입니다.

 

📌 개인적으로 반복 레벨 중 Code: 'en'의 레벨이 2인 부분이 굉장히 헷갈렸습니다. Name 내 Language 필드가 한 번 반복되었는데 왜 2지 라는 생각이 들었는데요, 반복 레벨을 볼 땐 반복된 필드가 어떤 단계에 있는지를 생각하면 됩니다. 'en'의 경우 Name.Language 필드의 반복이기 때문에 2가 됩니다. 

 

r1과 r2 값에 대한 반복 레벨과 정의 레벨

 

✅  인코딩 (Encoding)

• 이후 각 필드는 블록의 집합으로 저장되며 반복 레벨(r), 정의 레벨(d), 압축된 필드 값을 포함합니다.
• NULL값은 저장되지 않습니다. 정의 레벨이 필드 경로의 반복 및 선택 필드 개수보다 작으면 NULL이기 때문입니다.
• 정의 레벨과 반복 레벨은 필요한 경우에만 저장됩니다.
  • 예) 위 DocId에서 정의 레벨이 0인 것은 반복 레벨이 0인 것을 의미합니다. 따라서 반복 레벨은 생략할 수 있습니다.

 

BigQuery의 Nested Field 활용

 BigQuery에서는 STRUCT와 ARRAY타입을 통해 중첩된 데이터를 다룰 수 있습니다 [2]. 이는 앞서 설명한 Dremel 기술을 기반으로 한 방식으로 대규모 데이터 처리에서 성능 최적화를 가능하게 합니다. 또한 데이터를 비정규화하여 테이블 간 조인을 줄이고, 복잡한 데이터 모델을 단순화할 수 있습니다.

 

마치며

 이번 글에서는 Nested Data가 BigQuery에서 어떻게 저장될 수 있는지를 Dremel을 통해 살펴보았습니다. Dremel 논문을 읽다보니 쿼리 실행 시 Nested Data가어떤 방식으로 최적화되어 실행되는지에 대해서도 정리해 보면 좋을 것 같습니다. 그럼 다음 글로 돌아오겠습니다. 읽어주셔서 감사합니다☘️

 

 

---

참고 자료

 

[1] Dremel 관련 논문

Dremel: Interactive Analysis of Web-Scale Datasets

 

[2] BigQuery 중첩 및 반복 필드 관련 공식 문서

중첩 및 반복 필드 사용  |  BigQuery  |  Google Cloud