Method, system, and program for optimizing aggregate processing

• US 20040122815A1
• Filed: 12/19/2002
• Published: 06/24/2004
• Est. Priority Date: 12/19/2002
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Lin, Fen-Ling, Wang, Yun, Zhang, Guogen, Cu, Jason Alexander, Cai, Mengchu, Lebovitz, Allan Benjamin, Lee, Li-Mey, Chen, Yao Ching Stephen
• Granted Patent: US 7,243,098 B2
• Time in Patent Office: Days
• US Class Current: 707/4
• 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 a method, system, and program 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 processing an aggregate function, comprising:

grouping rows that contain a reference to intermediate result structures to form groups;

for each group,

forming aggregate element structures from the intermediate result structures; and

if the aggregate function specifies ordering, sorting the aggregate element structures based on a sort key.

2. The method of claim 1, further comprising:

if a first argument of the aggregate function is a nested function,

generating a composite structure that includes a tagging template for the nested function; and

generating an intermediate result structure for each row to be processed by the aggregate function, wherein each intermediate result structure references the tagging template.

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

4. The method of claim 1, wherein grouping is based on one or more grouping columns.

5. The method of claim 1, further comprising:

performing serialization after the aggregation function has been processed.

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

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

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

9. The method of claim 1, wherein sorting the aggregate element structures based on the sort key further comprises an in-memory sort for the aggregate element structures for a group based on the sort key.

10. The method of claim 9, wherein the aggregate element structures form a doubly-linked list and wherein sorting further comprises manipulating links of the doubly-linked list without moving data.

11. A system for processing an aggregate function, comprising:

a processor;

a memory coupled to the processor;

at least one program executed by the processor in the memory to cause the processor to perform;

grouping rows that contain a reference to intermediate result structures to form groups;

for each group,

forming aggregate element structures from the intermediate result structures; and

if the aggregate function specifies ordering, sorting the aggregate element structures based on a sort key.

12. The system of claim 11, wherein the at least one program further causes the processor to perform:

if a first argument of the aggregate function is a nested function,

generating a composite structure that includes a tagging template for the nested function; and

generating an intermediate result structure for each row to be processed by the aggregate function, wherein each intermediate result structure references the tagging template.

13. The system of claim 11, wherein the first argument of the aggregate function is a column representing intermediate result structures.

14. The system of claim 11, wherein grouping is based on one or more grouping columns.

15. The system of claim 11, wherein the at least one program further causes the processor to perform:

serialization after the aggregation function has been processed.

16. The system of claim 11, wherein the aggregate element structures form a doubly-linked list.

17. The system of claim 11, wherein each group of aggregate element structures has a group header.

18. The system of claim 17, wherein the group header references a first aggregate element structure and a last aggregate element structure in a group of aggregate element structures.

19. The system of claim 11, wherein sorting the aggregate element structures based on the sort key further comprises an in-memory sort for the aggregate element structures for a group based on the sort key.

20. The system of claim 19, wherein the aggregate element structures form a doubly-linked list and wherein sorting further comprises manipulating links of the doubly-linked list without moving data.

21. An article of manufacture including a program for processing an aggregate function, wherein the program causes operations to be performed, the operations comprising:

grouping rows that contain a reference to intermediate result structures to form groups;

for each group,

forming aggregate element structures from the intermediate result structures; and

if the aggregate function specifies ordering, sorting the aggregate element structures based on a sort key.

22. The article of manufacture of claim 21, the operations further comprising:

if a first argument of the aggregate function is a nested function,

generating a composite structure that includes a tagging template for the nested function; and

generating an intermediate result structure for each row to be processed by the aggregate function, wherein each intermediate result structure references the tagging template.

23. The article of manufacture of claim 21, wherein the first argument of the aggregate function is a column representing intermediate result structures.

24. The article of manufacture of claim 21, wherein grouping is based on one or more grouping columns.

25. The article of manufacture of claim 21, the operations further comprising:

performing serialization after the aggregation function has been processed.

26. The article of manufacture of claim 21, wherein the aggregate element structures form a doubly-linked list.

27. The article of manufacture of claim 21, wherein each group of aggregate element structures has a group header.

28. The article of manufacture of claim 27, wherein the group header references a first aggregate element structure and a last aggregate element structure in a group of aggregate element structures.

29. The article of manufacture of claim 21, wherein sorting the aggregate element structures based on the sort key further comprises an in-memory sort for the aggregate element structures for a group based on the sort key.

30. The article of manufacture of claim 29, wherein the aggregate element structures form a doubly-linked list and wherein sorting further comprises manipulating links of the doubly-linked list without moving data.