Dynamic partition enhanced joining

• US 7,319,997 B1
• Filed: 06/07/2004
• Issued: 01/15/2008
• Est. Priority Date: 06/07/2004
• Status: Active Grant

• Current Assignee: Teradata US, Inc. (Teradata Corporation)
• Original Assignee: NCR Corporation
• Inventors: Ramesh, Bhashyam, Morris, J. Mark
• Primary Examiner(s): Mofiz; Apu
• Assistant Examiner(s): Bibbee; Jared M
• Application Number:
  US10/862,686
• Time in Patent Office: 1,317 Days
• Field of Search: 707 1- 10, 707100-1041, 707200-206
• US Class Current: 707/714
• CPC Class Codes: G06F 16/2456 Join operations
• CPC Class Codes: Y10S 707/972 Partitioning
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching
• CPC Class Codes: Y10S 707/99942 Manipulating data structure, e.g. compression, compaction, compilation
• CPC Class Codes: Y10S 707/99945 Object-oriented database structure processing

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

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;

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;

storing the result; and

merging the results.

26. The database system of claim 25, where the demographic data includes one or more value count indexes.

27. The database system of claim 25, where the demographic data includes one or more compressed value lists.

28. The database system of claim 25, where the demographic data includes one or more column statistics.

29. The database system of claim 25, 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.

30. The database system of claim 29, where selecting a target work table includes:

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

31. The database system of claim 25, 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.

32. The database system of claim 25, 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.

33. The database system of claim 25, where partitioning the second table into the two or more second-table partitions includes:

creating two or more work tables;

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.

34. The database system of claim 33, where selecting a target work table includes:

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

35. The database system of claim 25, 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.

36. The database system of claim 35, 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.