Improving the performance of modern computing devices requires the adaptation of data processing algorithms for the efficient use of hardware resources. This article provides comparisons of existing database management systems and shows their disadvantages when used in conjunction with parallel processing algorithms. An approach to data storage is presented that can be used to optimize the execution of database queries using parallel processing. A method for constructing the proposed data structuring storage algorithm is described. At the same time, the advantages of the algorithm and the ways of interaction with it to achieve greater benefits in comparison with the existing analogs are shown.
With increasing productivity of modern computing systems [
In the article [
In this article, for more efficient reading of data from the database, we propose the use of a modified tree algorithm.
The most popular algorithm currently used by the DBMS is B + -tree. It belongs to the B-tree group, which are balanced trees. The main advantage of using B + tree in a DBMS is the method of data storage - all data is stored in the leaves of the tree, which can be linked to each other. This allows storing data in adjacent blocks, which reduces the chances of missing a cache in the process of paging data from the main memory. Because of the fact that the number of reading operations from a disk decreases, the overall data reading speed will be increased.
However, despite the increase in data reading performance when using B + -tree,
the algorithms for their application are not optimal when processing a large number of
database queries and when using multi-thread processing of query data[
Another type of tree that is used for parallel processing is the k-d tree. Its main
advantage is the effective search for keys in a given range. Such a tree is useful to use in
databases designed to store geometric data, for example, coordinates on a map. The
authors of the article [
The basic idea of creating a tree is that the tree should be distributed according to the number of physical cores available on the machine on which the DBMS is to be installed.
The tree must comply with the rules: ─ it must have a main vertex or root of a tree; ─ the tree consists of subtrees, which we will call child trees, each of which has its own root, which we will call child roots; ─ the root has connections with the child roots, each of which represents a root for its part of the tree; ─ the number of daughter roots must be equal to the number of physical cores of the involved processor for more efficient use of resources; ─ each subtree is traversed according to the rules of that subtree. Thus, all subtrees may not necessarily be of the same type, but on the contrary, each subtree can be implemented in accordance with various algorithms, including various traversal algorithms of this subtree.
Creating a tree is done in accordance with the rules:
Before determining which of the subtrees should add a new element, it is necessary to find the necessary child root. For a uniform distribution, the direction of passage from the child root with index 0 to the child root with index N alternates with the opposite direction. At each iteration, the following algorithm is executed: start { if(one_of_child_trees_ is_empty) { if (current_ child_tree_ is_empty) { current_child_tree.Add(new_element); sort(all_nodes); } else { go_to_next_in_order_child_root(); } } else if (more_than_one_of_child_trees_is_empty) { If (current_ child_tree_ is_empty) { current_child_tree.Add(new_element); } } else { If (current_direction_ equals_B) { function_1(); } else if (current_direction_ equals_A) { function_4(); } } } function_1 { If (new_element < maximum_of_current_node && new_element > minimum_of_current_node) { current_child_tree.Add(new_element); } function_2(); } function_2 { If (new_element < minimum_current_subtree AND new_element > maximum_of_next_subtree) { next_child_tree.Add(new_element); from узел_n to узел_0 { function_3 (node_i); } } else { go_to_next_in_order_child_root(); } } function_3 { If (size_of_current_subtree > Size_of_next_in_order_subtree) { next_child_tree.Add(minimum_of_current_subtree); current_child_tree.Remove(minimum_of_current_subtree); } } function_4 { If (new_element < maximum_of__current_subtree && new_element > Minimum_of_current_subtree) { current_child_tree.Add(new_element); } function_5 (); } function_5 { if (new_element > maximum_of_current_subtree AND new_element < minimum_of_next_subtree) { next_child_tree.Add(new_element); (1) The operation «Add» involves adding an element to the appropriate subtree according to the rules of that subtree. Performing the above described algorithm spends additional time at the stage of storing data in the tree, however, it allows to sort the data in the corresponding subtrees. This reduces the number of reads from the tree, and therefore increases the overall read performance of the tree.
The nodes should store the keys of each record without data. The target data set
that the user expects to receive is to be stored in the leaves of the tree. This will
minimize the number of reading operations from memory, thus speeding up queries. And
also, it separates the logic of finding the target element in the tree and accessing the
memory. Thus it is possible to use various computer resources for each operation.
For example, in article [
Based on the presented description of the algorithm, the scheme of the resulting tree is shown (see Fig. 2).
Figure 2 shows an example of a created tree for working with data under the control of a processor that has 4 physical cores. The user configures the number of child roots during the creation of the database.
The root of the tree from which the DBMS starts processing queries has connections with the child roots. At the first stage of processing, it is necessary to make a choice in which of the child trees to search for the requested data. Its physical processors must process each of the child trees. If one of the cores cannot be used on the computer, it is possible to use threads. Next, there is a need to make a pass through the corresponding subtree. Since there is an abstraction on subtrees, any tree structure can be applied to its subtree. However, the proposed use of B + - the tree is because it is well adapted to the storage of data of various types, in contrast to, for example, from k-d trees.
In the article [
The database created on the implementation of the proposed tree algorithm will faster process queries for reading data on high-performance hardware. A special increase in performance will be noticeable for databases in which read operations are most often performed.
In order to optimize database queries, it is possible to use different types of trees. However, even the most frequently used ones have their drawbacks, which consist of poor adaptation to parallel processing. 4
A tree algorithm has been developed that will efficiently process database queries using the processing power of the processor, which performs the search for keys and also the processing power of the graphics device that searches for data records using the received key.
Based on the proposed algorithm, it is planned to create a new database management system and create an experimental database in it in order to conduct an experiment. As a result, temporary assessments and an assessment of the overall efficiency of the use of this tree will be obtained.
The research was funded by RFBR and CITMA according to the research project №18-57-34001