CN116028506A - Hash connection method, device, equipment and medium - Google Patents

Abstract

The application discloses a hash connection method, a hash connection device, hash connection equipment and a hash connection medium, which relate to the field of hardware acceleration of database query operation and comprise the following steps: acquiring first data of a first data tuple to be connected and second data of a second data tuple to be connected, and respectively calculating the first data and the second data by using a cuckoo algorithm to obtain a hash result of the first data and a hash result of the second data; determining a first target hash table corresponding to the hash result of the first data and a second target hash table corresponding to the hash result of the second data; dividing the first data and the second data into a plurality of groups of first sub data and second sub data, and respectively storing the first sub data and the second sub data into a first target hash table and a second target hash table; reading the first sub data and the second sub data from the first hash target table and the second hash target table, and merging and connecting the first sub data and the second sub data meeting the equivalent condition to obtain connected data. And the hash connection speed is improved.

Description

Hash connection method, device, equipment and medium

technical field

The invention relates to the field of hardware acceleration of database query operations, in particular to a hash connection method, device, equipment and media.

Background technique

In database query operations, the hash join algorithm is one of the most widely used join algorithms in databases, which can realize join calculations with low time complexity and low power consumption. The hash join algorithm is divided into two phases: construction and detection. After all data calculations in the construction phase are completed, the data calculation in the detection phase is performed.

The commonly used hash connection acceleration method based on FPGA (Field Programmable Gate Array, that is, Field Programmable Logic Gate Array) mainly achieves a better acceleration method by resolving hash conflicts, but these methods cannot achieve the detection stage. Parallel processing of large amounts of data. The parallel data processing in the existing detection stage can only be realized by dividing the hash join, which is complex in calculation, and has poor parallelism and scalability, so the speed of the hash join is low.

To sum up, how to increase the speed of the hash join is a problem to be solved in this field.

Contents of the invention

In view of this, the object of the present invention is to provide a hash join method, device, equipment and medium, which can increase the speed of hash join. The specific plan is as follows:

In the first aspect, the application discloses a hash connection method, including:

Obtain the first data of the first data tuple to be connected and the second data of the second data tuple to be connected, and use the first hash function and the second hash function in the cuckoo algorithm to respectively process the first data and the second data performing calculations on the second data to obtain a hash result of the first data and a hash result of the second data;

determining a first target hash table corresponding to the hash result of the first data and a second target hash table corresponding to the hash result of the second data;

respectively dividing the first data and the second data into several groups of first sub-data and second sub-data, and respectively storing the first sub-data and the second sub-data in the first target hash table and said second target hash table;

Read the first sub-data and the second sub-data from the first hash table and the second target hash table, and store the first sub-data and the second sub-data that satisfy the equivalence condition Merge and join the second sub-data to obtain the joined data.

Optionally, the acquiring the first data of the first data tuple to be connected and the second data of the second data tuple to be connected includes:

Reading the first data tuple to be connected and the second data tuple to be connected in the external memory to obtain the first data of the first data tuple to be connected and the second data of the second data tuple to be connected ; Wherein, the external memory is any one of double-rate synchronous dynamic random access memory and synchronous dynamic random access memory.

Optionally, using the first hash function and the second hash function in the cuckoo algorithm to calculate the first data and the second data respectively, so as to obtain a hash result of the first data and The hash result of the second data includes:

Using the first hash function and the second hash function in the cuckoo algorithm to calculate the first data and the second data respectively, so as to obtain the first hash result and the second hash of the first data a result and a first hash result and a second hash result of said second data;

Correspondingly, the determining the first target hash table corresponding to the hash result of the first data and the second target hash table corresponding to the hash result of the second data includes:

determining a first hash table address and a second hash table address corresponding to the first hash result and the second hash result of the first data, and the first hash result and The third hash table address and the fourth hash table address respectively corresponding to the second hash result;

Determine the first target hash table address from the first hash table address and the second hash table address, and determine from the third hash table address and the fourth hash table address Output the address of the second target hash table;

Optionally, storing the first sub-data and the second sub-data in the first target hash table and the second target hash table respectively includes:

storing the first sub-data in a hash table corresponding to the first target hash table address, and storing the second sub-data in a hash table corresponding to the second target hash table address .

Optionally, determining the first target hash table address from the first hash table address and the second hash table address, and determining the first target hash table address from the third hash table address, the fourth hash table address The second target hash table address is determined in the hash table address, including:

