# US 6,732,096 B1 · Optimizing an aggregate join query

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 6,732,096 B1
- Document ID: US6732096B1
- Status: Granted
- Kind: B1
- Application number: 09/918,252
- Filed: 2001-07-30
- Granted: 2004-05-04
- Earliest claimed: 2001-07-30
- Assignees: NCR Corporation
- Inventors: Grace Kwan-On Au
- Web page: https://patentgrep.com/patent/US6732096B1

## CPC

- G06F 16/24556: {Aggregation; Duplicate elimination}
- Y10S 707/99932: Access augmentation or optimizing
- Y10S 707/99935: Query augmenting and refining, e.g. inexact access
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)
- Y10S: TECHNICAL SUBJECTS COVERED BY FORMER USPC CROSS-REFERENCE ART COLLECTIONS [XRACs] AND DIGESTS

## Abstract

A method and computer system for optimizing queries to a database are disclosed. The query specifies one or more data-to-be-aggregated columns (DAC), one or more explicit aggregation keys (EAK) and one or more join conditions. The query involves table T1. T1includes the one or more data-to-be-aggregated columns and an aggregation key. All join conditions that involve T1 join the aggregation key of T1 to the unique primary index of another table that is involved in the query. T1 is joined to a table T2 in accordance with a join condition of the aggregate join query. The joining process includes sorting T1 on a sort key that is the aggregation key. Aggregation processing is combined into the step of sorting if T1 is a significant table. Aggregation processing is also combined into the step of sorting if T2 is a significant table and the first join condition is between the aggregation key of T1 and the unique primary index of T2.

## Claims

### Claim 1

A method for optimizing an aggregate join query that specifies one or more data-to-be-aggregated columns (DAC), one or more explicit aggregation keys (EAK) and one or more join conditions, and that involves table T1, T1 including the one or more data-to-be-aggregated columns and an aggregation key, whereby all join conditions that involve T1 join the aggregation key of T1 to the unique primary index of another table that is involved in the query, the method including the steps of:
joining T1 to a table T2 in accordance with a first join condition of the aggregate join query, the step of joining including sorting T1 on a sort key that is the aggregation key;
combining aggregation processing into the step of sorting if either:
(a) T1 is a significant table or
(b) T2 is a significant table and the first join condition is between the aggregation key of T1 and the unique primary index of T2.

### Claim 2 (depends on 1)

The method of claim 1, wherein T1 is an intermediate join result table IJR.

### Claim 3 (depends on 2)

The method of claim 2, wherein the IJR resulted from the following steps:
identifying the set TJ of tables linked by join conditions, TJ including all of the one or more DACs; and
deriving a new aggregation key (NK) for table T3, a member of TJ, from a join condition in the query that joins T3. NK to the unique primary index of the significant table.

### Claim 4 (depends on 2)

The method of claim 2, wherein the IJR resulted from the following steps:
identifying a set TJ of tables linked by join conditions where TJ includes all of the one or more DACs and the query contains at least one join condition between a member of TJ and the unique primary index index of T2 and joining the member tables of TJ to form the IJR.

### Claim 5 (depends on 4)

The method of claim 4, wherein the set TJ has the smallest possible number of member tables.

### Claim 6 (depends on 1)

The method of claim 1, wherein determining if a table is a significant table includes
if only one table includes the one or more EAKs, then that table is a significant table; otherwise
if the set of tables TS that includes all tables that contain at least one of the one or more EAKs, has a member table for which the query includes a join condition between that member table and the unique primary index of every other table in TS, then that member table is a significant table.

### Claim 7 (depends on 1)

The method of claim 1 further comprising the step of performing the remaining joins in the query.

### Claim 8

