Кластеризация таблиц

Продуманный ключ сортировки — это самый эффективный инструмент физического проектирования в Selena. Это руководство объясняет, как работает ключ сортировки под капотом, какие системные преимущества он открывает, и предоставляет конкретный план действий для выбора эффективного ключа для вашей рабочей нагрузки.

Пример

Предположим, вы управляете системой телеметрии, которая получает миллиарды строк в день, каждая из которых помечена device_id и ts (временная метка). Определение ORDER BY (device_id, ts) для вашей таблицы фактов обеспечивает:

• Точечные запросы по device_id возвращаются за миллисекунды.
• Дашборды, фильтрующие недавние временные окна для каждого устройства, отсекают большую часть данных.
• Агрегации типа GROUP BY device_id получают преимущества от потоковой агрегации.
• Сжатие улучшается благодаря последовательностям близких временных меток для каждого устройства.

Этот простой двухколоночный ключ сортировки ORDER BY (device_id, ts) обеспечивает сокращение I/O, экономию CPU и более стабильную производительность запросов для миллиардов строк.

CREATE TABLE telemetry (
  device_id VARCHAR,
  ts DATETIME,
  value DOUBLE
)
ENGINE=OLAP
PRIMARY KEY(device_id, ts)
PARTITION BY RANGE (date_trunc('day', ts))
DISTRIBUTED BY HASH(device_id) BUCKETS 16
ORDER BY (device_id, ts);

---

Подробные преимущества

1. Массовое исключение I/O — отсечение сегментов и страниц

   Как это работает:

   Каждый сегмент и 64 КБ страница хранят минимальные/максимальные значения для всех колонок. Если предикат выходит за пределы этого диапазона, Selena пропускает весь блок и никогда не обращается к диску.

   Пример:

   SELECT count(*)
   FROM events
   WHERE tenant_id = 42
     AND ts BETWEEN '2025-05-01' AND '2025-05-07';

   С ORDER BY (tenant_id, ts) рассматриваются только сегменты, первый ключ которых равен 42, а внутри них только страницы, временное окно которых пересекается с этими семью днями. Таблица в 100 млрд строк может сканировать менее 1 млрд строк, превращая минуты в секунды.

---

2. Миллисекундные точечные поиски — разреженный префиксный индекс

   Как это работает:

   Разреженный префиксный индекс хранит каждое ~1000-е значение ключа сортировки. Бинарный поиск попадает на правильную страницу, затем одно чтение с диска (часто уже кэшированное) возвращает строку.

   Пример:

   SELECT *
   FROM orders
   WHERE order_id = 982347234;

   С ORDER BY (order_id) поиск требует ≈ 50 сравнений ключей в таблице из 50 млрд строк — задержка менее 10 мс даже при холодном кэше данных.

---

3. Более быстрая сортированная агрегация

   Как это работает:

   Когда ключ сортировки совпадает с предложением GROUP BY, Selena выполняет потоковую агрегацию во время сканирования — без необходимости сортировки или хэш-таблицы.

   Этот план сортированной агрегации сканирует строки в порядке ключа сортировки и выдает группы на лету, используя локальность CPU кэша и пропуская промежуточную материализацию.

   Пример:

   SELECT device_id, COUNT(*)
   FROM   telemetry
   WHERE  ts BETWEEN '2025-01-01' AND '2025-01-31'
   GROUP  BY device_id;

   Если таблица имеет ORDER BY (device_id, ts), движок группирует строки по мере их поступления — без построения хэш-таблицы или пересортировки. Для ключей с высокой кардинальностью, таких как device_id, это может значительно снизить использование как CPU, так и памяти.

   Потоковая агрегация с сортированным входом обычно улучшает пропускную способность в 2–3 раза по сравнению с хэш-агрегацией для больших кардинальностей групп.

---