Judging whether there is an idle hash bucket in the hash table corresponding to the first hash table address and the second hash table address respectively, if there is, it will be combined with the first hash table address, the second hash table address The address of the hash table with the largest number of free hash buckets in the hash tables corresponding to the two hash table addresses is determined as the first target hash table address, and the address of the other hash table is determined as the first target hash table table alternate address;

Judging whether there is a free hash bucket in the hash table corresponding to the third hash table address and the fourth hash table address respectively, if there is, it will be combined with the third hash table address and the fourth hash table address The hash table with the largest number of free hash buckets in the hash tables corresponding to the addresses of the four hash tables is determined as the second target hash table address, and the address of the other hash table is determined as the second target hash table for backup address;

Correspondingly, storing the first sub-data and the second sub-data in the first target hash table and the second target hash table respectively includes:

storing the first sub-data and the standby address of the first target hash table into an idle hash bucket of the first target hash table, and storing the second sub-data and the standby address of the second target hash table stored in an idle hash bucket of the second target hash table.

Optionally, after the judging whether there is an idle hash bucket in the hash table respectively corresponding to the first hash table address and the second hash table address, the method further includes:

If it does not exist, then look up the backup address of the data stored in the hash bucket in the hash table corresponding to the first hash table address and the second hash table address respectively, and judge whether there is a satisfying condition based on the backup address. Hash buckets with preset conditions;

If it exists, transfer the data stored in the hash bucket that meets the preset condition to the hash bucket in the hash table corresponding to the standby address, so that the first sub-data is stored until the preset condition is met hash bucket; if it does not exist, store the first sub-data in the linked list corresponding to the first target hash table.

Optionally, after storing the first sub-data and the second sub-data respectively in the first target hash table and the second target hash table, further comprising:

Record the total amount of data stored in the first target hash table and the second target hash table.

In a second aspect, the present application discloses a hash connection device, including:

The hash result acquisition module is used to acquire the first data of the first data tuple to be connected and the second data of the second data tuple to be connected, and utilize the first hash function and the second hash function in the cuckoo algorithm performing calculations on the first data and the second data respectively to obtain a hash result of the first data and a hash result of the second data;

a hash table determining module, configured to determine a first target hash table corresponding to the hash result of the first data and a second target hash table corresponding to the hash result of the second data;

a storage module, configured to divide the first data and the second data into several groups of first sub-data and second sub-data, and respectively store the first sub-data and the second sub-data in the a first target hash table and said second target hash table;

a merge connection module, configured to read the first sub-data and the second sub-data from the first hash table and the second target hash table, and combine the The first sub-data and the second sub-data are merged and joined to obtain the joined data.

In a third aspect, the present application discloses an electronic device, comprising:

memory for storing computer programs;

A processor, configured to execute the computer program, so as to realize the steps of the hash connection method disclosed above.

In a fourth aspect, the present application discloses a computer-readable storage medium for storing a computer program; wherein, when the computer program is executed by a processor, the steps of the hash connection method disclosed above are implemented.

It can be seen that the present application obtains the first data of the first data tuple to be connected and the second data of the second data tuple to be connected, and utilizes the first hash function and the second hash function in the cuckoo algorithm to respectively Perform calculations on the first data and the second data to obtain a hash result of the first data and a hash result of the second data; determine the first data corresponding to the hash result of the first data a target hash table and a second target hash table corresponding to the hash result of the second data; respectively dividing the first data and the second data into several groups of first sub-data and second sub-data, And storing the first sub-data and the second sub-data to the first target hash table and the second target hash table respectively; from the first hash target hash table and the second target The first sub-data and the second sub-data are read from the hash table, and the first sub-data and the second sub-data satisfying the equivalence condition are merged and connected to obtain the connected data. It can be seen that, in the construction stage, the present application implements hash calculation and storage of the first data of the first data tuple to be connected and the second data of the second data tuple to be connected, so that the subsequent The first sub-data and the second sub-data are merged and connected to obtain the connected data, which eliminates the limitation that only one data tuple connection can be processed at a time in the detection stage, that is, parallel hash calculation, storage and merge connection can be realized, so Increased the speed of hash joins.

Description of drawings

In order to more clearly illustrate the technical solutions in the embodiments of the present application or the prior art, the following will briefly introduce the drawings that need to be used in the description of the embodiments or the prior art. Obviously, the accompanying drawings in the following description are only It is an embodiment of the present invention, and those skilled in the art can also obtain other drawings according to the provided drawings without creative work.

Fig. 1 is a flow chart of a hash connection method disclosed in the present application;

