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,idquit:’id  write id,!

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

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

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

Код класса

/// Набор методов для создания и работы с битмап и битслайс-индексами
/// 
/// структура bitmap-индекса
/// массив вида array(value), элементы которого —
/// битовые строки с 1 в позициях, соответствующих номерам записей,
/// для которых некоторый параметр принимает значение value,
/// разбитая на массив из строк с максимальной длиной $$$MAXBITLENGTH
/// нумерация записей — с 1, элементов массива — с 0,
/// (далее, для краткости — битовые массивы).
/// пример заполнения
/// пусть у записи номер idfact параметр par имеет значение val
/// set idf0=idfact-1\$$$MAXBITLENGTH,idf1=idfact-1#$$$MAXBITLENGTH+1
/// set $bit(^BM("I",par,val,idf0),idf1)=1
/// set $bit(^BM("EXIST",idf0),idf1)=1
/// индекс существующих записей полезен, во-первых, поскольку
/// позволяет легко выполнять логическое удаление, а во-вторых,
/// даёт возможность найти количество записей в хранилище без
/// обращения к другим структурам, что необходимо для корректной
/// работы процедуры BMNot (см. ниже)
/// структура битслайс-индекса:
/// массив битмап-индексов. 1-й элемент массива — индекс знаков
/// значений, 2-й — индекс младшего бита значений (1/0), 3-й —
/// индекс предпоследнего бита (2/0), и т.д.
/// 
/// пример заполнения
/// пусть у записи номер idfact параметр par имеет целочисленное
/// значение val
/// set idf0=idfact-1\$$$MAXBITLENGTH,idf1=idfact-1#$$$MAXBITLENGTH+1
/// set val=$$CvtToBin(val)
/// for ix=1:1:$length(val) set:$extract(val,ix) $bit(^BM("S",par,ix,idf0),idf1)=1
/// при массовом заполнении, во избежание катастрофического падения
/// производительности, рекомендуется обложить соответствующий фрагмент
/// кода функциями $sortbegin(^BM) и $sortend(^BM)
/// для выборки фактов по заданным ограничениям и вычисления по полученным
/// выборкам группирующих функций "сумма", "максимум" и "минимум"
/// предназначены функции BSSum(), BSMax() и BSMin()
Class User.BitMapSlice Extends %RegisteredObject 
ProcedureBlock ]
{

/// Name ($na) of global where to store bitmaps and bitslices
/// Default value is "^BM"
Property 
BMGLOB As %String(TRUNCATE 1) [ InitialExpression "^BM" ];

/// Maximal length of $bit string to use
Parameter 
MAXBITLENGTH = 64000;

/// Создаёт и возвращает имя ($na()) временного подузла глобала
/// для хранения промежуточных битмапов
ClassMethod 
GetNewTMP() As %String
{
 
quit $name(^CacheTemp("BM",$job_$zutil(110),$increment(^CacheTemp("BM",$job_$zutil(110)))))
}

/// Удаляет все временные подузлы, созданные данным процессом
ClassMethod 
KillAllTMP()
{
 
kill ^CacheTemp("BM",$job_$zutil(110)) quit
}

/// Операции над битовыми массивами
/// здесь и далее, в целях гибкости, битовые индексы,
/// массивы и слайсы передаются по имени ($na())
/// 
/// находит следующую за pos позицию с единичным битом
/// в bm — передаваемом по имени битовом массиве
Method 
BMOrder(bm As %Stringpos As %StringAs %String
{
 
set sub=pos\..#MAXBITLENGTH,ix=$bitfind($get(@bm@(sub)),1,pos#..#MAXBITLENGTH+1)
 
quit:ix sub*..#MAXBITLENGTH+ix
 
for  set sub=$order(@bm@(sub)) quit:’sub  set ix=$bitfind($get(@bm@(sub)),1) quit:ix
 
quit:ix sub*..#MAXBITLENGTH+ix
 
quit ""
}

/// bmdest=bmdest & bmsrc
Method 
BMAnd(bmdest As %Stringbmsrc As %String)
{
 
set sub1=$order(@bmdest@($char(0)),-1),sub=$order(@bmsrc@($char(0)),-1)
 
set:sub<sub1 sub=sub1
 
for ix=0:1:sub set:$data(@bmdest@(ix))&$data(@bmsrc@(ix)) @bmdest@(ix)=$bitlogic(@bmdest@(ix)&@bmsrc@(ix)) kill:’$data(@bmsrc@(ix)) @bmdest@(ix)
 
quit
}

/// bmdest=bmdest | bmsrc
Method 
BMOr(bmdest As %Stringbmsrc As %String)
{
 
set sub1=$order(@bmdest@($char(0)),-1),sub=$order(@bmsrc@($char(0)),-1)
 
set:sub<sub1 sub=sub1
 
for ix=0:1:sub set:$data(@bmsrc@(ix)) @bmdest@(ix)=$select($data(@bmdest@(ix)):$bitlogic(@bmdest@(ix)|@bmsrc@(ix)),1:@bmsrc@(ix))
 
quit
}

Method BMNot(bm As %String)
{
 
set maxblk=$order(@(..BMGLOB)@("EXIST",""),-1),blklen=$bitcount(@(..BMGLOB)@("EXIST",maxblk))
 
for ix=maxblk:-1:0 set blk=$get(@bm@(ix)) set:$bitcount(blk)<blklen $bit(blk,blklen)=0 set @bm@(ix)=$bitlogic(~blk),blklen=..#MAXBITLENGTH
 do 
..BMAnd(bm,$name(@(..BMGLOB)@("EXIST")))
 
quit
}

/// возвращает количество единичных битов в массиве
Method 
BMCount(bm As %StringAs %Integer
{
 
set ix="",bmcret=0
 
for  set ix=$order(@bm@(ix)) quit:ix‘=+ix  set bmcret=bmcret+$bitcount(@bm@(ix),1)
 
quit bmcret
}

/// помещает в битовый массив bmdest выборку из битмап-индекса vbmsrc,
/// где значение параметра равно val
/// 
Method 
BMEq(bmdest As %Stringvbmsrc As %Stringval As %String)
{
 
kill @bmdest merge @bmdest=@vbmsrc@(val)
 
quit
}

/// помещает в битовый массив bmdest выборку из битмап-индекса vbmsrc,
/// где значение параметра не равно val
Method 
BMNe(bmdest As %Stringvbmsrc As %Stringval As %String)
{
 
do ..BMEq(bmdest,vbmsrc,valdo ..BMNot(bmdest)
 
quit
}

/// помещает в битовый массив bmdest выборку из битмап-индекса vbmsrc,
/// где значение параметра меньше (сортируется до) val
/// bmdest:=U(vbmsrc(v):v<val)
Method 
BMLt(bmdest As %Stringvbmsrc As %Stringval As %String)
{
 
kill @bmdest set ix=val
 
for  set ix=$order(@vbmsrc@(ix),-1) quit:ix=""  do ..BMOr(bmdest,$name(@vbmsrc@(ix)))
 
quit
}

/// аналогично BMLt() но "меньше или равно"
Method 
BMLe(bmdest As %Stringvbmsrc As %Stringvalue As %String)
{
 
kill @bmdest merge @bmdest=@vbmsrc@(valset ix=val
 
for  set ix=$order(@vbmsrc@(ix),-1) quit:ix=""  do ..BMOr(bmdest,$name(@vbmsrc@(ix)))
 
quit
}

/// аналогично BMLe, но "больше или равно"
Method 
BMGe(bmdest As %Stringvbmsrc As %Stringval As %String)
{
 
kill @bmdest merge @bmdest=@vbmsrc@(valset ix=val
 
for  set ix=$order(@vbmsrc@(ix)) quit:ix=""  do ..BMOr(bmdest,$name(@vbmsrc@(ix)))
 
quit
}

/// аналогично, значения больше или равно min и меньше или равно max
Method 
BMGeLe(bmdest As %Stringvbmsrc As %Stringmin As %Stringmax As %String)
{
 
kill @bmdest merge @bmdest=@vbmsrc@(minset ix=min
 
for  set ix=$order(@vbmsrc@(ix)) quit:ix]]max  quit:ix=""  do ..BMOr(bmdest,$name(@vbmsrc@(ix)))
 
quit
}

/// аналогично BMGe(), но "строго больше"
Method 
BMGt(bmdest As %Stringvbmsrc As %Stringval As %String)
{
 
kill @bmdest set ix=val
 
for  set ix=$order(@vbmsrc@(ix)) quit:ix=""  do ..BMOr(bmdest,$name(@vbmsrc@(ix)))
 
quit
}

/// аналогично, значения больше min и меньше max
Method 
BMGtLt(bmdest As %Stringvbmsrc As %Stringmin As %Stringmax As %String)
{
 
kill @bmdest set ix=min
 
for  set ix=$order(@vbmsrc@(ix)) quit:max‘]]ix  quit:ix=""  do ..BMOr(bmdest,$name(@vbmsrc@(ix)))
 
quit
}

/// аналогично, значения больше или равно min и меньше max
Method 
BMGeLt(bmdest As %Stringvbmsrc As %Stringmin As %Stringmax As %String)
{
 
kill @bmdest merge @bmdest=@vbmsrc@(minset ix=min
 
for  set ix=$order(@vbmsrc@(ix)) quit:max‘]]ix  quit:ix=""  do ..BMOr(bmdest,$name(@vbmsrc@(ix)))
 
quit
}

/// аналогично, значения больше min и меньше или равно max
Method 
BMGtLe(bmdest As %Stringvbmsrc As %Stringmin As %Stringmax As %String)
{
 
kill @bmdest set ix=min
 
for  set ix=$order(@vbmsrc@(ix)) quit:ix]]max  quit:ix=""  do ..BMOr(bmdest,$name(@vbmsrc@(ix)))
 
quit
}

