Индекс растрового изображения - Bitmap index

А индекс растрового изображения особый вид индекс базы данных который использует растровые изображения.

Растровые индексы традиционно считались подходящими для низкий-мощность столбцы, которые имеют небольшое количество различных значений, абсолютно или относительно количества записей, содержащих данные. Крайний случай малой мощности Логические данные (например, есть ли у жителя города доступ в Интернет?), который имеет два значения: True и False. Использование индексов Bitmap битовые массивы (обычно называемые растровыми изображениями) и отвечайте на запросы, выполняя побитовые логические операции на этих растровых изображениях. Индексы Bitmap имеют значительное преимущество в пространстве и производительности по сравнению с другими структурами для запроса таких данных. Их недостаток в том, что они менее эффективны, чем традиционные. B-дерево индексы для столбцов, данные которых часто обновляются: следовательно, они чаще используются в системах только для чтения, которые специализируются на быстрых запросах - например, в хранилищах данных, и обычно не подходят для онлайн-обработка транзакций Приложения.

Некоторые исследователи утверждают, что растровые индексы также полезны для данных с умеренным или даже большим количеством элементов (например, данных с уникальным значением), доступ к которым осуществляется в режиме только для чтения, а запросы обращаются к нескольким столбцам с растровым индексом, используя И, ИЛИ или XOR операторы широко.[1]

Индексы Bitmap также полезны в хранилище данных заявки на вступление в большой таблица фактов к меньшему таблицы размеров такие как те, что расположены в звездная схема.

Представление на основе растрового изображения также может использоваться для представления структуры данных, которая помечена и направлена ​​атрибутированным мультиграфом, используемым для запросов в графовые базы данных.Эффективное управление графами на основе индексов растровых изображений В статье показано, как представление растрового индекса можно использовать для управления большим набором данных (миллиарды точек данных) и эффективного ответа на запросы, связанные с графом.

пример

Продолжая пример доступа к Интернету, индекс растрового изображения можно логически рассматривать следующим образом:

ИдентификаторHasInternetРастровые изображения
YN
1да10
2Нет01
3Нет01
4Неопределенные00
5да10

Слева, Идентификатор относится к уникальному номеру, присвоенному каждому резиденту, HasInternet - это данные для индексации, содержимое индекса растрового изображения отображается в виде двух столбцов под заголовком растровые изображения. Каждый столбец на левой иллюстрации представляет собой битовая карта в индексе растрового изображения. В данном случае таких растровых изображений два, одно для "имеет Интернет". да и один для "есть интернет" Нет. Легко видеть, что каждый бит в растровом изображении Y показывает, относится ли данная строка к человеку, имеющему доступ в Интернет. Это простейшая форма растрового индекса. Большинство столбцов будут иметь более разные значения. Например, сумма продаж, вероятно, будет иметь гораздо большее количество различных значений. Вариации индекса растрового изображения также могут эффективно индексировать эти данные. Кратко рассмотрим три таких варианта.

Примечание. Многие из цитируемых здесь ссылок можно найти по адресу (Джон Ву (2007) ).[2] Для тех, кому может быть интересно поэкспериментировать с некоторыми из упомянутых здесь идей, многие из них реализованы в программном обеспечении с открытым исходным кодом, таком как FastBit,[3] Библиотека C ++ для растровых индексов Lemur,[4] библиотека Java Roaring Bitmap[5] и Apache Hive Система хранилищ данных.

Сжатие

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

Программное обеспечение может компресс каждое растровое изображение в растровом индексе для экономии места. По этой теме проделана значительная работа.[7][8]Хотя есть исключения, такие как растровые изображения Ревущего,[9] Алгоритмы сжатия растровых изображений обычно используют кодирование длин серий, например, растровый код с байтовым выравниванием,[10] гибридный код с выравниванием по словам,[11] гибридное сжатие с разделением по словам (PWAH),[12] гибридное выравнивание слов списка позиций,[13] сжатый адаптивный индекс (COMPAX),[14] Расширенный гибрид с выравниванием по словам (EWAH) [15] и COmpressed 'N' Composable Integer 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 различных значений, используя точечные рисунки журнала (C) с двоичное кодирование.[22]

Это уменьшает количество растровых изображений, дополнительно экономя место, но для ответа на любой запрос необходимо получить доступ к большинству растровых изображений. Это делает его потенциально не таким эффективным, как сканирование вертикальной проекции базовых данных, также известной как материализованный вид или индекс проекции. Поиск оптимального метода кодирования, который уравновешивает (произвольную) производительность запроса, размер индекса и обслуживание индекса, остается сложной задачей.