Fig. 2 is a kind of specific hash connection method flowchart disclosed in the present application;

FIG. 3 is a specific schematic diagram of data storage disclosed in the present application;

FIG. 4 is a schematic diagram of a specific data merge connection disclosed in the present application;

FIG. 5 is a schematic structural diagram of a hash connection device disclosed in the present application;

FIG. 6 is a structural diagram of an electronic device disclosed in the present application.

Detailed ways

The following will clearly and completely describe the technical solutions in the embodiments of the present application with reference to the accompanying drawings in the embodiments of the present application. Obviously, the described embodiments are only some of the embodiments of the present invention, not all of them. Based on the embodiments of the present invention, all other embodiments obtained by persons of ordinary skill in the art without making creative efforts belong to the protection scope of the present invention.

In database query operations, the hash join algorithm is one of the most widely used join algorithms in databases, which can realize join calculations with low time complexity and low power consumption. The hash join algorithm is divided into two phases: construction and detection. After all data calculations in the construction phase are completed, the data calculation in the detection phase is performed.

Commonly used FPGA-based hash join acceleration methods mainly achieve better acceleration methods by solving hash conflicts, but none of these methods can achieve parallel processing of a large amount of data in the detection phase. The parallel data processing in the existing detection stage can only be realized by dividing the hash join, which is complex in calculation, and has poor parallelism and scalability, so the speed of the hash join is low.

For this reason, the present application correspondingly provides a hash join solution, which can increase the speed of hash join.

Referring to Fig. 1, the embodiment of the present application discloses a hash connection method, including:

Step S11: Obtain the first data of the first data tuple to be connected and the second data of the second data tuple to be connected, and use the first hash function and the second hash function in the cuckoo algorithm to respectively A calculation is performed on the first data and the second data to obtain a hash result of the first data and a hash result of the second data.

In this embodiment, the acquisition of the first data of the first data tuple to be connected and the second data of the second data tuple to be connected includes: reading the first data tuple to be connected and the second data tuple to be connected in the external memory Connecting the data tuples to obtain the first data of the first data tuple to be connected and the second data of the second data tuple to be connected; wherein, the external memory is a double-rate synchronous dynamic random access memory, Any type of synchronous dynamic random access memory. It can be understood that, when the external memory is DDR (Double Data Rate, double-rate synchronous dynamic random access memory), then read the first data tuple to be connected and the second data tuple to be connected from the DDR to obtain The first data of the first data tuple to be connected and the second data of the second data tuple to be connected, when the external memory is SDRAM (Synchronous Dynamic Random Access Memory, i.e. synchronous dynamic random access memory), then from the SDRAM The first data tuple to be connected and the second data tuple to be connected are read to obtain the first data of the first data tuple to be connected and the second data of the second data tuple to be connected.

It should be noted that because the data volume of the first data tuple to be connected and the second data tuple to be connected is relatively large, the first data tuple to be connected and the second data tuple to be connected are generally divided into several data units , the first data and the second data are one of the data units, for example, the first to-be-connected data tuple and the second to-be-connected data tuple can be divided into 10 data units, and hash calculation, storage and The respective data units of the first data tuple to be connected and the second data tuple to be connected are merged and connected.

Step S12: Determine a first target hash table corresponding to the hash result of the first data and a second target hash table corresponding to the hash result of the second data.

In this embodiment, the address of the first target hash table corresponding to the hash result of the first data is determined, that is, the corresponding first target hash table can be determined based on the address. Similarly, the address of the second data can be determined. The address of the second target hash table corresponding to the hash result can be used to determine the corresponding second target hash table.

Step S13: Separate the first data and the second data into several groups of first sub-data and second sub-data, and respectively store the first sub-data and the second sub-data in the first a target hash table and the second target hash table.

It should be noted that the first data and the second data may respectively contain several sets of sub-data, for example, the first data contains 1000 sub-data, then these 1000 sub-data are stored in the first target hash table in turn.

It can be understood that after storing the first sub-data and the second sub-data in the first target hash table and the second target hash table respectively, it also includes: recording the first The total amount of data stored in the target hash table and the second target hash table.

Step S14: Read the first sub-data and the second sub-data from the first hash table and the second target hash table, and store the first sub-data satisfying the equivalence condition The data and the second sub-data are merged and joined to obtain the joined data.

