Индекс диапазона блоков - Block Range Index

А Индекс диапазона блоков или же BRIN это индексация базы данных техника. Они предназначены для повышения производительности при очень больших[я] таблицы.

Индексы BRIN обеспечивают аналогичные преимущества горизонтальное разделение или же шардинг но без явного объявления разделов.[1]

BRIN применим к индексу большой таблицы, где значение ключа индекса легко сортируется и оценивается с помощью Функция MinMax.[ii]

BRIN были первоначально предложены Альваро Эррерой из 2-й квартал в 2013 году как «индексы Minmax».[2] Реализации до сих пор тесно связаны с методами внутренней реализации и хранения таблиц базы данных. Это делает их эффективными, но ограничивает их услугами конкретных поставщиков. Так далеко PostgreSQL является единственным поставщиком, который анонсировал действующий продукт с этой функцией в PostgreSQL 9.5.[3][4] Другие поставщики описали некоторые похожие функции,[2] включая Oracle,[5][6] Netezza 'карты зон',[7] Infobright 'пакеты данных',[8] MonetDB[9] и Apache Hive с ORC / паркетом.[10]

Дизайн

Структура индекса B-дерева
Структура индекса BRIN

BRIN работает путем «суммирования» больших блоков данных в компактную форму, которую можно эффективно протестировать, чтобы на раннем этапе исключить многие из них из запроса к базе данных. Эти тесты исключают большой блок данных для каждого сравнения. Уменьшая объем данных на столь раннем этапе, как за счет представления больших блоков в виде небольших кортежей, так и за счет исключения множества блоков, BRIN существенно сокращает объем подробных данных, которые должны проверяться узлом базы данных построчно.[11]

Хранение данных в больших базах данных делится на уровни и фрагменты, при этом хранилище таблиц организовано в «блоки». Каждый блок содержит примерно 1 МБ в каждом блоке.[iii][13] и они извлекаются путем запроса определенных блоков из уровня хранения на диске. BRIN - это облегченный итоговый уровень в памяти, расположенный над этим: каждый кортеж в индексе суммирует один блок относительно диапазона содержащихся в нем данных: его минимальное и максимальное значения, и если блок содержит какие-либо ненулевые данные для столбца ( s) представляющий интерес.[14]

В отличие от традиционного индекса, который находит области таблицы, содержащие интересующие значения, BRIN действуют как «отрицательные индексы»,[5] показывая блоки, которые определенно нет представляют интерес и поэтому не требуют дальнейшей обработки.

Некоторые простые тесты предполагают пятикратное повышение производительности поиска при сканировании индекса по сравнению с неиндексированной таблицей.[3] По сравнению с B-деревьями они позволяют избежать накладных расходов на обслуживание.[2]

Поскольку BRIN настолько легкие, они могут полностью храниться в памяти, что позволяет избежать накладных расходов на диск во время сканирования. То же самое может не относиться к B-дереву: B-дереву требуется узел дерева для каждого приблизительно N строк в таблице, где N - емкость одного узла, поэтому размер индекса велик. Поскольку BRIN требует только кортеж для каждого блока (из многих строк), индекс становится достаточно маленьким, чтобы различать диск и память. Для "узкого" стола[iv] объем индекса B-дерева приближается к объему самой таблицы; BRIN может составлять всего 5-15% от него.[15]

Преимущества

Поиск и сканирование индекса

В большом индексе базы данных обычно используется B-дерево алгоритмы. BRIN не всегда заменяет B-дерево, это улучшение последовательного сканирования индекса с особыми (и потенциально большими) преимуществами, когда индекс удовлетворяет определенным условиям для упорядочивания, а целью поиска является узкий набор эти значения. В общем случае со случайными данными B-дерево все еще может быть лучше.[3]

Особое преимущество технологии BRIN, разделяемое с интеллектуальным сканированием Oracle Exadata,[6] используется этот тип индекса с Большое количество данных или же хранилище данных приложения, где известно, что почти вся таблица не имеет отношения к интересующему диапазону. BRIN позволяет запрашивать таблицу в таких случаях, извлекая только те блоки, которые май содержат интересующие данные и исключая те, которые явно выходят за пределы диапазона или не содержат данных для этого столбца.

