суббота, 21 мая 2016 г.

MUMPS: Битмап индекс (bitmap)

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

Набором идентификаторов является битовая последовательность, в которой идентификатору строки соответствует положение бита в соответствии с его величиной. Наличие записи с заданным значением атрибута отмечается 1, отсутствие - 0 или пустым хвостом. Положим, что есть три записи:
1   шарик    красный    12
2   шарик    синий       5
3   кубик    красный     7
4   кубик    синий       3
В этом случае есть 4 идентификатора, их значения рассматриваются как позиции битов в битовой карте. В карте получается в данном случае 4 бита. По атрибуту фигура два различных значения, поэтому в этом индексе будет две карты. То же самое по атрибуту цвет.
Индекс по фигуре
значение атрибута     биты  0  1  2  3  4
шарик                       0  1  1  0  0
кубик                       0  0  0  1  1
Индекс по цвету
значение атрибута     биты  0  1  2  3  4
красный                     0  1  0  1  0
синий                       0  0  1  0  1
Чтобы использовать битовые карты, база данных должна поддерживать операции с битовыми строками. Это может быть либо встроенный функционал, либо быть реализован с помощью какого-либо модуля расширения. В примере будем использовать функции $bit из состава Cache или MiniM.

Операции получения идентификаторов строк по значениям атрибутов сводятся к использованию битовых операций с битовыми картами и выборке из получившейся битовой карты позиций ненулевых битов. Значения этих позиций считаются идентификаторами строк.

К особенностям битовых индексов относится то, что они могут быть, как и простые индексы, составными, но не могут быть кластерными. Другим ограничением является то, что идентификатором строки данных должно быть строго натуральное число. В большинстве систем второе ограничение совершенно незаметно, поскольку идентификаторы и без того поддерживаются в автоинкрементном режиме.

Битовые индексы и простые индексы по одной и той же таблице могут быть совмещены. Но если для таблицы используется кластерный индекс, то битовый индекс для нее уже не может быть применен, поскольку идентификатор строки фактически нечисловой. Совмещение и одновременное применение простых и битовых индексов выполняется алгоритмически. Также может быть организована многоиндексная выборка совместно из нескольких простых и битовых индексов.

Небольшой пример реализации битового индекса:
ind04 ; битовые индексы, автоматическое поддержание идентификатора
 q
CreateRecords()
 k ^Index
 k ^Data
 n i,Figures,Colors,Counts,Figure,Color,Count,id
 s Figures="квадрат~круг~отрезок~треугольник"
 s Colors="красный~зелёный~синий~белый"
 s Counts="2~5~12~8"
 f i=1:1:12 d
 . s Figure=$p(Figures,"~",$r(4)+1)
 . s Color=$p(Colors,"~",$r(4)+1)
 . s Count=$p(Counts,"~",$r(4)+1)
 . s id=$$InsertRecord(Figure_"~"_Color_"~"_Count)
 q
InsertRecord(RecordValues)
 n id s id=$i(^Data)
 l +^Data(id)
 s ^Data(id)=RecordValues
 d InsertIndexRecords(id,RecordValues)
 l -^Data(id)
 q id
DeleteRecord(id)
 q:'$d(^Data(id))
 l +^Data(id)
 n RecordValues s RecordValues=$g(^Data(id))
 d DeleteIndexRecords(id,RecordValues)
 k ^Data(id)
 l -^Data(id)
 q
UpdateRecord(id,RecordValues)
 q:'$d(^Data(id))
 l +^Data(id)
 n OldRecordValues s OldRecordValues=$g(^Data(id))
 d DeleteIndexRecords(id,OldRecordValues)
 s ^Data(id)=RecordValues
 d InsertIndexRecords(id,RecordValues)
 l -^Data(id)
 q
DeleteIndex(IndexName)
 k ^Index(IndexName)
 q
InsertIndexRecords(id,RecordValues)
 d InsertIndexRecord("Figure",id,$p((RecordValues),"~",1))
 d InsertIndexRecord("Color",id,$p((RecordValues),"~",2))
 d InsertIndexRecord("Count",id,$p((RecordValues),"~",3))
 q
DeleteIndexRecords(id,RecordValues)
 d DeleteIndexRecord("Figure",id,$p((RecordValues),"~",1))
 d DeleteIndexRecord("Color",id,$p((RecordValues),"~",2))
 d DeleteIndexRecord("Count",id,$p((RecordValues),"~",3))
 q
InsertIndexRecord(IndexName,id,Value)
 s $bit(^Index(IndexName,Value),id)=1
 q
DeleteIndexRecord(IndexName,id,Value)
 s $bit(^Index(IndexName,Value),id)=0
 q
Сравнив с рутиной ind01 для простых индексов, несложно понять, что единственные отличия содержатся в функциях InsertIndexRecord и DeleteIndexRecord. Это простой учебный пример, здесь не проверяется что идентификатор действительно является натуральным числом.

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

Простой пример сегментирования битового индекса:
#define BITSEGMENT 32000
InsertIndexRecord(IndexName,id,Value)
 n seg,pos
 s seg=id\$$$BITSEGMENT
 s pos=id#$$$BITSEGMENT
 s $bit(^Index(IndexName,Value,seg),pos)=1
 q
DeleteIndexRecord(IndexName,id,Value)
 n seg,pos
 s seg=id\$$$BITSEGMENT
 s pos=id#$$$BITSEGMENT
 s $bit(^Index(IndexName,Value,seg),pos)=0
 q
Здесь номер сегмента получается делением идентификатора нацело на размер сегмента, а позиция в сегменте определяется остатком от деления нацело идентификатора на размер сегмента. Здесь, поскольку значения идентификаторов рассматриваются как позиции битов, величина сегмента BITSEGMENT означает число бит, а не байт. В зависимости от применяемой версии сервера, размера блока базы данных и метода применяемой упаковки битовой карты эту величину можно подобрать экспериментально более оптимальной, или обратиться в техподдержку MUMPS системы за рекомендациями.

В действительности, это тоже еще не все - у реализации битовых функций в Cach'e и MiniM есть техническая особенность - нельзя использовать нулевое число в качестве позиции в сегменте (третий параметр). При этом число ноль получается для идентификаторов, кратных размеру сегмента. Чтобы избежать этой проблемы, можно поступить просто - после вычисления правильной позиции в сегменте к ней прибавить единицу, например, и во всех функциях, использующих сегменты, учитывать эту неправильную единицу. Например:
#define BITSEGMENT 32000
InsertIndexRecord(IndexName,id,Value)
 n seg,pos
 s seg=id\$$$BITSEGMENT
 s pos=id#$$$BITSEGMENT+1
 s $bit(^Index(IndexName,Value,seg),pos)=1
 q
DeleteIndexRecord(IndexName,id,Value)
 n seg,pos
 s seg=id\$$$BITSEGMENT
 s pos=id#$$$BITSEGMENT+1
 s $bit(^Index(IndexName,Value,seg),pos)=0
 q
К обычным достоинствам битовых индексов относится то, что битовые операции могут быть оптимизированы и могут выполняться значительно быстрее, чем операции с простыми списками. Другим достоинством является относительно меньший объем используемой дисковой памяти, чем в случае обычных индексов.

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

К как преимуществам, так и недостаткам битовых индексов, в зависимости от характера их применения может быть отнесено сочетание их реализации с транзакционностью прикладной системы. Для отдельных реализаций битовых индексов транзакционность системы будет негативным фактором, для других она не имеет значения. Более подробной этот вопрос описывается в главе о транзакциях.

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

Подробнее о книге "MUMPS СУБД"

Комментариев нет:

Отправить комментарий