Hardware acceleration of relational operations
This disclosure describes an implementation of a computing system that utilizes accelerator hardware configured to perform parallel computation of matching pairs of a join operation of a database program. This computation is performed at least in part by, for each thread that determines a matching pair, computing an offset in an output tuple by adding a global rank of a respective block, an intra block rank of a respective warp, and an intra warp rank of a respective thread. This computation is further performed by storing index values for a primary key and a foreign key in a matching pair at the computed offset location in an output tuple, and outputting the output tuple.
1 . A computing system, comprising:
a central processing unit configured to execute a database program; and
accelerator hardware configured to perform parallel computation of matching pairs of a join operation of the database program at least in part by:
receiving a request for the join operation on two or more tables of data, the request including an identification of pair of columns to compare for matching in the join operation, one of the columns being designated as containing primary keys and the other column being designated as containing foreign keys;
at each of a plurality of threads in each of a plurality of warps that are grouped into a plurality of thread blocks, determining if a pair of values stored at one of the primary keys and one of the foreign keys are a matching pair, and, if the pair of values is a matching pair, then computing an intra warp rank for the respective thread within the respective warp using local memory of the respective thread;
at one of the plurality of threads in each warp, computing an intra block rank of each respective warp and storing the intra block rank at a location in shared memory;
at one of the plurality of threads in each thread block, computing a global rank of each respective block using global memory;
for each thread that has determined a matching pair, computing an offset in an output tuple by adding the global rank of the respective block, the intra block rank of the respective warp, and the intra warp rank of the respective thread;
storing index values for the primary key and the foreign key in the matching pair at the offset location in the output tuple; and
outputting the output tuple.
2 . The computing system of claim 1 , further comprising:
retrieving the value for the primary key at the primary key index and the value for the foreign key at the foreign key index for each matching pair.
3 . The computing system of claim 2 , further comprising:
creating a join result data structure including the primary key value and the foreign key value for each matching pair.
4 . The computing system of claim 3 , further comprising:
outputting the join result data structure to a storage location or downstream program.
5 . The computing system of claim 1 , wherein the join operation is a structured query language (SQL) join operation.
6 . The computing system of claim 1 , wherein the accelerator hardware includes: a plurality of compute units, each compute unit being configured to execute a plurality of threads grouped into warps, the warps being grouped into thread blocks, the local memory of the accelerator hardware being privately accessible by each thread, the shared memory of the accelerator hardware being mutually accessible by each thread in one of the thread blocks, and the global memory being mutually accessible by all threads in all thread blocks performing the parallel computation.
7 . The computing system of claim 6 , wherein the accelerator hardware is a graphics processing unit, a tensor processing unit, and/or neural processing unit.
8 . The computing system of claim 6 , wherein the accelerator hardware is an integrated circuit, and the local memory and shared memory are provided on-chip, in the integrated circuit.
9 . The computing system of claim 8 , wherein the global memory is provided off-chip of the integrated circuit.
10 . The computing system of claim 6 , wherein the accelerator hardware and central processing unit are formed in a system-on-chip (SoC).
11 . A computerized method for use in processing a join operation of a database program with accelerator hardware, the method comprising:
via the accelerator hardware, performing parallel computation of matching pairs of a join operation of the database program at least in part by:
receiving a request for the join operation on two or more tables of data, the request including an identification of pair of columns to compare for matching in the join operation, one of the columns being designated as containing primary keys and the other column being designated as containing foreign keys;
at each of a plurality of threads in each of a plurality of warps that are grouped into a plurality of thread blocks, determining if a pair of values stored at one of the primary keys and one of the foreign keys are a matching pair, and, if the pair of values is a matching pair, then computing an intra warp rank for the respective thread within the respective warp using local memory of the respective thread;
at one of the plurality of threads in each warp, computing an intra block rank of each respective warp and storing the intra block rank at a location in shared memory;
at one of the plurality of threads in each thread block, computing a global rank of each respective block using global memory;
for each thread that has determined a matching pair, computing an offset in an output tuple by adding the global rank of the respective block, the intra block rank of the respective warp, and the intra warp rank of the respective thread;
storing index values for the primary key and the foreign key in the matching pair at the offset location in the output tuple; and
outputting the output tuple.
12 . The computerized method of claim 11 , further comprising:
retrieving the value for the primary key at the primary key index and the value for the foreign key at the foreign key index for each matching pair.
13 . The computerized method of claim 12 , further comprising:
creating a join result data structure including the primary key value and the foreign key value for each matching pair.
14 . The computerized method of claim 13 , further comprising:
outputting the join result data structure to a storage location or downstream program.
15 . The computerized method of claim 11 , wherein the join operation is a structured query language (SQL) join operation.
16 . The computerized method of claim 11 , wherein the accelerator hardware includes: a plurality of compute units, each compute unit being configured to execute a plurality of threads grouped into warps, the warps being grouped into thread blocks, the local memory of the accelerator hardware being privately accessible by each thread, the shared memory of the accelerator hardware being mutually accessible by each thread in one of the thread blocks, and the global memory being mutually accessible by all threads in all thread blocks performing the parallel computation.
17 . The computerized method of claim 16 , wherein the accelerator hardware is a graphics processing unit, a tensor processing unit, and/or neural processing unit.
18 . The computing system of claim 16 , wherein the accelerator hardware is an integrated circuit, and the local memory and shared memory are provided on-chip, in the integrated circuit.
19 . The computing system of claim 18 , wherein the global memory is provided off-chip of the integrated circuit.
20 . Accelerator hardware for use with a central processing unit of a computing system, the accelerator hardware comprising:
a plurality of compute units, each compute unit being configured to execute a plurality of threads grouped into warps, the warps being grouped into thread blocks, a local memory of the accelerator hardware being privately accessible by each thread, a shared memory of the accelerator hardware being mutually accessible by each thread in one of the thread blocks, and a global memory being mutually accessible by all threads in all thread blocks performing the parallel computation, wherein the compute units of the accelerator hardware are configured to perform parallel computation of matching pairs of a join operation of the database program at least in part by:
receiving a request for the join operation on two or more tables of data, the request including an identification of pair of columns to compare for matching in the join operation, one of the columns being designated as containing primary keys and the other column being designated as containing foreign keys;
at each of a plurality of threads in each of a plurality of warps that are grouped into a plurality of thread blocks, determining if a pair of values stored at one of the primary keys and one of the foreign keys are a matching pair, and, if the pair of values is a matching pair, then computing an intra warp rank for the respective thread within the respective warp using local memory of the respective thread;
at one of the plurality of threads in each warp, computing an intra block rank of each respective warp and storing the intra block rank at a location in shared memory;
at one of the plurality of threads in each thread block, computing a global rank of each respective block using global memory;
for each thread that has determined a matching pair, computing an offset in an output tuple by adding the global rank of the respective block, the intra block rank of the respective warp, and the intra warp rank of the respective thread;
storing index values for the primary key and the foreign key in the matching pair at the offset location in the output tuple; and
outputting the output tuple.