Не принимая во внимание сжатие, Чан и Иоаннидис проанализировали класс методов многокомпонентного кодирования и пришли к выводу, что двухкомпонентное кодирование находится на изломе кривой зависимости производительности от размера индекса и, следовательно, представляет собой лучший компромисс между размером индекса и производительность запроса.[20]

Биннинг

Для столбцов с большим количеством элементов полезно группировать значения, где каждая ячейка охватывает несколько значений, и строить растровые изображения для представления значений в каждой ячейке. Такой подход уменьшает количество используемых растровых изображений независимо от метода кодирования.[23] Однако сгруппированные индексы могут отвечать только на некоторые запросы без изучения базовых данных. Например, если корзина охватывает диапазон от 0,1 до 0,2, тогда, когда пользователь запрашивает все значения меньше 0,15, все строки, попадающие в корзину, являются возможными попаданиями и должны быть проверены, чтобы убедиться, что они на самом деле меньше 0,15. . Процесс проверки базовых данных известен как проверка кандидата. В большинстве случаев время, используемое для проверки кандидата, значительно больше, чем время, необходимое для работы с индексом битовой карты. Следовательно, индексы с группировкой показывают нестабильную производительность. Они могут быть очень быстрыми для некоторых запросов, но намного медленнее, если запрос не точно соответствует корзине.

История

Концепция растрового индекса была впервые представлена ​​профессорами Израилем Шпиглером и Рафи Мааяном в их исследовании «Вопросы хранения и извлечения двоичных баз данных», опубликованном в 1985 году.[24] Первым коммерческим продуктом базы данных, реализовавшим растровый индекс, была компания Computer Corporation of America. Модель 204. Патрик О'Нил опубликовал статью об этой реализации в 1987 году.[25] Эта реализация представляет собой гибрид между базовым индексом битовой карты (без сжатия) и списком идентификаторов строк (RID-list). В целом индекс организован как B + дерево. Когда мощность столбца низкая, каждый листовой узел B-дерева будет содержать длинный список RID. В этом случае для представления списков RID в виде растровых изображений требуется меньше места. Поскольку каждое растровое изображение представляет одно отдельное значение, это основной индекс растрового изображения. По мере увеличения количества элементов столбца каждое растровое изображение становится разреженным, и для хранения растровых изображений может потребоваться больше дискового пространства, чем для хранения того же содержимого, что и списки RID. В этом случае он переключается на использование RID-списков, что делает его B + дерево показатель.[26][27]

Растровые изображения в памяти

Одна из самых веских причин для использования индексов растровых изображений заключается в том, что полученные из них промежуточные результаты также являются растровыми изображениями и могут быть эффективно повторно использованы в дальнейших операциях для ответа на более сложные запросы. Многие языки программирования поддерживают это как структуру данных битового массива. Например, в Java есть BitSet класс.

Некоторые системы баз данных, которые не предлагают постоянные индексы растровых изображений, используют растровые изображения внутри для ускорения обработки запросов. Например, PostgreSQL версии 8.1 и более поздние реализуют оптимизацию "сканирования индекса растрового изображения" для ускорения произвольно сложных логические операции между доступными индексами в одной таблице.

Для таблиц с большим количеством столбцов общее количество различных индексов, удовлетворяющих всем возможным запросам (с условиями фильтрации равенства для любого из полей), растет очень быстро, что определяется следующей формулой:

.[28][29]

Сканирование растрового индекса объединяет выражения для разных индексов, поэтому для поддержки всех возможных запросов к таблице требуется только один индекс для каждого столбца.

Применение этой стратегии доступа к индексам B-дерева также позволяет комбинировать запросы диапазона по нескольким столбцам. В этом подходе временное растровое изображение в памяти создается с одним немного для каждой строки в таблице (1 МиБ таким образом может хранить более 8 миллионов записей). Затем результаты каждого индекса объединяются в растровое изображение с помощью побитовые операции. После оценки всех условий растровое изображение содержит «1» для строк, соответствующих выражению. Наконец, растровое изображение просматривается и выбираются совпадающие строки. Помимо эффективного комбинирования индексов, это также улучшает местонахождение ссылки доступов к таблице, потому что все строки последовательно выбираются из основной таблицы.[30] Внутреннее растровое изображение отбрасывается после запроса. Если в таблице слишком много строк для использования 1 бита на строку, вместо этого создается растровое изображение с потерями, с одним битом на страницу диска. В этом случае растровое изображение используется только для определения страниц для выборки; затем критерии фильтрации применяются ко всем строкам на соответствующих страницах.

использованная литература

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