Efficient partitioned joins in a database with column-major layout

Patent metadata

Field	Value
Publication number	US-9355146-B2
Application number	US-201213537745-A
Country	US
Kind code	B2
Filing date	Jun 29, 2012
Priority date	Jun 29, 2012
Publication date	May 31, 2016
Grant date	May 31, 2016

Abstract

Embodiments of the present invention provide a database processing system for efficient partitioning of a database table with column-major layout for executing one or more join operations. One embodiment comprises a method for partitioning a database table with column-major layout, partitioning only the join-columns by limiting the partitions by size and number, executing one or more join operations for joining the partitioned columns, and optionally de-partitioning the join result to the original order by sequentially writing and randomly reading table values using P cursors.

First claim

What is claimed is:

1. A computer program product for partitioned join in a database, comprising a non-transitory computer usable medium including a computer readable program, wherein the computer readable program when executed on a computer causes the computer to perform:
partitioning a database table with column major layout by limiting partitioning to those columns containing join-columns including multiple keys for a join operator without partitioning other columns, wherein limiting partitioning is based on number of partitions determined by a first hardware constraint and size of the partitions that is determined by a second hardware constraint;
executing one or more join operations for joining the partitioned columns, wherein the other columns are not accessed during the one or more join operations;
joining a probe table with one or more build tables, comprising partitioning values of one or more join-columns in one or more steps, wherein in each step the number of the partitions and the size of the partitions is limited;
forming hash tables on the build tables;
mapping their respective join-column values of the hash tables to the values of any additional columns that are needed in a query;
scanning the probe table, wherein for each batch of join-column values, the values are looked up into the corresponding hash tables on the build tables;
looking up the corresponding partition from the build table;
extracting for each join-column value any auxiliary columns that are needed in the query;
computing one or more Boolean values for each join-column value including a Boolean value indicating whether a join-column value found any match in the hash table;
after lookup of a build table, de-partitioning the partitions;
limiting the number of partitions based on the first hardware constraint that comprises the number of entries in the level-1 translation lookaside buffer (TLB);
performing recursive partitioning when both the number of the partitions and the size of the partitions is constrained; and
de-partitioning the partitions to obtain the original ordering by sequentially writing and randomly reading table values using P cursors, wherein P is less than the number of entries in the TLB.

2. The computer program product of claim 1 , further comprising:
undoing the partitioning in a de-partitioning step to convert the join result back into original order.

3. The computer program product of claim 1 , wherein no other columns are accessed during the one or more join operations for joining the partitioned columns, and the multiple keys for the join operator comprise primary keys or foreign keys.

4. The computer program product of claim 1 , wherein the join-columns comprise columns having one or more equality join predicates relating one or more columns of a probe table to one or more columns of a build table.

5. The computer program product of claim 1 , wherein the size of each of the partitions is limited to the second hardware constraint that comprises a size of cache, and recursive partitioning comprises repeated partitioning of output partitions from a previous partitioning.

6. The computer program product of claim 1 , wherein partitioning of the join-columns is performed by a hash function computation on the values of each join-column, and the hash function is a same hash function used for the hash table.

7. The computer program product of claim 1 , wherein the partitioning comprises a permutation operation performed on an array of the join-column values for forming an output array.

Assignees

• Arndt Stefan
• Attaluri Gopi K
• Barber Ronald J
• Lohman Guy M
• Qiao Lin
• Raman Vijayshankar
• Shekita Eugene J
• Sidle Richard S
• IBM

Inventors

• Arndt Stefan
• Attaluri Gopi K
• Barber Ronald J
• Lohman Guy M
• Qiao Lin
• Raman Vijayshankar
• Shekita Eugene J
• Sidle Richard S

Classifications

• G06F17/30466 Primary

  Physics · mapped topic

• G06F16/2456

  Join operations · CPC title

• G06F16/221

  Column-oriented storage; Management thereof · CPC title

• G06F16/2255

  Hash tables · CPC title

• G06F16/24554 Primary

  Unary operations; Data partitioning operations · CPC title