Целочисленные кодировки: FOR, Delta, Bit-Packing
В Модуле 01 мы видели delta encoding и bit-packing как отдельные приёмы. В Модуле 02 — как Parquet реализует DELTA_BINARY_PACKED. В Модуле 03 — как ORC RLEv2 Delta использует second-order дельты.
Теперь посмотрим глубже: три фундаментальных техники кодирования целых чисел — Frame-of-Reference (FOR), Delta и Bit-Packing — и как каждый формат комбинирует их в свои собственные конвейеры. Ключевое отличие от Модуля 01: мы разберём bit-level layout и увидим, почему порядок упаковки бит влияет на скорость декодирования в 10 раз.
Frame-of-Reference (FOR): base + offset
FOR — самая простая из трёх техник, но основа для всех остальных. Идея: если все значения в блоке лежат в узком диапазоне, вычтем base (минимум) и будем хранить только offsets:
Без FOR (raw int64)
С FOR
FOR эффективен когда range ≪ max_value. Для цен 9990–10050: range = 60, max_value = 10050. Нужно 7 бит вместо 14 (для raw) или 64 (для int64). Экономия зависит от соотношения ceil(log₂(range)) / raw_bits.
Кто использует FOR
| Формат | Где FOR | Особенности |
|---|---|---|
| DuckDB | Основная кодировка для integer | FOR + bit-packing, SIMD-оптимизированное декодирование |
| BtrBlocks | Один из 8 кандидатов cascade | FOR после sampling, может каскадироваться с другими |
| FastLanes | FOR как часть expression encoding | FOR + transposed bit-packing для автовекторизации |
| ORC | Patched Base (RLEv2) | FOR + patches для outliers — уникальная комбинация |
| Parquet | прямого FOR | Использует delta вместо FOR — другая философия |
Parquet не имеет отдельного FOR-кодирования. Вместо этого DELTA_BINARY_PACKED фактически включает FOR-подобное поведение: min_delta вычитается из всех дельт в блоке — это FOR, применённый к дельтам, а не к значениям.
Delta-варианты: три уровня глубины
Delta encoding хранит разности вместо абсолютных значений. Но есть три варианта, отличающихся глубиной:
Simple Delta (Δ)
Block Delta + FOR
Delta-of-Delta (ΔΔ)
Кросс-форматное сравнение integer pipelines
Каждый формат строит свой конвейер из FOR, Delta и Bit-Packing. Вот как они обрабатывают одни и те же данные — отсортированные timestamps с шагом ~60 секунд:
Parquet DELTA_BINARY_PACKED
Δ = Xᵢ - Xᵢ₋₁ → [62, 59, 62, 57, …]
Шаг 1: вычислить дельты. Δ = [62, 59, 62, 57, ...]. Диапазон дельт: 55–65.Блоки по 128: min_Δ=55, offsets=[7,4,7,2,…]
Шаг 2: разбить на блоки по 128 значений. В каждом блоке: min_delta ≈ 55, вычесть из всех. Остатки: 0–10.Bit-pack: 4 бит/offset → ~4 бит/значение
Шаг 3: bit-pack offsets. Range 0–10 → 4 бита. 128 offsets × 4 бит = 64 байта на блок. + header: 1 base + 1 min_delta + 4 bit-widths.ORC RLEv2 Delta
base=1704067200, base_Δ=62
Шаг 1: base value = первое значение. Base delta = первая дельта. ΔΔᵢ = Δᵢ - Δᵢ₋₁.ΔΔ = [-3, +3, -5, …] → zigzag
Шаг 2: вычислить дельты дельт (second-order). ΔΔ = [-3, +3, -5, ...]. Zigzag: [5, 6, 9, ...].Bit-pack ΔΔ: 4 бит/значение
Шаг 3: bit-pack zigzag-encoded ΔΔ. Range ≈ ±5 → zigzag 0–10 → 4 бит. Аналогичная эффективность, но decode на один шаг дороже.DuckDB FOR + BitPacking
Delta → Δ = [62, 59, 62, 57, …]
Шаг 1: DuckDB сначала применяет delta (если данные монотонные). Δ = [62, 59, 62, 57, ...].FOR: base=55, offsets=[7, 4, 7, 2, …]
Шаг 2: FOR на дельтах. base = min(Δ) = 55. Offsets = [7, 4, 7, 2, ...]. Range 0–10.SIMD bit-pack: 4 бит/значение, vectorized decode
Шаг 3: SIMD-optimized bit-packing. DuckDB выравнивает bit-width до степеней 2 (4 бит). Decode: одна SIMD-операция распаковывает 64 значения.FastLanes FOR + Transposed BP
FOR на блоке 1024 значений
Шаг 1: FOR — вычесть base из блока 1024 значений. Дельты не нужны, если FOR достаточен.Transposed Layout (1024-bit virtual SIMD)
Шаг 2: Transposed Layout — переупорядочить значения для SIMD параллелизма. Индекс '04261537' чередует значения из разных SIMD-лейнов.Data-parallel bit-pack: > 100B int/sec decode
Шаг 3: Data-parallel bit-packing — каждый SIMD-лейн работает с непрерывным блоком бит. Автовекторизуется на любом CPU (SSE/AVX/NEON/WASM). >100B int/sec decode.Все четыре конвейера достигают ~4 бит/значение на этих данных. Но скорость декодирования различается на порядок — из-за bit-packing layout.
Bit-Packing: scalar vs transposed layout
Bit-packing — финальный шаг в каждом конвейере. Он определяет, как маленькие числа (offsets, дельты) упаковываются в байты. И здесь layout — порядок упаковки бит — критически влияет на производительность:
Scalar layout (Parquet, ORC)
Transposed layout (FastLanes)
FastLanes transposed layout — главная инновация для скорости декодирования. Обычный (scalar) bit-packing достигает ~5–15 миллиардов int/sec на современном CPU. FastLanes transposed layout — >100 миллиардов int/sec на scalar коде, и ~140 миллиардов с AVX-512. Разница — в автовекторизации: компилятор видит простые побитовые операции над массивами и генерирует SIMD-код автоматически.
Patched Base: FOR с обработкой outliers
ORC предлагает уникальную комбинацию — Patched Base (RLEv2 подкодировка 10). Это FOR, который обрабатывает outliers отдельно, вместо того чтобы расширять bit-width для всех значений:
base=100, reduced_width=3 бит
Шаг 1: вычислить base = min(values) = 100. Вычесть: [0, 2, 1, 3, 999899, 0, 4, 2]. Определить 90-й перцентиль bit-width: 3 бита (для 0–4).Основной: [0,2,1,3, 0*,0,4,2] (3 бит)
Шаг 2: значения, не помещающиеся в reduced_width (999899 > 7), помечаются как patches. На их месте в основном массиве — 0 (placeholder). Patch: (position=4, value=999899).Patches: [(pos=4, val=999899)]
Шаг 3: patch list хранит позиции и полные значения outliers отдельно. Bit-width patches — шире (20 бит), но их мало (1 из 8). Общий размер: 8×3 + 1×20 = 44 бит vs 8×20 = 160 бит.Patched Base — уникальная подкодировка ORC, не имеющая аналога в Parquet. Она особенно эффективна для данных с редкими выбросами: sensor data с аномалиями, financial data с extreme values, log data с occasional spikes.
Zigzag: кодирование знаковых чисел
Delta encoding производит знаковые числа (дельты могут быть отрицательными). Стандартное two’s complement представление неэффективно для varint/bit-packing: -1 в int64 = 0xFFFFFFFFFFFFFFFF = 64 бита.
Zigzag-кодирование решает это, отображая маленькие signed числа на маленькие unsigned:
Сводная таблица: кто что использует
Ключевые выводы
- FOR, Delta и Bit-Packing — три фундаментальных примитива, которые комбинируются в разном порядке: Parquet = Delta → FOR → scalar BP, ORC = ΔΔ → zigzag → scalar BP, DuckDB = Delta → FOR → SIMD BP, FastLanes = FOR → transposed BP.
- Bit-packing layout определяет скорость decode. Scalar (Parquet/ORC): ~5–10B int/sec. Transposed (FastLanes): >100B int/sec. Разница 10x — из-за автовекторизации.
- Patched Base (ORC) — единственный outlier-aware примитив среди файловых форматов. Один outlier не разрушает компрессию всего блока.
- Zigzag-кодирование обязательно для delta с signed дельтами: превращает
-1из 64-бит числа в 1-бит число. Используется в ORC, Parquet, DuckDB, Protocol Buffers. - Delta-of-delta (ORC) vs Delta + FOR (Parquet) — два подхода к одной задаче. ΔΔ лучше для строго-регулярных данных (timestamps с постоянным шагом). Delta + FOR — для данных с переменным, но ограниченным диапазоном дельт.
- FastLanes Unified Transposed Layout — главная инновация в скорости: переупорядочивание бит позволяет компилятору автоматически генерировать SIMD-код без платформо-специфичных intrinsics.