KR101550679B1 - Method For Combining Column-Wise Query Engine With Dynamic Compilation - Google Patents

Abstract

A method for combining a query processing engine with dynamic compilation and a column prioritized approach is disclosed.
A method of combining dynamic compilation and a query processing engine of a column-wise arrangement type in a database system, the method comprising: receiving a query; Generating a primitive source code which is a minimum operation unit for executing the query in the database system; Generating a primitive as an execution code by using a dynamic compiler of the primitive source code, and executing the primitive and generating a query processing result. Provides a way to combine query processing engines.

Description

[0001] The present invention relates to a method for combining dynamic compilation and a column-priority array query engine,

The present invention relates to a method of combining a dynamic compilation method with a query processing of a column-wise arrangement method.

It should be noted that the following description merely provides background information related to the present embodiment and does not constitute the prior art.

Many commercialized database systems are processing queries in a Tuple-at-a-time manner based on NSM (N-ary Storage Model) data storage structure. Such a scheme consumes most of the time for the CPU (Central Processing Unit) to traverse the query operation tree, rather than the actual data processing. The Tuple-at-a-time query execution method degrades instruction cache performance due to function calls to obtain tuples, and frequent branching makes execution difficult to predict, leading to performance degradation have. Moreover, the Tuple-at-a-time execution method can not use the Loop-Unrolling, SIMD (Single Instruction Multiple Data) instructions, It does not make good use of important functions.

The query processing engine of the database management system (DBMS) analyzes the input query syntax in real time in the situation where the query syntax such as SQL (Structured Query Language), which is a declarative language, And interpreting it to compile it. The interpreting method is an internal data structure (tree or graph) during execution of the internal calculation sequence and logic for query processing, and traverses this data structure every calculation. In the interpreting method, it is disadvantageous that the data structure is circulated and the data is processed in a large amount of overhead.

The data structure used in the interpreting method and the structure for traversing the data structure are shown in FIG. Since the get_next () function of the operator is called to obtain one tuple, a mismatch occurs in the instruction cache of the CPU (Central Processing Unit) frequently. In addition, because the state value of each physical operator must be maintained, a data cache inconsistency often occurs.

In addition to the overhead of interpreting the query syntax, the interpreting method frequently generates instruction cache inconsistencies due to the frequent occurrence of branches, and the pipelining and SIMD (Single Instruction Multiple Data ) Technology is difficult to utilize.

The main object of the present embodiment is to provide a method of combining a dynamic compilation and a query processing engine of a column priority arrangement type in a query processing engine of a database system.

According to an aspect of the present invention, there is provided a method of combining dynamic compilation and a query processing engine of a column-wise arrangement scheme in a database system, the method comprising: receiving a query; Generating a primitive source code which is a minimum operation unit for executing the query in the database system; Generating a primitive as an execution code by using a dynamic compiler of the primitive source code, and executing the primitive and generating a query processing result. Provides a way to combine query processing engines.

According to another aspect of the present invention, there is provided an apparatus for combining dynamic compilation and a query processing engine of a column prioritization scheme, the apparatus comprising: a database storage unit for storing database data; A query receiving unit that receives a query; A primitive source code generation unit for generating a primitive source code which is a minimum operation unit for executing the query in a database system; A dynamic compiler for generating a primitive which is an execution code by using a dynamic compiler of the primitive source code and a query execution unit for executing the primitive and generating a query processing result, Method query processing engine.

As described above, according to the present embodiment, in the column-wise query engine of the column-priority arrangement type in which the query is processed based on the column priority array, the operator processes all the column data, By performing the operation of the step, you can reduce the function calls and use the pipeline (Pipeline) and Sing Instruction Multiple Data (SIMD) instructions which are the advantages of the latest CPU. The vector form used by the query processing engine of the column-first array type can be represented by a one-dimensional array, thereby reducing the cost of the interpretation. This may be possible by combining certain columns and performing them in one operation when a plurality of columns are continuously used in the operation.

According to the present embodiment, the dynamic compilation method reduces the interpretation overhead and the code generation by the compiler is faster than the interpreter method. In addition, when combining the dynamic compilation and the query processing engine of the column priority arrangement method, the register of the CPU can be utilized, and a process of storing the intermediate result necessary for the column vector calculation in the memory (Write Back) becomes unnecessary. The primitives generated by the compiler can save the intermediate result to the CPU register without memory access, and can be used in the next operation, thereby reducing the memory access for storing the intermediate result, thereby improving the performance of the system.

