Bitmap-индексы в Caché на глобалах

В объектной СУБД Caché поддерживаются bitmap- и bitslice-индексы. Их очень просто использовать в классах Caché: достаточно в описании индекса указать признак Bitmap или Bitslice, и производительность некоторых SQL-запросов улучшается кардинально. Но как это работает?
В этой статье раскрывается, как устроены bitmap-индексы, как создать bitmap-индекс на произвольной структуре глобалов, как применять функции битовой логики и как эффективно их использовать при NoSQL работе в Caché.

Ещё с дообъектных времён при разработке приложений для быстрого поиска интересующих записей в глобалах чаще всего строились индексы вида

set ^Index("Property",value,id)=""

Такие индексы позволяют легко и быстро находить записи, для которых интересующее свойство имеет заданное значение:

set id="" for  set id=$order(^Index("Property",value,id)) quit:id=""  write id,!

выдаст идентификаторы всех записей, у которых значение свойства «Property» равно value, а проверить существование записей с данным значением свойства можно, например, с помощью такого кода:

if $data(^Index("Property",value))>1 {
  write "id "_$order(^Index("Property",value,""))_" with " _value_" exists" }
else {
  write "records with "_value_" do not exist" }

Нетрудно придумать и алгоритм для эффективного поиска записей, удовлетворяющих сразу нескольким условиям, объединённым логикой «И». Но для более сложных запросов требовалось либо разрабатывать (и каждый раз отлаживать) более сложный алгоритм, либо отказываться от применения индексов в пользу прямого перебора всех записей в базе.

Революционным изменением стало появление в Caché полноценных битовых функций: $bit(), $bitlogic(), $bitfind() и $bitcount(). Появилась возможность строить bitmap-индексы, в простейшем случае — вида

set $bit(^Index("Property",value),id)=1

Разумеется, поскольку длина битовой строки ограничена 256K, в реальных приложениях bitmap-индекс приходится размещать не в одной битовой строке, а в массиве.
Функции $bitlogic() дают возможность легко из таких индексов сформировать результирующий bitmap-индекс, соответствующий выборке записей, удовлетворяющих любому, сколь угодно заковыристому запросу, $bitcount() определяет количество записей, вошедших в выборку, а $bitfind() обеспечивает удобную навигацию по полученной выборке.

Например, собрать записи, для которых свойство “Pr1” имеет значения “A” или “B”, а свойство «Pr2» — значение «C»:

set ^mtemp.resbitmap=$bitlogic(^Index("Pr1","A")|^Index("Pr1","B"))
set ^mtemp.resbitmap=$bitlogic(^mtemp.resbitmap&^Index("Pr2","C"))

и выдать их id:

if '$bitcount(^mtemp.resbitmap) write "No records found",!
else  set id=0 for  set id=$bitfind(^mtemp.resbitmap,1,id) quit:'id  write id,!

Это далеко не всё, что можно выжать из битовых функций в Caché. Для вычисления значений группирующей функции (суммы, среднего арифметического, минимума, максимума) всё равно приходилось в цикле перебирать все записи, вошедшие в выборку, что при достаточном объёме выборки было не быстро. Но небольшая модификация структуры bitmap-индексов значительно ускоряет и эту процедуру — в случае, если значения свойства являются целочисленными или с фиксированной десятичной точкой.
Суть этой модификации — построение отдельных bitmap-индексов для каждого бита значения свойства. Такие конструкции называются битслайсами (bit-slices):

set $bit(^Index("Property",N),id)=NthBitOfValue

В реальности, опять же, вместо битовой строки используется массив.
При использовании bitslices несколько усложняется, например, поиск по ограничениям «больше» или «меньше», но выигрыш при вычислении группирующих функций существенно перевешивает данное неудобство. В самом деле, для вычисления суммы значений интересующего свойства для выбранных записей уже не нужен цикл по записям. Достаточно лишь просуммировать с соответствующими весами $bitcount() в результирующем bitmap-индексе для всех битов значения интересующего свойства. При достаточном объёме выборки выигрыш в производительности можно без преувеличения назвать потрясающим.


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

do ##class(User.BitMapSlice).Populate(1000000) ; миллион записей

и метод для выполнения этого тестового запроса, в которой значение той же группирующей функции вычисляется с использованием bitslices:

do ##class(User.BitMapSlice).TestGetData()

Вы можете сравнить и результат, и время, потраченное на его получение.

Для тех, кому привычен сокращённый синтаксис COS, напоминаю, что Caché Studio, начиная с версии 5.2, позволяет с лёгкостью преобразовывать выделенный фрагмент кода из полной формы в сокращённую — Ctrl-Shift-E и обратно — Ctrl-E.
В заключение необходимо прокомментировать одну тонкость. Промежуточные и результирующие bitmap-индексы для выборки рекомендуется строить в глобалах с префиксами ^CacheTemp или ^mtemp. Такие глобалы физически располагаются в базе CACHETEMP и за счёт того, что они не журналируются, в чём у нас нет никакой необходимости, работа с ними более производительна, чем даже с локальными переменными. Использование локальных переменных для этой цели нежелательно ещё и по другой причине — возможности упереться в 16-мегабайтное ограничение памяти пользовательского процесса.

Выделенное курсивом замечание не касается более новых версий СУБД Caché:

1. Large Local Arrays
2. Extended Memory
3. Unlimited Local Arrays

Описанный в данной статье код обязан своим появлением информации, любезно предоставленной компанией InterSystems на одной из презентаций продукта DeepSee, и был впоследствии применён компанией МаковаСофт в её хранилище данных Ортофакт.