Z-ordering и data skipping

Data skipping: пропускаем ненужные данные

Data skipping — это техника, при которой Spark не читает блоки данных, которые гарантированно не содержат нужных строк. Это работает благодаря min/max statistics, хранящимся в metadata каждого row group (Parquet) или stripe (ORC).

Как работают min/max statistics

Каждый row group в Parquet хранит минимальное и максимальное значение для каждого столбца:

Predicate pushdown с min/max

Когда Spark выполняет запрос с фильтром, он проверяет min/max statistics перед чтением row group:

# Запрос: заказы за февраль 2024
df = spark.read.parquet("/data/orders/")
feb_orders = df.filter(col("order_date") >= "2024-02-01")

Spark проверяет каждый row group:

• Row Group 1: max(order_date) = 2024-01-15 < 2024-02-01 → SKIP (не читаем!)
• Row Group 2: max(order_date) = 2024-01-31 < 2024-02-01 → SKIP
• Row Group 3: min(order_date) = 2024-02-01 >= 2024-02-01 → READ

Результат: Spark прочитал 1/3 данных вместо всего файла.

Проблема: фильтрация по нескольким столбцам

Данные можно отсортировать только по одному столбцу (или по нескольким, но с жёсткой иерархией). Если вы отсортировали по order_date, то фильтрация по city не будет эффективной — значения города разбросаны по всем row groups.

# Данные отсортированы по order_date
# Запрос по дате -- data skipping работает отлично
df.filter(col("order_date") == "2024-02-01")  # читает ~3% данных

# Запрос по городу -- data skipping НЕ работает
df.filter(col("city") == "Москва")  # читает 100% данных!
# Потому что "Москва" есть в КАЖДОМ row group (min/max покрывает весь диапазон)

Z-ordering: многомерная кластеризация

Z-ordering решает эту проблему, организуя данные так, что строки с похожими значениями по нескольким столбцам оказываются в одних и тех же файлах/row groups.

Как работает Z-ordering

Z-ordering использует Z-кривую (кривую Мортона) для отображения многомерных данных в одномерное пространство. Вместо сортировки по одному столбцу, данные организуются по чередующимся битам нескольких столбцов:

Z-ordering обеспечивает data skipping по обоим столбцам одновременно.

Применение Z-ordering (Delta Lake)

Z-ordering — это прежде всего фича Delta Lake (и других lakehouse-форматов):

-- Delta Lake: Z-ordering при компактизации
OPTIMIZE orders
ZORDER BY (order_date, city)

# Через DeltaTable API
from delta.tables import DeltaTable

delta_table = DeltaTable.forPath(spark, "/data/orders/")
delta_table.optimize().executeZOrderBy("order_date", "city")

Эффект Z-ordering: Before vs After

Before Z-ordering (стандартная запись):

Запрос: WHERE city = 'Москва' AND order_date = '2024-02-01'
Файлов в таблице: 1000
Файлов прочитано: 950 (95%)  ← data skipping почти не работает
Данных прочитано: 9.5 GB из 10 GB
Время выполнения: ~45 секунд

After Z-ordering (по city + order_date):

Запрос: WHERE city = 'Москва' AND order_date = '2024-02-01'
Файлов в таблице: 1000
Файлов прочитано: 50 (5%)   ← data skipping отсекает 95%
Данных прочитано: 0.5 GB из 10 GB
Время выполнения: ~2 секунды

20x ускорение за счёт чтения 5% данных вместо 95%.

Практические рекомендации

Выбор столбцов для Z-ordering

Оптимально: 2-4 столбца, которые чаще всего используются в WHERE и JOIN.

Альтернатива Z-ordering в чистом Spark

# Приближение Z-ordering через сортировку
df.repartitionByRange(100, col("city"), col("order_date")) \
  .sortWithinPartitions(col("city"), col("order_date")) \
  .write.parquet("/data/orders_sorted/")

Это обеспечит хороший data skipping по city (первый столбец) и умеренный по order_date (второй столбец), но не настоящий Z-ordering.

Анти-паттерн: Z-ordering по высококардинальным уникальным столбцам

-- ПЛОХО: Z-ordering по уникальному столбцу
OPTIMIZE orders
ZORDER BY (user_id)  -- миллионы уникальных значений

-- Каждый row group содержит уникальные user_id
-- min/max statistics покрывают весь диапазон
-- Data skipping не работает!

Z-ordering эффективен для столбцов со средней кардинальностью (сотни-тысячи уникальных значений). Для столбцов с миллионами уникальных значений используйте bloom filters (следующий урок).

Что дальше?

В следующем уроке мы изучим bloom filters — вероятностные структуры данных, которые дополняют min/max statistics для высококардинальных столбцов (user_id, session_id), где Z-ordering неэффективен.