Partitioned joins in analytical databases

Patent metadata

Field	Value
Publication number	US-10496760-B2
Application number	US-201514919092-A
Country	US
Kind code	B2
Filing date	Oct 21, 2015
Priority date	Oct 21, 2015
Publication date	Dec 3, 2019
Grant date	Dec 3, 2019

Abstract

A first data table and a second table to be joined is determined. The first data table and the second data table have a join attribute. Data blocks of the first data table are stored on a storage device. An attribute value information for the join attribute for the data block of the first data table is determined. At least one partition for the first data table and the second table is defined using at least he attribute value information on the join attribute. Each partition of the at least one partition has a respective partition range of values of the join attribute. A pair wise partition join is processed on a first partition range of the determined partition ranges.

First claim

What is claimed is:

1. A computer program product for performing a partitioned join, the computer program product comprising:
one or more computer readable storage media; and
program instructions stored on the one or more computer readable storage media, the program instructions comprising:
program instructions to determine a first data table and a second data table to be joined, wherein the first data table and the second data table have a join attribute, and wherein data blocks of the first data table are stored on a storage device;
program instructions to determine an attribute value information of the join attribute for the data blocks of the first data table;
program instructions to define at least one partition for the first data table and the second data table using at least the attribute value information on the join attribute, wherein each partition of the at least one partition has a respective partition range of values of the join attribute; and
program instructions to process a pair wise partition join on a first partition range of the determined partition ranges comprising:
determining a first data blocks of the first data table that fully fall under the first partition range using the attribute value information, reading the determined first data blocks from a disk into a memory and feeding the determined first data blocks to the partition join on the first partition range with the second data table; and
determining a second data blocks of the first data table that partially fall under the first partition range using the attribute value information and selectively feeding records of the determined second data blocks that fall under the first partition range to the processing of the first partition range with the second data table.

2. The computer program product of claim 1 , further comprising program instructions, stored on the one or more computer readable storage media, to:
determine a second partition range immediately following the first partition range;
extract at least one record of the second data blocks that fall under the second partition range; and
buffer the extracted at least one record to the memory.

3. The computer program product of claim 1 , wherein each partition of the at least one partition include at least one data block.

4. The computer program product of claim 3 , wherein each partition of the at least one partition include partition bounds at a beginning or an end of a data block of the data blocks, wherein the beginning of the data block is a minimum value of the join attribute of the data block and the end of the data block is a maximum value of the join attribute of the data block.

5. The computer program product of claim 1 , wherein program instructions to define at least one partition for the first data table and the second data table comprise:
program instructions to order each data block of the first data blocks in accordance with a minimal value of the join attribute of each data block;
program instructions to assign each data block of the first data blocks to a partition of at least one partitions in the order of the minimal value of the join attribute until a size of the partition reaches a predefined maximum memory size, and
program instructions to repeat the assigning program instructions for another partition of the one or more partitions using data blocks of the first data table not yet assigned until all data blocks are assigned.

6. The computer program product of claim 1 , wherein a partition range of each partition of the at least one partitions is determined by dividing a range between a smallest join attribute value and a largest join attribute value of the data blocks into a given number of partitions using the attribute value information and adjusting partition range boundaries to match a nearest beginning or a nearest end of a data block of the data blocks of the first data table.

7. The computer program product of claim 1 , wherein each data block of the data blocks of the first data table or second data table covers a block range defined by a minimum value and a maximum value of the join attribute associated with the data block and wherein determining of the partition ranges comprising:
program instructions to determine an initial range using a smallest join attribute and a largest join attribute value in the first or second data table;
program instructions to determine a cutting subrange of the initial range for which a number of data blocks having respective block ranges falling in the cutting subrange is minimized;
program instructions to divide the initial range into two subranges, wherein a maximum join attribute value of a first subrange of the two subranges and a minimum join attribute value of a second subrange of the two subranges are within the cutting subrange; and
responsive to determining a size supported by a range of the first subrange and the second subrange is larger than a predefined maximum memory size, program instruction to repeat the program instruction to divide the range until a size supported by that range is equal or below the predefined maximum memory size.

8. The computer program product of claim 7 , wherein the dividing is performed such that at least one data block is fully contained in each of the first sub-range and the second sub-range.

9. A computer system for performing a partitioned join, the computer system comprising:
one or more computer processors;
one or more computer readable storage media; and
program instructions stored on the one or more computer readable storage media for execution by at least one of the one or more computer processors, the program instructions comprising:
program instructions to determine a first data table and a second data table to be joined, wherein the first data table and the second data table have a join attribute, and wherein data blocks of the first data table are stored on a storage device;
program instructions to determine an attribute value information of the join attribute for the data blocks of the first data table;
program instructions to define at least one partition for the first data table and the second data table using at least the attribute value information on the join attribute, wherein each partition of the at least one partition has a respective partition range of values of the join attribute; and
program instructions to process a pair wise partition join on a first partition range of the determined partition ranges comprising:
determining a first data blocks of the first data table that fully fall under the first partition range using the attribute value information, reading the determined first data blocks from a disk into a memory and feeding the determined first data blocks to the partition join on the first partition range with the second data table; and
determining a second data blocks of the first data table that partially fall under the first partition range using the attribute value information and selectively feeding records of the determined second data blocks that fall under the first partition range to the processing of the first partition range with the second data table.

10. The computer system of claim 9 , further comprising program instructions, stored on the one or more computer readable storage media for execution by at least one of the one or more computer processors, to:
determine a second partition range immediately following the first partition range;
extract at least one record of the second data blocks that fall under the second partition range; and
buffer the extracted at least one record to the memory.

11. The computer system of claim 9 , wherein each partition of the at least one partit

Assignees

• IBM

Inventors

• Boehme Thomas
• Brodt Andreas
• Koeth Oliver
• Schiller Oliver

Classifications

• G06F16/24557

  Efficient disk access during query execution · CPC title

• G06F16/2456 Primary

  Join operations · CPC title

• G06F16/24544

  Join order optimisation · CPC title

• G06F16/24554

  Unary operations; Data partitioning operations · CPC title

• G06F16/24537

  of operators · CPC title