Using in-storage computation to improve the performance of hash join for database and data analytics

A method according to embodiments includes: storing an entire hash table of a table R in memory of a computational storage device; storing a second table S in storage media of the computational storage device, the table R being smaller than the table S, wherein the hash JOIN operation is directed to combining a cs-th column in the table S and a cr-th column in the table R; wherein, for each row of the table S, the computational storage device configured to perform a method, including: applying a hash function to a value of the cs-th column to provide a hash result; looking up the hash result in the hash table stored in the memory of the computational storage device; and if the hash result is found, sending the row of the table S and a corresponding row index of the table R to the host computing system.

TECHNICAL FIELD

The present invention relates to database and data analytics, and particularly to utilizing computational storage devices to accelerate database and data analytics.

BACKGROUND

Used to combine columns from multiple tables, JOIN is one of the most important and heavy-duty operations in almost all database and data analytics systems. Hence, it is highly desirable to improve the implementation efficiency of JOIN. Hash JOIN is one of the most widely used JOIN algorithms that implement the JOIN operation. The basics of the hash JOIN algorithm is described as follows. Suppose one wants to join two tables S and R, where the size of table S is larger than the size of table R. Using the hash JOIN algorithm, one first builds a hash table of the smaller table R. Each hash table entry contains one value of the column based upon which the JOIN is performed and its corresponding row index. Once the hash table is built, one scans the larger table S and finds the relevant rows from the smaller table R by looking up the hash table. In current practice, the entire table S must be first loaded from the underlying storage devices into host memory, and a CPU of the host must scan each row of the table S. As a result, storage I/O traffic and CPU usage are linearly proportional to the size of the table S.

SUMMARY

Accordingly, embodiments of the present disclosure are directed to the utilization of computational storage devices to reduce the I/O traffic and CPU usage for implementing hash JOIN.

A first aspect of the disclosure is directed to a method for enhancing a hash JOIN operation, including: storing an entire hash table of a table R in a memory of a computational storage device; storing a second table S in storage media of the computational storage device, wherein the table R is smaller than the table S, and wherein the hash JOIN operation is directed to combining a cs-th column in the table S and a cr-th column in the table R; wherein, for each row of the table S, the computational storage device is configured to perform a method, including: applying a hash function to a value of the cs-th column to provide a hash result; looking up the hash result in the hash table stored in the memory of the computational storage device; and if the hash result is found in the hash table, sending the row of the table S and a corresponding row index of the table R to the host computing system.

A second aspect of the disclosure is directed to a method for enhancing a hash JOIN operation, including: storing a Bloom filter of a table R in a memory of a computational storage device; storing a second table S in storage media of the computational storage device, wherein the table R is smaller than the table S, and wherein the hash JOIN operation is directed to combining a cs-th column in the table S and a cr-th column in the table R; wherein, for each row of the table S, the computational storage device is configured to perform a method, including: applying a hash function to a value of the cs-th column to provide a hash result; looking up the hash result in the Bloom filter stored in the memory of the computational storage device; and if the hash result is found in the Bloom filter, sending the row of the table S and a corresponding row index of the table R to the host computing system.

A third aspect of the disclosure is directed to a computational storage device, including: a memory for storing an entire hash table of a table R; storage media for storing a second table S, wherein the table R is smaller than the table S, and wherein the hash JOIN operation is directed to combining a cs-th column in the table S and a cr-th column in the table R; a computation module, including: a hash engine for applying, for each row in the table S, a hash function to a value of the cs-th column to provide a hash result; and a hash table look-up engine for looking up the hash result in the hash table stored in the memory of the computational storage device; and a communication module for sending the row of the table S and a corresponding row index of the table R to the host computing system if the hash result is found in the hash table, wherein the host computing system is configured to perform a hash JOIN based on the rows of the table S and the row indices of the table R received from the computational storage device.

A fourth aspect of the disclosure is directed to computing system for performing a hash JOIN operation, including: a host computing device; a computational storage device coupled to the host computing device, the computational storage device including: a memory for storing a Bloom filter of a table R in a memory of a computational storage device; storage media for storing a second table S, wherein the table R is smaller than the table S, and wherein the hash JOIN operation is directed to combining a cs-th column in the table S and a cr-th column in the table R; a computation module, including: a hash engine for applying, for each row in the table S, a hash function to a value of the cs-th column to provide a hash result; and a Bloom filter look-up engine for looking up the hash result in the Bloom filter stored in the memory of the computational storage device; and a communication module for sending the row of the table S and a corresponding row index of the table R to the host computing system if the hash result is found in the Bloom filter.

DETAILED DESCRIPTION

Reference will now be made in detail to embodiments of the disclosure, examples of which are illustrated in the accompanying drawings.

According to embodiments, computational storage devices are used to reduce the I/O traffic and CPU usage for the implementation of hash JOIN. An example of the architecture of a computational storage device10is depicted inFIG. 1. As shown, the computational storage device10includes storage media12(e.g., flash memory, non-volatile memory, hard disk, etc.) and a device controller14. The device controller14includes a media access module16that carries out all the necessary operations to ensure high-performance and reliable data read/write from/to the storage media12, and an I/O (e.g., communication) module18that handles the interfacing with a host20(e.g., a host computing system). The device controller12of the computational storage device10also includes a computation module22, which can carry out certain fixed or programmable computational tasks.

In the computational storage device10, after the media access module16reads data from the storage media12, the data may be directly sent back to the host20without further processing, or the data may be further processed by the computation module22, with the results of the computation sent back to the host20. To facilitate the in-storage computation, the computational storage device10includes a certain amount of memory24(e.g., SRAM or DRAM) that may be used by the computation module22and media access module16.

