Analysis of Some Algorithm of the Join Operation

Abstract

The relational approach to database organization has experienced enough collisions during its existence and has been repeatedly subjected to serious, and often unfounded, criticism. One of the points of criticism was the objection to the Join operation, which was considered ex-tremely inefficient. However, this operation existed in the earliest data processing systems. In early publications, it belongs to the class of merging non-strictly ordered information arrays. Later, it was called the operation of merging non-strictly ordered files. In recent works in the field of machine learning, the direction associated with relational databases has begun to actively develop. Modern analytical systems in manufacturing, finance, banking, medicine and many oth-er areas are based on large volumes of structured data that are stored, as a rule, in relational data-bases. An important direction for accelerating the implementation of queries in such databases is the use of parallel data processing methods. And since the Join operation is the most complex of all other operations that make up queries, the issues of choosing the most effective algorithms for its implementation, which, in turn, can be simple and effective, are of great importance. The arti-cle proposes an algebraic method for formalizing the Join operation. Based on this method, an algorithm for its implementation using a specific queue structure called a “scoop” is proposed. The results of an experimental analysis of the algorithm are presented, confirming its advantage over the algorithm implemented in the used Microsoft SQL Server database management system. Methods for parallel implementation of the proposed algorithm are given. For this purpose, a traditional flow approach and an approach based on the architecture of a computing system with associative resource distribution are used.