Encoding/Compression Types (인코딩/압축 종류)

00 개요

• 회사에서 코드분석 할 때 sql 파일 안 쿼리문에서 encoding을 COMMONDELTA_COMP이랑 RLE를 많이 사용하는데 이것들이 뭔지 알기 위해 정리하고자 함

01 Encoding Types

• Vertica는 여러가지 encoding 및 compression 종류를 제공함

종류	설명
AUTO (기본값)	- ideal for sorted, many-valued columns such as Primary Keys - also suitable for general purpose applications for which no other encoding or compression scheme is applicable - CPU requirements for this type are relatively small - in the worst case, data might expand by 8% for LZO and 20% for integer data
BLOCK_DICT	- for each block of storage, Vertica compiles distinct column values into a dictionary and then stores the dict and a list of indexes to represent the data block - ideal for few-valued, unsorted columns where saving space is more important than encoding speed - also suitable for data (e.g., stock prices) that are typically few-valued w/n a localized area after the data is sorted (e.g., by stock symbol and timestamp)  - CHAR and VARCHAR columns that contain 0x00 or 0xFF characters should not be encoded w/ BLOCK_DICT  - BINARY/VARBINARY columns do not support BLOCK_DICT encoding - BLOCK_DICT encoding requires significatly higher CPU usage than default encoding schemes - MAX data expansion is 8%
BLOCKDICT_COMP	- similar to BLOCK_DICT except dictionary indexes are entropy coded - requires significantly more CPU time to encode and decode and has a poorer worst-case performance - if the distribution of values is extremely skewed, using BLOCK_DICT_COMP encoding can lead to space savings
BZIP_COMP	- uses the bzip2 compression algorithm on the block contents - this algorithm results in higher compression than the automatic LZO and gzip encoding; - requires more CPU time to compress - this algorithm is best used on large string columns such as VARCHAR, VARBINARY, CHAR, and BINARY - ideal when you are willing to trade slower load speeds for higher data compression
COMMONDELTA_COMP	- builds a dictionary of all deltas in the block and then stores indexes into the delta dictionary using entropy coding - 즉, 1) 데이터 블록 내에서 델타를 계산. 2) 델타 값들로 사전을 만들고, 각 델타 값을 사전의 인덱스로 변환. 3) 변환된 인덱스들에 대해 엔트로피 코딩을 적용하여 데이터 압축. - 이렇게 하면 데이터의 크기를 줄이고 저장 또는 전송 효율을 높일 수 있음. - ideal for sorted FLOAT and INTEGER-based (DATE/TIME/TIMESTAMP/INTERVAL) data columns with predictable sequences and only occasional sequence breaks (e.g., timestamps recorded at periodic intervals or primary keys) - 예) the following sequence compresses well: 300, 600, 900, 1200, 1500, 600, 1200, 1800, 2400 - 예) the following sequence does not compress well: 1, 3, 6, 10, 15, 21, 28, 36, 45, 55 - if delta distribution is excellent, columns can be stored in less than one bit per row - very CPU intensive → if you use this scheme on data with arbitrary deltas, it can cause significant data expansion
DELTARANGE_COMP	- primarily used for floating-point data - stores each value as a delta from the previous one - ideal for many-valued FLOAT columns that are sorted or confined to a range - Do not use this scheme for unsorted columns that contain NULL values, as the storage cost for representing a NULL value is high - has a high cost for both compression and decompression - To determine if DELTARANGE_COMP is suitable for a particular set of data, compare it to other schemes. Be sure to use the same sort order as the projection, and select sample data that will be stored consecutively in the database.
DELTAVAL	- for INTEGER and DATE/TIME/TIMESTAMP/INTERVAL columns, data is recorded as a difference from the smallest value in the data block. This encoding has no effect on other data types. - best used for many-valued, unsorted integer or integer-based columns - CPU requirements for this encoding type are minimal, and data never expands
GCDDELTA	- for INTEGER and DATE/TIME/TIMESTAMP/INTERVAL columns, and NUMERIC columns with 18 or fewer digits, data is recorded as the difference from the smallest value in the data block divided by the greatest common divisor (GCD) of all entries in the block. This encoding has no effect on other data types. - best used for many-valued, unsorted, integer columns or integer-based columns, when the values are a multiple of a common factor - 예) timestamps are stored internally in microseconds, so data that is only precise to the millisecond are all multiples of 1000 - CPU requirements for decoding GCDDELTA encoding are minimal, and the data never expands - GCDDELTA may take more encoding time than DELTAVAL
GZIP_COMP	- uses the gzip compression algorithm - this algorithm results in better compression than the automatic LZO compression, but lower compression than BZIP_COMP - requires more CPU time to compress than LZO but less CPU time than BZIP_COMP - best used on large string columns such as VARCHAR, VARBINARY, CHAR, and BINARY - use when you want a better compression than LZO, but at less CPU time than bzip2
RLE	- RLE (run length encoding) - replaces sequences (runs) of identical values w/ a single pair that contains the value and number of occurrences - best used for low cardinality columns that are present in the ORDER BY clause of a projection - the Vertica execution egine processes RLE encoding run-by-run and the Vertica optimizer gives it preference - use it only when run length is large, such as when low-cardinality columns are sorted - storage for RLE and AUTO encoding of CHAR/VARCHAR and BINARY/VARBINARY is always the same

