Learning Platform
Глоссарий Troubleshooting
Урок 04.03 · 30 мин
Продвинутый
ORCIndexesBloom FiltersSARGsPredicate PushdownRow IndexColumn Statistics

Индексная система

Три уровня индексов

ORC реализует трёхуровневую индексную систему — от грубой (весь файл) до точной (каждые 10 000 строк). Каждый уровень позволяет пропустить данные без чтения, сужая область сканирования:

  1. File-level — статистики в Footer: min/max/count/sum по каждой колонке для всего файла
  2. Stripe-level — статистики в Metadata: min/max/count/sum по каждой колонке для каждой stripe
  3. Row-level — Row Index внутри stripe: статистики по каждые 10 000 строк + позиции для seek
Три уровня индексов ORC

File-level (Footer)

Footer содержит ColumnStatistics для каждой колонки: min, max, count (non-null), hasNull, sum (для числовых). Позволяет пропустить ВЕСЬ файл, если предикат не пересекается с диапазоном.

min/max/count по колонке
Гранулярность: весь файл
Пропускает: файл целиком

Stripe-level (Metadata)

Metadata (опционально) содержит StripeStatistics для каждой stripe. По структуре идентичны file-level stats, но для каждой stripe отдельно. Позволяют пропустить ненужные stripes.

min/max/count по колонке/stripe
Гранулярность: stripe (64–250 MB)
Пропускает: отдельные stripes

Row-level (Row Index)

Row Index внутри каждой stripe: ColumnStatistics для каждых 10 000 строк (row index stride) + позиции потоков для быстрого seek. Самый точный уровень отсечения.

min/max/count по 10K строк
Гранулярность: row group (10K строк)
Пропускает: блоки по 10K строк

NOTE

Parquet имеет два уровня статистик: file-level (в FileMetaData) и page-level (в PageHeader для data pages). ORC добавляет третий уровень — stripe-level в отдельной Metadata-структуре. На практике stripe-level stats — самые полезные: они позволяют пропустить целые stripes по 64–250 MB.

Column Statistics

Каждый уровень использует одну и ту же Protobuf-структуру ColumnStatistics, адаптированную под тип данных:

message ColumnStatistics {
 numberOfValues: uint64 // количество non-null значений
 hasNull: bool // есть ли NULL в диапазоне
 bytesOnDisk: uint64 // размер данных колонки на диске

 // Type-specific расширения:
 intStatistics: IntegerStatistics // minimum, maximum, sum
 doubleStatistics: DoubleStatistics // minimum, maximum, sum
 stringStatistics: StringStatistics // minimum, maximum, sum (total length)
 dateStatistics: DateStatistics // minimum, maximum
 decimalStatistics: DecimalStatistics // minimum, maximum, sum
 timestampStatistics: TimestampStatistics // minimum, maximum
 booleanStatistics: BooleanStatistics // trueCount
 // ... и другие
}
Column Statistics по типам данных
IntegerStatisticsmin, max, sum для INT, LONG, SHORT, BYTE. Sum — int64, может переполниться для больших таблиц. Используется для pushdown WHERE x > 100.
StringStatisticsmin, max строки (лексикографически), sum — суммарная длина всех строк в байтах. Min/max позволяют отсекать по LIKE и range predicates.
DoubleStatisticsmin, max, sum для FLOAT и DOUBLE. NaN обрабатывается особо — NaN не влияет на min/max (IEEE 754 comparisons).
BooleanStatisticsКоличество true-значений. В сочетании с numberOfValues позволяет вычислить false-count = numberOfValues - trueCount. Полезно для фильтрации.
TimestampStatisticsmin, max в миллисекундах от epoch (UTC). Позволяет отсекать по WHERE ts BETWEEN ... AND ... без чтения наносекунд.
DateStatisticsmin, max в днях от epoch (1970-01-01). Целочисленное представление — эффективное сравнение и отсечение.

Row Index: внутри stripe

Row Index — самый точный уровень индексирования. Каждая stripe делится на row groups (не путать с Parquet Row Groups) по rowIndexStride строк. По умолчанию stride = 10 000 строк.

Для каждого row group в Row Index хранится:

  • ColumnStatistics — min/max/count для этих 10K строк
  • Stream positions — byte offset в каждом потоке (DATA, PRESENT, LENGTH), чтобы перескочить напрямую к нужному row group
