Индекс растрового изображения
Растровый индекс — это особый вид индекса базы данных , в котором используются растровые изображения .
Традиционно считалось, что битовые индексы хорошо работают для с низкой мощностью столбцов , которые имеют небольшое количество различных значений, либо абсолютно, либо относительно количества записей, содержащих данные. Крайним случаем низкой мощности являются логические данные (например, есть ли у жителя города доступ в Интернет?), которые имеют два значения: True и False. Индексы растровых изображений используют битовые массивы (обычно называемые растровыми изображениями) и отвечают на запросы, выполняя побитовые логические операции над этими растровыми изображениями. Битовые индексы имеют значительное преимущество в пространстве и производительности по сравнению с другими структурами для запроса таких данных. Их недостатком является то, что они менее эффективны, чем традиционные индексы B-дерева для столбцов, данные которых часто обновляются: следовательно, они чаще используются в системах только для чтения, которые специализируются на быстрых запросах, например, в хранилищах данных и, как правило, непригодны для для обработки онлайн-транзакций приложения .
Некоторые исследователи утверждают, что индексы растровых изображений также полезны для данных средней или даже высокой мощности (например, данных с уникальным значением), доступ к которым доступен только для чтения, а запросы обращаются к нескольким столбцам, индексированным по растровым изображениям, с использованием операторов AND , OR или XOR. операторы широко. [1]
Растровые индексы также полезны в приложениях хранилищ данных для объединения большой таблицы фактов с таблицами меньшего размера, например таблицами, расположенными в звездообразной схеме .
Пример
[ редактировать ]Продолжая пример доступа в Интернет, растровый индекс можно логически рассматривать следующим образом:
| Идентификатор | ХасИнтернет | Растровые изображения | |
|---|---|---|---|
| И | Н | ||
| 1 | Да | 1 | 0 |
| 2 | Нет | 0 | 1 |
| 3 | Нет | 0 | 1 |
| 4 | Не указано | 0 | 0 |
| 5 | Да | 1 | 0 |
Слева Identifier относится к уникальному номеру, присвоенному каждому резиденту, HasInternet — это данные, подлежащие индексированию, содержимое индекса растрового изображения отображается в виде двух столбцов под заголовком bitmaps . Каждый столбец на левом рисунке под заголовком «Растровые изображения» представляет собой растровое изображение в индексе растрового изображения. В этом случае есть два таких растровых изображения: одно для «есть Интернет» Да и другое для «есть Интернет» Нет . Легко заметить, что каждый бит растрового изображения Y показывает, относится ли определенная строка к человеку, имеющему доступ в Интернет. Это простейшая форма растрового индекса. Большинство столбцов будут иметь более четкие значения. Например, сумма продаж, скорее всего, будет иметь гораздо большее количество различных значений. Вариации индекса растрового изображения также могут эффективно индексировать эти данные. Мы кратко рассмотрим три таких варианта.
Примечание. Многие из цитируемых здесь ссылок приведены в ( John Wu (2007) ). [2] Для тех, кому может быть интересно поэкспериментировать с некоторыми из упомянутых здесь идей, многие из них реализованы в программном обеспечении с открытым исходным кодом, таком как FastBit. [3] библиотека C++ растрового индекса Lemur, [4] Java-библиотека Roaring Bitmap [5] и система хранилища данных Apache Hive .
Сжатие
[ редактировать ]По историческим причинам сжатие растровых изображений и сжатие инвертированных списков были разработаны как отдельные направления исследований и только позже были признаны решающими по существу одну и ту же проблему. [6]
Программное обеспечение может сжимать каждое растровое изображение в индексе растрового изображения для экономии места. На эту тему проделана значительная работа. [7] [8] Хотя есть исключения, такие как ревущие растровые изображения, [9] Алгоритмы сжатия растровых изображений обычно используют кодирование длин серий , такое как код растрового изображения с выравниванием по байтам. [10] гибридный код, выровненный по словам, [11] сжатие Partitioned Word-Aligned Hybrid (PWAH), [12] Гибрид с выравниванием по словам в списке позиций, [13] сжатый адаптивный индекс (COMPAX), [14] Усовершенствованный гибрид с выравниванием по словам (EWAH) [15] и набор сжатых составных целых чисел 'N' (CONCISE). [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] Первым коммерческим продуктом базы данных, реализовавшим растровый индекс, была модель 204 компании Computer Corporation of America . Патрик О'Нил опубликовал статью об этой реализации в 1987 году. [25] Эта реализация представляет собой гибрид базового растрового индекса (без сжатия) и списка идентификаторов строк (RID-список). В целом индекс организован в виде B+дерева . Когда мощность столбца низкая, каждый листовой узел B-дерева будет содержать длинный список RID. В этом случае для представления списков RID в виде растровых изображений требуется меньше места. Поскольку каждое растровое изображение представляет одно отдельное значение, это базовый индекс растрового изображения. По мере увеличения мощности столбца каждое растровое изображение становится разреженным, и для хранения растровых изображений может потребоваться больше дискового пространства, чем для хранения того же содержимого в виде списков RID. В этом случае он переключается на использование RID-списков, что делает его индексом B+дерева . [26] [27]
Растровые изображения в памяти
[ редактировать ]Одна из веских причин для использования растровых индексов заключается в том, что полученные с их помощью промежуточные результаты также являются растровыми изображениями и могут эффективно повторно использоваться в дальнейших операциях для ответа на более сложные запросы. Многие языки программирования поддерживают это как структуру данных битового массива. Например, в Java есть BitSet сорт.
Некоторые системы баз данных, которые не предлагают постоянные растровые индексы, используют растровые изображения внутри себя для ускорения обработки запросов. Например, PostgreSQL версии 8.1 и более поздних версий реализует оптимизацию «сканирования растрового индекса» для ускорения произвольно сложных логических операций между доступными индексами в одной таблице.
Для таблиц со многими столбцами общее количество различных индексов для удовлетворения всех возможных запросов (с условиями фильтрации равенства по любому из полей) растет очень быстро и определяется следующей формулой:
![{\displaystyle \mathbf {C} _{n}^{\left[{\frac {n}{2}}\right]}\equiv {\frac {n!}{\left(n-\left[{ \frac {n}{2}}\right]\right)!\left[{\frac {n}{2}}\right]!}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/9160ac60d370e6a8b56c98a5ca0d30e8679b89d5)
Сканирование индекса растрового изображения объединяет выражения по разным индексам, поэтому для поддержки всех возможных запросов к таблице требуется только один индекс на столбец.
Применение этой стратегии доступа к индексам B-дерева также позволяет комбинировать запросы диапазона по нескольким столбцам. При таком подходе в памяти создается временное растровое изображение с одним битом для каждой строки таблицы (таким образом, в 1 МБ можно хранить более 8 миллионов записей). Далее результаты каждого индекса объединяются в растровое изображение с помощью побитовых операций . После оценки всех условий растровое изображение содержит «1» для строк, соответствующих выражению. Наконец, растровое изображение просматривается и извлекаются соответствующие строки. Помимо эффективного объединения индексов, это также улучшает локальность ссылок при доступе к таблице, поскольку все строки извлекаются последовательно из основной таблицы. [30] Внутреннее растровое изображение отбрасывается после запроса. Если в таблице слишком много строк, чтобы использовать 1 бит на строку, вместо этого создается растровое изображение с потерями, с одним битом на страницу диска. В этом случае растровое изображение используется только для определения того, какие страницы следует извлечь; критерии фильтра затем применяются ко всем строкам на соответствующих страницах.
Ссылки
[ редактировать ]- Примечания
- ^ Индекс растрового изображения против индекса B-дерева: какой и когда? , Вивек Шарма, Техническая сеть Oracle.
- ^ Джон Ву (2007). «Аннотированные ссылки на индекс растровых изображений» . Архивировано из оригинала 30 июня 2012 г.
- ^ ФастБит
- ^ Библиотека C++ индекса растровых изображений Lemur
- ^ Ревущие растровые изображения
- ^ Цзяньго Ван; Чунбин Лин; Яннис Папаконстантину; Стивен Суонсон. «Экспериментальное исследование сжатия растровых изображений по сравнению со сжатием инвертированного списка». Архивировано 7 декабря 2019 г. на Wayback Machine .2017.дои: 10.1145/3035918.3064007
- ^ Т. Джонсон (1999). «Измерения производительности сжатых индексов растровых изображений» (PDF) . У Малкольма П. Аткинсона; Мария Евгеньевна Орловская ; Патрик Вальдурье; Стэнли Б. Здоник; Майкл Л. Броди (ред.). VLDB'99, Материалы 25-й Международной конференции по очень большим базам данных, 7–10 сентября 1999 г., Эдинбург, Шотландия, Великобритания . Морган Кауфманн. стр. 278–89. ISBN 978-1-55860-615-9 .
- ^ Ву К., Отоо Э., Шошани А. (5 марта 2004 г.). «О производительности индексов растровых изображений для атрибутов высокой мощности» (PDF) .
- ^ Чамби, С.; Лемир, Д.; Казер, О.; Годин, Р. (2016). «Повышение производительности растровых изображений с помощью растровых изображений Roaring». Программное обеспечение: практика и опыт . 46 (5): 709–719. arXiv : 1402.6407 . дои : 10.1002/спе.2325 . S2CID 1139669 .
- ^ Сжатие данных с выравниванием по байтам
- ^ Метод сжатия растровых изображений с выравниванием по словам, структура данных и устройство
- ^ ван Шайк, Себастьян; де Мур, Оге (2011). «Структура данных достижимости с эффективным использованием памяти посредством сжатия битового вектора» . Материалы международной конференции по управлению данными 2011 года . СИГМОД '11. Афины, Греция: ACM. стр. 913–924. дои : 10.1145/1989323.1989419 . ISBN 978-1-4503-0661-4 .
- ^ Jump up to: а б Дельеж Ф., Педерсен Т.Б. (2010). «Гибрид с выравниванием по словам в списке позиций: оптимизация пространства и производительности для сжатых растровых изображений» (PDF) . В Иоана Манолеску, Стефано Спаккапьетра, Йенс Тойбнер, Масару Кицурегава, Ален Леже, Феликс Науманн, Анастасия Айламаки, Фатма Озджан (ред.). EDBT '10, Материалы 13-й Международной конференции по расширению технологий баз данных . Нью-Йорк, штат Нью-Йорк, США: ACM. стр. 228–39. дои : 10.1145/1739041.1739071 . ISBN 978-1-60558-945-9 . S2CID 12234453 .
- ^ Jump up to: а б Ф. Фуско; М. Стеклин; М. Влахос (сентябрь 2010 г.). «NET-FLi: оперативное сжатие, архивирование и индексирование потокового сетевого трафика» (PDF) . Учеб. ВЛДБ Эндоу . 3 (1–2): 1382–93. дои : 10.14778/1920841.1921011 . S2CID 787443 .
- ^ Jump up to: а б Лемир, Д.; Казер, О.; Ауиш, К. (2010). «Сортировка улучшает индексы растровых изображений, выравниваемые по словам». Инженерия данных и знаний . 69 : 3–28. arXiv : 0901.3751 . дои : 10.1016/j.datak.2009.08.006 . S2CID 6297890 .
- ^ Краткое описание: сжатый и составной набор целых чисел. Архивировано 28 мая 2011 г., в Wayback Machine.
- ^ Jump up to: а б Колантонио А., Ди Пьетро Р. (31 июля 2010 г.). «Кратко: сжатый и составной набор целых чисел» (PDF) . Письма об обработке информации . 110 (16): 644–50. arXiv : 1004.0403 . дои : 10.1016/j.ipl.2010.05.018 . S2CID 8092695 . Архивировано из оригинала (PDF) 22 июля 2011 года . Проверено 2 февраля 2011 г.
- ^ Ву К, Отоо Э.Дж., Шошани А. (2001). «Сравнение производительности растровых индексов» (PDF) . Энрике Пакес, Лин Лю , Дэвид Гроссман (ред.). CIKM '01 Материалы десятой международной конференции по управлению информацией и знаниями . Нью-Йорк, штат Нью-Йорк, США: ACM. стр. 559–61. дои : 10.1145/502585.502689 . ISBN 978-1-58113-436-0 . S2CID 10974671 .
- ^ Д. Лемир; О. Казер; К. Ауиш (январь 2010 г.). «Сортировка улучшает индексы растровых изображений, выравниваемые по словам». Инженерия данных и знаний . 69 (1): 3–28. arXiv : 0901.3751 . дои : 10.1016/j.datak.2009.08.006 . S2CID 6297890 .
- ^ Jump up to: а б К.-Ю. Чан; Ю.Е. Иоаннидис (1998). «Проектирование и оценка растрового индекса» (PDF) . В Ашутош Тивари; Майкл Франклин (ред.). Материалы международной конференции ACM SIGMOD 1998 года по управлению данными (SIGMOD '98) . Нью-Йорк, штат Нью-Йорк, США: ACM. стр. 355–6. дои : 10.1145/276304.276336 . ISBN 0897919955 .
- ^ К.-Ю. Чан; Ю.Е. Иоаннидис (1999). «Эффективная схема кодирования растровых изображений для запросов выбора» (PDF) . Материалы международной конференции ACM SIGMOD 1999 г. по управлению данными (SIGMOD '99) . Нью-Йорк, штат Нью-Йорк, США: ACM. стр. 215–26. дои : 10.1145/304182.304201 . ISBN 1581130848 .
- ^ ЧП О'Нил; Д. Касс (1997). «Улучшенная производительность запросов с помощью индексов вариантов». У Джоан М. Пекман; Судха Рам; Майкл Франклин (ред.). Материалы международной конференции ACM SIGMOD 1997 г. по управлению данными (SIGMOD '97) . Нью-Йорк, штат Нью-Йорк, США: ACM. стр. 38–49. дои : 10.1145/253260.253268 . ISBN 0897919114 .
- ^ Н. Кудас (2000). «Экономичное индексирование растровых изображений». Материалы девятой международной конференции по управлению информацией и знаниями (CIKM '00) . Нью-Йорк, штат Нью-Йорк, США: ACM. стр. 194–201. дои : 10.1145/354756.354819 . ISBN 978-1581133202 . S2CID 7504216 .
- ^ Шпиглер I; Мааян Р. (1985). «Аспекты хранения и поиска из баз двоичных данных». Обработка информации и управление . 21 (3): 233–54. дои : 10.1016/0306-4573(85)90108-6 .
- ^ О'Нил, Патрик (1987). «Архитектура и производительность модели 204». У Дитера Гаулика; Марк Н. Хейни; Андреас Рейтер (ред.). Материалы 2-го международного семинара по высокопроизводительным транзакционным системам . Лондон, Великобритания: Springer-Verlag. стр. 40–59.
- ^ Д. Ринфрет; П. О'Нил; Э. О'Нил (2001). «Побитовая индексная арифметика». В Тимосе Селлисе (ред.). Материалы международной конференции ACM SIGMOD 2001 г. по управлению данными (SIGMOD '01) . Нью-Йорк, штат Нью-Йорк, США: ACM. стр. 47–57. дои : 10.1145/375663.375669 . ISBN 1581133324 .
- ^ Э. О'Нил; П. О'Нил; К. Ву (2007). «Выбор дизайна индекса растрового изображения и его влияние на производительность» (PDF) . 11-й Международный симпозиум по разработке баз данных и приложениям (IDEAS 2007) . стр. 72–84. дои : 10.1109/IDEAS.2007.19 . ISBN 978-0-7695-2947-9 .
- ^ Алекс Боленок (9 мая 2009 г.). «Создание индексов» .
- ^ Егор Тимошенко. «О минимальных коллекциях индексов» (PDF) .
- ^ Том Лейн (26 декабря 2005 г.). «Re: Растровые индексы и т. д.» . Списки рассылки PostgreSQL . Проверено 6 апреля 2007 г.
- Библиография
- О'Коннелл, С. (2005). «Конспекты курса продвинутых баз данных». Саутгемптон : Университет Саутгемптона .
{{cite journal}}: Для цитирования журнала требуется|journal=( помощь ) - О'Нил, П.; О'Нил, Э. (2001). «Принципы баз данных, программирование и производительность». Сан-Франциско : Издательство Морган Кауфманн .
{{cite journal}}: Для цитирования журнала требуется|journal=( помощь ) - Закер, М.; Фон-Амнуайсюк, С.; Хау, Южная Каролина (2008). «Адекватный дизайн для больших систем хранилищ данных: индекс растрового изображения и индекс B-дерева» (PDF) . Международный журнал компьютеров и коммуникаций . 2 (2) . Проверено 7 января 2010 г.