In this embodiment, the merge join is the detection stage of the hash join. Since the first data and the second data are divided into several groups of sub-data in advance, it is necessary to divide the first sub-data of the first data and the sub-data of the second data The second sub-data is sequentially merged and connected until all the sub-data are connected. Among them, it should be noted that before performing the merge connection, it is necessary to judge whether the current first sub-data and the current second sub-data meet the equivalence condition. If it is satisfied, the merge connection can be performed. If not, then Skip the current first sub-data and the current second sub-data, and judge whether the next first sub-data and the next second sub-data satisfy the equivalence condition. Among them, the merge calculation of single-line hash table data elements is used for illustration:

1) Detect the number of data elements in the same hash table row corresponding to the first sub-data and the second sub-data respectively. When the total amount of data in the hash table row corresponding to a sub-data is 0, directly skip the The data is merged and calculated, and the next hash row data is detected;

2) When both hash rows have sub-data, read the data in the single-row hash bucket from the corresponding hash table; when there is a linked list, read all the data in the corresponding linked list; read all the data and Cache; each hash bucket corresponds to a linked list storage module, which is used to improve the reading speed of the linked list;

3) When the first sub-data cache data is greater than or equal to the second sub-data, the data is sequentially written into M merge connection units based on the first sub-data cache; the data in the second sub-data cache is written in pipeline form The merge connection unit is sequentially passed to the merge connection unit M to complete the merge connection calculation;

4) In the merge connection unit, when there are two data elements at the same time, compare the two data elements to see if the connection condition is satisfied, and if the connection condition is met, the connection result is output; otherwise, skip; repeat the above operation, and complete all hash tables Merge join of data in rows.

It is understandable that after obtaining the connected data, the connected data needs to be transferred to the CPU (central processing unit, central processing unit) processing module outside the acceleration structure through DMA (direct memory access, namely DirectMemory Access).

It can be seen that the present application obtains the first data of the first data tuple to be connected and the second data of the second data tuple to be connected, and utilizes the first hash function and the second hash function in the cuckoo algorithm to respectively Perform calculations on the first data and the second data to obtain a hash result of the first data and a hash result of the second data; determine the first data corresponding to the hash result of the first data a target hash table and a second target hash table corresponding to the hash result of the second data; respectively dividing the first data and the second data into several groups of first sub-data and second sub-data, And storing the first sub-data and the second sub-data to the first target hash table and the second target hash table respectively; from the first hash target hash table and the second target The first sub-data and the second sub-data are read from the hash table, and the first sub-data and the second sub-data satisfying the equivalence condition are merged and connected to obtain the connected data. It can be seen that, in the construction stage, the present application implements hash calculation and storage of the first data of the first data tuple to be connected and the second data of the second data tuple to be connected, so that the subsequent The first sub-data and the second sub-data are merged and connected to obtain the connected data, which eliminates the limitation that only one data tuple connection can be processed at a time in the detection stage, that is, parallel hash calculation, storage and merge connection can be realized, so Increased the speed of hash joins.

Referring to Figure 2, the embodiment of the present application discloses a specific hash connection method, including:

Step S21: Obtain the first data of the first data tuple to be connected and the second data of the second data tuple to be connected.

Step S22: Using the first hash function and the second hash function in the cuckoo algorithm to calculate the first data and the second data respectively, so as to obtain the first hash result and the second hash result of the first data Two hash results and a first hash result and a second hash result of the second data.

Step S23: Determine the address of the first hash table, the address of the second hash table and the first hash of the second data respectively corresponding to the first hash result and the second hash result of the first data. The third hash table address and the fourth hash table address corresponding to the hash result and the second hash result respectively.

Step S24: Determine the first target hash table address from the first hash table address and the second hash table address, and determine the first target hash table address from the third hash table address, the fourth hash table address The second target hash table address is determined from the address.

In this embodiment, the first target hash table address is determined from the first hash table address and the second hash table address, and the first target hash table address is determined from the third hash table address, the second hash table address Determining the second target hash table address from the four hash table addresses includes: judging whether there is an idle hash bucket in the hash table respectively corresponding to the first hash table address and the second hash table address , if it exists, the address of the hash table with the largest number of free hash buckets in the hash tables corresponding to the first hash table address and the second hash table address respectively is determined as the first target hash Table address, the address of another hash table is determined as the standby address of the first target hash table; judge whether there is in the hash table respectively corresponding to the third hash table address and the fourth hash table address Free hash buckets, if they exist, determine the hash table with the largest number of free hash buckets in the hash tables corresponding to the third hash table address and the fourth hash table address as the second target The address of the hash table is used to determine the address of another hash table as the standby address of the second target hash table. Wherein, the empty and full status item of the hash bucket is empty, that is, it is determined that the hash bucket is an idle hash bucket. It can be understood that the hash table contains N (N ≥ 2) hash bucket slots, and the hash bucket contains flag signals such as data elements, linked list addresses, empty and full states, and backup hash bucket addresses. Store data in the format of {data element; empty and full flag; linked list address; backup hash bucket address}.

