Partitioned joins in analytical databases

Patent metadata

Field	Value
Publication number	US-10528680-B2
Application number	US-201715452778-A
Country	US
Kind code	B2
Filing date	Mar 8, 2017
Priority date	Oct 21, 2015
Publication date	Jan 7, 2020
Grant date	Jan 7, 2020

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 implemented method for performing a partitioned join, the method comprising:
determining, by one or more computer processors, 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;
determining, by one or more computer processors, an attribute value information of the join attribute for the data blocks of the first data table;
defining, by one or more computer processors, 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
processing, by one or more computer processors, a pair wise partition join on a first partition range of the determined partition ranges comprising:
determining, by one or more computer processors, 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, by one or more computer processors, 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 method of claim 1 , further comprising:
determining, by one or more computer processors, a second partition range immediately following the first partition range;
extracting, by one or more computer processors, at least one record of the second data blocks that fall under the second partition range; and
buffering, by one or more computer processors, the extracted at least one record to the memory.

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

4. The method 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 method of claim 1 , wherein defining at least one partition for the first data table and the second data table comprises:
ordering, by one or more computer processors, each data block of the first data blocks in accordance with a minimal value of the join attribute of each data block;
assigning, by one or more computer processors, 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
repeating the assigning step 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 method 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 method 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:
determining, by one or more computer processors, an initial range using a smallest join attribute and a largest join attribute value in the first or second data table;
determining, by one or more computer processors, 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;
dividing, by one or more computer processors, 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, repeating, by one or more computer processors, the step of dividing the range until a size supported by that range is equal or below the predefined maximum memory size.

8. The method 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.

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/24537

  of operators · CPC title

• G06F16/24544

  Join order optimisation · CPC title

• G06F16/24554

  Unary operations; Data partitioning operations · CPC title