Индекс растрового это специальный вид индекса базы данных , который использует растровые изображения .
Растровые индексы традиционно считались хорошо работающими для столбцов с низкой мощностью , которые имеют небольшое количество различных значений, абсолютно или относительно количества записей, содержащих данные. Крайний случай низкой мощности - это логические данные (например, есть ли у жителя города доступ в Интернет?), Которые имеют два значения: True и False. Индексы растровых изображений используют битовые массивы (обычно называемые растровыми изображениями) и отвечают на запросы, выполняя побитовые логические операции с этими растровыми изображениями. Индексы Bitmap имеют значительное преимущество в пространстве и производительности по сравнению с другими структурами для запроса таких данных. Их недостаток в том, что они менее эффективны, чем традиционное B-дерево.индексы для столбцов, данные которых часто обновляются: следовательно, они чаще используются в системах только для чтения, которые специализируются на быстрых запросах - например, в хранилищах данных и обычно не подходят для приложений обработки онлайн-транзакций .
Некоторые исследователи утверждают, что растровые индексы также полезны для данных с умеренным или даже большим количеством элементов (например, данных с уникальным значением), доступ к которым осуществляется в режиме только для чтения, а запросы обращаются к нескольким столбцам с растровым индексом, используя операции AND , OR или XOR. операторы широко. [1]
Растровые индексы также полезны в приложениях хранилищ данных для присоединения большой таблицы фактов к меньшим таблицам измерений, например, к таблицам , расположенным в звездообразной схеме .
Пример
Продолжая пример доступа к Интернету, индекс растрового изображения можно логически рассматривать следующим образом:
Идентификатор | HasInternet | Растровые изображения | |
---|---|---|---|
Y | N | ||
1 | да | 1 | 0 |
2 | Нет | 0 | 1 |
3 | Нет | 0 | 1 |
4 | Неопределенные | 0 | 0 |
5 | да | 1 | 0 |
Слева Идентификатор относится к уникальному номеру, присвоенному каждому резиденту, HasInternet - это данные, которые необходимо проиндексировать, содержимое индекса растрового изображения отображается в виде двух столбцов под заголовком « Растровые изображения» . Каждый столбец на левой иллюстрации представляет собой растровое изображение в индексе растрового изображения. В данном случае есть два таких растровых изображения: одно для «есть интернет» - Да, а второе - для «есть интернет» - Нет . Легко видеть, что каждый бит в растровом изображении Y показывает, относится ли конкретная строка к человеку, имеющему доступ в Интернет. Это простейшая форма растрового индекса. Большинство столбцов будут иметь более разные значения. Например, сумма продаж, вероятно, будет иметь гораздо большее количество различных значений. Вариации индекса битовой карты также могут эффективно индексировать эти данные. Кратко рассмотрим три таких варианта.
Примечание. Многие из цитируемых здесь ссылок можно найти в ( John Wu (2007) ). [2] Для тех, кому может быть интересно поэкспериментировать с некоторыми из идей, упомянутых здесь, многие из них реализованы в программном обеспечении с открытым исходным кодом, таком как FastBit, [3] библиотека Lemur Bitmap Index C ++, [4] Java-библиотека Roaring Bitmap. [5] и система хранилища данных Apache Hive .
Сжатие
По историческим причинам сжатие растровых изображений и сжатие инвертированных списков были разработаны как отдельные направления исследований и только позже были признаны решающими, по сути, одну и ту же проблему. [6]
Программное обеспечение может сжимать каждое растровое изображение в растровом индексе для экономии места. По этой теме был проделан значительный объем работы. [7] [8] Хотя есть исключения, такие как Ревущие битовые карты, [9] алгоритмы сжатия битовых карт обычно используют кодирование длины серий , такое как битовый код с выравниванием по байтам, [10] гибридный код с выравниванием по словам , [11] гибридное сжатие с разделением по словам (PWAH), [12] гибридное с выравниванием по словам списка позиций, [13] сжатый адаптивный индекс (COMPAX), [14] гибридное с расширенным выравниванием по словам (EWAH) [15] и COmpressed ' N 'Составное целое число SEt. [16] [17] Эти методы сжатия требуют очень мало усилий для сжатия и распаковки. Что еще более важно, растровые изображения, сжатые с помощью BBC, WAH, COMPAX, PLWAH, EWAH и CONCISE, могут напрямую участвовать в побитовых операциях без декомпрессии. Это дает им значительные преимущества перед обычными методами сжатия, такими как LZ77 . Сжатие BBC и его производные используются в коммерческой системе управления базами данных . BBC эффективен как для уменьшения размеров индексов, так и для поддержания производительности запросов . BBC кодирует растровые изображения в байтах , а WAH кодирует словами, что лучше соответствует текущим процессорам . «Как для синтетических данных, так и для данных реальных приложений, новые схемы с выравниванием слов используют только на 50% больше места, но выполняют логические операции со сжатыми данными в 12 раз быстрее, чем BBC». [18] Растровые изображения PLWAH занимают 50% дискового пространства, потребляемого растровыми изображениями WAH, и обеспечивают до 20% более высокую производительность логических операций . [13] Аналогичные соображения можно сделать для CONCISE [17] и расширенного гибрида с выравниванием по словам . [15]
Производительность таких схем, как BBC, WAH, PLWAH, EWAH, COMPAX и CONCISE, зависит от порядка строк. Простая лексикографическая сортировка может разделить размер индекса на 9 и ускорить его в несколько раз. [19] Чем больше таблица, тем важнее сортировать строки. Также были предложены методы перестановки для достижения тех же результатов сортировки при индексировании потоковых данных. [14]
Кодирование
Базовые индексы битовой карты используют одну битовую карту для каждого отдельного значения. Можно уменьшить количество используемых растровых изображений, используя другой метод кодирования . [20] [21] Например, можно кодировать C различных значений, используя битовые карты log (C) с двоичным кодированием . [22]
Это уменьшает количество растровых изображений, дополнительно экономя пространство, но для ответа на любой запрос необходимо получить доступ к большинству растровых изображений. Это делает его потенциально не таким эффективным, как сканирование вертикальной проекции базовых данных, также известной как материализованный вид или индекс проекции. Поиск оптимального метода кодирования, который уравновешивает (произвольную) производительность запроса, размер индекса и обслуживание индекса, остается сложной задачей.
Не рассматривая сжатие, Чан и Иоаннидис проанализировали класс методов многокомпонентного кодирования и пришли к выводу, что двухкомпонентное кодирование находится на изломе кривой зависимости производительности от размера индекса и, следовательно, представляет собой лучший компромисс между размером индекса и производительность запроса. [20]
Биннинг
Для столбцов с высокой мощностью полезно группировать значения, где каждая ячейка охватывает несколько значений, и строить растровые изображения для представления значений в каждой ячейке. Такой подход уменьшает количество используемых растровых изображений независимо от метода кодирования. [23] Однако сгруппированные индексы могут отвечать только на некоторые запросы без изучения базовых данных. Например, если корзина охватывает диапазон от 0,1 до 0,2, тогда, когда пользователь запрашивает все значения меньше 0,15, все строки, попадающие в корзину, являются возможными попаданиями и должны быть проверены, чтобы проверить, действительно ли они меньше 0,15. . Процесс проверки базовых данных известен как проверка кандидата. В большинстве случаев время, используемое для проверки кандидата, значительно больше времени, необходимого для работы с индексом битовой карты. Следовательно, индексы с группировкой показывают нестабильную производительность. Они могут быть очень быстрыми для некоторых запросов, но намного медленнее, если запрос не точно соответствует корзине.
История
Концепция растрового индекса была впервые представлена профессором Израилем Шпиглером и Рафи Мааяном в их исследовании «Хранение и извлечение двоичных баз данных», опубликованном в 1985 году. [24] Первым коммерческим продуктом для баз данных, реализовавшим растровый индекс, была Computer Corporation of Модель Америки 204 . Патрик О'Нил опубликовал статью об этой реализации в 1987 году. [25] Эта реализация представляет собой гибрид между базовым индексом битовой карты (без сжатия) и списком идентификаторов строк (список RID). В целом индекс организован в виде дерева B + . Когда мощность столбца низка, каждый листовой узел B-дерева будет содержать длинный список RID. В этом случае для представления списков RID в виде растровых изображений требуется меньше места. Поскольку каждое растровое изображение представляет одно отдельное значение, это базовый индекс растрового изображения. По мере увеличения количества элементов столбца каждое растровое изображение становится разреженным, и для хранения растровых изображений может потребоваться больше дискового пространства, чем для хранения того же содержимого, что и списки RID. В этом случае он переключается на использование RID-списков, что делает его индексом дерева B + . [26] [27]
Растровые изображения в памяти
Одна из самых веских причин для использования индексов растровых изображений заключается в том, что полученные из них промежуточные результаты также являются растровыми изображениями и могут быть эффективно повторно использованы в дальнейших операциях для ответа на более сложные запросы. Многие языки программирования поддерживают это как структуру данных битового массива. Например, в Java есть BitSet
класс.
Некоторые системы баз данных, которые не предлагают постоянные индексы растровых изображений, используют растровые изображения внутри для ускорения обработки запросов. Например, PostgreSQL версии 8.1 и более поздних реализует оптимизацию «сканирования индекса по битовой карте» для ускорения произвольно сложных логических операций между доступными индексами в одной таблице.
Для таблиц с большим количеством столбцов общее количество различных индексов, удовлетворяющих всем возможным запросам (с условиями фильтрации равенства для любого из полей), растет очень быстро, что определяется следующей формулой:
- . [28] [29]
Сканирование растрового индекса объединяет выражения для разных индексов, поэтому для поддержки всех возможных запросов к таблице требуется только один индекс на столбец.
Применение этой стратегии доступа к индексам B-дерева также позволяет комбинировать запросы диапазона по нескольким столбцам. При таком подходе создается временное растровое изображение в памяти с одним битом для каждой строки в таблице ( таким образом, в 1 МБ может храниться более 8 миллионов записей). Затем результаты каждого индекса объединяются в битовую карту с помощью побитовых операций . После оценки всех условий растровое изображение содержит «1» для строк, соответствующих выражению. Наконец, выполняется обход растрового изображения и извлекаются совпадающие строки. Помимо эффективного комбинирования индексов, это также улучшает локальность ссылок при доступе к таблице, поскольку все строки последовательно выбираются из основной таблицы. [30] Внутренний битовый массив удаляется после запроса. Если в таблице слишком много строк для использования 1 бита на строку, вместо этого создается растровое изображение с потерями, с одним битом на страницу диска. В этом случае растровое изображение используется только для определения страниц для выборки; затем критерии фильтрации применяются ко всем строкам на соответствующих страницах.
Рекомендации
- Заметки
- ^ Индекс Bitmap против индекса B-дерева: что и когда? , Вивек Шарма, Oracle Technical Network.
- ^ Джон Ву (2007). «Аннотированные ссылки на растровый индекс» . Архивировано из оригинала на 2012-06-30.
- ^ FastBit
- ^ Библиотека С ++ для растровых индексов Lemur
- ^ Ревущие растровые изображения
- ^ Цзяньго Ван; Чунбин Линь; Яннис Папаконстантину; Стивен Суонсон. «Экспериментальное исследование сжатия растровых изображений по сравнению со сжатием с инвертированным списком» . 2017. doi: 10.1145 / 3035918.3064007
- ^ Т. Джонсон (1999). «Измерения производительности сжатых индексов растровых изображений» (PDF) . В Малкольме П. Аткинсоне; Мария Е. Орловска ; Патрик Вальдурье; Стэнли Б. Здоник; Майкл Л. Броди (ред.). VLDB'99, Материалы 25-й Международной конференции по очень большим базам данных, 7–10 сентября 1999 г., Эдинбург, Шотландия, Великобритания . Морган Кауфманн. С. 278–89. ISBN 978-1-55860-615-9.
- ^ Ву К., Отоо Э, Шошани А. (5 марта 2004 г.). «О производительности растровых индексов для атрибутов высокой мощности» (PDF) .
- ^ Chambi, S .; Lemire, D .; Kaser, O .; Годин Р. (2016). «Лучшая производительность растровых изображений с ревущими растровыми изображениями». Программное обеспечение: практика и опыт . 46 (5): 709–719. arXiv : 1402.6407 . DOI : 10.1002 / spe.2325 . S2CID 1139669 .
- ^ Сжатие данных с выравниванием по байтам
- ^ Метод сжатия растрового изображения с выравниванием по словам, структура данных и устройство
- ^ ван Шайк, Себастьян; де Моор, Оге (2011). «Структура данных достижимости с эффективным использованием памяти посредством сжатия битовых векторов» . Материалы международной конференции 2011 г. по управлению данными . SIGMOD '11. Афины, Греция: ACM. С. 913–924. DOI : 10.1145 / 1989323.1989419 . ISBN 978-1-4503-0661-4.
- ^ а б Дележ Ф., Педерсен ТБ (2010). «Гибрид с выравниванием по словам в списке позиций: оптимизация места и производительности для сжатых растровых изображений» (PDF) . Иоана Манолеску, Стефано Спаккапьетра, Йенс Тойбнер, Масару Китсурегава, Ален Леже, Феликс Науманн, Анастасия Айламаки, Фатьма Озкан (ред.). EDBT '10, Труды 13-й Международной конференции по расширению технологий баз данных . Нью-Йорк, Нью-Йорк, США: ACM. С. 228–39. DOI : 10.1145 / 1739041.1739071 . ISBN 978-1-60558-945-9. S2CID 12234453 .
- ^ а б Ф. Фуско; М. Стоклин; М. Влахос (сентябрь 2010 г.). «NET-FLi: сжатие, архивирование и индексирование потокового сетевого трафика на лету» (PDF) . Proc. VLDB Endow . 3 (1-2): 1382–93. DOI : 10.14778 / 1920841.1921011 . S2CID 787443 .
- ^ а б Lemire, D .; Kaser, O .; Ауиш, К. (2010). «Сортировка улучшает индексы растровых изображений с выравниванием по словам». Инженерия данных и знаний . 69 : 3–28. arXiv : 0901.3751 . DOI : 10.1016 / j.datak.2009.08.006 . S2CID 6297890 .
- ^ Сжатый: Сжатый 'п' наборный Integer Set архивации 28 мая 2011, в Wayback Machine
- ^ а б Колантонио А., Ди Пьетро Р. (31 июля 2010 г.). «Краткий: сжатый и составной целочисленный набор» (PDF) . Письма об обработке информации . 110 (16): 644–50. arXiv : 1004.0403 . DOI : 10.1016 / j.ipl.2010.05.018 . S2CID 8092695 . Архивировано из оригинального (PDF) 22 июля 2011 года . Проверено 2 февраля 2011 года .
- ^ Ву К., Отоо Э.Дж., Шошани А. (2001). «Сравнение производительности растровых индексов» (PDF) . В Энрике Пакес, Лин Лю, Дэвид Гроссман (ред.). CIKM '01 Материалы десятой международной конференции по управлению информацией и знаниями . Нью-Йорк, Нью-Йорк, США: ACM. С. 559–61. DOI : 10.1145 / 502585.502689 . ISBN 978-1-58113-436-0. S2CID 10974671 .
- ^ Д. Лемир; О. Касер; К. Ауиш (январь 2010 г.). «Сортировка улучшает индексы растровых изображений с выравниванием по словам». Инженерия данных и знаний . 69 (1): 3–28. arXiv : 0901.3751 . DOI : 10.1016 / j.datak.2009.08.006 . S2CID 6297890 .
- ^ а б C.-Y. Чан; Ю. Е. Иоаннидис (1998). «Дизайн и оценка растровых индексов» (PDF) . В Ашутоше Тивари; Майкл Франклин (ред.). Материалы международной конференции ACM SIGMOD 1998 г. по управлению данными (SIGMOD '98) . Нью-Йорк, Нью-Йорк, США: ACM. С. 355–6. DOI : 10.1145 / 276304.276336 .
- ^ C.-Y. Чан; Ю. Е. Иоаннидис (1999). «Эффективная схема кодирования растровых изображений для запросов выбора» (PDF) . Материалы международной конференции ACM SIGMOD 1999 г. по управлению данными (SIGMOD '99) . Нью-Йорк, Нью-Йорк, США: ACM. С. 215–26. DOI : 10.1145 / 304182.304201 .
- ^ ЧП О'Нил; Д. Квасс (1997). «Повышение производительности запросов с помощью индексов вариантов». У Джоан М. Пекман; Судха Рам; Майкл Франклин (ред.). Материалы международной конференции ACM SIGMOD 1997 года по управлению данными (SIGMOD '97) . Нью-Йорк, Нью-Йорк, США: ACM. С. 38–49. DOI : 10.1145 / 253260.253268 .
- ^ Н. Кудас (2000). «Экономичное индексирование растровых изображений». Материалы девятой международной конференции по управлению информацией и знаниями (CIKM '00) . Нью-Йорк, Нью-Йорк, США: ACM. С. 194–201. DOI : 10.1145 / 354756.354819 . ISBN 978-1581133202. S2CID 7504216 .
- ^ Spiegler I; Мааян Р. (1985). «Соображения по хранению и извлечению двоичных баз данных». Обработка информации и управление . 21 (3): 233–54. DOI : 10.1016 / 0306-4573 (85) 90108-6 .
- ^ О'Нил, Патрик (1987). «Архитектура и характеристики модели 204». У Дитера Гоулика; Марк Н. Хейни; Андреас Рейтер (ред.). Труды 2-го международного семинара по высокопроизводительным системам транзакций . Лондон, Великобритания: Springer-Verlag. С. 40–59.
- ^ Д. Ринфрет; П. О'Нил; Э. О'Нил (2001). «Арифметика побитовых индексов». В Тимосе Селлисе (ред.). Материалы международной конференции ACM SIGMOD 2001 г. по управлению данными (SIGMOD '01) . Нью-Йорк, Нью-Йорк, США: ACM. С. 47–57. DOI : 10.1145 / 375663.375669 .
- ^ Э. О'Нил; П. О'Нил; К. Ву (2007). «Варианты дизайна растровых индексов и их влияние на производительность» (PDF) . 11-й Международный симпозиум по проектированию баз данных и приложениям (IDEAS 2007) . С. 72–84. DOI : 10.1109 / IDEAS.2007.19 . ISBN 978-0-7695-2947-9.
- ^ Алексей Боленок (09.05.2009). «Создание индексов» .
- ^ Егор Тимошенко. «О минимальных наборах указателей» (PDF) .
- ^ Том Лейн (2005-12-26). «Re: Индексы Bitmap и т . Д.» . Списки рассылки PostgreSQL . Проверено 6 апреля 2007 .
- Библиография
- О'Коннелл, С. (2005). «Примечания к курсу расширенных баз данных». Саутгемптон : Саутгемптонский университет . Цитировать журнал требует
|journal=
( помощь ) - О'Нил, П .; О'Нил, Э. (2001). «Принципы баз данных, программирование и производительность». Сан-Франциско : Издательство Морган Кауфманн . Цитировать журнал требует
|journal=
( помощь ) - Закер, М .; Phon-Amnuaisuk, S .; Haw, SC (2008). «Адекватный дизайн для систем хранилищ больших данных: растровый индекс по сравнению с индексом в виде B-дерева» (PDF) . Международный журнал компьютеров и коммуникаций . 2 (2) . Проверено 7 января 2010 .