Simultaneous computation of multiple moving aggregates in a relational database management system

• US 6,567,803 B1
• Filed: 05/31/2000
• Issued: 05/20/2003
• Est. Priority Date: 05/31/2000
• Status: Active Grant

• Current Assignee: Teradata US, Inc. (Teradata Corporation)
• Original Assignee: NCR Corporation
• Inventors: Deshpande, Prasad Manikarao, Shukla, Amit, Ramasamy, Karthikeyan, Naughton, Jeffrey F.
• Primary Examiner(s): WONG, LESLIE
• Application Number:
  US09/583,633
• Time in Patent Office: 1,084 Days
• Field of Search: 707/2, 707/3, 707/4, 707/5, 707/102, 707/104.1
• US Class Current: 1/1
• CPC Class Codes: G06F 16/284 Relational databases
• CPC Class Codes: Y10S 707/99932 Access augmentation or optimizing
• 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/99943 Generating database or data structure, e.g. via user interface
• CPC Class Codes: Y10S 707/99945 Object-oriented database structure processing

Abstract

An On-Line Analytic Processing (OLAP) system identifies a plurality of simultaneously computable moving aggregate functions in a query. The identified moving aggregate functions are then partitioned into sets that can be computed simultaneously based on equivalent sort expressions. Finally, the OLAP system generates an access plan that executes the partitioned sets simultaneously.

Claims

1. A method for computing moving aggregates in an on-line analytical processing (OLAP) system, comprising:

(a) identifying a plurality of simultaneously computable moving aggregate functions in a query, and

(b) partitioning the identified moving aggregate functions into sets that can be computed simultaneously, and

(c) generating an access plan that executes the partitioned sets simultaneously.

2. The method of claim 1, wherein a moving aggregate function is described by a tuple including a mnemonic for the function, an expression for the function, a width of tuples for computing the function, and a sort order for the function.

3. The method of claim 2, wherein the sort orders for simultaneously computable moving aggregate functions are equivalent.

4. The method of claim 3, wherein the simultaneously computable moving aggregate functions are partitioned into sets based on their sort orders.

5. The method of claim 4, further comprising performing only a single sort for each of the partitioned sets.

6. The method of claim 5, further comprising evaluating tree isomorphism for the access plan to identify equivalent sort orders.

7. The method of claim 6, wherein the evaluating step comprises checking, in a recursive fashion, whether operator trees of two or more access plans are equivalent.

8. The method of claim 1, wherein the generating step comprises expanding each operator node in the access plan containing moving aggregate functions into a set of operators equal to a number of sets.

9. The method of claim 8, wherein each set is computed in a mutually exclusive fashion.

10. An on-line analytical processing (OLAP) system that computes moving aggregates, comprising:

(a) a computer system;

(b) logic, performed by the computer system, for;

(1) identifying a plurality of simultaneously computable moving aggregate functions in a query, and

(2) partitioning the identified moving aggregate functions into sets that can be computed simultaneously; and

(3) generating an access plan that executes the partitioned sets simultaneously.

11. An article of manufacture embodying logic for computing moving aggregates in an on-line analytical processing (OLAP) system, the logic comprising:

(a) identifying a plurality of simultaneously computable moving aggregate functions in a query; and

(b) partitioning the identified moving aggregate functions into sets that can be computed simultaneously; and

(c) generating an access plan that executes the partitioned sets simultaneously.