Row Index внутри Stripe
Stripe (1 000 000 строк, stride = 10 000)Stripe с миллионом строк делится на 100 row groups по 10 000 строк. Каждый row group имеет свои column statistics и stream positions.
TIP

Row Index stride — настраиваемый параметр (orc.row.index.stride). Меньший stride (1000) даёт точнее отсечение, но больше metadata overhead. Больший stride (100 000) — меньше overhead, но грубее predicate pushdown. 10 000 — хороший баланс для большинства рабочих нагрузок.

Bloom Filters

Bloom filter — вероятностная структура данных, которая отвечает на вопрос «содержит ли этот набор данных значение X?» с двумя возможными ответами:

  • «Точно нет» — значения гарантированно нет, row group можно пропустить
  • «Возможно да» — значение может быть, нужно прочитать и проверить

ORC хранит bloom filter для каждого row group (stride, 10K строк) для указанных колонок. Bloom filters — опциональные, включаются через orc.bloom.filter.columns.

Bloom Filter: принцип работы

Запись (вставка)

Значение "apple" → k хешейКаждое значение хешируется k раз (ORC использует Murmur3). Каждый хеш определяет позицию бита в битовом массиве.

Установить k бит в массив

Биты на позициях хешей устанавливаются в 1. Остальные биты остаются 0. Коллизии допустимы — это источник false positive.

Bit array: [0, 0, 1, 0, 1, 0, 0, 0, 1, 0, …]

Битовый массив: 0010100010... Размер определяется количеством элементов и допустимым FPP (false positive probability, дефолт 0.05 = 5%).

Чтение (проверка)

Запрос: "banana" → k хешейПроверяем: содержит ли row group значение 'banana'? Хешируем 'banana' теми же k функциями.

Все k бит = 1?

Проверяем все k бит. Если хотя бы один = 0 → значения ТОЧНО нет (definite NO). Если все = 1 → ВОЗМОЖНО есть (possible YES).

→ SKIP

Хотя бы один бит = 0 → значения гарантированно нет в этом row group. Можно безопасно пропустить 10K строк.
Да → READ (возможно FP)Все биты = 1 → возможно есть, возможно коллизия (false positive). Нужно прочитать row group и проверить точно.

Параметры bloom filter в ORC:

ПараметрЗначение по умолчаниюОписание
orc.bloom.filter.columns(пусто)Колонки для bloom filter
orc.bloom.filter.fpp0.05 (5%)False positive probability
Хеш-функцияMurmur3 (64-bit)Используется double hashing: h1 + i × h2
WARNING

Bloom filters увеличивают размер Index Data в каждой stripe. При FPP 0.05 и 10 000 уникальных значений в row group bloom filter занимает ~7.5 KB. Для 100 row groups × 50 колонок = ~37 MB дополнительного overhead. Включайте bloom filters только для колонок с равенственными предикатами (WHERE id = X).

SARGs (Search ARGuments)

SARG — Search ARGument — это формализованное представление предиката SQL, которое ORC-ридер может проверить по индексам до чтения данных. Не все SQL-предикаты транслируются в SARGs.

Какие предикаты транслируются в SARGs

Да Поддерживаемые

column = valueРавенство проверяется по min/max stats и bloom filter. Если value < min или value > max → skip. Bloom filter даёт дополнительное отсечение.
column < / > / <= / >=Range predicates: проверяются по min/max stats. WHERE age > 50 при max = 35 → skip. Работает для всех числовых и строковых типов.
column BETWEENЭквивалент column >= low AND column <= high. Проверяется по min/max stats за одну операцию.
column IN (...)Проверяется как набор equality predicates. Bloom filter ускоряет для каждого значения в списке.
column IS NULLПроверяется по hasNull в ColumnStatistics. Если hasNull = false → точно нет NULL, skip. Если true — нужно читать PRESENT stream.

Нет Не поддерживаемые