According to the present embodiment, the loop unrolling technique increases the index of the loop at regular intervals when the argument used in the loop is used only in the loop, and the operation on the column vector between the It is possible to improve the performance of the system by optimizing the use of the pipeline and the cache of the CPU by reducing the branch caused by the loop by executing the code repeatedly in the separate body in the body of the loop. An array of data types, such as a database column vector, can use a SIMD instruction that can perform multiple rows as a single operation, similar to loop unrolling. The SIMD instruction is an efficient way to maximize the CPU's ability, but it is difficult to use it in the interpreting method, but it is possible to generate the CPU-optimized SIMD instruction code if dynamic compilation is possible.

Combining dynamic compilation and column-oriented query processing engines can maximize the use of the CPU's pipeline, cache, and registers, as well as optimize SIMD instructions. Even if the CPU of the system in use is changed, the execution code optimized for the changed CPU can be generated by changing the SIMD instruction setting of the dynamic compiler.

FIG. 1 is an illustration of a method of operating a Tuple-at-a-time type engine.
2A is an illustration of an example of a database table.
2B is an illustration of an example of a low priority storage scheme.
2C is an illustration of an example of the column priority storage method according to the present embodiment.
3A is a flowchart of a query processing process of a database of a Tuple-at-a-time method.
FIG. 3B is a flowchart of a process of processing a query by combining the dynamic compilation according to the present embodiment and the query processing engine of the column priority arrangement method.
FIG. 4A is an example of a query syntax and an example of a primitive source code therefor.
4B is an example of a primitive source code to which loop unrolling according to the present embodiment is applied.
4C is an illustration of a primitive source code using a SIMD instruction according to the present embodiment.
5 is an illustration of a method for combining operations for generating primitives in a query syntax according to the present embodiment.
FIG. 6 is a block diagram of an apparatus for combining a dynamic compilation and a query processing engine of a column priority arrangement scheme according to the present embodiment.

Hereinafter, the present embodiment will be described in detail with reference to the accompanying drawings.

The database query processing engine according to the present embodiment is characterized in that the performance is improved at a micro level compared to a conventional query processing engine. Conventionally, a method of optimizing a query operation to improve the performance of a query processing engine is used. However, in the present invention, in order to improve the performance by making full use of the technologies of the pipeline of the CPU, L1, L2 cache, SIMD, The method comprising the steps of:

FIG. 1 is an illustration of a method of operating a Tuple-at-a-time type engine.

Tuple-at-a-time method is widely used in existing databases such as MySQL. In this method, when a query is given, a physical operator is constructed as a tree at execution time from a query plan for query processing. To get a single tuple, we call the get_next () function on the top node of the tree and the get_next () function on the descendant node recursively. Each call returns a tuple, It is passed to the get_next () function.

However, the Tuple-at-a-time type of engine has a problem that Instruction Cache mismatch frequently occurs in the CPU because the get_next () function of several operators is called to obtain one tuple. (Data Cache) inconsistency often occurs because the state value of the Physical Operator must be maintained. Also, calling the get_next () function frequently can cause the CPU to spend a lot of time. In the case of the C ++ programming language, the time taken to call a virtual function corresponds to 20 cycles in the CPU. Since the get_next () function is mostly implemented as a virtual function, the recursive call of the get_next () function for a complex query consumes a lot of CPU time.

2A is an illustration of an example of a database table.

FIG. 2A is an illustration of the structure of a table that is a basic unit of relational database data storage. 2A includes columns of ID, Name, and Age. For each column, the first row values "101 "," Yongjin ", and "32 " form one tuple . There are a row-wise method and a column-wise method for physically storing data in a storage device in a database. This will be described in detail in FIGS. 2B and 2C.

2B is an illustration of an example of a low priority storage scheme.

Row-Wise storage stores tuple values in a contiguous space. When the table of FIG. 2A is stored in the low priority storage mode, "101", "Yong Jin Jin" and "32" are stored in successive spaces and the tuples "102" Is stored next. In such a low-priority storage method, a CPU data cache inconsistency occurs in a database characterized by a column-by-column operation, and there is a problem that SIMD instructions and registers are difficult to efficiently use.

2C is an illustration of an example of the column priority storage method according to the present embodiment.

