Здесь поведем речь о реализации теоретико-множественных операций над битовыми
индексами.
Битовый индекс структурно представляет собой отображение значений атрибутов на набор идентификаторов в виде сопоставления с каждым значением битовой последовательности. При этом в силу того, что технически неограниченная последовательность не может быть реализована, она разбивается на сегменты. Единичному биту в такой последовательности сопоставляется признак, что номер этого бита в общей последовательности (с учетом всех предшествующих сегментов) представляет собой числовой идентификатор индексированной записи.
Для выполнения операций поиска в таких индексах строится дерево логического выражения и каждой операции сопоставляется логическая операция над битовыми последовательностями. Каждая из операций имеет результатом битовую последовательность такой же структуры - совокупность битовых сегментов.
При этом, что важно, семантика битовой последовательности является открытой - если есть единичный бит, то ему соответствует объект. Если его нет - то объекта нет. При этом под состояние "нет единичного бита" попадает как нулевой бит, так и отсутствие сегмента как такового. Над непосредственно битовыми последовательностями, таким образом, отсутствует операция унарной инверсии (отрицания), поскольку нет признака окончания последовательности. Таких же принципов открытости логических множеств придерживаются большинство других программных систем, например, в языке Prolog нет операции получить множество неизвестных высказываний.
При этом, хотя нет операции унарной инверсии, в модели открытого мира присутствует операция вычитания, которая в логике закрытого мира эквивалентна операции AND (И) первого операнда с результатом инверсии второго операнда. В модели открытого мира такая операция не раскладывается на отдельные и применяется как есть, без промежуточной инверсии вычитаемого множества.
С точки зрения применения в базах данных логическая операция "исключающее или" над индексами весьма спорна, поскольку пока не было разумных примеров ее использования. Видимо, именно поэтому в битовых функциях Cache и MiniM этой операции нет. Впрочем, если она потребуется (поскольку мир разнообразен), ее можно выразить через имеющиеся базовые логические операции.
Рассмотрим остальные операции:
Для испытаний воспользуемся тестовыми данными, сделанными с помощью:
Для операций с сегментами битовых карт есть нюанс, неуловимый на первый взгляд - работа с пропущенными сегментами. При простановке битов может оказаться, что по каким-либо сегментам совсем не было операций, и такой сегмент будет отсутствовать. Поэтому операции OR и SUB опираются на первый операнд, но проход выполняют по второму, а операция AND выполняет проход по первому операнду, игнорируя наличие сегментов второго.
Отличительной особенностью реализации операций на битовыми индексами также является отсутствие проверки существования самих битовых сегментов, поскольку реализация функций $bit отсутствующие сегменты (неопределенные значения) считает как не содержащие единичных битов.
Интересной задачей по оптимизации работы приведенных функций AND, OR, SUB выглядит переход от операции merge к проходам по имеющимся сегментам.
Кроме описанных, для типовых операций с данными часто требуется еще две операции - операция получения количества единичных битов:
В целом же, если сравнить битовые индексы с древовидными, то древовидные несомненно богаче по функциональности, но битовые намного проще в реализации и, видимо, несколько быстрее в работе. Особенно если используются встроенные и характерные для битовых сегментов операции, например $bitcount. Видится перспективным, что если для древовидных структур в MUMPS появятся аналогичные специализированные функции, то быстродействие древовидных индексов также можно ускорить.
Как возможные направления в развитии Cache и MiniM с целью ускорения древовидных индексов можно было бы назвать встроенные системные функции или команды
Получить число потомков у узла
Системная функция, похожая на $data, но возвращающая число различных значений непосредственных потомков узла, например если есть
Выполнить логический И между потомками двух или больше заданных узлов
Команда, похожая на merge, но оставляющая в результате пересечения подиндексов, например если есть
В оценке какие именно индексы лучше использовать наилучшим критерием выглядит практика. В задачах OLTP обычно проще применять древовидные, а в задачах OLAP битовые индексы. Преимущество битовых индексов существенно возрастает при увеличении объемов данных, и некоторые системы OLAP построенные не на MUMPS, имели в качестве ключевого преимущества по скорости именно реализацию битовых индексов.
Подробнее о книге "MUMPS СУБД"
Битовый индекс структурно представляет собой отображение значений атрибутов на набор идентификаторов в виде сопоставления с каждым значением битовой последовательности. При этом в силу того, что технически неограниченная последовательность не может быть реализована, она разбивается на сегменты. Единичному биту в такой последовательности сопоставляется признак, что номер этого бита в общей последовательности (с учетом всех предшествующих сегментов) представляет собой числовой идентификатор индексированной записи.
Для выполнения операций поиска в таких индексах строится дерево логического выражения и каждой операции сопоставляется логическая операция над битовыми последовательностями. Каждая из операций имеет результатом битовую последовательность такой же структуры - совокупность битовых сегментов.
При этом, что важно, семантика битовой последовательности является открытой - если есть единичный бит, то ему соответствует объект. Если его нет - то объекта нет. При этом под состояние "нет единичного бита" попадает как нулевой бит, так и отсутствие сегмента как такового. Над непосредственно битовыми последовательностями, таким образом, отсутствует операция унарной инверсии (отрицания), поскольку нет признака окончания последовательности. Таких же принципов открытости логических множеств придерживаются большинство других программных систем, например, в языке Prolog нет операции получить множество неизвестных высказываний.
При этом, хотя нет операции унарной инверсии, в модели открытого мира присутствует операция вычитания, которая в логике закрытого мира эквивалентна операции AND (И) первого операнда с результатом инверсии второго операнда. В модели открытого мира такая операция не раскладывается на отдельные и применяется как есть, без промежуточной инверсии вычитаемого множества.
С точки зрения применения в базах данных логическая операция "исключающее или" над индексами весьма спорна, поскольку пока не было разумных примеров ее использования. Видимо, именно поэтому в битовых функциях Cache и MiniM этой операции нет. Впрочем, если она потребуется (поскольку мир разнообразен), ее можно выразить через имеющиеся базовые логические операции.
Рассмотрим остальные операции:
- Логическое И или пересечение множеств.
- Логическое ИЛИ или объединение множеств.
- Логический бинарный НЕТ или вычитание множеств.
Для испытаний воспользуемся тестовыми данными, сделанными с помощью:
#define BITSIZE (260000)
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
InsertIndexRecords(id,RecordValues)
d SET($na(^Index("Figure",$p(RecordValues,"~",1))),id)
d SET($na(^Index("Color",$p(RecordValues,"~",2))),id)
d SET($na(^Index("Count",$p(RecordValues,"~",3))),id)
q
SET(name,id,bit=1)
n seg,pos
s seg=id\$$$BITSIZE s pos=id#$$$BITSIZE+1
s $bit(@name@(seg),pos)=''bit
q
Для реализации операции И или пересечения множеств:
AND(out,in1,in2) n i k @out m @out=@in1 s i="" f s i=$o(@out@(i)) q:i="" d . s @out@(i)=$bitlogic(@out@(i)&@in2@(i)) qДля реализации операции ИЛИ или объединения множеств:
OR(out,in1,in2) n i k @out m @out=@in1 s i="" f s i=$o(@in2@(i)) q:i="" d . s @out@(i)=$bitlogic(@out@(i)|@in2@(i)) qДля реализации операции SUB или дополнения множеств:
SUB(out,in1,in2) n i k @out m @out=@in1 s i="" f s i=$o(@in2@(i)) q:i="" d . s @out@(i)=$bitlogic(@out@(i)&~@in2@(i)) qПри этом этим операциям не требуется использовать размер сегмента - они должны провести операции с теми сегментами, которые имеются.
Для операций с сегментами битовых карт есть нюанс, неуловимый на первый взгляд - работа с пропущенными сегментами. При простановке битов может оказаться, что по каким-либо сегментам совсем не было операций, и такой сегмент будет отсутствовать. Поэтому операции OR и SUB опираются на первый операнд, но проход выполняют по второму, а операция AND выполняет проход по первому операнду, игнорируя наличие сегментов второго.
Отличительной особенностью реализации операций на битовыми индексами также является отсутствие проверки существования самих битовых сегментов, поскольку реализация функций $bit отсутствующие сегменты (неопределенные значения) считает как не содержащие единичных битов.
Интересной задачей по оптимизации работы приведенных функций AND, OR, SUB выглядит переход от операции merge к проходам по имеющимся сегментам.
Кроме описанных, для типовых операций с данными часто требуется еще две операции - операция получения количества единичных битов:
COUNT(in) n i,ret s ret=0 s i="" f s i=$o(@in@(i)) q:i="" d . s ret=ret+$bitcount(@in@(i),1) q retи получение следующего единичного бита после заданного:
NEXT(name,from)
n ret,seg,pos s ret=0 s from=+from
s seg=from\$$$BITSIZE s pos=from#$$$BITSIZE+2
f s:(seg'="") ret=$bitfind(@name@(seg),1,pos) »
q:(ret)!(seg="") d
. s seg=$o(@name@(seg)) q:seg=""
. s pos=0
q:ret seg*$$$BITSIZE+ret-1
q ""
С использованием приведенных функций уже очень легко составить довольно сложные
запросы, например запрос "выдать идентификаторы с заданными Figure и Color":
Select(Figure,Color)
n id,result
d AND($na(result),$na(^Index("Figure",Figure)), »
$na(^Index("Color",Color)))
s id="" f s id=$$NEXT($na(result),id) q:id="" d
. w id,!
q
Если провести сравнение простоты и удобства пользования битовыми и древовидными
индексами, то у различных систем баз данных, несмотря на общие
принципы, реализация битовых индексов различна. И, вероятно, это также является
весомым фактором в сравнении. Например, Cache и MiniM имеют перед другими СУБД
чисто
технические преимущества - 1) битовые операции атомарны, несмотря на то что
операции различных процессов могут прийтись на один и тот же сегмент, 2) откат
транзакций работает вполне корректно, 3) блокирование сегментов не требуется в
силу пункта 1, 4) применение встроенной компрессии при хранении сегмента и 5)
действительно малый объем журнала по сравнению с другими реализациями.
В целом же, если сравнить битовые индексы с древовидными, то древовидные несомненно богаче по функциональности, но битовые намного проще в реализации и, видимо, несколько быстрее в работе. Особенно если используются встроенные и характерные для битовых сегментов операции, например $bitcount. Видится перспективным, что если для древовидных структур в MUMPS появятся аналогичные специализированные функции, то быстродействие древовидных индексов также можно ускорить.
Как возможные направления в развитии Cache и MiniM с целью ускорения древовидных индексов можно было бы назвать встроенные системные функции или команды
Получить число потомков у узла
Системная функция, похожая на $data, но возвращающая число различных значений непосредственных потомков узла, например если есть
s ^d("s",1)=""
s ^d("s",4)=""
s ^d("s",78)=""
s ^d("s",54,789)=""
s ^d("s",100)=""
s ^d("k",3)=""
s ^d("k",8)=""
s ^d("k",12,456)=""
то такая новая функция вернет:
w $data2(^d("s"))
5
w $data2(^d("k"))
3
Это позволит упростить часто используемую операцию оценки количества элементов.
Выполнить логический И между потомками двух или больше заданных узлов
Команда, похожая на merge, но оставляющая в результате пересечения подиндексов, например если есть
s ^d("s",1)=""
s ^d("s",4)=""
s ^d("s",12)=""
s ^d("k",1)=""
s ^d("k",12)=""
s ^d("k",34)=""
то такая новая команда сделает
merge2 ^d("R")=^d("s")&^d("k")
zw ^d("R")
^d("R",1)=""
^d("R",12)=""
В остальном же сравнение битовых и древовидных индексов скорее всего в той или
иной форме приходит к тому, что битовые индексы имеют намного более бедные
покрывающие свойства (меньшее число различных операций, в которых они могут быть
применены). Если к используемой системе предъявляются довольно сложные
требования по запросам, то применение исключительно битовых индексов вместо
древовидных может в некоторых случаях даже ухудшить результаты. С другой
стороны, если можно обойтись только структурно простыми запросами, легко
реализующимися на битовых операциях, это скорее всего приведет к ускорению
работы системы, особенно если операция применяется к очень большому объему
данных.
В оценке какие именно индексы лучше использовать наилучшим критерием выглядит практика. В задачах OLTP обычно проще применять древовидные, а в задачах OLAP битовые индексы. Преимущество битовых индексов существенно возрастает при увеличении объемов данных, и некоторые системы OLAP построенные не на MUMPS, имели в качестве ключевого преимущества по скорости именно реализацию битовых индексов.
Подробнее о книге "MUMPS СУБД"
Комментариев нет:
Отправить комментарий