ORC in Hive/Spark - “анатомия” файла, индексация и фильтр Блума
ORC — это колоночный формат, то есть данные хранятся не по строкам (как в CSV), а по столбцам. Именно это даёт ему способность эффективно сжимать и читать только нужные колонки. Есть ещё встроенная индексация и фильтр Блума, которые позволяют не перелопачивать лишние данные.
Давайте заглянем под капот и посмотрим, как устроен ORC-файл, зачем там индексы и как фильтр Блума ускоряет поиск.
I. Анатомия файла
Что лежит внутри ORC?
Будем рассматривать по принципу «снаружи внутрь»:
1. Postscript (самая последняя часть)
Точка входа в файл, содержит только координаты: где лежит File Footer и какая версия формата используется.
2. File Footer (глобальное оглавление)
Содержит полную схему данных (список столбцов) и карту файла: перечень всех полос (stripes) с их смещениями в байтах. Позволяет сразу «перепрыгнуть» к нужной полосе, не читая всё подряд.
3. Полосы (stripe) — самостоятельные блоки данных
Каждая полоса — это мини-таблица, которая содержит данные за определённый диапазон строк. Внутри полосы всё разбито на колонки и состоит из трёх частей:
Index Data: индекс внутри полосы (минимумы/максимумы для блоков внутри колонки) и фильтры Блума.
Row Data: сами данные, разложенные по столбцам (колоночное хранение).
Stripe Footer: подвал полосы со схемой расположения её собственных потоков данных.
II. Индексация внутри файла
ORC не требует создания отдельных индексов, как в классических базах данных. Необходимая информация для быстрого поиска вшита прямо в структуру файла и автоматически поддерживается при записи данных.
Рассмотрим устройство этой индексации, её уровни, содержимое и практическую пользу.
Общая концепция: индексация без индексов
В классических базах данных индексы создаются явно и хранятся отдельно от таблиц. Они ускоряют поиск, но требуют дополнительного места и обслуживания, например, как в PostgreSQL. ORC идёт другим путём: при записи данных в файл автоматически формируются компактные метаданные, которые играют роль индексов. Эти метаданные располагаются в специальных секциях файла и используются при чтении для отсеивания ненужных блоков данных ещё до того, как они будут прочитаны с диска.
Уровни индексации в ORC
Индексация в ORC организована иерархически, что соответствует физической структуре файла (файл → полосы → потоки). Можно выделить три основных уровня:
1. Глобальный уровень (File Footer)
Хранит общую информацию обо всех полосах: их местоположение в файле и базовую статистику по каждой полосе (минимум, максимум, количество null). Позволяет сразу отсечь целые полосы, которые не подходят под условия запроса.
2. Уровень полосы (Stripe Index)
Находится в начале каждой полосы. Содержит детальную статистику для небольших групп строк внутри полосы (минимум, максимум, позиции блоков). Даёт возможность читать только те блоки строк, которые действительно нужны, пропуская остальные данные внутри полосы.
3. Уровень потока (Stream level)
Самый глубокий уровень — данные каждого столбца разбиты на отдельные потоки. Индексы верхних уровней указывают точные позиции в этих потоках, позволяя обращаться к данным произвольно, без последовательного чтения.
Эта информация занимает очень мало места (по сравнению с самими данными), но даёт огромный выигрыш при фильтрации.
Как используется индексация при выполнении запроса
Когда приходит запрос с условием where age > 50, движок читает Index Data полосы. Если в статистике указано, что в этой полосе возраст от 18 до 30, то вся полоса пропускается без чтения Row Data.
Таким образом, индексация позволяет минимизировать объём данных, извлекаемых с диска, что критически важно для производительности в Big Data.
Несколько фактов:
- индексы создаются автоматически при записи без участия разработчика и не требуют дополнительного обслуживания (перестроения, обновления статистики).
- компактность: индексы занимают обычно единицы процентов от общего размера файла.
- эффективность для диапазонных запросов: статистика min/max идеально подходит для фильтров вида >, <, BETWEEN.
- поддержка скипа данных на нескольких уровнях: можно отбросить целые полосы или только отдельные блоки внутри полосы.
- интеграция с фильтрами Блума: для точечных запросов индексы min/max дополняются вероятностными структурами.
Настройка параметров индексации
Хотя индексация встроена и автоматическая, некоторые параметры можно регулировать для достижения оптимального баланса между размером индексов и гранулярностью скипа:
- orc.row.index.stride — количество строк в одном блоке (row group), для которого сохраняется статистика. Меньшее значение даёт более точную фильтрацию, но увеличивает размер индексов. По умолчанию 10 000.
- orc.create.index — включает/отключает построение индексов (по умолчанию true).
- orc.bloom.filter.column и orc.bloom.filter.fpp — включают фильтры Блума для указанных столбцов.
Ограничения
- Индексы min/max эффективны только для упорядочиваемых типов данных (числа, даты, строки). Для некоторых типов (например, сложных структур) статистика может быть менее полезна.
- Если данные в столбце слабо коррелированы с физическим порядком записей (например, случайные идентификаторы), диапазоны блоков будут широкими, и эффективность индексации снижается. В таких случаях помогают фильтры Блума.
- Индексы не обновляются при изменении данных — в ORC файлы иммутабельны, поэтому новые данные записываются в новые файлы, и индексы строятся заново.
Перед сохранением таблицы в ORC мы можем сделать сортировку, что позволяет:
ускорить запрос — если данные отсортированы по нужному столбцу, Hive читает ровно одну полосу, в которой содержится нужная информация, вместо сканирования всей таблицы
повысить эффективность индексов и фильтров Bloom — похожие данные хранятся вместе, что улучшает фильтрацию
улучшить сжатие — отсортированные данные могут быть лучше сжаты, так как ORC сохраняет минимальную и максимальную статистику по файлам.
Сортировку следует использовать только тогда, когда есть чёткое понимание того, как запросы будут использовать данные. Неоправданное использование сортировки может привести к дополнительным накладным расходам.
III. Фильтр Блума (Bloom Filter)
В дополнение к стандартным индексам (минимум/максимум), ORC поддерживает фильтры Блума — вероятностную структуру данных для проверки принадлежности элемента к множеству.
Индекс по минимуму/максимуму эффективен для диапазонных запросов, но бесполезен для точного поиска редких значений. Например, если мы ищем id = 999999, а этот id попадает в диапазон значений полосы (например, от 1 до 2 млн), статистика не поможет — полоса будет прочитана. Фильтр Блума же может точно сказать, есть ли такое конкретное значение в полосе, с высокой вероятностью избегая лишних чтений. Это критически важно для поиска по ключам или конкретным ID.
Рассмотрим “игрушечный” пример чтобы понять, как работает данный фильтр:
Пусть у нас есть массив из 20 ячеек (битов), пронумерованных от 0 до 19. Сначала все они пустые:
array[0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0]
Добавляем элементы с помощью хэш-функций
У нас есть три хэш-функции (для простоты).
Они умеют превращать любое слово в три числа от 0 до 19.
Добавляем слово «яблоко»
Хэш-функции выдали позиции: 3, 7, 12.
Ставим в этих ячейках единицы:
array[0 0 0 1 0 0 0 1 0 0 0 0 1 0 0 0 0 0 0 0]
Добавляем слово «груша»
Хэш-функции выдали: 7, 11, 18.
Смотрим: ячейка 7 уже была от «яблока», оставляем 1.
Ячейки 11 и 18 были 0, ставим 1.
array[0 0 0 1 0 0 0 1 0 0 0 1 1 0 0 0 0 0 1 0]
Добавляем слово «апельсин»
Хэш-функции: 3, 8, 15.
Ячейка 3 уже 1, ячейки 8 и 15 были 0, ставим 1.
array[0 0 0 1 0 0 0 1 1 0 0 1 1 0 0 1 0 0 1 0]
Теперь массив хранит «отпечатки» трёх слов.
Проверяем, есть ли слово
Проверяем слово «слива»
Хэш-функции дали: 5, 12, 18.
Смотрим в массив:
ячейка 5 → 0
ячейка 12 → 1
ячейка 18 → 1
Одна из ячеек (5) равна 0. Значит, слово «слива» точно не добавляли. Ведь если бы мы его добавляли, то обязательно поставили бы единицу в ячейке 5. Раз её нет — вывод однозначен.
Проверяем слово «банан»
Хэш-функции: 7, 11, 15.
Смотрим:
ячейка 7 → 1
ячейка 11 → 1
ячейка 15 → 1
Все три ячейки равны 1. Это значит, что «банан» возможно есть, но не гарантированно. Почему? Потому что эти единицы могли появиться от других слов, как получилось в нашем случае: 7 поставило «яблоко» и «груша», 11 — «груша», 15 — «апельсин». Все три бита оказались заняты, хотя «банан» мы не добавляли. Это и есть ложноположительное срабатывание.
Почему размер массива важен?
Если массив слишком маленький (как в нашем примере — всего 20 ячеек), то при добавлении даже небольшого числа слов многие ячейки становятся единицами, и ложные срабатывания случаются часто. Чем больше массив, тем реже разные слова будут попадать в одни и те же ячейки, и тем точнее фильтр. В реальных ORC-фильтрах размер массива может быть, например, 10 000 бит на одну группу строк. Это позволяет хранить отпечатки тысяч значений с вероятностью ошибки меньше 1%.
Как это хранится в ORC?
В ORC такой битовый массив не хранится как длинная строка из нулей и единиц — это было бы неэффективно. Его упаковывают в массив 64-битных чисел. Каждое число хранит 64 бита «упакованными» внутри себя. При проверке Hive вычисляет хэши и быстро проверяет нужные биты прямо в этих числах, не разворачивая весь массив.
В структуре файла ORC фильтры Блума располагаются в секции Index Data каждой полосы (stripe). Для каждого столбца, для которого включено построение фильтра, в Index Data сохраняется отдельный поток (bloom filter stream), содержащий сериализованный битовый массив и параметры хеш-функций. Эта информация располагается перед потоками с самими данными (Row Data) и позволяет при выполнении запроса быстро проверить, нужно ли читать полосу.
При создании таблицы в Hive (или при записи данных через другие движки, поддерживающие ORC) можно указать, для каких столбцов строить фильтры Блума, а также желаемую вероятность ложноположительного срабатывания (FPP, false positive probability).
Настройка фильтров Блума в ORC
В Hive параметры управления фильтрами Блума задаются через свойства таблицы (TBLPROPERTIES) или через конфигурационные параметры при записи:
orc.bloom.filter.columns — список столбцов (через запятую), для которых нужно строить фильтры Блума. Обычно это столбцы, используемые в точечных поисках: идентификаторы, ключи, уникальные коды.
orc.bloom.filter.fpp — целевая вероятность ложноположительного срабатывания (например, 0.05 для 5%). Чем меньше значение, тем точнее фильтр, но тем больше места он занимает.
orc.bloom.filter.write.version — версия формата фильтра (обычно "original" или "utf8").
Пример создания таблицы с фильтрами Блума для столбца user_id:
CREATE TABLE users ( user_id INT, name STRING, age INT ) STORED AS ORC TBLPROPERTIES ( "orc.bloom.filter.columns" = "user_id", "orc.bloom.filter.fpp" = "0.01" );
Эксперимент с фильтром Блума в ORC
Посмотрим влияние фильтра Блума (Bloom filter) на производительность запросов в двух вычислительных средах: Hive и Kyuubi (Spark). Тестировались две таблицы в формате ORC: одна без дополнительной оптимизации, другая с фильтром Блума на столбце id.
TBLPROPERTIES ("orc.bloom.filter.columns"="id")
Условия эксперимента
Две таблицы:
schema.without_bloom — без фильтра Блума на поле id.
schema.with_bloom — с фильтром Блума на поле id.
Размеры таблиц (вес):
without_bloom — 174 267 байт
with_bloom — 208 921 байт.
Таблица с фильтром Блума имеет больший размер из-за дополнительной служебной информации, хранящейся внутри ORC-файлов.
Запрос: SELECT * FROM ... WHERE id = 11805738 (выборка по конкретному значению).
Замеры времени выполнения (в секундах) для трёх последовательных запусков в каждой среде (Hive и Kyuubi).
Среда | Таблица | Время выполнения (сек) | Размер таблицы |
Kyuubi | Без фильтра | 1.784, 0.981, 0.754 | 174 267 байт |
Kyuubi | С фильтром (bloom) | 0.822, 0.688, 0.624 | 208 921 байт |
Hive | Без фильтра | 0.626, 0.566, 0.529 | 174 267 байт |
Hive | С фильтром (bloom) | 0.543, 0.507, 0.459 | 208 921 байт
|
Наблюдения:
В обеих средах запросы к таблице с фильтром Блума выполняются быстрее, несмотря на её больший физический размер. Выигрыш во времени составляет примерно 15–20% (в Hive — с 0.53–0.63 до 0.46–0.54 сек; в Kyuubi — с 0.75–1.78 до 0.62–0.82 сек).
Hive показывает более стабильные и в среднем меньшие времена по сравнению с Kyuubi. Это объясняется тем, что Kyuubi работает через Spark, добавляя накладные расходы на планирование и распределённое выполнение, которые для маленьких объёмов данных могут быть избыточны.
Почему фильтр Блума ускоряет запрос даже при большем размере таблицы?
Таблица с фильтром Блума занимает больше места, потому что к данным добавляются битовые массивы фильтров. Однако эти дополнительные данные позволяют пропускать целые блоки при чтении, если значение id в них отсутствует. В результате:
Без фильтра: ридер вынужден сканировать все блоки, которые потенциально могут содержать искомое значение (полагаясь только на границы мин/макс, которые есть всегда). Если значение попадает в диапазон блока, блок читается целиком.
С фильтром: перед чтением блока выполняется вероятностная проверка. Для значения, которое встречается редко, большинство блоков будут отсеяны ещё на этапе индекса. Таким образом, реально считывается гораздо меньше данных, что с лихвой компенсирует увеличение общего размера таблицы.
Итак, подведем небольшой итог о плюсах и минусах ORC:
Плюсы
Относительно высокая производительность запросов — благодаря колоночному формату читаются только нужные столбцы, а встроенные индексы (min/max, фильтры Блума) позволяют быстро отсеивать целые блоки данных.
Эффективное сжатие — данные одного типа хранятся вместе, что улучшает степень сжатия и экономит место на диске.
Автоматическая индексация — индексы создаются при записи без дополнительных усилий, ускоряя фильтрацию (особенно для точечных и диапазонных условий).
Поддержка эволюции схемы. ORC позволяет добавлять новые поля и менять типы данных полей.
Минусы:
Накладные расходы при записи — построение индексов и фильтров требует дополнительных вычислений и памяти, поэтому запись данных идёт медленнее, чем в простые форматы (например, текстовые).
Не подходит для частых мелких обновлений — ORC-файлы иммутабельны (неизменяемы), любые изменения требуют перезаписи данных.
Увеличение размера при использовании фильтров Блума — дополнительные структуры занимают место, но это окупается ускорением чтения.
Сложность формата — требует понимания настроек (например, размера полосы, шага индекса) для достижения оптимальной производительности.