The column priority storage method stores the values of one column in a continuous space. "101 "," 102 ", " , "115" are stored in a continuous space, and the values of the Name column "Ahn Yong Jin", "Kim Woo Joong", ... , "Han Yong-Ju" is stored in a continuous space, and the values of Age column "32", "47", ... , And "45" in a continuous space. When the column priority storage method is used, it is possible to increase the data cache hit rate of the CPU in a database which performs a lot of operations on a column basis, to use a SIMD instruction in combination with dynamic compilation, There is an advantage of improving the performance of the database by reducing memory access.

3A is a flowchart of a query processing process of a database of a Tuple-at-a-time method.

When the user or the application program sends a query statement in a declarative language such as SQL to the query processing engine, the query processing engine receives the query statement (S310). The parser of the query processing engine having received the query generates a parse tree from the query syntax by parsing the query sentence (S312). The parser also checks whether the meaning of the query syntax is appropriate. When the parse tree is generated, the parse tree is converted into a relational algebra expression to establish a logical plan (S314). The query processing engine establishes a physical plan (S316) for converting the operator into an operator for executing the relational algebra expression. The query processing engine of the Tuple-at-a-time method performs a query according to the physical plan (S318), and transmits the query execution result to the user or application program requesting the query (S320).

FIG. 3B is a flowchart of a process of processing a query by combining the dynamic compilation according to the present embodiment and the query processing engine of the column priority arrangement method.

In the case of combining the dynamic compilation and the query processing engine of the column priority arrangement method according to the present embodiment, the query is received (S330) as in the Tuple-at-a-time method, the query is parsed (S332) The process of establishing (S334) is the same. However, there is a difference in the method of generating executable code for query processing when the dynamic compilation and the query processing engine of the column priority arrangement method are combined. In the embodiment of the present invention, a source code of a primitive function which is the minimum unit of operation in the query processing method of the column priority arrangement method is generated (S336). The primitive source code is then compiled into a dynamic compiler to generate a primitive (S338). A low level virtual machine (LLVM) can be used as a dynamic compiler to compile primitive source code. However, dynamic compilers are not limited to LLVM. The various operations of the primitive source code can be optimized when generating primitives.

Hereinafter, a primitive optimization method will be described. The database system according to the embodiment of the present invention executes a column vector operation while performing a loop. In the primitive generation process (S336), a source code of a function for performing a loop operation for processing a column vector is generated. If an argument used in a loop is used only in a loop, a loop unrolling process can be performed. Loop unrolling will be described in detail in FIG. 4B.

When using dynamic compilation, it is easy to perform processing of data stored in a column priority manner using a SIMD (Single Instruction Multiple Data) instruction. When the data is stored in the low priority scheme used in the Tuple-at-a-time scheme, it is difficult to use the SIMD because the continuity of the data in the database for processing the data by the column vector is not ensured. However, in the case of having a data layout of a column priority scheme, execution performance can be improved by using a SIMD instruction that can process a plurality of data at one time. The SIMD is described in detail in FIG. 4C.

In the case of using only the query processing engine of the column priority arrangement mode without using the dynamic compiler, there is no overhead to interpolate in a tuple unit, The overhead to be done still exists and the computation result of the vector unit must be stored back into memory. You can not use a register to save intermediate results, and an intermediate result stored in a register to the next operation to reduce memory access. However, if the dynamic compilation method is applied to the query processing engine of the column-priority arrangement method, a primitive can be generated so that the intermediate result is stored in a register without write-back to the memory and then used again for the next operation.

When the primitive generation is completed, the query processing engine executes a query by executing a primitive (S340). Then, the query execution result is transmitted to the user or the application program which has requested the query again (S342).

FIG. 4A is an example of a query syntax and an example of a primitive source code therefor.

Figure 4A is an example of a query syntax that can be passed to a database system and is an example of primitive source code for this syntax. In the query statement, four column vectors l_extendedprice, l_discount, l_tax, and sum_charge are used. In the query processing engine of the column priority arrangement type, four primitives can be used to process the query statement. In the first primitive, 1-l_discount is computed using the l_discount column in the query statement and stored in the output_1 column vector. In the second primitive, 1 + l_tax is calculated using the l_tax column and stored in the output_2 column vector. In the third primitive, the output_1 column vector is multiplied by the output_2 column vector, and the result is stored in the output_3 column vector. In the fourth primitive, the output_4 vector is generated by multiplying the l_extendedprice column vector by the output_3 vector calculated from the third primitive. However, there is a problem in that it is necessary to generate all possible primitives because the query processing engine does not know which query is to be input.

