Globals are key-value stores for data storage. Trees. Part 2

Introduction — see part 1.

3. Structure variations when using globals

A structure like an ordered tree has different special cases. Let's consider those that have practical value when working with globals.

3.1 Special Case 1. One node without branches

Globals can be used not only like arrays but also as ordinary variables. For example, as a counter:

Set ^counter = 0  ; initialize counter
Set id=$Increment(^counter) ; atomic increment

In this case, a global can have branches in addition to its value. One does not exclude the other.

3.2 Special Case 2. One vertex and many branches

In general — this is a classic key-value database. If we store a tuple of values as the value, we get a regular table with a primary key.

To implement a table in globals, we will have to form rows from column values ourselves and then save them in the global by the primary key. To split the row back into columns upon reading, we can use:

1. delimiter symbols.

   Set ^t(id1) = "col11/col21/col31"
   Set ^t(id2) = "col12/col22/col32"

2. a rigid scheme, where each field occupies a pre-defined number of bytes, as done in relational databases.
3. a special function $LB (available in Cache), which composes a string from values.

   Set ^t(id1) = $LB("col11", "col21", "col31")
   Set ^t(id2) = $LB("col12", "col22", "col32")

Interestingly, it is not difficult to create something similar to secondary indexes in relational databases with globals. We will call such structures indexed globals. An indexed global is an auxiliary tree for quick searching by fields that are not parts of the primary key of the main global. To fill and use it, additional code must be written.

Let's create an indexed global based on the first column.

Set ^i("col11", id1) = 1
Set ^i("col12", id2) = 1

Now, for quick information retrieval by the first column, we need to look into the global ^i and find the primary keys (id) corresponding to the desired value of the first column.

When inserting a value, we can create both the value and the indexed globals for the needed fields immediately. For reliability, we will wrap all this in a transaction.

TSTART
Set ^t(id1) = $LB("col11", "col21", "col31")
Set ^i("col11", id1) = 1
TCOMMIT

Details on how to do this in M tables in globals, emulation of secondary indexes.

Such tables will operate as fast as traditional databases (or even faster) if the row insert/update/delete functions are written in COS/M and compiled.I verified this statement with tests on mass INSERT and SELECT to a two-column table, including using TSTART and TCOMMIT commands (transactions).

I did not test more complex scenarios with concurrent access and parallel transactions.

Without using transactions, the speed of inserts was 778,361 inserts/second for a million values.
With 300 million values — 422,141 inserts/second.

When using transactions — 572,082 inserts/second for 50 million inserts. All operations were conducted from compiled M-code.
Regular hard drives, not SSDs. RAID5 with Write-back. Processor Phenom II 1100T.

For similar SQL database testing, a stored procedure needs to be written that will perform inserts in a loop. When testing MySQL 5.5 (InnoDB storage), this method yielded no more than 11K inserts per second.
Yes, the implementation of tables in globals seems more complex than in relational databases. Therefore, industrial databases on globals have SQL access to simplify working with tabular data.

In general, if the data schema will not change frequently, the speed of insertion is not critical, and the entire database can be easily represented as normalized tables, working with SQL is simpler, as it provides a higher level of abstraction.

In this particular case, I wanted to show that globals can serve as a constructor for creating other databases. Like an assembler, on which other languages can be written. Here are examples of how to create analogs on globals key-value, lists, sets, tabular, document-oriented databases.

If you need to create some non-standard database with minimal effort, it’s worth looking towards globals.

3.3 Special case 3. Two-level tree, with each second-level node having a fixed number of branches

You probably guessed: this is an alternative implementation of tables in globals. Let's compare this implementation with the previous one.

Tables on a two-level tree vs. on a one-level tree.

Cons
Advantages

1. Slower for inserts, as the number of nodes needs to match the number of columns.
2. More disk space consumption. Since global indexes (understood as array indexes) with column names occupy disk space and are duplicated for each row.

1. Faster access to individual column values, as there is no need to parse the row. In my tests, it's 11.5% faster with 2 columns and even more with a larger number of columns.
2. Easier to change the data schema
3. Clearer code

Output: subjective. Since speed is one of the key advantages of globals, there is almost no point in using this implementation, as it is likely to not perform faster than tables in relational databases.

3.4 General case. Trees and ordered trees

Any data structure that can be represented as a tree fits perfectly into globals.

3.4.1 Objects with sub-objects

This is the traditional application area of globals. In the medical field, there are immense numbers of diseases, medications, symptoms, and treatments. Creating a table with a million fields for each patient is impractical. Moreover, 99% of the fields would be empty.

Imagine an SQL database with tables: ‘patient’ ~ 100,000 fields, ‘Medication’ — 100,000 fields, ‘Therapy’ — 100,000 fields, ‘Complications’ — 100,000 fields, etc. Alternatively, one could create a database with many thousands of tables, each tailored for a specific type of patient (which may indeed overlap!), treatment, medication, and thousands more tables to link these tables.

Globals are perfectly suited for medicine, as they allow the creation of an accurate description of each patient's medical history, various therapies, and medication actions in the form of a tree, without wasting extra disk space on empty columns, as would be the case in a relational model.

Globals are convenient for building databases with information about people, when it's important to accumulate and systematize as much varied information about the client as possible. This is in demand in the medical field, banking sector, marketing, archival work, and other areas.

