Dictionary encoding и FSST для строк

Предыдущие схемы — constant, RLE, bit packing, FOR — работали с числами. Но добрая половина колонок в реальных таблицах — строки: имена, города, категории, URL, email, коды. Строки сжимаются иначе: у них своя избыточность, и под неё две специализированные схемы. Dictionary encoding убирает повторы целых строк. FSST идёт глубже — извлекает повторяющиеся куски внутри строк, даже когда сами строки целиком все разные. Этот урок про обе.

Почему строки требуют особого подхода

Число — это фиксированное количество байт: BIGINT всегда 8, INTEGER всегда 4. Строка — переменной длины: 'PL' — два символа, 'Netherlands' — одиннадцать, длинный URL — сотни. Уже это делает строки неудобными для схем, заточенных под числа фиксированной ширины.

Но главное — у строк своя избыточность, и её две разновидности. Первая: повторяются целые строки. Колонка country на миллион записей — это десяток разных стран, повторённых много раз. Колонка city, status, category — то же самое: мало уникальных значений, каждое встречается тысячи раз. Вторая, более тонкая: повторяются фрагменты внутри строк, даже когда строки целиком уникальны. Колонка email: адреса все разные, но домен @gmail.com повторяется в тысячах из них. Колонка URL: ссылки уникальны, но префикс https://www. есть почти у каждой. Целиком строки разные — а куски внутри них совпадают.

Этим двум видам избыточности соответствуют две схемы. Dictionary encoding бьёт по первой — повторам целых строк. FSST бьёт по второй — повторам подстрок.

Dictionary encoding: строки в номера

Dictionary encoding — словарное кодирование. Идея проста и узнаваема: вместо того чтобы хранить длинную строку каждый раз заново

FSST: сжатие строк таблицей символов, заведём словарь уникальных строк и будем хранить вместо строк короткие номера-ссылки в этот словарь.

Механика на сегменте. Движок проходит по значениям колоночного сегмента и собирает все различные строки в словарь — список уникальных значений, каждому присвоен порядковый номер: 'Poland' это 0, 'Germany' это 1, 'France' это 2. После этого сам сегмент хранится не как строки, а как поток номеров: вместо 'Poland' стоит 0, вместо 'Germany' стоит 1. Плюс отдельно хранится словарь — сами строки, один раз каждая.

Откуда экономия. Строка 'Poland' — это шесть байт (а строки бывают и куда длиннее). Номер в словарь из десяти стран — это число 0..9, помещается в 4 бита. Замена строки на номер — это замена многих байт на горстку бит. Чем длиннее строки и чем чаще они повторяются, тем больше выигрыш: словарь хранит каждую длинную строку единожды, а миллион ссылок на неё — это миллион крошечных номеров.

И ещё одно. Поток номеров — это целые числа, а целые числа DuckDB умеет сжимать дальше. К потоку словарных номеров применяется bit packing из прошлого урока: если в словаре 10 строк, номера 0..9 упаковываются в 4 бита каждый. Dictionary encoding и bit packing складываются: словарь убирает повторы строк, превращая их в маленькие целые, bit packing упаковывает эти целые.

Декомпрессия дешёвая: взять номер из потока, использовать его как индекс в массив-словарь, достать строку. Индексация в массив — операция в один такт. При сканировании такой сегмент естественно ложится на DICTIONARY_VECTOR — физический тип вектора, который хранит словарь и поток номеров-ссылок раздельно.

Где dictionary encoding силён, а где буксует

Dictionary encoding блестит на колонках низкой кардинальности — там, где различных значений мало, а строк много. Страна, город, валюта, статус заказа, категория товара, код региона — десятки или сотни уникальных значений на миллионы строк. Словарь маленький, номера узкие, экономия огромна. Это очень распространённый тип колонки, поэтому dictionary encoding — одна из самых частых схем в реальных базах.

Где dictionary encoding буксует — на колонках высокой кардинальности, где почти каждое значение уникально. Колонка с именами пользователей, где совпадений мало. Колонка URL, где каждая ссылка своя. Колонка email. Если уникальных строк почти столько же, сколько строк всего, словарь раздувается до размера самих данных, номера становятся широкими, и смысл схемы теряется: мы храним и огромный словарь, и поток почти-уникальных номеров. Повторов целых строк нет — dictionary encoding нечего убирать.

И вот тут — граница, за которой нужна другая схема.

FSST: сжатие подстрок

