JP5382383B2 - Database processing apparatus, database processing method, program, and database data structure - Google Patents

Description

  The present invention relates to a database technology using GPGPU (General Purpose Computing on Graphics Processing Units).

In recent years, attention has been paid to GPGPU technology that allows a general-purpose arithmetic processing to be performed by a parallel arithmetic unit such as a GPU (Graphics Processing Unit). GPU is CPU (Central Processing)
The degree of parallelism of the computing units is higher than that of Unit, and the computation throughput is high. Further, it has a configuration similar to a SIMD arithmetic unit that supplies instructions to a plurality of arithmetic units. In order to achieve high processing performance using GPGPU, the number of instruction branches should be reduced, and the data supply to a certain set of computing units must be consistent with the data supplied. It is necessary to have a state.

  The data structure by the column store is considered to be a structure suitable for processing by a parallel computing unit such as GPGPU. Since data processing of fixed length data is expressed as a fixed length array for each column by the column store, this may be used for data processing by GPGPU.

  For example, Non-Patent Document 1 discloses a technique for performing a full-text search of the content of a single large-scale text with the aid of GPGPU.

Ryuichi Higashi, Noriyuki Fujimoto, Kenichi Sugawara, “Examination of high-speed full-text search for large text on main memory using GPU's general-purpose computing environment CUDA”, IPSJ Research Report, No. 19, 2008, pp. 139-144

  However, a database that efficiently stores a data group including variable-length data and a database processing method that can efficiently process such a database have not yet been realized.

  The present invention has been made in view of the above problems, and provides a database system, a database processing method, and the like that can implement efficient database processing for variable-length data using a parallel computing unit. Objective.

The present invention is a database processing apparatus having a parallel computing unit, which determines a fragment length according to a data processing unit of the parallel computing unit, and stores tuple data including variable length data in a fragment in a column store database. In addition, when processing the data stored in the column store database, the data storage means for storing the fragment metadata as a fragment header, the fragment to be assigned to each thread is determined with reference to the metadata, Parallel operation means for allocating fragments to each thread and executing parallel operations on the basis of each of the threads, the parallel operation means searches for a character string for the allocated fragment in each thread, and the byte position of the fragment as a search result Bit invert A means for recording things, and assigning a number of the search results corresponding to the data processing unit of the parallel computing unit to each thread, detecting bit inversion for the assigned search results in each thread, and a detection result flag And a means for recording as a tuple level search result .

The present invention relates to a data processing method in a database processing apparatus having a parallel computing unit, wherein a fragment length is determined according to a data processing unit of the parallel computing unit, and tuple data including variable length data is stored in a column store database. A data storage step for storing the fragment metadata as a fragment header and processing the data stored in the column store database to determine a fragment to be assigned to each thread with reference to the metadata. A parallel operation step for assigning a fragment to each thread based on the determined content and executing a parallel operation , wherein the parallel operation step searches for a character string for the allocated fragment in each thread, and as a search result Hula A bit-inversion of the byte position of the event, and a number of the search results corresponding to the data processing unit of the parallel computing unit are allocated to each thread, and each thread has a bit for the search result allocated. A database processing method comprising: detecting inversion and recording a detection result flag as a tuple level search result .

The present invention determines a fragment length according to a data processing unit of the parallel computing unit in a computer having a parallel computing unit, stores tuple data including variable length data in the fragment in the column store database, and also includes a fragment header. In the data storage step for storing the metadata of the fragment, in processing the data stored in the column store database, the fragment to be assigned to each thread is determined with reference to the metadata, and each thread is determined based on the determined content parallel operation step of executing a parallel operation by assigning a fragment, is executed, the parallel operation step, in each thread, search for the string for the allocated fragment, results byte position of a fragment obtained by bit inversion as And a number of the search results corresponding to the data processing unit of the parallel computing unit are allocated to each thread, and in each thread, bit inversion is detected for the allocated search results, and a detection result flag Recording a tuple level search result as a tuple level search result .