02 용어 정리

• Delta: 데이터 간의 차이
  • 예) 연속된 숫자 배열이 있다면 각 숫자 간의 차이를 delta라 함
  • 예) [10, 12, 15, 18]라는 배열이 있다면, 델타는 [2, 3, 3]
• Delta Encoding: 원래 데이터 대신 데이터 간의 차이를 저장하는 방법, 이 방법은 데이터가 큰 값이 아닌 작은 값의 차이로 이루어져 있을 때 효과적
• Dictionary: 데이터 내에서 반복되는 패턴을 식별하고 이 패턴을 고유한 index(또는 code)로 변환 후, 원래 데이터를 이 index들로 대체하는 방법
• Dictionary Coding: 반복되는 데이터를 dictionary로 만들어 해당 데이터 대신 사전의 index를 저장함으로써 데이터를 압축하는 방법
• Entropy Encoding: 데이터 내에서 더 자주 나타나는 패턴에는 더 짧은 코드, 덜 자주 나타나는 패턴에는 더 긴 코드를 부여하여 데이터를 압축하는 방법
  • 예) Huffman Coding, Arithmetic Coding

03 개념 정리

COMMONDELTA

• 1. Builds a dictionary of all deltas in the block 
  • 블록: 데이터를 일정한 크기로 나눈 단위. 여기서는 데이터의 한 부분(블록)을 처리한다고 가정함.
  • 모든 델타의 사전을 구축. 즉, 블록 내의 모든 델타 값을 모아서 각각의 델타에 고유한 인덱스를 부여.
  • 예) 데이터 블록이 [100, 105, 110, 112]라면 델타는 [5, 5, 2]가 됨. 이 델타 값들 [5, 5, 2]에 대해 사전을 만들면 {5: 0, 2: 1}과 같은 형태가 될 수 있음. 
• 2. Stores indexes into the delta dictionary using entropy coding 
  • 인덱스를 저장. 사전을 통해 델타 값들이 인덱스로 변환되었으므로 이제 원래의 델타 대신 인덱스를 저장.
  • 예) 위의 사전으로 델타 [5, 5, 2]는 인덱스 [0, 0, 1]로 변환됨. 엔트로피 코딩을 사용함. 변환된 인덱스 [0, 0, 1]에 대해 엔트로피 코딩을 적용하여 더 효율적으로 압축. 이 과정에서는 자주 나타나는 패턴(예: 0)을 더 짧은 비트 길이로, 덜 나타나는 패턴(예: 1)을 더 긴 비트 길이로 인코딩함.
• 요약
  • 데이터 블록 내에서 델타를 계산.
  • 델타 값들로 사전을 만들고, 각 델타 값을 사전의 인덱스로 변환.
  • 변환된 인덱스들에 대해 엔트로피 코딩을 적용하여 데이터를 압축.
• 효과
  • 이렇게 하면 데이터의 크기 감소 및 저장/전송 효율 증가