.
Certainly, it is also possible to emulate a tree in SQL using just a few tables (EAV, 1,2,3,4,5,6,7,8,9,10), however, this is significantly more complicated and will work slower. Essentially, it would require writing a global working on tables and hiding all table interactions under a layer of abstraction. It is incorrect to emulate a lower-level technology (globals) using a higher-level one (SQL). This is impractical.

It’s no secret that changing the schema of gigantic tables (ALTER TABLE) can take considerable time. MySQL, for instance, performs ALTER TABLE ADD|DROP COLUMN by fully copying information from the old table to the new one (I tested MyISAM and InnoDB engines). This can hang a working database with billions of records for days, if not weeks.

Changing the data structure, if we use globals, costs us nothing. At any moment we can add any required new properties to any object, at any level of hierarchy. Changes related to renaming branches can be launched in the background on a running database.


Therefore, when it comes to storing objects with a vast number of optional properties, globals are an excellent choice.

Moreover, let me remind you, access to any of the properties is instantaneous, as all paths in a global are represented by a B-tree.

Databases based on globals, in general, are a type of document-oriented DB, with the ability to store hierarchical information. Therefore, in the field of storing medical records, globals can compete with document-oriented databases. But still, it's not quite comparable.Let's take MongoDB, for example. In this area, it loses to globals for the following reasons:

1. Document size. The unit of storage is text in JSON format (more precisely BSON) with a maximum size of about 16MB. The restriction is deliberately set so that the JSON database does not slow down during parsing if it stores a huge JSON document and later refers to it by fields. This document should concentrate all information about the patient. We all know how thick patient records can be. The maximum size of 16MB immediately eliminates patients whose disease records include MRI files, X-ray scans, and other studies. In one branch of a global, however, you can have information spanning gigabytes and terabytes. In principle, this could be the end of the discussion, but I will continue.
2. Time for awareness/change/deletion of new properties in the patient map. Such a database must load the entire map into memory (that's a large volume!), parse BSON, add/change/delete a new node, update indices, pack it into BSON, and save it to disk. For the global, it's sufficient to simply access a specific property and perform operations on it.
3. Speed of access to individual properties. With multiple properties in a document and its multi-level structure, access to individual properties will be faster since each path in the global is a B-tree. In BSON, however, you will need to parse the document linearly to find the required property.

3.3.2 Associative Arrays

Associative arrays (even with nested arrays) fit perfectly into globals. For example, such an array from PHP will be represented in the first image of section 3.3.1.

$a = array(
  "name" => "Vince Medvedev",
  "city" => "Moscow",
  "threatments" => array(
    "surgeries" => array("apedicectomy", "biopsy"),
    "radiation" => array("gamma", "x-rays"),
    "physiotherapy" => array("knee", "shoulder")
  )
);

3.3.3 Hierarchical Documents: XML, JSON

They are also easily stored in globals. Various ways of structuring can be used.

XML
The simplest way to map XML into globals is to store tag attributes in the nodes. And if quick access to tag attributes is needed, they can be extracted into separate branches.

<note id="5">
<to>Vasya</to>
<from>Sveta</from>
<heading>Reminder</heading>
<body>Call me tomorrow!</body>
</note>

On COS, this will correspond to the code:

Set ^xml("note")="id=5"
Set ^xml("note","to")="Sasha"
Set ^xml("note","from")="Sveta"
Set ^xml("note","heading")="Reminder"
Set ^xml("note","body")="Call me tomorrow!"

Note: For XML, JSON, and associative arrays, many different ways of mapping to globals can be devised. In this case, we did not reflect the order of nested tags in the note tag. In the global ^xml nested tags will appear in alphabetical order. To strictly reflect the order, you can use a mapping like this:

JSON.
The first image in section 3.3.1 shows the representation of this JSON document:

var document = {
  "name": "Vince Medvedev",
  "city": "Moscow",
  "treatments": {
    "surgeries": ["apedicectomy", "biopsy"],
    "radiation": ["gamma", "x-rays"],
    "physiotherapy": ["knee", "shoulder"]
  },
};

3.3.4 Identical Structures Linked by Hierarchical Relationships

Examples: structure of sales offices, location of people in a MLM structure, chess opening database.

Opening database. You can use the evaluation of the strength of moves as the value of the global node index. Then, to select the strongest move, it will be enough to choose the branch with the highest weight. In the global context, all branches at each level will be sorted by move strength.

Sales office structure, structure of people in MLM. The nodes can store certain caching values reflecting the characteristics of the entire subtree. For example, the sales volume of that subtree. At any time, we can retrieve a figure reflecting the achievements of any branch.

4. When is it most advantageous to use globals?

The first column presents cases where you will gain a significant speed advantage by using globals, and the second where development or data model will be simplified.

Speed
Convenience of processing/presenting data.

1. Insertion [with automatic sorting at each level], [indexing by the main key].
2. Deletion of subtrees.
3. Objects with a multitude of nested properties requiring individual access.
4. Hierarchical structure with the ability to traverse child branches from any point, even from nonexistent ones.
5. Deep traversal of subtrees.

1. Objects/entities with a vast number of optional [and/or nested] properties/entities.
2. Schema-less data. When new properties can frequently emerge and old ones disappear.
3. A non-standard database needs to be created.
4. Path databases and decision trees. When paths are conveniently represented as trees.
5. Deletion of hierarchical structures without using recursion.

Continued Globals are data storage swords with sparse arrays. Part 3..

Disclaimer: This article and my comments on it reflect my opinion and do not represent the official position of InterSystems.

Source: habr.com