///  Операции над Bit-Sliced данными
/// преобразует целочисленное значение в текстовую битовую строку
/// {sign,1,2,4,…,2**N}
ClassMethod 
CvtToBin(value As %IntegerAs %String
{
 
set value=$fnumber(+value,"",0),res=(value<0)
 
for  quit:’value  set res=res_(value#2),value=value\2
 
quit res
}

/// конвертирует битовый список $lb(sign,1,2,4,…2**N) в целое число
ClassMethod 
CvtFromSlice(slice As %StringAs %Integer
{
 
set res=0
 
for i=$listlength(slice):-1:2 set res=res+res set res=res+$listget(slice,i,0)
 
quit $select($listget(slice):-res,1:res)
}

/// помещает биты из позиции pos битслайса vbs в список ($lb())
Method 
GetSlice(vbs As %Stringpos As %IntegerAs %String
{
 
set sub=pos\..#MAXBITLENGTH,ix=pos-1#..#MAXBITLENGTH+1
 
for i=1:1:$order(@vbs@(""),-1) set $list(slice,i)=$bit($get(@vbs@(i,sub)),ix)
 
quit slice
}

/// помещает в битовый массив bmdest выборку из битслайс-индекса vbs,
/// где значение параметра равно val
Method 
BSEq(bmdest As %Stringvbs As %Stringval As %Integer)
{
 
set bswork=..GetNewTMP() set vbit=..CvtToBin(val)
 
kill @bmdest merge @bmdest=@(..BMGLOB)@("EXIST")
 
set maxbit=$order(@vbs@(""),-1) set:maxbit<$length(vbitmaxbit=$length(vbit)
 
for ix=1:1:maxbit kill @bswork merge @bswork=@vbs@(ixdo:’$extract(vbit,ix) ..BMNot(bsworkdo ..BMAnd(bmdest,bswork)
 
kill @bswork quit
}

/// помещает в битовый массив bmdest выборку из битслайс-индекса vbs,
/// где значение параметра больше или равно val
Method 
BSGe(bmdest As %Stringvbs As %Stringval As %Integer)
{
 
do ..BSLt(bmdest,vbs,val),..BMNot(bmdestquit
}

/// помещает в битовый массив bmdest выборку из битслайс-индекса vbs,
/// где значение параметра не равно val
Method 
BSNe(bmdest As %Stringvbs As %Stringval As %Integer)
{
 
do ..BSEq(bmdest,vbs,val),..BMNot(bmdest)
 
quit
}

/// помещает в битовый массив bmdest выборку из битслайс-индекса vbs,
/// где значение параметра больше val
/// 
Method 
BSGt(bmdest As %Stringvbs As %Stringval As %Integer)
{
 
do ..BSLe(bmdest,vbs,val),..BMNot(bmdestquit
}

/// помещает в битовый массив bmdest выборку из битслайс-индекса vbs,
/// где знак параметра равен sign (ноль считается положительным)
Method 
BSSign(bmdest As %Stringvbs As %Stringsign As %Integer)
{
 
set bswork=..GetNewTMP() kill @bmdest
 
merge @bmdest=@(..BMGLOB)@("EXIST"),@bswork=@vbs@(1)
 
do:$get(sign)'<0 ..BMNot(bsworkdo ..BMAnd(bmdest,bswork)
 
kill @bswork quit
}

/// помещает в битовый массив bmdest выборку из битслайс-индекса vbs,
/// где значение параметра меньше или равно val
Method 
BSLe(bmdest As %Stringvbs As %Stringval As %Integer)
{
 
set tmpLe=..GetNewTMP()
 
do ..BSLtAbs(bmdest,vbs,val),..BSSign(tmpLe,vbs,-1)
 
if val‘<0 do ..BMOr(bmdest,tmpLe),..BSEq(tmpLe,vbs,val),..BMOr(bmdest,tmpLeif 1
 
else  do ..BMNot(bmdest),..BMAnd(bmdest,tmpLe)
 
kill @tmpLe quit
}

/// помещает в битовый массив bmdest выборку из битслайс-индекса vbs,
/// где значение параметра меньше val
Method 
BSLt(bmdest As %Stringvbs As %Stringval As %Integer)
{
 
set tmpLt=..GetNewTMP()
 
do ..BSLtAbs(bmdest,vbs,val),..BSSign(tmpLt,vbs,-1)
 
if val‘<0 do ..BMOr(bmdest,tmpLtif 1
 
ELSE  do ..BMNot(bmdest),..BMAnd(bmdest,tmpLt),..BSNe(tmpLt,vbs,val),..BMAnd(bmdest,tmpLt)
 
kill @tmpLt quit
}

/// помещает в битовый массив bmdest выборку из битслайс-индекса vbs,
/// где значение параметра больше или равно val1 и меньше или равно val2
Method 
BSGeLe(bmdest As %Stringvbs As %Stringval1 As %Integerval2 As %Integer)
{
 
set tmpGeLe=..GetNewTMP()
 
do ..BSGe(bmdest,vbs,val1),..BSLe(tmpGeLe,vbs,val2),..BMAnd(bmdest,tmpGeLe)
 
kill @tmpGeLe quit
}

/// помещает в битовый массив bmdest выборку из бит-слайс-индекса vbs,
/// где значение параметра больше или равно val1 и меньше val2
Method 
BSGeLt(bmdest As %Stringvbs As %Stringval1 As %Integerval2 As %Integer)
{
 
set tmpGeLt=..GetNewTMP()
 
do ..BSGe(bmdest,vbs,val1),..BSLt(tmpGeLt,vbs,val2),..BMAnd(bmdest,tmpGeLt)
 
kill @tmpGeLt quit
}

/// помещает в битовый массив bmdest выборку из битслайс-индекса vbs,
/// где значение параметра больше val1 и меньше или равно val2
Method 
BSGtLe(bmdest As %Stringvbs As %Stringval1 As %Integerval2 As %Integer)
{
 
set tmpGtLe=..GetNewTMP()
 
do ..BSGt(bmdest,vbs,val1),..BSLe(tmpGtLe,vbs,val2),..BMAnd(bmdest,tmpGtLe)
 
kill @tmpGtLe quit
}

/// помещает в битовый массив bmdest выборку из бит-слайс-индекса vbs,
/// где значение параметра больше val1 и меньше val2
Method 
BSGtLt(bmdest As %Stringvbs As %Stringval1 As %Integerval2 As %Integer)
{
 
set tmpGtLt=..GetNewTMP()
 
do ..BSGt(bmdest,vbs,val1),..BSLt(tmpGtLt,vbs,val2),..BMAnd(bmdest,tmpGtLt)
 
kill @tmpGtLt quit
}

/// помещает в битовый массив bmdest выборку из бит-слайс-индекса vbs,
/// где значение параметра по абсолютной величине меньше, чем val
Method 
BSLtAbs(bmdest As %Stringvbs As %Stringval As %Integer)
{
 
set bswork=..GetNewTMP(),test=..GetNewTMP()
 
kill @bmdest set vbit=..CvtToBin(val),ixmax=$order(@vbs@(""),-1)
 
kill @test merge @test=@(..BMGLOB)@("EXIST")
 
if ixmax<$length(vbit{
   
merge @bmdest=@test
 
else {
   
for ix=ixmax:-1:2 {
     
kill @bswork merge @bswork=@vbs@(ix)
     
do ..BMNot(bswork),..BMAnd(bswork,test)
     
do:$extract(vbit,ix) ..BMOr(bmdest,bswork),..BMNot(bswork)
     
do ..BMAnd(test,bswork)
   
}
 }
 
kill @test,@bswork quit
}

///  группирующие функции для битслайс-индексов
/// возвращает максимальное значение (при необязательном параметре
/// bsmin’=0 — минимальное) для выборки bitmap из битслайс-индекса vbs
Method 
BSMax(vbs As %Stringbitmap As %Stringbsmin As %StringAs %Integer
{
 
set bsmin$get(bsmin),bswork=..GetNewTMP()
 
set resBSM=..GetNewTMP(),tmpBSM=..GetNewTMP()
 
merge @resBSM=@vbs@(1) do:’bsmin ..BMNot(resBSMdo ..BMAnd(resBSM,bitmap)
 
if ..BMCount(resBSMset min=0
 
ELSE  set min=1 kill @resBSM merge @resBSM=@vbs@(1) do:bsmin ..BMNot(resBSMdo ..BMAnd(resBSM,bitmap)
 
for ix=$order(@vbs@(""),-1):-1:2 {
   
kill @tmpBSM,@bswork merge @tmpBSM=@resBSM,@bswork=@vbs@(ix)
   
do:min ..BMNot(bsworkdo ..BMAnd(tmpBSM,bswork)
   
if ..BMCount(tmpBSMkill @resBSM merge @resBSM=@tmpBSM
 
}
 
set pos=..BMOrder(resBSM,0) quit:’pos 0
 
set val=..CvtFromSlice(..GetSlice(vbs,pos))
 
kill @bswork,@resBSM,@tmpBSM quit val
}

Method BSMin(vbs As %Stringbitmap As %StringAs %Integer
{
 
quit ..BSMax(vbs,bitmap,1)
}

/// возвращает сумму значений для выборки bitmap из битслайс-индекса vbs
Method 
BSSum(vbs As %Stringbitmap As %StringAs %Integer
{
 
set bswork=..GetNewTMP(),resBSSum=..GetNewTMP(),tmpBSSum=..GetNewTMP()
 
merge @resBSSum=@vbs@(1) do ..BMNot(resBSSum),..BMAnd(resBSSum,bitmapset slice=""
 
for ix=2:1:$order(@vbs@(""),-1) kill @tmpBSSum merge @tmpBSSum=@vbs@(ixdo ..BMAnd(tmpBSSum,resBSSumset $list(slice,ix)=..BMCount(tmpBSSum)
 
set val=..CvtFromSlice(slice)
 
kill @resBSSum merge @resBSSum=@vbs@(1) do ..BMAnd(resBSSum,bitmapset slice=""
 
for ix=2:1:$order(@vbs@(""),-1) kill @tmpBSSum merge @tmpBSSum=@vbs@(ixdo ..BMAnd(tmpBSSum,resBSSumset $list(slice,ix)=..BMCount(tmpBSSum)
 
set val=val-..CvtFromSlice(slice)
 
kill @bswork,@resBSSum,@tmpBSSum quit val
}

/// методы для заполнения битмап и битслайс-индексов
/// 
/// устанавливает соответствующий бит в битмап-индексе
/// данного значения данного свойства
/// при необязательном параметре setexist=1 устанавливает также бит в
/// битмап-индексе существующих записей (необходимо для корректной
/// работы метода BMNot())
Method 
SetBitMap(idfact As %Integerproperty As %Stringvalue As %Stringsetexist As %String)
{
 
set idf0=idfact-1\..#MAXBITLENGTH,idf1=idfact-1#..#MAXBITLENGTH+1
 
set:$get(setexist$bit(@(..BMGLOB)@("EXIST",idf0),idf1)=1
 
set $bit(@(..BMGLOB)@("I",property,value,idf0),idf1)=1
 
quit
}

/// устанавливает соответствующий бит в битслайс-индексе
/// данного значения данного свойства.
/// Необязательный парамерт setexist — аналогично методу SetBitMap()
Method 
SetBitSlice(idfact As %Integerproperty As %Stringvalue As %Integersetexist As %String)
{
 
set idf0=idfact-1\..#MAXBITLENGTH,idf1=idfact-1#..#MAXBITLENGTH+1
 
set:$get(setexist$bit(@(..BMGLOB)@("EXIST",idf0),idf1)=1
 
set v=..CvtToBin(+value)
 
for ix=1:1:$length(vset:$extract(v,ix$bit(@(..BMGLOB)@("S",property,ix,idf0),idf1)=1
 
quit
}

/// возвращает имя подузла индексного глобала, содержащего
/// битмап-индекс (если slice=0 или не определён) или битслайс (ghb slice’=0)
/// для данного свойства. Если property пусто или не определено —
/// то битмап-индекс существующих записей
Method 
GetBitMapName(property As %Stringslice As %StringAs %String
{
 
quit:$get(property)="" $name(@(..BMGLOB)@("EXIST"))
 
quit $name(@(..BMGLOB)@($select(+$get(slice):"S",1:"I"),property))
}

///  демонстрационное заполнение и выборка
///  
ClassMethod 
Populate(count As %String 10000)
{
  
set ix=..%New()
  
set ix.BMGLOB=$name(^BMI)
  
set count=$get(count,10000),m=0
  
set names=$listbuild("SantaClause","Crocodile","Simba")
  
set colors=$listbuild("Cyan","Magenta","Yellow","Black")
  
if $sortbegin(^BMI)
  
for idfact=1:1:count {
    
set name=$list(names,1+$random($listlength(names)))
    
set color=$list(colors,1+$random($listlength(colors)))
    
set length=10+$random(90)
    
set weight=(10+$random(40))*100
    
; для цвета создаём битмап-индекс
    
do ix.SetBitMap(idfact,"C",color,1)
    
; для веса и длины создаём битслайс-индексы
    
do ix.SetBitSlice(idfact,"L",length)
    
do ix.SetBitSlice(idfact,"W",weight)
    
; для проверки тестовой выборки (см. ниже) считаем
    ; суммарный вес чёрных и жёлтых крокодилов длиной 45-70 см
    ; включительно
    
set:((color="Black")!(color="Yellow"))&(length‘<45)&(length‘>70) m=m+weight
  
}
  
if $sortend(^BMI)
  
write m_" gramms total",!
  
kill ix quit
}

/// тестовая выборка
ClassMethod 
TestGetData()
{
  
set ix=..%New()
  
set ix.BMGLOB=$name(^BMI)
  
set b=..GetNewTMP(),b1=..GetNewTMP()
  
do ix.BMEq(b,ix.GetBitMapName("C"),"Black")
  
do ix.BMEq(b1,ix.GetBitMapName("C"),"Yellow")
  
do ix.BMOr(b,b1)
  
do ix.BSGeLe(b1,ix.GetBitMapName("L",1),45,70)
  
do ix.BMAnd(b,b1)
  
set count=ix.BMCount(b)
  
write count_" items selected",!
  
; определяем суммарный вес выбранного
  
write ix.BSSum(ix.GetBitMapName("W",1),b)_" gramms total",!
  
do ..KillAllTMP()
  
kill ix quit
}

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

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

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

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

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

Для тех, кому привычен сокращённый синтаксис Caché ObjectScript, напоминаю, что 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, и был впоследствии применён компанией МаковаСофт в её хранилище данных Ортофакт.

Добавить комментарий

Ваш e-mail не будет опубликован. Обязательные поля помечены *