Вставлять

Обычная проблема при обработке больших таблиц заключается в том, что для извлечения требуется использование индекса, но поддержание этого индекса замедляет добавление новых записей. Типичная практика заключалась в том, чтобы сгруппировать дополнения вместе и добавить их как одну массовую транзакцию или удалить индекс, добавить пакет новых записей и затем воссоздать индекс. И то, и другое мешает одновременным операциям чтения / записи и может быть невозможно в некоторых постоянно работающих предприятиях.[16]

С BRIN замедление от поддержки индекса значительно сокращается по сравнению с B-деревом.[17] Вонг сообщает, что B-tree замедлило добавление к неиндексированной таблице размером 10 ГБ на 85%, но сопоставимый BRIN имел накладные расходы только на 11%.[1]

Создание индекса

BRIN может быть создан для очень больших данных, где B-дерево потребует горизонтального разделения.[14]

Создание BRIN также происходит намного быстрее, чем для B-дерева, на 80%.[1] Это было бы полезным улучшением рефакторинг существующие приложения баз данных, которые используют подход drop-add-reindex, не требуя изменения кода.

Выполнение

Зависимость от порядка столов

Для разных столбцов одной таблицы можно определить несколько BRIN. Однако есть ограничения.

BRIN эффективны только в том случае, если порядок значений ключей соответствует организации блоков на уровне хранения.[13][15] В простейшем случае это может потребовать физического упорядочения таблицы, которое часто является порядком создания строк в ней, чтобы соответствовать порядку ключа. Если этот ключ является датой создания, это может быть тривиальным требованием.[14]:9

Если данные действительно случайны или если в «горячей» базе данных наблюдается значительный отток значений ключей, предположения, лежащие в основе BRIN, могут не работать. Все блоки содержат записи "представляющие интерес", поэтому некоторые из них могут быть исключены на раннем этапе фильтром диапазона BRIN.

В большинстве случаев BRIN ограничивается одним индексом для каждой таблицы. Может быть определено несколько BRIN, но только один, вероятно, будет иметь подходящий порядок. Если два (или более) индекса имеют схожее поведение упорядочивания, может быть возможно и полезно определить несколько BRIN в одной таблице. Очевидным примером является то, что и дата создания, и столбец record_id увеличиваются. монотонно с последовательностью создания записи. В других случаях значение ключа может быть не монотонным, но при условии, что в физическом порядке записи все еще существует сильная группировка, BRIN будет эффективным.

Индексы Exadata Storage

BRIN имеет некоторое сходство с Oracle Exadata "Индексы хранилища ".[2][5][18] В стеке архитектуры Exadata четко сформулирована концепция «уровня хранения». Табличные данные хранятся в блоках или «ячейках памяти» на серверах хранения. Эти ячейки хранения непрозрачен для сервера хранения и возвращаются в ядро ​​базы данных по запросу по их идентификатору. Раньше узлы базы данных должны были запрашивать все ячейки памяти для их сканирования.[6]

Индексы хранения обеспечивают сокращение данных на этом уровне: эффективно указывая разделы, которые больше не представляют интереса.[13][v][19] Индекс хранилища загружается в память на сервере хранилища, так что, когда выдается запрос ячеек, он может быть предсказан с помощью значений поиска. Они сравниваются с индексом хранилища, после чего на узел базы данных нужно возвращать только соответствующие ячейки.

Преимущества в производительности с индексом хранилища наиболее очевидны, когда индексированный столбец содержит много нули. При сканировании через скудные данные.[20]

Разработка

Разработка под PostgreSQL велась в рамках Проект AXLE (Расширенная аналитика для очень больших европейских баз данных)[21] Работа частично финансировалась Европейским союзом. Седьмая рамочная программа (FP7 / 2007-2013).[22]

PostgreSQL

Впервые реализация PostgreSQL появилась в 2013 году.[2] BRIN появился в выпуске 9.5 PostgreSQL в начале 2016 года.[15][23]

Смотрите также

