Data processing: database and file management or data structures – Database design – Data structure types
Reexamination Certificate
2000-09-07
2002-05-14
Mizrahi, Diane D. (Department: 2171)
Data processing: database and file management or data structures
Database design
Data structure types
C707S793000, C707S793000, C707S793000, C707S793000, C707S793000
Reexamination Certificate
active
06389410
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates generally to database query operations performed within computer systems and, more specifically, to minimizing the number of sort operations required for a database query containing window functions.
BACKGROUND OF THE INVENTION
Relational databases store information in tables that are organized into rows and columns. A user retrieves information from the tables by entering a request that is converted to queries by a database application, which then submits the queries to a database server. In response to the queries, the database server accesses the tables specified by the queries to determine which information within the tables satisfies the queries. The information that satisfies the queries is then retrieved by the database server and transmitted to the database application and ultimately to the user.
Online analytical processing (“OLAP”) applications, also known as decision support processing applications, are applications that provide analysis over large volumes of data stored in a database. Analytic calculations are critical for data warehousing applications. Examples of analytic functions are those functions used in basic business intelligence calculations such as moving averages, rankings and lead/lag comparisons of data. Analytic functions are broadly classified as window functions. Window functions are so named because they operate over a set of rows of data in the database tables. The set of rows upon which the window functions operate are described by a window definition. The window definition describes which rows qualify for the window. The window has a starting row and an ending row. For example, a window defined for a moving average would have both the starting and end points of the window slide so that the end points maintain a constant physical or logical range. For example, the following query calculates a 3 month moving average per stock ticker.
AVG (stock_price) OVER (Partition By (stock_name) Order By (time) RANGE ‘3’ MONTH PRECEDING)
The clause “Partition By (stock_name)” partitions the data by stock_name, and the clause “Order By (time)” orders the data within a partition by time. RANGE ‘3’ MONTH PRECEDING is a logical expression of window size. In this example, the “window” has the logical size of three months. Alternatively, window size may be expressed by a physical interval. That is, the interval includes a certain number of rows before and after the current row in the ordered set of rows (ordered based on ORDER By columns in window function.) For example, the following query calculates the moving average for each stock ticker over 90 preceding rows of data.
AVG (stock_price) OVER (Partition By (stock_name) Order By (time) ROWS 90 PRECEDING)
TABLE 1 below illustrates a result set for the-query containing the window function “AVG (stock_price) OVER (Partition By (stock_name) Order By (time) RANGE ‘3’ MONTH PRECEDING)”. The above window function calculates a moving average of stock price for each stock within a three month window.
TABLE 1
stock_name
Time
stock_price
moving_average
ORCL
Jan. 1, '99.
20
20
ORCL
Feb. 1, '99.
30
(20 + 30)/2 = 25
ORCL
Mar. 1, '99.
58
(20 + 30 + 58)/3 = 36
ORCL
Apr. 1, '99.
11
(30 + 58 + 11)/3 = 33
ORCL
May 1, '99.
51
(58 + 11 + 51)/3 = 40
ABCD
Jan. 1, '99.
25
25
ABCD
Feb. 1, '99.
35
(25 + 35)/2 = 30
ABCD
Mar. 1, '99.
45
(25 + 35 + 45)/3 = 35
ABCD
Apr. 1, '99.
55
(35 + 45 + 55)/3 = 45
ABCD
May 1, '99.
65
(45 + 55 + 65)/3 = 55
Thus, the use of window functions enhances developer productivity because window functions allow for a succinct representation of otherwise, complicated queries. However, a separate sort is typically required for each window function. In addition, when the query block that contains window functions also contains “Group By” and/or “Order By” clauses, additional sorts are required. Thus, the number of sorts is greater than or equal to the number of window functions in the query. A typical query contains multiple window functions. The computation time required for the total number of sorts may be massive.
Based on the foregoing, there is clear need for a mechanism for minimizing the number of sort operations that are required to satisfy a query that contains window functions.
SUMMARY OF THE INVENTION
Techniques are provided for minimizing the number of sort operations that are required for satisfying a query containing a set of window functions. According to one embodiment, the window functions are grouped into Ordering Groups. An Ordering Group is a subset of the window functions, which are capable of being satisfied by a particular sort operation.
According to one embodiment, the Ordering Groups are constructed around the window functions that require the most restrictive sort operations. From the set of Ordering Groups, a minimal set of Ordering Groups is selected. The number of sort operations corresponding to the minimal set of Ordering Groups is the minimal number of sort operations needed to satisfy the sorting requirements of the set of window functions.
Since “GROUP BY” & “ORDER BY” clauses of the query block are mapped to window functions, the minimal set of ordering groups represents the minimal number of sort operations required for the whole query block excluding join operations.
REFERENCES:
patent: 5555403 (1996-09-01), Cambot et al.
patent: 5566330 (1996-10-01), Sheffield
patent: 5701456 (1997-12-01), Jacopi et al.
patent: 5897632 (1999-04-01), Dar et al.
patent: 6125360 (2000-09-01), Witkowski et al.
patent: 6134543 (2000-10-01), Witkowski et al.
patent: 6199063 (2001-03-01), Colby et al.
Chaudhuri, Surajit et al., “Optimizing Queries with Materialized Views”, Proceedings of the Eleventh International Conference on Data Engineering, Mar. 6-10, 1995, pp. 190-200.
Gopalkrishnan, Vivekanand et al., “Issues of Object-Relational View Design in Data Warehousing Environment”, 1998 IEEE International Conference on Systems, Man, and Cybernetics, Oct. 11-14, 1998, vol. 3, pp. 2732-2737.
Kuno, Harumi et al., “Augmented Inherited Multi-Index Structure for Maintenance of Materialized Path Query Views”, Proceedings of the Sixth International Conference on Research Issues in Data Engineering, Feb. 26-27, 1996, pp. 128-137.
Segev, Arie et al., “Maintaining Materialized Views in Distributed Databases”, Proceedings of the Fifth International Conference on Data Engineering, Feb. 6-10, 1989, pp. 262-270.
Becker Edward A.
Hickman Palermo & Truong & Becker LLP
Mizrahi Diane D.
Oracle Corporation
Tan Carina M.
LandOfFree
Method for minimizing the number of sorts required for a... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method for minimizing the number of sorts required for a..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method for minimizing the number of sorts required for a... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2859977