Резаный битовый индекс представляет собой совокупность структур, отображающих
фрагменты значений атрибутов на набор идентификаторов строк данных. Структурно
аналогичен битовому индексу (bitmap), но представляет собой N битовых индексов,
работающих для всех значений атрибутов. Индексации подвергаются только числовые
атрибуты либо те, которые могут быть приведены к числовому виду. Значение N
зависит от типа выбранного атрибута.
В карту входят отдельные карты по каждому биту значения атрибута. В примере рассмотрим тип натуральное число. Само число в нашем примере рассматривается как 32-битное без знака. Берутся отдельные биты числа и по этим битам строится 32 отдельных битовых индекса.
При поиске по индексу производится обратная операция - выясняется какие биты в значении атрибута должны быть единичными и какие нулевыми и конструируется соответствующая битовая операция. Операция применяется к всем 32 битовым картам. В результате производится хранение всех значений индексов в фактически ограниченном дисковом пространстве. Причем объем хранения примерно пропорционален количеству строк данных и не зависит от кардинальности индексируемых атрибутов.
Приведем пример раскладки значений атрибутов по bit-slice индексу.
Как и для битмап (bitmap) индексов, при реальном построении движка, использующего bit-slice индексы, из-за априори большого числа записей следует прибегать к сегментированию битовых карт. Схема сегментирования может быть выбрана, например, такой же как и в предыдущем случае с битмап (bitmap) индексами. Формально говоря, bit-slice индексы могут быть совмещены с традиционными bitmap индексами напрямую при выборе совпадающего параметра размера битового сегмента.
К достоинствам bit-slice индексов по сравнению с bitmap индексами относится меньший занимаемый объем при высоко-кардинальных атрибутах. Фактически, из-за своего структурирования bit-slice индексы стремятся повторно использовать дисковое пространство и битовые карты. При снижении кардинальности атрибутов bit-slice индексы фактически приближаются по соотношению нулевых и единичных битов к битмап индексам или имеют худшие характеристики. На этот факт следует обратить внимание при реализации модулей расширения системы базы данных при реализации битовых операций внешними средствами.
К недостаткам относится большее время на выполнение разборок по битовым картам и сборок обратно, а также ещё большая по сравнению с битовыми индексами вероятность взаимоблокировок процессов. Также к недостаткам относятся увеличенные в 32 раза (в приведенном примере) затраты на распаковку сжатых битовых карт для получения того же результата, что и при использовании битовых индексов.
То преимущество bit-slice индексов, что они потенциально могут занимать меньше места чем битовые, в каких-то случаях может перевесить недостаток, связанный с усложнением выборки. При уменьшении занимаемого дискового пространства ускорение достигается меньшим количеством дисковых операций и, во-вторых, в силу совмещения в битовых картах информации о различных значениях атрибутов, значительно более эффективным использованием кеширования.
Проведенный эксперимент с размером, занимаемым индексами на диске в СУБД Cache подтверждает теоретические рассуждения:
Впрочем, пока Cache и MiniM не имеют такой встроенной поддержки битовой нарезки, но специализированные движки баз данных или специальный модуль расширения вполне могут выполнять такие битовые операции не прибегая к интерпретируемому режиму. В качестве примера применения bit-slice индексов приведем воспроизводимый код для Cache и MiniM, построенный на $bit функциях. Код приводится только в учебных целях.
В таком варианте от функций построения битовых карт отделяются две функции, специфичные для используемого типа атрибута. При добавлении еще одного типа нужно будет просто изменить соответственно функции BitCount и GetBit. При использовании иных типов чем числовые можно значительно сократить битовое представление значения атрибута.
Это пример для односегментных bit-slice индексов. Код приведен без оптимизации, только в учебных целях. Для поддержания разделения по сегментам карт нужно просто скорректировать функции изменения карт:
Наиболее распространенной операцией, где bit-slice индексы дают существенное преимущество, является операция суммирования значений атрибутов в столбик.
Продемонстрируем принцип вычисления суммы по bit-slice индексу на примере найденной bit-slice карты:
Каждое из значений атрибутов есть сумма битов умноженных на степень двойки, соответствующей его позиции. Таким образом, полную сумму всех значений можно получить как сумму сумм битов по каждой позиции (здесь в виде колонки) умноженных на степень двойки для этой позиции. Для получения суммы битов по каждой колонке используется встроенная системная функция $bitcount. Таким образом, для вычисления общей суммы необходимо 5 вызовов функции $bitcount и 5 произведений на степени двойки.
И для вычисления суммы всех чисел необходимо вычислить суммы битов при каждой из степеней двойки, что и выполняется системной функцией $bitcount.
Битовое системное расширение, функция $bitcount, выполняется на нижнем уровне так, что просто возвращает число единиц или нулей. Выполнение счета проводится на нижнем уровне, в кодах процессора, и очень быстро. При увеличении числа записей выигрыш во времени может достигать сотен раз по сравнению с простым сложением в столбик чисел, на получение каждого из которых выполняется обращение к глобали функцией $order.
Одним из наиболее традиционных применений bit-slice индексов для получения ключевого преимущества по скорости работы являются аналитические системы класса OLAP. В них операции выборки и суммирования применяются одновременно к большому числу записей и их атрибутов.
Для битмап и битслайс индексов в примерах используются блокировки, но для операций выполняемых функциями $bit они не требуются, поскольку эти операции проставляют единичный или нулевой бит атомарно. Во время непосредственно выполнения функций $bit никакие другие процессы не могут изменить значение переменной в то же самое время. При откате транзакции операции, выполненные функциями $bit, также откатываются атомарно, не затрагивая другие биты.
К интересным особенностям алгоритма поддержки bit-slice индексов можно отнести то, что обе системы, и Cache и MiniM, при отсутствии установки бита явным образом используют эту позицию как нулевой бит. Эквивалент нулевого бита используется как при дополнении битовой строки, так и при чтении бита за ее пределами. Поэтому, если разделить операции обновления индексов на три вида
Подробнее о книге "MUMPS СУБД"
В карту входят отдельные карты по каждому биту значения атрибута. В примере рассмотрим тип натуральное число. Само число в нашем примере рассматривается как 32-битное без знака. Берутся отдельные биты числа и по этим битам строится 32 отдельных битовых индекса.
При поиске по индексу производится обратная операция - выясняется какие биты в значении атрибута должны быть единичными и какие нулевыми и конструируется соответствующая битовая операция. Операция применяется к всем 32 битовым картам. В результате производится хранение всех значений индексов в фактически ограниченном дисковом пространстве. Причем объем хранения примерно пропорционален количеству строк данных и не зависит от кардинальности индексируемых атрибутов.
Приведем пример раскладки значений атрибутов по bit-slice индексу.
Строки данных id Count Битовое представление атрибута 1 17 00000000000000000000000000010001 2 6 00000000000000000000000000000110 3 5 00000000000000000000000000000101 4 8 00000000000000000000000000001000 5 14 00000000000000000000000000001110 6 18 00000000000000000000000000010010 Индексные записи биты битовые карты, младшие разряды слева 0 0101000 1 0010011 2 0011010 3 0000110 4 0100001 В остальных битовых картах нулиИспользование bit-slice индексов в силу его структуры может быть оправдано не только для числовых атрибутов, но и для любых, для которых возможно битовое представление фиксированной длины, например, даты, номера телефонов, условные коды в виде нескольких символов. Для использования нечислового атрибута для индексации просто потребуются две операции:
- определение максимального количества бит (для корректного дополнения нулями) для выбранного типа атрибута
- получение значащей битовой последовательности по значению атрибута
Как и для битмап (bitmap) индексов, при реальном построении движка, использующего bit-slice индексы, из-за априори большого числа записей следует прибегать к сегментированию битовых карт. Схема сегментирования может быть выбрана, например, такой же как и в предыдущем случае с битмап (bitmap) индексами. Формально говоря, bit-slice индексы могут быть совмещены с традиционными bitmap индексами напрямую при выборе совпадающего параметра размера битового сегмента.
К достоинствам bit-slice индексов по сравнению с bitmap индексами относится меньший занимаемый объем при высоко-кардинальных атрибутах. Фактически, из-за своего структурирования bit-slice индексы стремятся повторно использовать дисковое пространство и битовые карты. При снижении кардинальности атрибутов bit-slice индексы фактически приближаются по соотношению нулевых и единичных битов к битмап индексам или имеют худшие характеристики. На этот факт следует обратить внимание при реализации модулей расширения системы базы данных при реализации битовых операций внешними средствами.
К недостаткам относится большее время на выполнение разборок по битовым картам и сборок обратно, а также ещё большая по сравнению с битовыми индексами вероятность взаимоблокировок процессов. Также к недостаткам относятся увеличенные в 32 раза (в приведенном примере) затраты на распаковку сжатых битовых карт для получения того же результата, что и при использовании битовых индексов.
То преимущество bit-slice индексов, что они потенциально могут занимать меньше места чем битовые, в каких-то случаях может перевесить недостаток, связанный с усложнением выборки. При уменьшении занимаемого дискового пространства ускорение достигается меньшим количеством дисковых операций и, во-вторых, в силу совмещения в битовых картах информации о различных значениях атрибутов, значительно более эффективным использованием кеширования.
Проведенный эксперимент с размером, занимаемым индексами на диске в СУБД Cache подтверждает теоретические рассуждения:
Число записей Число различных Объем хранения, байт
значений атрибута
10000 4 bitmap 116
bit-slice 5396
10000 10000 bitmap 120272
bit-slice 17452
Объем хранения индексируемых данных, 260000
То есть, при увеличении кардинальности атрибута bit-slice индекс намного
эффективнее по объему хранения, чем bitmap индекс, по объему хранения.
Приведенные числа не
пропорциональны параметрам исходных условий, поскольку приведены не
информационная емкость индекса, а объем, занимаемый структурой данных на диске.
Функции $bit в Cache оперируют сжатыми битовыми строками. При чтении строка
распаковывается, при записи снова сжимается. Поэтому объем хранения может
варьироваться еще и в зависимости от состояния индекса, насколько хорошо он
сжимается реализованным алгоритмом.
Впрочем, пока Cache и MiniM не имеют такой встроенной поддержки битовой нарезки, но специализированные движки баз данных или специальный модуль расширения вполне могут выполнять такие битовые операции не прибегая к интерпретируемому режиму. В качестве примера применения bit-slice индексов приведем воспроизводимый код для Cache и MiniM, построенный на $bit функциях. Код приводится только в учебных целях.
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("Count",id,$p((RecordValues),"~",3))
q
DeleteIndexRecords(id,RecordValues)
d DeleteIndexRecord("Count",id,$p((RecordValues),"~",3))
q
InsertIndexRecord(IndexName,id,Value)
n i
l +^Index(IndexName)
f i=0:1:31 d
. s $bit(^Index(IndexName,i),id)=(Value\(2**i))#2
l -^Index(IndexName)
q
DeleteIndexRecord(IndexName,id,Value)
n i
l +^Index(IndexName)
f i=0:1:31 s $bit(^Index(IndexName,i),id)=0
l -^Index(IndexName)
q
Здесь приведен вариант не сегментированного индекса, для построения
сегментированного нужно дополнить структуру и алгоритм вычислением номера
сегмента и смещения в сегменте:
#define BITSEGMENT 32000 InsertIndexRecord(IndexName,id,Value) n i n seg,pos s seg=id\$$$BITSEGMENT s pos=id#$$$BITSEGMENT l +^Index(IndexName) f i=0:1:31 q:'Value d . s $bit(^Index(IndexName,seg,i),pos)=Value#2 . s Value=Value\2 l -^Index(IndexName) q DeleteIndexRecord(IndexName,id,Value) n i n seg,pos s seg=id\$$$BITSEGMENT s pos=id#$$$BITSEGMENT l +^Index(IndexName) f i=0:1:31 s $bit(^Index(IndexName,seg,i),pos)=0 l -^Index(IndexName) qКстати, можно отметить интересную особенность, что при удалении записи собственно значение атрибута при использовании bit-slice (как и bitmap) индексов, вообще говоря, не требуется, поскольку проставление нулевых значений выполняется на все биты, а их количество определяется не значением атрибута, а его типом, тем, сколько бит используется при кодировании атрибута этого типа. Использование значения атрибута позволяет сократить число обращений к индексной глобали, если не проставлять несуществующие значения:
DeleteIndexRecord(IndexName,id,Value) n i n seg,pos s seg=id\$$$BITSEGMENT s pos=id#$$$BITSEGMENT l +^Index(IndexName) f i=0:1:31 q:'Value d . s:Value#2 $bit(^Index(IndexName,seg,i),pos)=0 . s Value=Value\2 l -^Index(IndexName) qПри замене типа с числового на иной, как было описано ранее, нужно использовать не явно заданные выражения получения количества битов, а функции, которые а) определяют число бит для типа и б) получают значения бит для значения атрибута, примерно это может выглядеть так:
DeleteIndexRecord(IndexName,id,Value) n i,len s len=$$BitCount(IndexName) l +^Index(IndexName) f i=0:1:len s $bit(^Index(IndexName,i),id)=0 l -^Index(IndexName) q InsertIndexRecord(IndexName,id,Value) n i,len s len=$$BitCount(IndexName) l +^Index(IndexName) f i=0:1:len d . s $bit(^Index(IndexName,i),id)=$$GetBit(IndexName,Value,i) l -^Index(IndexName) q BitCount(IndexName) q:IndexName="Count" 31 q 0 GetBit(IndexName,Value,i) q:IndexName="Count" (Value\(2**i))#2 q 0
В таком варианте от функций построения битовых карт отделяются две функции, специфичные для используемого типа атрибута. При добавлении еще одного типа нужно будет просто изменить соответственно функции BitCount и GetBit. При использовании иных типов чем числовые можно значительно сократить битовое представление значения атрибута.
Это пример для односегментных bit-slice индексов. Код приведен без оптимизации, только в учебных целях. Для поддержания разделения по сегментам карт нужно просто скорректировать функции изменения карт:
#define BITSEGMENT 32000 InsertIndexRecord(IndexName,id,Value) n i,seg,pos s seg=id\$$$BITSEGMENT s pos=id#$$$BITSEGMENT l +^Index(IndexName) f i=0:1:31 d . s $bit(^Index(IndexName,i,seg),pos)=(Value\(2**i))#2 l -^Index(IndexName) q DeleteIndexRecord(IndexName,id,Value) n i,seg,pos s seg=id\$$$BITSEGMENT s pos=id#$$$BITSEGMENT l +^Index(IndexName) f i=0:1:31 s $bit(^Index(IndexName,i,seg),pos)=0 l -^Index(IndexName) q
Наиболее распространенной операцией, где bit-slice индексы дают существенное преимущество, является операция суммирования значений атрибутов в столбик.
Продемонстрируем принцип вычисления суммы по bit-slice индексу на примере найденной bit-slice карты:
Строки данных id Count Битовое представление 1 17 010001 2 6 000110 3 5 000101 4 8 001000 5 14 001110 6 18 010010Колонки справа являются двоичным представлением значений атрибутов. Математически каждой из позиций соответствует позиция в разложении числа по степеням двойки:
Строки данных id Count Битовое представление 1 17 10001 2 6 00110 3 5 00101 4 8 01000 5 14 01110 6 18 10010 Степени двойки 43210
Каждое из значений атрибутов есть сумма битов умноженных на степень двойки, соответствующей его позиции. Таким образом, полную сумму всех значений можно получить как сумму сумм битов по каждой позиции (здесь в виде колонки) умноженных на степень двойки для этой позиции. Для получения суммы битов по каждой колонке используется встроенная системная функция $bitcount. Таким образом, для вычисления общей суммы необходимо 5 вызовов функции $bitcount и 5 произведений на степени двойки.
И для вычисления суммы всех чисел необходимо вычислить суммы битов при каждой из степеней двойки, что и выполняется системной функцией $bitcount.
Битовое системное расширение, функция $bitcount, выполняется на нижнем уровне так, что просто возвращает число единиц или нулей. Выполнение счета проводится на нижнем уровне, в кодах процессора, и очень быстро. При увеличении числа записей выигрыш во времени может достигать сотен раз по сравнению с простым сложением в столбик чисел, на получение каждого из которых выполняется обращение к глобали функцией $order.
Одним из наиболее традиционных применений bit-slice индексов для получения ключевого преимущества по скорости работы являются аналитические системы класса OLAP. В них операции выборки и суммирования применяются одновременно к большому числу записей и их атрибутов.
Для битмап и битслайс индексов в примерах используются блокировки, но для операций выполняемых функциями $bit они не требуются, поскольку эти операции проставляют единичный или нулевой бит атомарно. Во время непосредственно выполнения функций $bit никакие другие процессы не могут изменить значение переменной в то же самое время. При откате транзакции операции, выполненные функциями $bit, также откатываются атомарно, не затрагивая другие биты.
К интересным особенностям алгоритма поддержки bit-slice индексов можно отнести то, что обе системы, и Cache и MiniM, при отсутствии установки бита явным образом используют эту позицию как нулевой бит. Эквивалент нулевого бита используется как при дополнении битовой строки, так и при чтении бита за ее пределами. Поэтому, если разделить операции обновления индексов на три вида
- При добавлении новой записи.
- При изменении записи.
- При удалении записи.
Подробнее о книге "MUMPS СУБД"
Комментариев нет:
Отправить комментарий