Caché Globals Bitmap Indexes

In the Caché object DBMS, bitmap and bitslice indexes are supported. It is very easy to use them in Caché classes: it is enough to indicate Bitmap or Bitslice in the description of the index, and the performance of some SQL queries is improved dramatically. But how does this work?
This article describes how bitmap indexes are organized, how to create a bitmap index on an arbitrary global structure, how to use bit logic functions and how to use them effectively when working with NoSQL in Caché.

Since the very beginning of the time, when developing applications to quickly find interesting records in globals, type indices were most often built

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

Such indexes allow you to easily and quickly find records for which the property of interest has a specified value:
')
set id = "" for set id = $ order (^ Index ( "Property" , value , id )) quit : id = "" write id ,!

will give the identifiers of all records that have the value of the property “Property” equal to value, and you can check for the existence of records with this property value, for example, using this code:

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

It is easy to come up with an algorithm for the effective search of records that satisfy several conditions at once, combined by the logic of "AND". But for more complex queries, it was necessary either to develop (and to debug each time) a more complex algorithm, or to abandon the use of indices in favor of directly iterating over all records in the database.

A revolutionary change was the emergence in Caché of full- bit bit functions : $ bit (), $ bitlogic (), $ bitfind () and $ bitcount (). Now you can build bitmap-indices, in the simplest case - of the form

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

Of course, since the length of the bit string is limited to 256K, in real-world applications, the bitmap index has to be placed not in a single bit string, but in an array.
The $ bitlogic () functions make it easy to create a resultant bitmap index corresponding to a sample of records that satisfy any arbitrary query, $ bitcount () determines the number of records included in the sample, and $ bitfind () provides easy navigation through received sample.

For example, to collect records for which the property “Pr1” has the values ​​“A” or “B”, and the property “Pr2” - the value “C”:

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

and give them an 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 ,!

This is not all that can be squeezed out of the bit functions in Caché. To calculate the values ​​of the grouping function (sum, arithmetic average, minimum, maximum), it was still necessary to cycle through all the records in the sample, which, with a sufficient sample size, was not fast. But a small modification of the structure of bitmap-indices significantly speeds up this procedure, if the property values ​​are integer or with a fixed decimal point.
The essence of this modification is the construction of separate bitmap-indices for each bit of the property value. Such constructions are called bit-slices:

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

In reality, again, instead of a bit string, an array is used.
When using bitslices, it is somewhat more difficult, for example, to search for “more” or “less” restrictions, but the gain in calculating grouping functions outweighs this inconvenience. In fact, to calculate the sum of the values ​​of the property of interest for the selected records, the cycle of records is no longer needed. It is enough to sum up with the corresponding weights $ bitcount () in the resulting bitmap-index for all bits of the value of the property of interest. With a sufficient sample size, the performance gain can be called amazing without exaggeration.


The attached code contains a complete set of functions for developing a data warehouse using bitmap indexes and bitslices in classes and routines, supporting all the required manipulations with these structures. Also included is a demonstration method for filling the test repository with data, during which the value of the grouping function is calculated directly - the sum for the subsequent test request:

do ## class ( User.BitMapSlice ). Populate (1,000,000) ; million records

and a method for executing this test query, in which the value of the same grouping function is computed using bitslices:

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

You can compare the result and the time spent on getting it.

For those who are accustomed to the abbreviated COS syntax, I recall that Caché Studio, starting with version 5.2, allows you to easily convert the selected code fragment from the full form to the abbreviated form - Ctrl-Shift-E and back - Ctrl-E .
In conclusion, you need to comment on one subtlety. It is recommended to build intermediate and resulting bitmap indices for sampling in globals with ^ CacheTemp or ^ mtemp prefixes. Such globals are physically located in the CACHETEMP database and due to the fact that they are not logged , which we have no need for, work with them is more productive than even with local variables. The use of local variables for this purpose is also undesirable for another reason - the possibility of resting on the 16-megabyte memory limit of the user process.

The italicized note does not apply to newer versions of the Caché DBMS:

1. Large local arrays
2. Extended memory
3. Unlimited Local Arrays

The code described in this article owes its appearance to the information kindly provided by InterSystems at one of the presentations of the DeepSee product, and was subsequently applied by MakovaSoft in its Orthofact data storage.