Теория информации и кодирование
В Модуле 01 мы рассмотрели четыре базовых кодировки — dictionary, RLE, delta, bit-packing — и увидели, как они комбинируются. Но почему они работают? Почему словарь для строки department даёт 44x сжатие, а для UUID — ничего? Почему delta на timestamps сжимает до почти 0 бит, а на случайных числах бесполезен?
Ответ — в теории информации. Она задаёт точный математический предел: насколько данные можно сжать, не теряя информации. Кодировки работают, потому что колоночные данные содержат мало информации относительно их размера — и теория объясняет, сколько именно и почему.
Энтропия Шеннона: минимум бит на значение
Клод Шеннон (1948) определил энтропию — среднее количество бит, необходимое для кодирования одного значения из источника:
H(X) = -Σ p(x) · log₂(p(x))Ключевое свойство: H(X) — абсолютный нижний предел. Никакое кодирование без потерь (lossless) не может в среднем использовать меньше, чем H(X) бит на значение. Это доказанная теорема, а не эмпирическое наблюдение.
Энтропия на реальных колонках
Посмотрим, как энтропия выглядит для типичных колонок аналитической базы данных:
Два наблюдения из этого спектра:
- Большинство аналитических колонок имеют низкую энтропию — status, country, department, boolean-флаги — далеко от теоретического максимума.
- Энтропия зависит от модели данных — для timestamps прямая энтропия высока (64 бита), но delta-энтропия (разность соседних значений) — всего 3–4 бит. Кодировка, которая использует правильную модель, приближается к пределу.
Почему колоночные данные так хорошо сжимаются
Колоночное хранение создаёт три свойства, которые радикально снижают энтропию:
Гомогенность типов
Все значения в колонке имеют один тип (INT64, STRING, FLOAT). Это исключает overhead смешанных типов и позволяет type-specific кодирование: delta для чисел, dictionary для строк.Локальность значений
Соседние значения в колонке — из одного поля разных строк. Часто похожи: даты идут подряд, статусы повторяются, ID растут монотонно.Кластеризация при записи
Сортировка данных при записи (partition columns, sort keys) группирует одинаковые значения. Кластеризация превращает случайные данные в длинные серии.Именно поэтому row-ориентированные форматы (JSON, CSV) сжимаются хуже: значения разных типов чередуются, разрушая все три свойства. В строке {"id": 42, "name": "Alice", "active": true} — int, string и bool перемешаны. Колоночное хранение отделяет поток id (низкая delta-энтропия) от потока name (dictionary-friendly) от потока active (1-бит RLE).
Условная энтропия и модель кодирования
Ключевая идея: кодировка определяет модель данных, а модель определяет условную энтропию.
Рассмотрим колонку timestamps: [1704067200, 1704067260, 1704067320, ...]
Каждая кодировка — это неявная модель данных:
- PLAIN — «значения независимы» (никакой модели)
- Dictionary — «значения из малого алфавита» (модель: p(x) для каждого уникального значения)
- Delta — «соседние значения похожи» (модель: Xᵢ = Xᵢ₋₁ + Δ)
- RLE — «одинаковые значения идут подряд» (модель: серии)
- FOR — «все значения в узком диапазоне» (модель: base + offset)
Кодировка, чья модель лучше соответствует данным, достигает более низкой условной энтропии — и, следовательно, лучшего сжатия.
Кодирование vs компрессия: два слоя сжатия
Почему нужны оба — и кодирование, и компрессия? Потому что они работают с разными видами избыточности:
Raw данные: 1M строк × 11 байт = 11 MB
Колонка department: 1M значений из 4 уникальных. 64-бит указатели. Размер: ~11 MB. Энтропия: 1.75 бит/значение (при равных вероятностях 4 значений).Закодировано: 250 KB (44x сжатие)
Dictionary (4 значения = 2 бита/индекс) + bit-packing: 1M × 2 бит = 250 KB + ~40 байт словарь. Достигнуто ~2 бит/значение — близко к энтропии H = 1.75 бит.Сжато: ~160 KB (1.6x дополнительно)
Zstd находит оставшиеся паттерны в потоке bit-packed индексов: неравномерность p(0)=0.5, p(1)=0.3, p(2)=0.15, p(3)=0.05. Дополнительное 1.5x сжатие.Принцип: кодирование эксплуатирует знание о типе данных (dictionary для строк, delta для чисел, RLE для серий). Компрессия обрабатывает остаток — паттерны в потоке байтов, которые кодировка не устранила. Вместе они дают мультипликативный эффект.
Предсказание степени сжатия
Зная энтропию колонки, можно оценить достижимое сжатие:
Практическое правило: если H(model) ≪ raw_bits — кодирование даст значительный выигрыш. Если энтропия близка к raw_bits (UUID, random float) — кодирование бесполезно, и даже компрессия поможет минимально.
Эмпирическая энтропия: как измерить
Теоретическая энтропия требует знания распределения p(x). На практике используют эмпирическую энтропию — оценку по реальным данным:
Шаг 1: Взять N значений колонки
Берём N значений колонки: все или репрезентативную выборку. Для колонки в миллиард строк — первые 10,000–100,000 достаточно.Шаг 2: Посчитать частоту каждого уникального значения
Для каждого уникального значения xᵢ считаем количество вхождений count(xᵢ). Оценка вероятности: p̂(xᵢ) = count(xᵢ) / N.Шаг 3: Вычислить H = -Σ p̂(x) · log₂(p̂(x))
H(X) = -Σ p̂(xᵢ) · log₂(p̂(xᵢ)). Сумма по всем уникальным значениям. Результат — биты на значение.Шаг 4: Сравнить H для разных моделей (raw, delta, dictionary)
Для delta-модели: вычислить дельты Δᵢ = xᵢ - xᵢ₋₁, затем энтропию дельт H(Δ). Для FOR: вычислить offsets = xᵢ - min(x), затем H(offsets). Выбрать модель с наименьшей H.Именно этот алгоритм (в упрощённом виде) используют writers форматов. Parquet writer пробует dictionary для каждой колонки и переключается на PLAIN, если словарь превышает порог. DuckDB анализирует первые значения колонки, чтобы выбрать между Dictionary, RLE, BitPacking, FOR и Constant. BtrBlocks сэмплирует данные и перебирает 8 кодировок, выбирая каскад с наименьшим размером.
Пределы: когда кодирование бесполезно
Теория информации говорит чётко: нельзя сжать без потерь ниже энтропии. Но есть нюанс — нельзя без потерь. Для аналитики есть обходные пути:
Ключевые выводы
- Энтропия Шеннона H(X) — абсолютный нижний предел сжатия без потерь. Никакая кодировка не может в среднем использовать менее H(X) бит на значение.
- Большинство аналитических колонок имеют низкую энтропию: boolean — 0.3 бит, enum — 1.3 бит, timestamps (delta) — 3 бит. Это объясняет, почему колоночные форматы сжимают 10–100x.
- Кодировка определяет модель данных. Delta-модель даёт H(Δ) ≪ H(X). Dictionary-модель даёт H(index) ≪ H(string). Правильный выбор модели — ключ к приближению к теоретическому пределу.
- Кодирование устраняет type-specific избыточность, компрессия обрабатывает остаточную. Вместе дают мультипликативный эффект: 70x вместо 7x.
- Три свойства колонок снижают энтропию: гомогенность типов, локальность значений, кластеризация при записи. Row-ориентированные форматы разрушают все три.
- Если H ≈ raw_bits (UUID, random float) — кодирование бесполезно. Используйте компактное представление (binary вместо string) и general-purpose компрессию.