In this embodiment, after the judging whether there is a free hash bucket in the hash table respectively corresponding to the first hash table address and the second hash table address, it also includes: if not, searching A standby address for storing data in the hash bucket in the hash table corresponding to the first hash table address and the second hash table address respectively, and judging whether there is a hash that satisfies the preset condition based on the standby address Bucket; if it exists, transfer the data stored in the hash bucket that meets the preset condition to the hash bucket in the hash table corresponding to the standby address, so that the first sub-data is stored in the hash bucket that meets the preset condition A conditional hash bucket is set; if it does not exist, the first sub-data is stored in a linked list corresponding to the first target hash table.

It can be understood that, if there is no idle hash bucket, it is detected whether the standby hash bucket is idle, and if there is an idle standby hash bucket, then in the addresses corresponding to the first hash table address and the second hash table address respectively Filter out the hash table with the most free spare hash buckets from the hash table, and determine it as the first target hash table, and then transfer the data in hash bucket 1 to spare hash bucket 1 for subsequent storage When sub-data of the first data is stored, the sub-data is stored in the hash bucket 1 .

Step S25: Separate the first data and the second data into several groups of first sub-data and second sub-data, and store the first sub-data in the hash corresponding to the address of the first target hash table and store the second sub-data in the hash table corresponding to the address of the second target hash table.

In this embodiment, the first subdata and the standby address of the first target hash table are stored in an idle hash bucket of the first target hash table, and the second subdata and the second target The standby address of the hash table is stored in an idle hash bucket of the second target hash table.

Step S26: Read the first sub-data and the second sub-data from the first hash table and the second target hash table, and store the first sub-data satisfying the equivalence condition The data and the second sub-data are merged and joined to obtain the joined data.

It can be seen that the application calculates and stores two data tuples to be connected in parallel in the construction phase, so that the two sub-data can also be connected in parallel in the subsequent detection phase, which improves the speed of the hash connection; A hash function is calculated, the calculation results of the first data and the second data increase, and the hash tables that can be stored also increase accordingly, thus increasing the probability of storing the first data and the second data.

The technical scheme of the present application is further described below:

1) Reading the first data tuple to be connected and the second data tuple to be connected in the external memory to obtain the first data of the first data tuple to be connected and the second data of the second data tuple to be connected.

2) Using the first hash function and the second hash function in the cuckoo algorithm to calculate the first data and the second data respectively, to obtain the hash result 11 and the hash result 12 of the first data and the hash result 12 of the second data Hash result 21 and hash result 22.

3) Determine the first hash table address 11 corresponding to the hash result 11 and the second hash table address 12 corresponding to the hash result 12, from the first hash table address 11 and the second hash table address 12 The address of the first target hash table is determined in ; the determination process is specifically as follows:

Determine the number of free hash buckets in the hash table 11 and the hash table 12 respectively corresponding to the first hash table address 11 and the second hash table address 12, and determine whether there is a hash bucket in the hash table 11 and the hash table 12 free hash bucket;

If it exists, the hash table with the largest number of free hash buckets is used as the first target hash table, and the address of another hash table is the standby address of the first target hash table;

If it does not exist, then determine the number of idle standby hash buckets in the hash table 11 and the hash table 12, first judge whether there is an idle standby hash bucket in the hash table 11 and the hash table 12, if there is, then use idle The hash table with the largest number of spare hash buckets is the first target hash table. If it does not exist, the linked list address slot of the hash bucket is determined, and the hash table with the largest number of empty linked list address slots is determined as the first target hash table. a target hash table;

It can be understood that the process of the second target hash table is the same as the process of determining the first target hash table. It should be noted that if one of the hash tables is determined as the target hash table, the other hash table The table is identified as an alternate hash table.

4) Dividing the first data and the second data into several groups of first sub-data and second sub-data respectively, and storing the first sub-data and the second sub-data to the first target hash table and the second target hash table respectively ; Among them, because the process of determining the target hash table is different, the storage process is also different, such as storing the first sub-data as an example:

If there is an idle hash bucket in the determined first target hash table, store the first sub-data of the first data in the data element item of the free hash bucket 1, and reserve the first target hash table The address is stored in the standby hash bucket address item of hash bucket 1;