4. Более высокое сжатие и горячие кэши

   Как это работает:

   Сортированные данные показывают небольшие дельты или длинные последовательности, ускоряя словарное кодирование, RLE и кодирование относительно опорного значения. Компактные страницы последовательно проходят через CPU кэши.

   Пример:

   Таблица телеметрии, отсортированная по (device_id, ts), достигла в 1,8 раза лучшего сжатия (LZ4) и на 25% меньшего CPU/сканирование по сравнению с теми же данными, загруженными несортированными.

---

Как работает ключ сортировки

Влияние ключа сортировки начинается с момента записи строки и сохраняется через каждую оптимизацию времени чтения. Этот раздел проходит через жизненный цикл — путь записи ➜ иерархия хранения ➜ внутренности сегмента ➜ путь чтения — чтобы показать, как каждый слой усиливает ценность упорядочивания.

1. Путь записи
   1. Прием: строки попадают в MemTable, сортируются по объявленному ключу сортировки, а затем сбрасываются как новый Rowset, содержащий один или несколько упорядоченных сегментов.
   2. Compaction: фоновые накопительные/базовые задания объединяют множество маленьких Rowset в более крупные, восстанавливая удаления и снижая количество сегментов без пересортировки, поскольку каждый исходный Rowset уже имеет тот же порядок.
   3. Репликация: каждый Tablet (шард, владеющий Rowset) синхронно реплицируется на узлы Back-End, гарантируя согласованность сортированного порядка между репликами.

2. Иерархия хранения

Объект	Что это	Почему это важно для ключа сортировки
Partition	Крупнозернистый логический срез таблицы (например, дата или tenant_id).	Позволяет отсечение разделов во время планирования и изолирует операции жизненного цикла (TTL, массовая загрузка).
Tablet	Хэш/случайный bucket внутри раздела, независимо реплицируемый между узлами Back-End.	Единица, строки которой физически упорядочены по ключу сортировки; все внутриразделное отсечение начинается здесь.
MemTable	Буфер записи в памяти (~96 МБ), который сортирует по объявленному ключу перед сбросом на диск.	Гарантирует, что каждый сегмент на диске уже упорядочен — внешняя сортировка не нужна позже.
Rowset	Неизменяемый пакет одного или нескольких сегментов, созданный циклом сброса, потоковой загрузки или compaction.	Дизайн только для добавления позволяет Selena принимать данные одновременно, пока читатели остаются без блокировок.
Segment	Самодостаточный колоночный файл (~512 МБ) внутри Rowset, несущий страницы данных плюс индексы отсечения.	Zone-map и префиксные индексы уровня сегмента полагаются на порядок, установленный на стадии MemTable.

3. Внутри файла сегмента

Каждый сегмент самоописывается. Сверху вниз вы найдете:

• Страницы данных колонок: 64 КБ блоки, закодированные (Dictionary, RLE, Delta) и сжатые (LZ4 по умолчанию).
• Порядковый индекс: отображает порядковый номер строки → смещение страницы, чтобы движок мог перейти прямо к странице n.
• Zone-map индекс: min, max и has_null для каждой страницы и для всего сегмента — первая линия защиты для отсечения.
• Short-key (префиксный) индекс: разреженная таблица бинарного поиска первых 36 байт ключа сортировки каждые ~1K строк — обеспечивает миллисекундные точечные/диапазонные поиски.
• Footer и магическое число: смещения к каждому индексу и контрольная сумма для целостности; позволяет Selena отображать в память только хвост для обнаружения остального.

Поскольку страницы уже отсортированы по ключу, эти индексы крошечные, но чрезвычайно эффективные.

4. Путь чтения

   1. Отсечение разделов (время планирования): если предложение WHERE ограничивает ключ раздела (например, dt BETWEEN '2025-05-01' AND '2025-05-07'), оптимизатор открывает только соответствующие каталоги разделов.
   2. Отсечение Tablet (время планирования): когда фильтр равенства включает колонку хэш-распределения, Selena вычисляет целевые ID tablet и планирует только эти Tablet.
   3. Поиск по префиксному индексу: разреженный short-key индекс по ведущим колонкам сортировки нацеливается на точный сегмент или страницу.
   4. Zone-map отсечение: метаданные min/max для каждого сегмента и 64 КБ страницы отбрасывают блоки, которые не попадают в окно предиката.
   5. Векторизованное сканирование и поздняя материализация: выжившие страницы колонок последовательно проходят через CPU кэши; материализуются только ссылочные строки и колонки, сохраняя память компактной.

   Поскольку данные фиксируются в порядке ключей при каждом сбросе, каждый слой отсечения времени чтения усиливает предыдущий, обеспечивая субсекундные сканирования таблиц с миллиардами строк.