The present invention provides a data structure of a column store database has a fragment length of a fixed length determined by the computer according to the data processing unit of the parallel arithmetic unit, tuple data containing variable length data is stored by the computer and fragments that have been, by the computer, which is assigned to each of said fragment, and numbers indicate the order of the fragments, and fragment header indicating an offset from the tuple head position of said fragment rearmost data position, Is a data structure of a database comprising

  According to the present invention, efficient database processing can be realized even for variable-length data using a parallel computing unit.

FIG. 1 is a schematic diagram of a system configuration of a database system according to an embodiment of the present invention. FIG. 2 shows an example of the data structure in the database. FIG. 3 is a flowchart for explaining the operation of the database system. FIG. 4 is a diagram exemplifying search processing results recorded in the storage area. FIG. 5 is a diagram illustrating a reprocessing result recorded in the predetermined storage area. FIG. 6 is a diagram illustrating an outline of the operation of the database system. FIG. 7 is a flowchart for explaining processing for determining a fragment to be assigned to each thread by the parallel processing unit. FIG. 8 is a flowchart for explaining a process in which the variable length data storage / processing unit stores data in the database.

  Embodiments of the present invention will be described below with reference to the drawings.

  FIG. 1 is a schematic diagram of a system configuration of a database system according to an embodiment of the present invention. As shown in the figure, this system includes a database 10 and a database processing device 20, which are connected by a network such as a LAN (Local Area Network).

  The database 10 is a column store database. The management unit of the database 10 is a tuple, a column, a table, and a schema, and a plurality of units can be stored for each upper structure. A tuple contains a row of data inside the database. In a certain column store, data of a specific column is collected in units of tuples.

  The database processing device 20 includes a host computer and a coprocessor (parallel computing unit). The database processing device 20 includes a parallel computing unit environment detection unit 21, a variable length data storage length determination unit 22, a variable length data storage / processing unit 23, a parallel processing unit 24, a data processing result / storage / reprocessing unit 25, and the like. Prepare.

  The parallel computing unit environment detection unit 21 acquires information (data processing unit or the like) related to the processing capability of the parallel computing unit (GPU) in this apparatus. The variable length data storage length determination unit 22 determines the data storage length (fragment length) in the database 10 based on the information acquired by the parallel computing unit environment detection unit 21.

  The variable length data storage / processing unit 23 stores data in the database 10 based on the data storage length determined by the variable length data storage length determination unit 22. Variable-length tuple data (column tuple) including fixed-length data in column units is stored in fixed-length fragments. Tuple data of a certain column is stored in a fragment set composed of a plurality of fragments as necessary.

  An example of the data structure of the database 10 is shown in FIG. As illustrated, data stored in the database 10 includes a fragment and a fragment header attached to the fragment. The fragment stores partial data or the whole of one column tuple. The fragment header stores metadata related to the column tuple. Fragments belonging to the same tuple are always stored continuously. The fragment header indicates a number (ct id) indicating the order of fragments storing partial data of the column tuple, and an offset (Length) from the tuple head position of the fragment last data position.

  The fragment length can be a fixed length for each column in the fragment set, but can be set independently for each column or for each fragment set. The variable length data storage length determination unit 22 measures the data length appearing in the column or fragment set, and uses a suitable algorithm to increase the processing efficiency or the space efficiency suitable for the processing capability of the parallel computing unit. Can guide you. For example, a data length (4, 8, 16, 32, 64 bytes, etc.) suitable for the data processing unit of the parallel computing unit may be set. In addition, an average value of the data length of variable length data or the like may be set, and a data length suitable for a data processing unit of a parallel computing unit near the average value may be set.

  The parallel arithmetic processing unit 24 performs parallel arithmetic processing on the data stored in the database 10. The data processing result / storage / reprocessing unit 25 processes the calculation result by the parallel calculation processing unit 24.

  Next, the operation of the database system according to this embodiment will be described by taking as an example a case where a character string is searched from the database 21.

  The search execution process includes: 1. When processing across fragments is necessary, Processing across fragments may not be necessary.

  Above 1. In this case, the search target character string (variable length byte string) is longer than the fragment processing storage unit byte length, and the search target tuple is composed of a plurality of fragments. In this case, the responsible fragment is overlapped for each thread and multistage processing is performed. The Nth thread is responsible for the Nth fragment and the (N + 1) th fragment, and the (N + 1) th thread is responsible for the (N + 1) th fragment and the (N + 2) th fragment. The last thread is responsible only for the END-th fragment.

  2. In the case of (1), the search includes a single data input shortest length management unit (Byte) search to a fragment and a search in the case where each fragment can be configured with only one fragment. These are described in 1. above. Can be processed as a special example, and since a plurality of processing stages are not used, high-speed processing is possible. Therefore, hereinafter, the above 1. The case will be described with reference to FIG.

  First, the parallel processing unit 24 secures a storage area for a search processing result set (step S1). The search result is given in bits for each byte inside the fragment in order to correspond to a plurality of hit results. Specifically, the bit position corresponding to the first byte of the search target byte string is inverted.

  The parallel processing unit 24 determines a fragment to be assigned to each thread executed by the parallel computing unit with reference to metadata attached to the fragment (step S2). At this time, the number of fragments to be processed by one thread is changed depending on the fragment length. For example, by setting 8 as the bit length of the byte and the least common multiple of the byte length of the fragment, it is possible to give the same data to all threads without gaps in the result set. For example, for a fragment having a fragment length of 4 bytes, 2 fragments may be given to the thread. For a fragment having a fragment length of 8 bytes, one fragment may be given to the thread. For a fragment with a fragment length of 16 bytes, one fragment may be given to the thread. Further, a fragment to be assigned to each thread may be determined based on the data processing unit of the parallel computing unit. When the arithmetic unit is 32 bits, the data length given to each thread may be a multiple of 32 bits.

  A parallel calculation process is executed based on the content determined in step S2 (step S3). Specifically, the following processing is executed by each thread. When a variable length byte string to be searched is given, the thread calculates the length of the search target byte string. In addition, the position of the fragment set to be handled by the thread is given. The thread sequentially reads the specified fragment and performs a search process to determine whether the search target byte string appears in the read fragment set.

  As a condition for performing the search process, the total length of data stored in the sequential fragments given up to now is calculated, and a predetermined condition [(search target byte string length-1) + sequential fragment data length or more ] May be executed when the above condition is satisfied. That is, as a condition for performing the search process, the search process may be executed when the unprocessed data length in the fragment currently executing the process is longer than the search target byte string. If the condition is not satisfied, the next fragment may be continuously read and the data total length may be calculated to determine whether the above condition is satisfied.

  In the search process, if the first offset of the search target byte string is inside the first fragment assigned to the thread and only one tuple ID is detected in the match area of the search target byte string, the search target byte string is detected. As a result, the bit at the start position is inverted to obtain a search processing result. The search processing result is recorded in a byte-aligned area in units of threads. An example of the search processing result recorded in the predetermined storage area is shown in FIG.

  Next, the data processing result / storage / reprocessing unit 25 secures a storage area for the result set of the recalculation process in order to perform the recalculation process of the search process result (step S4). As a result of the recalculation, it is sufficient to secure a capacity of 1 bit for the tuple. That is, the number of tuples * the number of bits + the number of alignments.

  The data processing result / storage / reprocessing unit 25 determines a fragment to be assigned to each thread (step S5). At this time, by setting the number of tuples to be assigned to one thread to a multiple of 8 which is the bit length of the byte, the tuple level result set can be given the same length to all threads without gaps. Moreover, you may determine the fragment allocated based on the data processing unit of a parallel computing unit. When the data processing unit of the arithmetic unit is 32 bits, the data length given to each thread may be a multiple of 32 bits.

  A parallel calculation process is executed based on the determination content of step S5 (step S6). Specifically, the following processing is executed by each thread. The thread is notified of the tuple ID in charge, the position in charge of reading the result set of the search process, and the position in charge of the fragment set.

  Each thread performs the following processing for the tuple ID that it is responsible for. A fragment is read from the notified position, and its tuple ID is calculated. It is determined whether the tuple ID is in charge. If the tuple ID is in charge, the corresponding search result is read. If the flag is raised, the tuple level flag indicates that the search target byte string exists in the tuple. Raise. This processing result is recorded in a byte-aligned area in units of threads. An example of the reprocessing result recorded in the predetermined storage area is shown in FIG. This indicates whether or not a search target byte string exists in each tuple.

  An outline of the operation of the database system described above is illustrated in FIG. In the example of FIG. 6, tuple data such as “HELLO!”, “Parallel”, “GPU”, and “GPGPU” is stored in each fragment in the database. The parallel processing unit 24 secures an area for storing the result of the search processing for searching for the byte string “GPU”, and assigns a fragment to be assigned to each thread executed by the parallel processing unit to the metadata or the parallel processing unit. It is determined based on the data processing unit. A fragment is assigned to each thread based on this determination. Each thread performs arithmetic processing for searching for a byte string “GPU” for the allocated fragment, and records the processing result. In FIG. 6, the bit at the head position of the area corresponding to the byte string in which “GPU” is detected is inverted in the calculation result recording area. Next, the data processing result / storage unit 25 secures an area for storing a processing result obtained by recalculating the calculation result, and determines a tuple to be assigned to each thread. At this time, the number of tuples assigned to each thread is set to a multiple of 8. Each thread reads an operation result corresponding to the assigned tuple, and when a flag is set in the read operation result, sets a flag as a processing result of the tuple. In FIG. 6, the flag “1” is set as the processing result of “100” and “00100”, which are the calculation results for which the flag is set.

  Next, the details of the process of determining the fragment to be assigned to each thread by the parallel processing unit 24 (step S2 above) will be described with reference to FIG. The parallel processing unit 24 identifies the allocation target fragment from the processing target data, and acquires the fragment length (step S11). The parallel processing unit 24 determines whether the fragment length of the fragment to be allocated is a predetermined number that is a multiple of 8 (e.g., the least common multiple of 8 and the fragment) (step S12). If the fragment length is not a predetermined number (step S12: NO), the parallel processing unit 24 adds another fragment in the processing target data to the allocation target fragment, and calculates the fragment length of the allocation target fragment again. (Step S13), the process returns to Step S12. When the fragment length is a predetermined number (step S12: YES), the parallel processing unit 24 assigns the fragment to be assigned to one of the threads (step S14). The parallel processing unit 24 determines whether the assignment has been completed for all the fragments in the processing target data (step S15), and if completed (step S15: YES), the process ends. If the assignment has not been completed (step S15: NO), the process returns to step S11, and the processing for the remaining fragments is continued. This process is an example, and other assignment processes may be used.

  Next, processing in which the variable length data storage / processing unit 23 stores data in the database 10 will be described with reference to FIG. The variable length data storage / processing unit 23 reads data to be stored (step S21). The data to be read is variable-length tuple data including fixed-length data in column units. The variable length data storage / processing unit 23 stores the read tuple data in fragments in the database 10 (step S22). The fragment has a fixed length, and its length is determined by the variable length data storage length determination unit 22 based on the data processing unit of the parallel computing unit used in this system. The variable length data storage / processing unit 23 stores the metadata corresponding to the tuple data stored in the fragment in the fragment header in the database 10 (step S23). The metadata includes an ID for identifying the tuple data and an offset from the tuple head position at the end of the fragment. The variable length data storage / processing unit 23 determines whether or not all data to be stored has been stored in the database 10 (step S24), and if completed (step S24: YES), the process ends. If the storage has not been completed (step S24: NO), the process returns to step S21, and the process for the remaining data is continued. Note that this processing is an example, and other storage processing may be used. As the fragment length of a fragment, a preset value (for example, 4 bytes, 8 bytes, 16 bytes, or the like) based on a data processing unit of a general parallel computing unit may be used.

  As described above, according to the present embodiment, efficient processing is realized by balancing space efficiency and processing efficiency in order to perform efficient processing on the GPU of variable-length data.

  Parallel computing unit environment detection unit 21, variable length data storage length determination unit 22, variable length data storage / processing unit 23, parallel processing unit 24, data processing result / storage / reprocessing unit according to the embodiment of the present invention described above 25 may be realized by the CPU or coprocessor of the database processing apparatus 20 reading out and executing an operation program or the like stored in the storage unit, or may be configured by hardware. Only some functions of the above-described embodiments can be realized by a computer program.

  Although the present invention has been described with reference to the preferred embodiments, the present invention is not necessarily limited to the above-described embodiments, and various modifications can be made within the scope of the technical idea. This application claims the priority on the basis of Japanese application Japanese Patent Application No. 2011-065171 for which it applied on March 24, 2011, and takes in those the indications of all here.