Примечания

  1. ^ «Большой» здесь относится к количеству строк в стол, а не размеры поля или общий размер.
  2. ^ Функция, которая эффективно оценивает большое количество элементов данных и возвращает их минимальные и максимальные значения. Понятия «минимум» и «максимум» широки и могут применяться к любому типу данных или их комбинациям, которые сортируемый.
  3. ^ PostgreSQL имеет размер блока по умолчанию 128 × 8 КБ страниц или 1 МБ.[3] Oracle называет эти «области хранения» и дает им размер по умолчанию 1 МБ.[12]
  4. ^ Столбцы таблицы чуть шире индексированных столбцов.
  5. ^ Фут[13] описывает индекс как содержащий «флаг, указывающий, существуют ли какие-либо пустые значения». Вероятно, это опечатка: Oracle описывает их как «отрицательные индексы», где «они определяют области, которые определенно не будут содержать значений»[5] В таком случае флаг будет более четко описан как обозначающий либо "Только Нулевые значения существуют "или если" Любые не-Нули существуют ".

Рекомендации

  1. ^ а б c Марк Вонг (10 октября 2014 г.). «Загрузка таблиц и создание индексов B-дерева и диапазонов блоков». Проект AXLE.
  2. ^ а б c d е Альваро Эррера (14.06.2013). «Индексы Minmax». Pg Hackers.
  3. ^ а б c d «Что нового в PostgreSQL 9.5». PostgreSQL.
  4. ^ «Глава 62. Индексы BRIN». Документация PostgreSQL 9.5.0. 2016.
  5. ^ а б c d Аруп Нанда (май – июнь 2011 г.). «Интеллектуальное сканирование соответствует индексам хранилища». Журнал Oracle. Oracle.
  6. ^ а б c «Понимание индексов хранилища в Oracle Exadata».
  7. ^ «С Netezza всегда используйте целочисленные ключи соединения для хорошего сжатия, карт зон и соединений». Netezza. 2010 г.
  8. ^ «Пакеты данных». Infobright. Архивировано из оригинал 27 июня 2009 г.
  9. ^ «Совместное сканирование: динамическое разделение полосы пропускания в СУБД». MonetDB. 2007 г. CiteSeerX  10.1.1.108.2662. Цитировать журнал требует | журнал = (помощь)
  10. ^ "Оптимизация улья с помощью индексов, фильтров Блума и статистики". Йорн Франке. 2015 г.
  11. ^ Эррера, Альваро (7 ноября 2014 г.). "commitdiff - BRIN: Индексы диапазона блоков". git.postgresql.org. Получено 2017-10-03.
  12. ^ «Когда используются индексы хранения Exadata?». OakTable.net.
  13. ^ а б c d Ричард Фут (4 октября 2012 г.). «Индексы хранения Exadata - Часть I».
  14. ^ а б c Марк Вонг (10 марта 2015 г.). «Презентация производительности PostgreSQL» (PDF). С. 7–10.
  15. ^ а б c "Индексы диапазона блоков (BRIN) в PostgreSQL 9.5". Сладость питона. 22 мая 2015 года.
  16. ^ Петр Елинек (28 ноября 2014 г.). «Прогресс в онлайн-обновлении». Проект AXLE.
  17. ^ Марк Вонг (10 октября 2014 г.). «Накладные расходы на индекс на растущем столе».
  18. ^ «Лучшие практики Oracle Sun Database Machine для хранилищ данных». Oracle. 1094934.1. Отсутствует или пусто | url = (помощь)
  19. ^ Марк Филдинг (20 июля 2010 г.). «Самый надежный секрет Exadata: индексы хранилища».
  20. ^ Керри Осборн (10 августа 2010 г.). «Oracle Exadata - индексы хранилища».
  21. ^ «Проект AXLE (Расширенная аналитика для очень больших европейских баз данных)». 2014.
  22. ^ «Седьмая рамочная программа Европейского Союза (FP7 / 2007-2013) в соответствии с соглашением о гранте № 318633». Отсутствует или пусто | url = (помощь)
  23. ^ Альваро Эррера (07.11.2014). "BRIN: Индексы диапазонов блоков". PostgreSQL. Получено 2016-01-14.