---

Как выбрать эффективный ключ сортировки

1. Начните с анализа рабочей нагрузки

   Сначала проанализируйте топ-N паттернов запросов:

   • Предикаты равенства (= / IN). Колонки, почти всегда фильтруемые по равенству, являются идеальными ведущими кандидатами.
   • Предикаты диапазона. Временные метки и числовые диапазоны обычно следуют за колонками равенства в ключе сортировки.
   • Ключи агрегации. Если колонка диапазона также появляется в предложениях GROUP BY, размещение ее раньше в ключе (после селективных фильтров) может включить сортированную агрегацию.
   • Ключи join/group-by. Рассмотрите размещение ключей соединения или группировки рано, если они распространены.

   Измерьте кардинальность колонок: колонки с высокой кардинальностью (миллионы различных значений) отсекают лучше всего.

2. Эвристики и практические правила

   1. Правило порядка: (колонки равенства с высокой селективностью) → (основная колонка диапазона) → (помощники кластеризации).
   2. Упорядочивание по кардинальности: размещение колонок с низкой кардинальностью перед колонками с высокой кардинальностью может улучшить сжатие данных.
   3. Ширина: ограничьтесь 3-5 колонками. Очень широкие ключи замедляют прием и переполняют 36-байтовый лимит префиксного индекса.
   4. Строковые колонки: длинная ведущая строковая колонка может занять большую часть или весь 36-байтовый лимит в префиксном индексе, не позволяя последующим колонкам в ключе сортировки эффективно индексироваться.

   Это снижает мощность отсечения префиксного индекса и ухудшает производительность точечных запросов.

3. Координируйте с другими инструментами проектирования

   • Разделение: выберите ключ раздела, который грубее ведущей колонки сортировки (например, PARTITION BY date, ORDER BY (tenant_id, ts)). Таким образом, отсечение разделов сначала удаляет целые диапазоны дат, а отсечение сортировки очищает внутри.
   • Bucketing: использование одних и тех же колонок для bucketing и кластеризации служит разным целям. Bucketing обеспечивает равномерное распределение данных по кластеру, в то время как сортировка позволяет эффективное исключение I/O.
   • Тип таблицы: таблицы Primary-Key по умолчанию используют первичный ключ как ключ сортировки, но они также могут указывать дополнительные колонки для уточнения физического порядка и улучшения отсечения. Агрегатные и дублирующие таблицы должны следовать стратегиям ключей сортировки, управляемым аналитическими предикатами, обсуждаемым выше.

---

4. Справочные шаблоны

Сценарий	Раздел	Ключ сортировки	Обоснование
B2C заказы	date_trunc('day', order_ts)	(user_id, order_ts)	Большинство запросов сначала фильтруют по пользователю, затем по недавним временным диапазонам.
IoT телеметрия	date_trunc('day', ts)	(device_id, ts)	Доминируют чтения временных рядов в рамках устройства.
SaaS мультитенант	tenant_id	(dt, event_id)	Изоляция тенантов через раздел; сортировка кластеризует по дням для дашбордов.
Поиск в измерениях	none	(dim_id)	Маленькая таблица, чистые точечные поиски — достаточно одной колонки.

---

Заключение

Хорошо спроектированный ключ сортировки обменивает небольшие, предсказуемые накладные расходы на прием на драматические улучшения в задержке сканирования, эффективности хранения и использовании CPU. Основывая свой выбор на реалиях рабочей нагрузки, уважая кардинальность и проверяя с помощью EXPLAIN, вы можете поддерживать работу Selena даже при росте данных и количества пользователей в 10 раз и более.