FIG. 2illustrates an operational flow diagram of a process for using the computational storage device10to facilitate hash JOIN when an entire hash table can be stored in the memory24of the computational storage device10.FIG. 3shows the corresponding configuration of the computation module22of the computational storage device10.FIGS. 1-3will be referred to simultaneously. In the following discussion, it is assumed that a hash JOIN is to be applied on two tables S and R, that the size of table R is less than the size of table S, and that the host20has downloaded the table S to the storage media12. It is further assumed that the JOIN aims to combine columns based on the cs-th column in table S and cr-th column in table R.

According to the hash JOIN algorithm, at process A1, a hash table HRis first built using a hash function fh, based upon the smaller table R. At process A2, the entire hash table HRis loaded into the memory24of the computational storage device10. The hash table HRmay be built by the host20, the computational storage device10, or may be provided in any other suitable manner.

At process A3, the media access module16of the device controller14fetches the data of table S from the storage media12, and feeds the data to the computation module22of the device controller14. While receiving data from the media access module16, at process A4, a table parser26of the computation module22parses the data to extract each row in the table S. For each row in the table S (Y at process A5), at process A6, a row parser28of the computation module22extracts the value of the cs-th column from the row, and a hash engine30of the computation module22applies the hash function fhto the extracted value. At process A7, for the i-th row in the table S, a hash table look-up engine32of the computation module22looks up the hash result obtained at process A6against the hash table HRstored in the memory24. If the hash result for the i-th row in the table S matches the j-th row in the table R (Y at process A8), the device controller14sends the i-th row in the table S plus the row index j in the table R to the host20at process A9. If the i-th row in the table S does not match any row in the table R (N at process A8) (i.e., the i-th row in table S will not participate in the JOIN operation), the device controller14simply discards the i-th row of the table S. If there are no more rows in the table S (N at process A5), at process A10, the host20combines the columns to finish the JOIN operation.

By discarding the i-th row of the table S if the i-th row in the table S does not match any row in the table R, the device controller14of the computational storage device10internally filters out all the rows in the table S that will not participate the JOIN. This can significantly reduce I/O data traffic. Further, since all of the hashing and hash table look-up operations are completely handled by the computation module22of the computational storage device10, CPU usage of the host20for implementing hash JOIN is greatly reduced.

FIG. 4illustrates an operational flow diagram of a process for using the computational storage device10to facilitate hash JOIN when a hash table cannot entirely fit into the memory24of the computational storage device10.FIG. 5shows the corresponding configuration of the computation module22.FIGS. 1, 4, and 5will be referred to simultaneously. In the following discussion, it is again assumed that a hash JOIN is to be applied on two tables S and R, that the size of table R is less than the size of table S, and that the host20has downloaded the table S to the storage media12. Further, it is again assumed that the JOIN aims to combine columns based on the cs-th column in table S and cr-th column in table R.

In some cases, due to its limited capacity, the memory24of a computational storage device10may not be able to hold the entire hash table HR. If the memory24is not able to hold the entire hash table HR, it may not be possible to use above presented design solution. To address this issue, the present disclosure presents a two-stage hybrid hash JOIN implementation.

FIG. 4shows the operational flow diagram. At process B1, a hash table HRand a Bloom filter BRof the smaller table R are built using a set of hash functions Fh. At process B2, the entire Bloom filter BRis loaded into the memory24of the computational storage device10. The hash table HRand the Bloom filter BRmay be built by the host20, the computational storage device10, or may be provided in any other suitable manner.

At process B3, the media access module16of the device controller14fetches the data of table S from the storage media12, and feeds the data to the computation module22of the device controller14. While receiving data from the media access module16, at process B4, a table parser26of the computation module22parses the data to extract each row in the table S. For each row in the table S (Y at process B5), at process B6, a row parser28of the computation module22extracts the value of the cs-th column from the row, and a hash engine30of the computation module22applies the set of hash function Fhto the extracted value.

At process B7, a Bloom table look-up engine34of the computation module22looks up the hash result obtained at process B6against the Bloom filter BRstored in the memory24. In the case of a hit to the Bloom filter BR(Y at process B8) then the value may likely (but not guaranteed) exist in the smaller table R. In case of a miss to the Bloom filter BR(N at process B8) then the value does not exist in the smaller table R and can be ignored/discarded. Therefore, using a Bloom filter BRthat can be much smaller than the complete hash table HR, many (but not all) of the entries that will not participate the JOIN operation can be filtered out. To this extent, the computational storage device10performs approximate data filtering (e.g., performs a pre-filtering operation).

At process B9, in the case of a hit to the Bloom filter BR(Y at process B8), the device controller14sends the i-th row in the table S plus the row index j in the table R to the host20. If there are no more rows in the table S (N at process B5), flow passes to process B10. At process B10, upon receiving the table-S rows from the computational storage device10, the host20scans the rows (based upon the hash table HR) to identify all the rows that should participate the JOIN. At process B11, the host20combines the columns to finish the JOIN operation.

It is understood that aspects of the present disclosure may be implemented in any manner, e.g., as a software program, or an integrated circuit board or a controller card that includes a processing core, I/O and processing logic. Aspects may be implemented in hardware or software, or a combination thereof. For example, aspects of the processing logic may be implemented using field programmable gate arrays (FPGAs), ASIC devices, or other hardware-oriented system.

The foregoing description of various aspects of the present disclosure has been presented for purposes of illustration and description. It is not intended to be exhaustive or to limit the concepts disclosed herein to the precise form disclosed, and obviously, many modifications and variations are possible. Such modifications and variations that may be apparent to an individual in the art are included within the scope of the present disclosure as defined by the accompanying claims.