Колонка высокой кардинальности — все строки разные — для dictionary encoding потеряна. Но мы помним: даже когда строки разные целиком, внутри них повторяются куски. @gmail.com в email, https:// в URL, общие префиксы артикулов, повторяющиеся слова в адресах. Эта избыточность есть — просто она на уровне подстрок, а не целых строк.

FSST — Fast Static Symbol Table — именно её и использует. Название переводится как «быстрая статическая таблица символов», и оно описывает устройство. FSST строит таблицу символов, но «символ» здесь — не одна буква, а часто встречающаяся последовательность байт, подстрока. FSST анализирует строки сегмента, находит часто повторяющиеся короткие последовательности байт и заносит их в таблицу, присваивая каждой короткий однобайтовый код.

После построения таблицы каждая строка перекодируется: повторяющиеся подстроки заменяются на свои однобайтовые коды. Строка [email protected] — если @gmail.com стало одним кодом — превращается в user плюс один байт. Email-адреса все уникальны как целые строки, dictionary encoding на них бессилен, но общий кусок @gmail.com FSST вынесет в таблицу и в тысячах адресов заменит одним байтом.

Можно сказать так: dictionary encoding — это словарь целых строк, FSST — это словарь подстрок. FSST работает на уровень глубже. Там, где dictionary encoding ищет «эта строка уже была целиком?», FSST ищет «этот кусок байт уже встречался?» — и находит избыточность даже в колонке, где двух одинаковых строк нет вообще.

Декомпрессия FSST остаётся лёгкой — это то, ради чего схема и спроектирована. Распаковка строки — это проход по её закодированным байтам: обычный байт копируется как есть, байт-код подстроки заменяется на свою последовательность из таблицы. Таблица символов маленькая, помещается в кэш CPU; замена кода на подстроку — дешёвая операция. FSST спроектирована быстрой — это прямо заложено в название, «Fast» — и распаковывается на скорости сканирования, как и положено lightweight-схеме.

Как увидеть выбор движка на строковых колонках

Посмотрим, что DuckDB выбирает для строковых колонок разной кардинальности.

duckdb strlab.duckdb

CREATE TABLE customers AS
  SELECT range AS id,
         ['Poland','Germany','France','Spain','Italy'][(range % 5) + 1] AS country,
         ('user_' || range || '@example.com') AS email
  FROM range(1000000);
CHECKPOINT;

SELECT column_name, compression, count(*) AS segments
FROM pragma_storage_info('customers')
GROUP BY column_name, compression
ORDER BY column_name;

Вывод:

column_name  compression  segments
country      dictionary   9
email        fsst         9
id           bitpacking   9

Картина ровно по теории. Колонка country — всего 5 уникальных значений на миллион строк, классическая низкая кардинальность; движок выбрал dictionary. Колонка email — каждый адрес уникален (в нём числовой range), повторов целых строк нет, но кусок @example.com есть в каждом; движок выбрал fsst, который этот общий хвост и сожмёт. Колонка id — целые числа, для них строковые схемы неприменимы, выбран bitpacking. Один запрос показывает обе строковые схемы и границу между ними: dictionary — для повторяющихся целых строк, FSST — для уникальных строк с общими подстроками.

Попробуй сам

Исследуйте границу между dictionary encoding и FSST.

1. Создайте колонку низкой кардинальности: CREATE TABLE low AS SELECT range AS id, ['active','inactive','pending'][(range % 3) + 1] AS status FROM range(2000000); и CHECKPOINT. Какую схему получила status?
2. Создайте колонку высокой кардинальности с общим хвостом: CREATE TABLE high AS SELECT range AS id, ('account_' || range || '@company.org') AS email FROM range(2000000); и CHECKPOINT. Какую схему получила email?
3. Создайте колонку высокой кардинальности БЕЗ общих кусков — случайные несжимаемые строки: например, ('row' || (random() * 1e15)::BIGINT) AS rnd. Сравните, как сожмётся такая колонка, с колонкой email из шага 2. Почему общий хвост @company.org так помогает?
4. Сравните размеры файлов баз low и high на диске. Колонка низкой кардинальности должна дать заметно меньший файл — почему словарь из трёх значений настолько компактнее?
5. Создайте таблицу с колонкой URL, где у всех адресов общий префикс https://www.example.com/page/, а дальше — уникальный числовой хвост. Посмотрите её схему и прикиньте, какую долю каждой строки FSST способен заменить кодами.

Этот эксперимент показывает на практике: dictionary encoding выигрывает на повторах целых строк, FSST — на повторах подстрок, и кардинальность колонки определяет, какая схема сработает.