If there is no idle hash bucket in the determined first target hash table, but there is an idle standby hash bucket, then the data in the data element item of hash bucket 1 is transferred to the standby corresponding to hash bucket 1 in the hash bucket, and then store the first sub-data of the first data in the hash bucket 1;

If there is neither an idle hash bucket nor an idle standby hash bucket in the determined first target hash table, then, for example, in a specific data storage schematic diagram shown in FIG. 3 , the first The first sub-data of the group is stored in the linked list 1-1, the address of the linked list 1-1 is stored in the linked list address item, the second group of the first sub-data of the first data is stored in the linked list 1-2, and the linked list 1-2 The address of is stored in the linked list address item until the storage of the first data is completed;

It is understandable that in the above process, there will be data writing or/and data transfer, so it is necessary to record the total amount of data elements written in the current hash table, and the data format of the hash bucket can be adjusted to a certain extent , delete, add, and when the spare address slot is not free, it can continue to detect the spare address of the spare slot; perform multi-level spare slot detection to improve the success rate of data element insertion.

5) read the first sub-data and the second sub-data from the first hash table and the second target hash table, and merge and connect the first sub-data and the second sub-data satisfying the equivalence condition, to Get the data after connection; take a specific data merge connection schematic diagram shown in Figure 4 as an example, write the first sub-data into the merge connection unit according to the order of the data groups, read the first group of second sub-data, if the first A group of first sub-data and a first group of second sub-data satisfy the equivalence condition, then write the first group of second sub-data into the merge connection unit 1, perform merge connection, and so on, until all data are merged and connected After completion, output all the connected data to the connection result buffer module, and input the data result to the CPU processing unit according to the control instruction. Among them, the multi-row hash table data elements are merged and calculated, and each hash table merged calculation module reads and calculates the data elements of a single row; after the calculation is completed, continue to read the next valid row and calculate, through the extended data element merge module , can realize the parallel merging calculation of data in the multi-line hash table, fully utilizes the ability of FPGA parallel computing, and has strong scalability and portability.

Referring to Figure 5, the embodiment of the present application discloses a hash connection device, including:

The hash result acquisition module 11 is used to acquire the first data of the first data tuple to be connected and the second data of the second data tuple to be connected, and utilize the first hash function and the second hash in the cuckoo algorithm The function calculates the first data and the second data respectively to obtain a hash result of the first data and a hash result of the second data;

a hash table determining module 12, configured to determine a first target hash table corresponding to the hash result of the first data and a second target hash table corresponding to the hash result of the second data;

A storage module 13, configured to divide the first data and the second data into several groups of first sub-data and second sub-data, and respectively store the first sub-data and the second sub-data in the said first target hash table and said second target hash table;

A merge connection module 14, configured to read the first sub-data and the second sub-data from the first hash object hash table and the second target hash table, and combine all the sub-data that meet the equivalence condition The first sub-data and the second sub-data are merged and connected to obtain the connected data.

It can be seen that the present application obtains the first data of the first data tuple to be connected and the second data of the second data tuple to be connected, and utilizes the first hash function and the second hash function in the cuckoo algorithm to respectively Perform calculations on the first data and the second data to obtain a hash result of the first data and a hash result of the second data; determine the first data corresponding to the hash result of the first data a target hash table and a second target hash table corresponding to the hash result of the second data; respectively dividing the first data and the second data into several groups of first sub-data and second sub-data, And storing the first sub-data and the second sub-data to the first target hash table and the second target hash table respectively; from the first hash target hash table and the second target The first sub-data and the second sub-data are read from the hash table, and the first sub-data and the second sub-data satisfying the equivalence condition are merged and connected to obtain the connected data. It can be seen that, in the construction stage, the present application implements hash calculation and storage of the first data of the first data tuple to be connected and the second data of the second data tuple to be connected, so that the subsequent The first sub-data and the second sub-data are merged and connected to obtain the connected data, which eliminates the limitation that only one data tuple connection can be processed at a time in the detection stage, that is, parallel hash calculation, storage and merge connection can be realized, so Increased the speed of hash joins.

Further, the embodiment of the present application also provides an electronic device. Fig. 6 is a structural diagram of an electronic device 20 according to an exemplary embodiment, and the content in the diagram should not be regarded as any limitation on the application scope of the present application.