4B is an example of a primitive source code to which loop unrolling according to the present embodiment is applied.

In FIG. 4A, a loop operation is performed to perform a query. This causes a branch due to the loop. Such a branch causes degradation of the pipeline performance of the CPU. In order to reduce the branch due to the loop, the program code can be written so that no branch occurs within a certain range of the loop when the argument used in the loop is not used outside the loop. This process is called Loop-Unrolling. When loop unrolling is applied, branching is reduced and optimized for the CPU pipeline, improving query processing engine performance. In the primitive source code of FIG. 4B, the index used for the loop operation is incremented by 4, and the calculation between the columns is repeatedly performed in the body of the loop in a separate code.

4C is an illustration of a primitive source code using a SIMD instruction according to the present embodiment.

When processing data in the form of an array, a plurality of array elements can be grouped together and processed as a vector operation at a time. This is called SIMDization. 4C is an example of a primitive source code of a process of loading four values in the l_dependentprice and l_discount columns into consecutive memory spaces, performing an operation on them, and storing the results in a memory. SIMD improves the throughput of a system by processing multiple pieces of data in parallel at the same time with a single instruction.

SIMD instructions used in the CPU can be changed even with small changes in the CPU, making it difficult for the dynamic compiler to cope with these changes. Therefore, the dynamic compiler needs a means to receive information from outside about which SIMD instruction to use while generating a primitive. This can be done in various ways, such as using a dynamic compiler API or a configuration file, and is not limited to any one method.

5 is an illustration of a method for combining operations for generating primitives in a query syntax according to the present embodiment.

In the query syntax shown in FIG. 5, six column vectors l_returnflag, l_extendedprice, l_discount, l_tax, l_quantity, and refund are used. When the matrix of the example shown in FIG. 5 is generated by using the six column vectors as rows and columns, and the number of column pairs appearing in the query syntax is obtained, the l_extendedprice and l_discount column pairs are divided into two columns, l_extendedprice, l_tax, l_discount, l_tax, l_quantity The refund column pair appears once each time. Priority is assigned according to the number of occurrences. If the priority is higher than a certain priority, operations including the column pair are combined into one to generate a primitive. The l_extendedprice and l_discount column pairs appear with the highest frequency, giving the highest priority. Therefore, operations including l_extendedprice and l_discount column pairs with the greatest number of occurrences can be combined into a single primitive. l_extendedprice * (1-l_discount), (l_extendedprice * (1-l_discount) * (1 + l_tax)) operation generates a primitive by combining operations on column pairs appearing above a certain priority. Lt; / RTI > primitive. If you do not combine operations, l_extendedprice * (1-l_discount) will need primitives to calculate 1-l_discount and store it in output1 and a primitive to calculate l_extendedprice * output1 and store it in output2. However, if we combine this operator with a single primitive in units of operations, it is not necessary to store ouput1 in memory in order to store 1-l_discount, and the result of 1-1_discount is stored in the CPU register, and the register and l_extendedprice Lt; / RTI >

FIG. 6 is a block diagram of an apparatus for combining a dynamic compilation and a query processing engine of a column priority arrangement scheme according to the present embodiment.

In the query processing engine of the database system, the apparatus 500 for combining the dynamic compilation and the query processing engine of the column prioritizing method includes a query receiving unit 510 for receiving a query from a user or an application program, A logical plan generation unit 530 for generating a relational algebra expression in the parse tree, a source code generation unit 530 for generating a source code for a primitive that performs an actual query operation in the logical plan, A primitive generating unit 550 for generating primitive binary codes by compiling primitive source codes, a query executing unit 560 for executing a query by executing primitives, a query executing unit 560 ), The query execution result obtained from the query execution result is transmitted to the user or the application program And a transfer unit 570.