A database system in which an aggregate join query can be optimized, the query specifying one or more data-to-be-aggregated columns (DAC), one or more explicit aggregation keys (EAK) and one or more join conditions, and that involves table T1, T1 including the one or more data-to-be-aggregated columns and an aggregation key, whereby all join conditions that involve T1 join the aggregation key of T1 to the unique primary index of another table that is involved in the query, the database system comprising:
a massively parallel processing system comprising:
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 processes each of the one or more CPUs providing access to one or more virtual processes;
each process configured to manage data stored in one of a plurality of data-storage facilities;
the rows of each of the tables specified in the query being distributed among the plurality of data-storage facilities based on respective primary indices for each table;
a database-management component configured to execute the query by joining T1 to a table T2 in accordance with a first join condition of the aggregate join query, the step of joining including sorting T1 on a sort key that is the aggregation key;
combining aggregation processing into the step of sorting if either:
(a) T1 is a significant table or
(b) T2 is a significant table and the first join condition is between the aggregation key of T1 and the unique primary index of T2.

### Claim 9 (depends on 8)

The database system of claim 8 wherein T1 is an intermediate join result table IJR.

### Claim 10 (depends on 9)

The database system of claim 9, wherein the IJR resulted from identifying a set TJ of tables linked by join conditions where TJ includes all of the one or more DACs and the query contains at least one join condition between a member of TJ and the unique primary index index of T2 and joining the member tables of TJ to form the IJR.

### Claim 11 (depends on 10)

The database system of claim 10, wherein T2 is the significant table and joining the member tables of TJ to form the IJR comprises deriving a new aggregation key (NK) for table T3, a member of TJ, from a join condition that joins T3. NK to the unique primary index of the significant table and joining T1 and T3 to form a IJR that includes the one or more data-to-be-aggregated columns and an aggregation key.

### Claim 12 (depends on 11)

The database system of claim 11, wherein the set TJ has the smallest possible number of member tables.

### Claim 13 (depends on 8)

The database system of claim 8, wherein determining if a table is a significant table includes
if only one table includes the one or more EAKs, then that table is a significant table; otherwise
if the set of tables TS that includes all tables that contain at least one of the one or more EAKs, has a member table for which the query includes a join condition between that member table and the unique primary index of every other table in TS, then that member table is a significant table.

### Claim 14 (depends on 8)

The database system of claim 8, wherein the database-management component is configured to further execute the query by performing the remaining joins in the query.

### Claim 15

A computer program, stored in a tangible medium, that can accept a query specifying one or more data-to-be-aggregated columns (DAC), one or more explicit aggregation keys (EAK) and one or more join conditions, and that involves table T1, T1 including the one or more data-to-be-aggregated columns and an aggregation key, whereby all join conditions that involve T1 join the aggregation key of T1 to the unique primary index of another table that is involved in the query; the program comprising executable instructions that cause a computer to:
join T1 to a table T2 in accordance with a first join condition of the aggregate join query, the joining including sorting T1 on a sort key that is the aggregation key; and
combine aggregation processing into the sorting if either:
(a) T1 is a significant table or
(b) T2 is a significant table and the first join condition is between the aggregation key of T1 and the unique primary index of T2.

### Claim 16 (depends on 15)

The program of claim 15, wherein T1 is an intermediate join result table IJR.

### Claim 17 (depends on 16)

The program of claim 16, wherein the IJR resulted from executable instructions causing the computer to:
identify a set TJ of tables linked by join conditions where TJ includes all of the one or more DACs and the query contains at least one join condition between a member of TJ and the unique primary index index of T2 and join the member tables of TJ to form the IJR.

### Claim 18 (depends on 17)

The program of claim 17, wherein T2 is the significant table and joining the member tables of TJ to form the IJR comprises deriving a new aggregation key (NK) for table T3, a member of TJ, from a join condition that joins T3.NK to the unique primary index of the significant table and joining T1 and T3 to form a IJR that includes the one or more data-to-be-aggregated columns and an aggregation key.

### Claim 19 (depends on 18)

The program of claim 18, wherein the set TJ has the smallest possible number of member tables.

### Claim 20 (depends on 15)

The program of claim 15, wherein determining if a table is a significant table includes
if only one table includes the one or more EAKs, then that table is a significant table; otherwise
if the set of tables TS that includes all tables that contain at least one of the one or more EAKs, has a member table for which the query includes a join condition between that member table and the unique primary index of every other table in TS, then that member table is a significant table.

### Claim 21 (depends on 15)

The program of claim 15 further comprising the step of performing the remaining joins in the query.
