Optimizing aggregate processing

• US 7,657,570 B2
• Filed: 04/20/2007
• Issued: 02/02/2010
• Est. Priority Date: 12/19/2002
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Cai, Mengchu, Lebovitz, Allan Benjamin, Lin, Fen-Ling, Wang, Yun, Zhang, Guogen, Cu, Jason Alexander, Chen, Yao-Ching, Lee, Li-Mey
• Primary Examiner(s): Woo; Isaac M
• Application Number:
  US11/738,406
• Publication Number:
  US 20070192285A1
• Time in Patent Office: 1,019 Days
• Field of Search: 707 1- 10, 707100-1041, 707200-206
• US Class Current: 1/1
• CPC Class Codes: G06F 16/20 of structured data, e.g. relational data
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching
• CPC Class Codes: Y10S 707/99934 Query formulation, input preparation, or translation
• CPC Class Codes: Y10S 707/99935 Query augmenting and refining, e.g. inexact access
• CPC Class Codes: Y10S 707/99948 Application of database or data structure, e.g. distributed, multimedia, or image

Abstract

Disclosed is method for processing an aggregate function. Rows that contain a reference to intermediate result structures are grouped to form groups. For each group, aggregate element structures are formed from the intermediate result structures and, if the aggregate function specifies ordering, the aggregate element structures are sorted based on a sort key.

Claims

1. A method for making a computer implemented process to enable processing of an aggregate function, said method comprising:

instantiating first computer instructions onto a computer readable medium, said first computer instructions configured to, if a first argument of the aggregate function is a nested function, generate a composite structure that includes a tagging template for the nested function and generate an intermediate result structure for each row to be processed by the aggregate function, wherein each intermediate result structure references the tagging template;

instantiating second computer instructions onto a computer readable medium, said second computer instructions configured to group rows that contain a reference to intermediate result structures to form groups, wherein each of the intermediate result structures holds intermediate results including argument input values to represent different levels of nested functions; and

instantiating third computer instructions onto a computer readable medium, said third computer instructions configured to, for each group, form aggregate element structures in memory from the intermediate result structures and, if the aggregate function specifies ordering, sort the aggregate element structures based on a sort key in memory.

2. The method of claim 1, wherein the first argument of the aggregate function is a column representing intermediate result structures.

3. The method of claim 1, wherein said second computer instructions configured to group rows are adapted to group the rows based on one or more grouping columns.

4. The method of claim 1, further comprising:

instantiating fourth computer instructions onto a computer readable medium, said fourth computer instructions configured to performing serialization after the aggregation function has been processed.

5. The method of claim 1, wherein the aggregate element structures form a doubly-linked list.

6. The method of claim 1, wherein each group of aggregate element structures has a group header.

7. The method of claim 6, wherein the group header references a first aggregate element structure and a last aggregate element structure in a group of aggregate element structures.

8. The method of claim 1, wherein said third computer instructions configured to sort the aggregate element structures based on the sort key are adapted to further perform an in-memory sort for the aggregate element structures for a group based on the sort key.

9. The method of claim 8, wherein the aggregate element structures form a doubly-linked list and wherein said third computer instructions configured to sort are adapted to manipulate links of the doubly-linked list without moving data.