The apparatus 500 for combining the dynamic compilation and the query processing engine of the column priority arrangement method according to the embodiment of the present invention may be a personal computer (PC), a notebook computer, a tablet, a personal digital assistant Digital assistant, a game console, a portable multimedia player (PMP), a PlayStation Portable (PSP), a wireless communication terminal, a smart phone, a TV, User terminal. The apparatus 500 for combining the dynamic compilation and the column priority arrangement query processing engine according to the embodiment of the present invention may be a server terminal such as an application server and a service server. The apparatus 500 for combining the dynamic compilation and the column priority arrangement query processing engine according to the embodiment of the present invention includes (i) a communication device such as a communication modem for performing communication with various devices or wired / wireless communication networks, (ii) A memory for storing data for executing the program, and (iii) a microprocessor for executing and controlling the program by executing the program. According to at least one embodiment, the memory may be a computer such as a random access memory (RAM), a read only memory (ROM), a flash memory, an optical disk, a magnetic disk, or a solid state disk Readable recording / storage medium. According to at least one embodiment, a microprocessor can be programmed to selectively perform one or more of the operations and functions described in the specification. In accordance with at least one embodiment, the microprocessor may be implemented in hardware, such as an Application Specific Integrated Circuit (ASIC), in wholly or partially of a particular configuration.

The foregoing description is merely illustrative of the technical idea of the present embodiment, and various modifications and changes may be made to those skilled in the art without departing from the essential characteristics of the embodiments. Therefore, the present embodiments are to be construed as illustrative rather than restrictive, and the scope of the technical idea of the present embodiment is not limited by these embodiments. The scope of protection of the present embodiment should be construed according to the following claims, and all technical ideas within the scope of equivalents thereof should be construed as being included in the scope of the present invention.

500 Dynamic compilation and a device that combines a query processing engine in a column-first array manner
510 query receiver 520 parser
530 Logical Plan Generation Unit 540 Primitive Source Code Generation Unit
550 dynamic compiler 560 query execution unit
570 < tb >

Claims (11)

A method for combining dynamic compilation and a column-wise array query processing engine in a database system,
Receiving a query;
Generating a primitive source code which is a minimum operation unit for executing the query in the database system;
Generating a primitive which is an execution code by using a dynamic compiler;
Executing the primitive and generating a query processing result,
In the generating of the primitive, when the query includes a plurality of operators, the primitives are generated by combining the plurality of operators based on the frequency of accesses to the column pairs included in the query syntax. A method to combine dynamic compilation and query processing engines in a column-by-array manner. The method according to claim 1,
Wherein the table storing method of the database system is a column-wise arrangement method. The method according to claim 1,
Wherein the primitive source code comprises a loop operation on a column vector basis. The method according to claim 1,
Wherein the generating of the primitive includes: when a factor used in the loop in the primitive source code is used only in the loop,
And a loop unrolling process for the loop. ≪ Desc / Clms Page number 21 > The method according to claim 1,
Wherein the step of generating the primitive includes a step of generating an SIMD instruction when an array type data format is found, the method comprising combining a dynamic compilation and a column priority arrangement query processing engine. The method according to claim 1,
Wherein the dynamic compiler includes a step of acquiring SIMD instruction information that can be processed by a central processing unit (CPU). delete The method according to claim 1,
The generating of the one primitive includes:
Storing an access frequency for a column pair included in the syntax of the query;
A process of assigning a higher priority to the access frequency as the value of the access frequency is larger, and
Preset Combining the operations including the column pair having a priority higher than the priority to generate the primitive
And a query processing engine for performing dynamic compilation and column prioritization. On the computer,
Receiving a query;
Generating a primitive source code that is a minimum operation unit for executing the query in the database system;
Generating a primitive which is an execution code by using a dynamic compiler;
Executing the primitive and generating a query processing result,
In the process of generating the primitive, when the query includes a plurality of operators, a process of generating a single primitive by combining the plurality of operators based on an access frequency for a column pair included in the query syntax A computer-readable recording medium having recorded thereon a program for performing the method. 1. An apparatus for combining dynamic compilation and a query processing engine in a column prioritized manner,
A database storage unit for storing database data;
A query receiving unit that receives a query;
A primitive source code generation unit for generating a primitive source code which is a minimum operation unit for executing the query in a database system;
A dynamic compiler for generating a primitive which is an execution code using the dynamic compiler;
And a query execution unit for executing the primitive to generate a query processing result,
Wherein when the query includes a plurality of operators, the dynamic compiler combines the plurality of operators based on the frequency of accesses to the column pairs included in the syntax of the query to generate one primitive. A device that combines a query processing engine of the column priority arrangement type. 11. The method of claim 10,
Wherein the table storing method of the database storing unit is a column-wise arranging method.

Images