Data processing: database and file management or data structures – Database design – Data structure types
Reexamination Certificate
2000-09-06
2003-09-16
Mizrahi, Diane D. (Department: 2175)
Data processing: database and file management or data structures
Database design
Data structure types
Reexamination Certificate
active
06622138
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates generally to query operations performed within computer systems and, more specifically, to optimizing the computation of OLAP ranking functions.
BACKGROUND OF THE INVENTION
Relational databases store information in indexed 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 of data stored in a database. OLAP applications involve the use of analytic functions. 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 or window size. The window size 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 time wise within a partition. RANGE ‘3’ MONTH PRECEDING is a logical expression of window size. In the example, the “window” has the logical size of three months. Alternatively, window size may be expressed by a physical interval. That is, the interval may refer to how the data is stored within the database. 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
1-Jan′99
20
20
ORCL
1-Feb′99
30
(20 + 30)/2 = 25
ORCL
1-Mar′99
58
(20 + 30 + 58)/3 = 36
ORCL
1-Apr′99
11
(30 + 58 + 11)/3 = 33
ORCL
1-May′99
51
(58 + 11 + 51)/3 = 40
ABCD
1-Jan′99
25
25
ABCD
1-Feb′99
35
(25 + 35)/2 = 30
ABCD
1-Mar′99
45
(25 + 35 + 45)/3 = 35
ABCD
1-Apr′99
55
(35 + 45 + 55)/3 = 45
ABCD
1-May′99
65
(45 + 55 + 65)/3 = 55
Thus, the use of window functions enhances developer productivity because window functions allow for computerized decision support that may be either interactive or batch report jobs.
An important category of window functions is the “ranking” family of window functions. Window functions in the ranking family compute the rank of a row of data with respect to other rows of data in the dataset based on the values of a set of measures. To illustrate, the following query ranks salesmen in Acme Company based on sales amount in each geographical sales region.
SELECT sales_person, sales region, sales_amount,
RANK ( ) OVER (PARTITION BY sales_region ORDER BY s_amount DESC)
FROM Sales_table;
TABLE 2A below illustrates a result set for the preceding query. The “rank” column in Table 2A lists the sales persons in descending order based on the sales amount. The rank values are reset for each sales region.
TABLE 2A
sales_person
sales_region
sales_amount
rank
Adams
East
100
1
Baker
East
99
2
Connors
East
89
3
Davis
East
75
4
Edwards
West
74
1
Fitzhugh
West
66
2
Garibaldi
West
45
3
Examples of window functions in the ranking family include RANK, DENSE_RANK, NTILE, PERCENT_RANK, ROW_NUMBER, and CUME_DIST. Window functions that belong to the ranking family are hereafter referred to as ranking functions. Ranking functions are widely used in queries for ranking rows of data in a dataset based on some ordering criterion and subsequently filtering out all but the rows in the top-N ranks. For example, assume that the query corresponding to TABLE 2A asked for the top 2 salespersons in each sales region based on the sales amount credited to each sales person. TABLE 2B illustrates a results set where data rows corresponding to a rank that is greater than 2 are filtered out. Queries that result in the computation and selection of top-N ranks are hereafter referred to as “TOP-N” queries.
TABLE 2A
sales_person
sales_region
sales_amount
rank
Adams
East
100
1
Baker
East
99
2
Edwards
West
74
1
Fitzhugh
West
66
2
TOP-N queries are often computationally expensive when massive amounts of data need to be sorted and ranked. Because the use of TOP-N queries is frequent and widespread in the industry, any improvement in computation efficiency of TOP-N queries may amount to significant savings.
Based on the foregoing, there is clear need for a mechanism for optimizing the computation of OLAP Ranking functions.
SUMMARY OF THE INVENTION
Techniques are provided for optimizing the computation of OLAP ranking functions. According to one embodiment, a push-down technique is used whereby the filtering predicate associated with a ranking function is pushed down into the window sort, which filters rows while sorting the data. The set of conditions ensures that the push down technique does not result in filtering out data that is needed in other window sorts in the query.
REFERENCES:
patent: 5897632 (1999-04-01), Dar et al.
patent: 5956706 (1999-09-01), Carey et al.
patent: 6112198 (2000-08-01), Lohman 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.
patent: 6338056 (2002-01-01), Dessloch et al.
patent: 6385603 (2002-05-01), Chen et al.
John Clear, Debbie Dunn,Brad Harvey,Michael Heytens,Peter Lohman,Abhay Mehta,Mark Melton,Lars Rohrberg, Ashok Savasere, Robert Wehrmeister, Melody Xu Titled “NonStop SQL/MX Primitives for Knowledge Discovery” Copyright ACM 1999 1-58113-143-7/99/08 p425-429.*
Red Brick Warehouse Manual Version 5.1 SQL Reference guide and SQL Self-study guide Copyrigth Red Brick System,Inc. copyright 1991-1998 Revision No. 1, Jan. 1998, Part No. 401551.*
John Clear, Debbie Dunn,Brad Harvey,Michael Heytens,Peter Lohman,Abhay Mehta,Mark Melton,Lars Rohrberg, Ashok Savasere, Robert Wehrmeister, Melody Xu Titled “NonStop SQL/MX Primitives for Knowledge Discovery” Copyright ACM 1999 1-58113-143-7/99/08 p425-429.*
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”
Bellamkonda Srikanth
Ghosh Bhaskar
Witkowski Andrew
Hickman Palermo & Truong & Becker LLP
Mizrahi Diane D.
Nicholes Christian A.
Oracle International Corporation
LandOfFree
Method and apparatus for optimizing computation of OLAP... 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 and apparatus for optimizing computation of OLAP..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for optimizing computation of OLAP... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3018901