function(column)Функция над колонкой: UPPER(name), YEAR(ts), ABS(value). Индекс хранит raw min/max — после функции они бесполезны.
column LIKE '%pattern%'Wildcard в начале строки: min/max stats не помогают, bloom filter тоже — он проверяет точное равенство, не подстроку.
column1 op column2Сравнение двух колонок: WHERE a > b. Индексы хранят stats по одной колонке, не по парам. Невозможно отсечь без чтения обеих.
NOT / OR (частично)NOT инвертирует SARG (поддерживается, но менее эффективно). OR поддерживается через CNF (Conjunctive Normal Form), но complex OR может fallback на full scan.

Predicate Pushdown: полный цикл

Когда SQL-движок (Hive, Spark, Trino) выполняет запрос с WHERE-предикатом, ORC-ридер проходит все три уровня индексов сверху вниз:

Predicate Pushdown: от файла до строки

① File stats → пропустить весь файл?

Шаг 1: проверяем file-level stats в Footer. Если предикат невозможен для всего файла (например, WHERE year = 2030, а max year = 2025) — пропускаем ВЕСЬ файл.

② Stripe stats → пропустить stripe?

Шаг 2: для каждой stripe проверяем stripe-level stats из Metadata. Пропускаем stripes, где предикат гарантированно не выполняется.

③ Row Index → пропустить row group (10K строк)?

Шаг 3: для оставшихся stripes читаем Row Index. Для каждого row group (10K строк) проверяем column stats. Пропускаем row groups, не содержащие нужных данных.

④ Bloom filter → дополнительное отсечение?

Шаг 4: если bloom filter включен для колонки — дополнительная проверка. Для equality predicates (WHERE id = X) bloom filter может отсечь row group, даже если min/max его пропустили.

⑤ Читаем и декодируем только нужные row groups

Шаг 5: только оставшиеся row groups декомпрессируются и декодируются. Seek по позициям из Row Index — без чтения промежуточных данных.

Пример: таблица 100 stripes × 100 row groups = 10 000 row groups.

WHERE city = 'Moscow' AND age > 30

Шаг 1: File stats — city min='Almaty', max='Zurich', age min=1, max=99 → файл может содержать
Шаг 2: Stripe stats — 40 из 100 stripes отсечены (city или age не пересекаются)
Шаг 3: Row Index — из оставшихся 6 000 row groups отсечены ещё 4 500
Шаг 4: Bloom filter на city — из 1 500 row groups отсечены ещё 1 200
Результат: читаем 300 row groups из 10 000 (3%)

ORC Indexes vs Parquet

ХарактеристикаORCParquet
Уровни статистик3 (file, stripe, row group)2 (file, page)
Минимальная гранулярность10 000 строк (row index stride)~4–8 KB (data page)
Bloom filterВстроенный (per row group, Murmur3)С Parquet 2.0 (per page)
SARGsФормализованные, встроенные в ридерЗависит от движка (Spark, Trino)
Stripe-level statsОтдельная Metadata-структура аналога (только row group stats)
Position indexStream positions для seekPage offset в column metadata
TIP

ORC’s Row Index с stream positions позволяет seek внутри stripe — перескочить к конкретному row group без чтения предыдущих. Parquet для этого использует page offset, но гранулярность привязана к размеру data page (обычно 1 MB), а не к фиксированному количеству строк.

Ключевые выводы

  1. Три уровня индексов: file (Footer), stripe (Metadata), row (Row Index) — каждый сужает область сканирования
  2. Row Index stride: по умолчанию 10 000 строк — min/max stats и stream positions для seek
  3. Bloom filters: вероятностное отсечение для equality predicates, FPP по умолчанию 5%
  4. SARGs: формализованные предикаты — =, <, >, BETWEEN, IN, IS NULL поддерживаются; функции над колонками — нет
  5. Predicate pushdown проходит все 3 уровня + bloom filter, отсекая данные до декомпрессии
  6. ORC vs Parquet: ORC имеет на один уровень индексов больше (stripe-level) и встроенную поддержку SARGs

Проверьте понимание

Результат: 0 из 0
Прикладной
Вопрос 1 из 4. ORC имеет 3 уровня индексов: file-level, stripe-level, row-level. Запрос: WHERE user_id = 'u-12345'. Данные не отсортированы. Какой индекс наиболее эффективен?

Закончили урок?

Отметьте его как пройденный, чтобы отслеживать свой прогресс

Войдите чтобы оценить урок
Вернуться к курсу
Прогресс модуля
0 из 7