IP Library › Granted Patent US 7,319,997

Granted Patent B1

US 7,319,997 · App. 10/862,686 · Granted Jan 15, 2008

Dynamic partition enhanced joining

View Patent ↗

Loading inventors, assignments & file history…

Monitor This Case

Get email alerts when status or documents change.

Order Certified Copies

Most orders are placed with the USPTO same day — all within 24 business hours.

Order via The Patent Place →

Pre-filled with this patent's details

Quick Facts

Patent No.: US 7,319,997
App. No.: 10/862,686
Granted: Jan 15, 2008
Kind: B1

External Links

USPTO Patent Center↗ Full Patent PDF↗

Abstract

Methods, computer programs, and database systems for performing a database query that includes a join on an equality condition are disclosed. The method includes defining two or more first-table partitions and two or more corresponding second-table partitions. The method includes performing the join on the first-table partition and the second-table partition, storing the result, and merging the results.

Claims (143)

1. A method of performing a database query including a join on an equality condition between one or more columns in a first table and one or more columns in a second table, each of the first table and the second table including zero or more rows, the method including:

defining two or more first-table partitions, where each row in the first table appears in exactly one first-table partition;

defining two or more second-table partitions, each second-table partition corresponding to a first-table partition, and where each row in the second table appears in exactly one second-table partition;

where defining the two or more first-table partitions and the two or more second-table partitions includes:

acquiring first-table-demographic data for the one or more columns in the first table, the demographic data including zero or more first-table-column values;

acquiring second-table-demographic data for the one or more columns in the second table, the demographic data including zero or more second-table-column values;

creating a qualifying set by joining the first table demographic data and the second table demographic data on the equality condition;

partitioning the first table into the two or more first-table partitions, using the qualifying set; and

partitioning the second table into the two or more second-table partitions, using the qualifying set; and

for one or more corresponding first-table partitions and second-table partitions:

performing the join on the first-table partition and the second-table partition; and

storing the result; and

merging the results.

2. The method of claim 1 , where the demographic data includes one or more value count indexes.

3. The method of claim 1 , where the demographic data includes one or more compressed value lists.

4. The method of claim 1 , where the demographic data includes one or more column statistics.

5. The method of claim 1 , where partitioning the first table into the two or more first-table partitions includes:

creating two or more work tables;

for each first-table row:

selecting a target work table based on the qualifying set and one or more first-table-row values; and

placing the first-table row in the target work table.

6. The method of claim 5 , where selecting a target work table includes:

determining whether one of the first-table-row values is in the qualifying set.

7. The method of claim 1 , where partitioning the first table into the two or more first-table partitions includes:

creating a work table with a partitioned-primary index;

defining the partitioned-primary index based on the qualifying set; and

populating the work table from the first table.

8. The method of claim 7 , where defining the partitioned-primary index based on the qualifying set includes:

defining the partitioned-primary index so that:

rows with first-table-column values in the qualifying set are placed in a first partition; and

rows with first-table-column values not in the qualifying set are placed in a second partition.

9. The method of claim 1 , where partitioning the second table into the two or more second-table partitions includes:

creating two or more work tables; and

for each second-table row:

selecting a target work table based on the qualifying set and one or more second-table-row values; and

placing the second-table row in the target work table.

10. The method of claim 9 , where selecting a target work table includes:

determining whether one of the second-table-row values is in the qualifying set.

11. The method of claim 1 , where partitioning the second table into the two or more second-table partitions includes:

creating a work table with a partitioned-primary index;

defining the partitioned-primary index based on the qualifying set; and

populating the work table from the second table.

12. The method of claim 11 , where defining the partitioned-primary index based on the qualifying set includes:

defining the partitioned-primary index so that;

rows with second-table-column values in the qualifying set are placed in a first partition; and

rows with second-table-column values not in the qualifying set are placed in a second partition.

13. A computer program, stored on a tangible storage medium, for use in performing a database query including a join on an equality condition between one or more columns in a first table and one or more columns in a second table, each of the first table and the second table including zero or more rows, the computer program including executable instructions that cause a computer to:

define two or more first-table partitions, where each row in the first table appears in exactly one first-table partition;

define two or more second-table partitions, each second-table partition corresponding to a first-table partition, and where each row in the second table appears in exactly one second-table partition;

where the executable instructions that cause the computer to define the two or more first-table partitions and the two or more second-table partitions further cause the computer to:

acquire first-table-demographic data for the one or more columns in the first table, the demographic data including zero or more first-table-column values;

acquire second-table-demographic data for the one or more columns in the second table, the demographic data including zero or more second-table-column values;

create a qualifying set by joining the first table demographic data and the second table demographic data on the equality condition; and

partition the first table into the two or more first-table partitions, using the qualifying set;

partition the second table into the two or more second-table partitions, using the qualifying set; and

for one or more corresponding first-table partitions and second-table partitions:

perform the join on the first-table partition and the second-table partition; and

store a result; and

merge the results.

14. The computer program of claim 13 , where the demographic data includes one or more value count indexes.

15. The computer program of claim 13 , where the demographic data includes one or more compressed value lists.

16. The computer program of claim 13 , where the demographic data includes one or more column statistics.

17. The computer program of claim 13 , where the executable instructions that cause the computer to partition the first table into the two or more first-table partitions further cause the computer to:

create two or more work tables;

for each first-table row:

select a target work table based on the qualifying set and one or more first-table-row values; and

place the first-table row in the target work table.

18. The computer program of claim 17 , where the executable instructions that cause the computer to select a target work table further cause the computer to:

determine whether one of the first-table-row values is in the qualifying set.

19. The computer program of claim 13 , where the executable instructions that cause the computer to partition the first table into the two or more first-table partitions further cause the computer to:

create a work table with a partitioned-primary index;

define the partitioned-primary index based on the qualifying set; and

populate the work table from the first table.

20. The computer program of claim 19 , where the executable instructions that cause the computer to define the partitioned-primary index based on the qualifying set further cause the computer to:

defining the partitioned-primary index so that:

rows with first-table-column values in the qualifying set are placed in a first partition; and

rows with first-table-column values not in the qualifying set are placed in a second partition.

21. The computer program of claim 13 , where the executable instructions that cause the computer to partition the second table into the two or more second-table partitions further cause the computer to:

create two or more work tables;

for each second-table row:

select a target work table based on the qualifying set and one or more second-table-row values; and

place the second-table row in the target work table.

22. The computer program of claim 21 , where the executable instructions that cause the computer to select a target work table further cause the computer to:

determine whether one of the second-table-row values is in the qualifying set.

23. The computer program of claim 13 , where the executable instructions that cause the computer to partition the second table into the two or more second-table partitions further cause the computer to:

create a work table with a partitioned-primary index;

define the partitioned-primary index based on the qualifying set; and

populate the work table from the second table.

24. The computer program of claim 23 , where the executable instructions that cause the computer to define the partitioned-primary index based on the qualifying set further cause the computer to:

define the partitioned-primary index so that:

rows with second-table-column values in the qualifying set are placed in a first partition; and

rows with second-table-column values not in the qualifying set are placed in a second partition.

25. A database system including:

a massively parallel processing system including:

one or more nodes;

a plurality of CPUs, each of the one or more nodes providing access to one or more CPUs;

a plurality of data storage facilities each of the one or more CPUs providing access to one or more data storage facilities;

a process for execution on the massively parallel processing system for performing a database query including a join on an equality condition between one or more columns in a first table and one or more columns in a second table, each of the first table and the second table including zero or more rows, the process including: