Кодировки колонок

Потоковая модель ORC

ORC хранит данные колонок как набор streams (потоков). Каждая колонка порождает от 1 до 5 потоков, в зависимости от типа данных. Это фундаментальное отличие от Parquet, где данные колонки живут в одной data page.

Каждый stream — последовательность байтов с конкретным назначением. Stripe Footer хранит stream directory: для каждого stream — column ID, stream kind и length.

RLEv1: базовая кодировка

RLEv1 — оригинальная кодировка ORC (Hive 0.11, формат v0). Два подрежима:

Run (повторение): header byte ≥ 0, значение = header + 3 повторений одного значения или дельты.

Literal (литералы): header byte < 0, значение = abs(header) литеральных значений.

RLEv2: четыре подкодировки

RLEv2 (Hive 0.12+, формат v1) — основная кодировка для integer-данных в ORC. Она включает четыре подкодировки, каждая оптимальна для своего паттерна данных. Encoder выбирает подкодировку автоматически для каждого run.

Первые два бита каждого заголовка определяют подкодировку:

• 00 — Short Repeat
• 01 — Direct
• 10 — Patched Base
• 11 — Delta

Short Repeat (00)

Самая простая подкодировка: одно значение, повторённое 3–10 раз.

Формат: [header: 1 byte] [value: 1-8 bytes]

• Биты 7–6: 00 (идентификатор подкодировки)
• Биты 5–3: ширина значения в байтах - 1 (0–7 → 1–8 байт)
• Биты 2–0: количество повторений - 3 (0–7 → 3–10)

Используется для: коротких серий одинаковых значений, часто встречающихся в enum-колонках, boolean-счётчиках, дефолтных значениях.

Direct (01)

Bit-packed значения с вычисленной фиксированной шириной. Encoder определяет максимальное значение в run, вычисляет минимальное количество бит для его представления и пакует все значения с этой шириной.

Формат: [header: 2 bytes] [values: bit-packed]

• Биты 15–14: 01
• Биты 13–9: encoded bit width (W)
• Биты 8–0: length - 1 (0–511 → 1–512 значений)

Patched Base (10)

Самая сложная подкодировка. Для данных, где большинство значений близки, но есть outliers (выбросы):

1. Вычисляется base value (минимум серии)
2. Все значения = value - base (shifted to positive)
3. Определяется reduced bit width — ширина для 90-го перцентиля
4. Outliers, не помещающиеся в reduced width, записываются как patches

Delta (11)

Для монотонных или quasi-монотонных последовательностей: timestamps, auto-increment IDs, sorted columns.

Кодирует second-order deltas: дельты между дельтами. Для строго монотонной последовательности (1, 2, 3, 4, …) все second-order deltas = 0, что даёт максимальную компрессию.

Данные: [10, 13, 16, 19, 22, 25]
Дельты (Δ): [3, 3, 3, 3, 3]
Дельты дельт: [0, 0, 0, 0] → все нули → минимальный bit width

Zigzag-кодирование

ORC использует zigzag-кодирование для signed integer, чтобы маленькие отрицательные числа не занимали максимальное количество байт в varint-представлении:

Формула: zigzag(n) = (n << 1) ^ (n >> 63) для int64.

Dictionary Encoding

Для строковых колонок с низкой кардинальностью ORC использует dictionary encoding:

1. DICTIONARY_DATA stream — отсортированный список уникальных строк
2. LENGTH stream — длина каждой строки в словаре
3. DATA stream — индексы в словарь (RLEv2-encoded)

Byte RLE и Boolean RLE

Byte RLE — простейшая кодировка для потоков PRESENT (NULL bitmap):

• Run: header byte ≥ 0 → value + 3 повторений одного байта
• Literal: header byte < 0 → abs(header) литеральных байтов

Boolean RLE — Byte RLE, где каждый байт содержит 8 бит (8 boolean значений). Биты идут от MSB к LSB.

Выбор кодировки: ORC vs Parquet

Ключевые выводы

1. ORC хранит данные как streams — каждая колонка порождает 1–5 потоков (PRESENT, DATA, LENGTH, DICTIONARY_DATA, SECONDARY)
2. RLEv2 — основная кодировка с 4 подкодировками: Short Repeat, Direct, Patched Base, Delta
3. Patched Base — уникальная подкодировка для данных с outliers, не имеет аналога в Parquet
4. Zigzag encoding превращает маленькие отрицательные числа в маленькие положительные для эффективного varint
5. Dictionary encoding в ORC сортирует словарь лексикографически (Parquet — в порядке появления)
6. Byte RLE кодирует NULL bitmap (PRESENT stream) — 8 boolean на байт