DESCRIPTION OF SYMBOLS 10 Database 20 Database processing apparatus 21 Parallel computing unit environment detection part 22 Variable length data storage length determination part 23 Variable length data storage / processing part 24 Parallel arithmetic processing part 25 Data processing result / storage / reprocessing part

Claims (3)

A database processing apparatus having a parallel computing unit,
Data storage means for determining a fragment length according to a data processing unit of the parallel computing unit, storing tuple data including variable length data in the fragment in the column store database, and storing metadata of the fragment as a fragment header When,
Parallel processing means for determining a fragment to be assigned to each thread with reference to the metadata when processing the data stored in the column store database, and assigning the fragment to each thread based on the determined content and executing a parallel operation; ,
Equipped with a,
The parallel operation means searches the character string for the allocated fragment in each thread, records the result obtained by bit-inversion of the byte position of the fragment as a search result, and according to the data processing unit of the parallel operation unit Means for assigning a number of search results to each thread, detecting bit inversion for each assigned search result in each thread, and recording a detection result flag as a tuple level search result. A database processing apparatus characterized by that. A data processing method in a database processing apparatus having a parallel computing unit,
A data storage step of determining a fragment length according to a data processing unit of the parallel computing unit, storing tuple data including variable length data in the fragment in the column store database, and storing metadata of the fragment as a fragment header When,
A parallel operation step of determining a fragment to be assigned to each thread with reference to the metadata when processing the data stored in the column store database, and assigning the fragment to each thread based on the determined content and executing a parallel operation; ,
Equipped with a,
In the parallel operation step, in each thread, a character string is searched for the allocated fragment, and a result obtained by bit-inversion of the byte position of the fragment is recorded as a search result, and according to a data processing unit of the parallel operation unit Assigning a number of search results to each thread, detecting bit inversion for the assigned search results in each thread, and recording a detection result flag as a tuple level search result. A database processing method characterized by the above. For computers with parallel computing units,
A data storage step of determining a fragment length according to a data processing unit of the parallel computing unit, storing tuple data including variable length data in the fragment in the column store database, and storing metadata of the fragment as a fragment header ,
A parallel operation step of determining a fragment to be assigned to each thread with reference to the metadata when processing the data stored in the column store database, and assigning a fragment to each thread based on the determined content to execute a parallel operation;
Was executed,
In the parallel operation step, in each thread, a character string is searched for the allocated fragment, and a result obtained by bit-inversion of the byte position of the fragment is recorded as a search result, and according to a data processing unit of the parallel operation unit Assigning a number of search results to each thread, detecting bit inversion for the assigned search results in each thread, and recording a detection result flag as a tuple level search result. A program characterized by that.

Images