FIG. 6 is a schematic structural diagram of an electronic device provided by an embodiment of the present application. Specifically, it may include: at least one processor 21 , at least one memory 22 , a power supply 23 , a communication interface 24 , an input/output interface 25 and a communication bus 26 . Wherein, the memory 22 is used to store a computer program, and the computer program is loaded and executed by the processor 21 to implement relevant steps in the hash connection method performed by the electronic device disclosed in any of the foregoing embodiments.

In this embodiment, the power supply 23 is used to provide working voltage for each hardware device on the electronic device; the communication interface 24 can create a data transmission channel between the electronic device and the external device, and the communication protocol it follows is applicable to this Any communication protocol for applying for a technical solution is not specifically limited here; the input and output interface 25 is used to obtain external input data or output data to the external world, and its specific interface type can be selected according to specific application needs, and will not be described here. Specific limits.

Wherein, the processor 21 may include one or more processing cores, such as a 4-core processor, an 8-core processor, and the like. Processor 21 can adopt at least one hardware form in DSP (Digital Signal Processing, digital signal processing), FPGA (Field-Programmable Gate Array, field programmable gate array), PLA (Programmable Logic Array, programmable logic array) accomplish. Processor 21 also can comprise main processor and coprocessor, and main processor is the processor that is used for processing the data in wake-up state, also claims CPU (Central Processing Unit, central processing unit); Low-power processor for processing data in standby state. In some embodiments, the processor 21 may be integrated with a GPU (Graphics Processing Unit, image processor), and the GPU is used for rendering and drawing the content required to be displayed on the display screen. In some embodiments, the processor 21 may also include an AI (Artificial Intelligence, artificial intelligence) processor, and the AI processor is used to process computing operations related to machine learning.

In addition, the memory 22, as a resource storage carrier, can be a read-only memory, random access memory, magnetic disk or optical disk, etc., and the resources stored thereon include the operating system 221, computer program 222 and data 223, etc., and the storage method can be short-term storage or permanent storage.

Among them, the operating system 221 is used to manage and control each hardware device and computer program 222 on the electronic device, so as to realize the calculation and processing of the massive data 223 in the memory 22 by the processor 21, which can be Windows, Unix, Linux, etc. In addition to the computer program that can be used to complete the hash connection method performed by the electronic device disclosed in any of the foregoing embodiments, the computer program 222 can further include a computer program that can be used to complete other specific tasks. The data 223 may not only include data received by the electronic device and transmitted from an external device, but may also include data collected by its own input and output interface 25 and the like.

Further, the embodiment of the present application also discloses a computer-readable storage medium, and a computer program is stored in the storage medium, and when the computer program is loaded and executed by a processor, it can implement the hashing method disclosed in any of the above-mentioned embodiments. Method steps performed during connection.

Finally, it should also be noted that in this text, relational terms such as first and second etc. are only used to distinguish one entity or operation from another, and do not necessarily require or imply that these entities or operations, any such actual relationship or order exists. Furthermore, the term "comprises", "comprises" or any other variation thereof is intended to cover a non-exclusive inclusion such that a process, method, article, or apparatus comprising a set of elements includes not only those elements, but also includes elements not expressly listed. other elements of or also include elements inherent in such a process, method, article, or device. Without further limitations, an element defined by the phrase "comprising a ..." does not exclude the presence of additional identical elements in the process, method, article or apparatus comprising said element.

A hash connection method, device, equipment, and medium provided by the present invention have been introduced in detail above. In this paper, specific examples have been used to illustrate the principle and implementation of the present invention. The descriptions of the above embodiments are only used to help Understand the method of the present invention and its core idea; at the same time, for those of ordinary skill in the art, according to the idea of the present invention, there will be changes in the specific implementation and scope of application. In summary, the content of this specification is not It should be understood as a limitation of the present invention.

Claims (10)

1. A hash connection method, comprising:

acquiring first data of a first data tuple to be connected and second data of a second data tuple to be connected, and respectively calculating the first data and the second data by utilizing a first hash function and a second hash function in a cuckoo algorithm to obtain a hash result of the first data and a hash result of the second data;

determining a first target hash table corresponding to the hash result of the first data and a second target hash table corresponding to the hash result of the second data;

dividing the first data and the second data into a plurality of groups of first sub data and second sub data respectively, and storing the first sub data and the second sub data into the first target hash table and the second target hash table respectively;

And reading the first sub data and the second sub data from the first hash target hash table and the second hash target table, and merging and connecting the first sub data and the second sub data which meet the equivalent condition to obtain connected data.

2. The hash connection method as claimed in claim 1, wherein the acquiring the first data of the first data tuple to be connected and the second data of the second data tuple to be connected comprises:

reading a first data tuple to be connected and a second data tuple to be connected in an external memory to obtain first data of the first data tuple to be connected and second data of the second data tuple to be connected; the external memory is any one of a double-rate synchronous dynamic random access memory and a synchronous dynamic random access memory.

3. The hash connection method as claimed in claim 1, wherein the calculating the first data and the second data by using a first hash function and a second hash function in a cuckoo algorithm to obtain a hash result of the first data and a hash result of the second data includes:

Calculating the first data and the second data by using a first hash function and a second hash function in a cuckoo algorithm to obtain a first hash result and a second hash result of the first data and a first hash result and a second hash result of the second data;

correspondingly, the determining the first target hash table corresponding to the hash result of the first data and the second target hash table corresponding to the hash result of the second data includes:

determining a first hash table address and a second hash table address which correspond to the first hash result and the second hash result of the first data respectively, and a third hash table address and a fourth hash table address which correspond to the first hash result and the second hash result of the second data respectively;

and determining a first target hash table address from the first hash table address and the second hash table address, and determining a second target hash table address from the third hash table address and the fourth hash table address.

4. The hash connection method as claimed in claim 3, wherein said storing said first sub data and said second sub data to said first target hash table and said second target hash table, respectively, comprises:

Storing the first sub data into a hash table corresponding to the first target hash table address, and storing the second sub data into a hash table corresponding to the second target hash table address.

5. The hash table connection method as claimed in claim 4, wherein determining a first target hash table address from the first hash table address and the second hash table address, and determining a second target hash table address from the third hash table address and the fourth hash table address, comprises:

judging whether idle hash buckets exist in hash tables corresponding to the first hash table address and the second hash table address respectively, if so, determining the hash table address with the largest idle hash bucket number in the hash tables corresponding to the first hash table address and the second hash table address as a first target hash table address, and determining the other hash table address as a first target hash table standby address;

judging whether idle hash buckets exist in hash tables corresponding to the third hash table address and the fourth hash table address respectively, if so, determining the hash table with the largest idle hash bucket quantity in the hash tables corresponding to the third hash table address and the fourth hash table address as a second target hash table address, and determining the address of the other hash table as a second target hash table standby address;

Correspondingly, the storing the first sub data and the second sub data in the first target hash table and the second target hash table respectively includes:

storing the first sub-data and the first target hash table standby address into a free hash bucket of the first target hash table, and storing the second sub-data and the second target hash table standby address into a free hash bucket of the second target hash table.

6. The hash connection method as claimed in claim 5, wherein after determining whether there is a free hash bucket in the hash tables corresponding to the first hash table address and the second hash table address, respectively, the method further comprises:

if the hash table addresses do not exist, searching standby addresses of data stored in hash buckets in the hash tables corresponding to the first hash table address and the second hash table address respectively, and judging whether the hash buckets meeting preset conditions exist or not based on the standby addresses;

if so, the data stored in the hash bucket meeting the preset condition are transferred to the hash bucket in the hash table corresponding to the standby address, so that the first sub-data are stored in the hash bucket meeting the preset condition; and if the first sub data does not exist, storing the first sub data into a linked list corresponding to the first target hash table.

7. The hash connection method as claimed in any one of claims 1 to 6, wherein after storing the first sub data and the second sub data in the first target hash table and the second target hash table, respectively, further comprises:

and recording the total amount of data stored in the first target hash table and the second target hash table.

8. A hash connection apparatus, comprising:

the hash result acquisition module is used for acquiring first data of a first data tuple to be connected and second data of a second data tuple to be connected, and calculating the first data and the second data by using a first hash function and a second hash function in a cuckoo algorithm respectively to obtain a hash result of the first data and a hash result of the second data;

the hash table determining module is used for determining a first target hash table corresponding to the hash result of the first data and a second target hash table corresponding to the hash result of the second data;

the storage module is used for dividing the first data and the second data into a plurality of groups of first sub data and second sub data respectively and storing the first sub data and the second sub data to the first target hash table and the second target hash table respectively;

And the merging connection module is used for reading the first sub data and the second sub data from the first hash target table and the second hash target table, and merging and connecting the first sub data and the second sub data which meet the equivalent condition to obtain connected data.

9. An electronic device, comprising:

a memory for storing a computer program;

a processor for executing the computer program to implement the steps of the hash connection method as claimed in any one of claims 1 to 7.

10. A computer-readable storage medium storing a computer program; wherein the computer program when executed by a processor implements the steps of the hash connection method as claimed in any one of claims 1 to 7.

Images