US6622138B1

Movatterモバイル変換

Info

Publication number: US6622138B1
Application number: US09/656,304
Authority: US
Inventors: Srikanth Bellamkonda; Bhaskar Ghosh; Andrew Witkowski
Original assignee: Oracle International Corp
Current assignee: Oracle International Corp
Priority date: 2000-09-06
Filing date: 2000-09-06
Publication date: 2003-09-16

Abstract

Techniques are described for optimizing the computation of OLAP ranking functions. The techniques involve push-down of the filtering operation into the window sort operation corresponding to a target ranking function. The push-down technique may be employed when a predetermined set of push-down conditions are met.

Description

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.

BRIEF DESCRIPTION OF THE DRAWINGS

The present invention is illustrated by way of example, and not by way of limitation, in the figures of the accompanying drawings and in which like reference numerals refer to similar elements and in which:

FIG. 1A-1C are flowcharts that illustrate an overview of one embodiment of the invention;

FIG. 2 is a flowchart that illustrates the condition to be satisfied by the filtering predicate associated with the target ranking function;

FIG. 3 is a flowchart that illustrates the condition that is to be satisfied by unordered window functions in the query block;

FIG. 4 is a flowchart that illustrates the condition that is to be satisfied by all ranking functions other than the target ranking function in the query block;

FIG. 5 is a flowchart that illustrates the condition that is to be satisfied by all ordered window functions with ROWS option in the query block;

FIG. 6 is a flowchart that illustrates the condition that is to be satisfied by all ordered window functions with RANGE option in the query block;

FIG. 7 illustrates a row source tree and DFO tree associated with the parallel execution of a TOP-N query;

FIG. 8 illustrates the row source tree and DFO tree associated with the parallel execution of a TOP-N query; and

FIG. 9 depicts a computer upon which embodiments of the invention may be implemented.

DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENT

Techniques are provided for optimizing the computation of OLAP ranking functions. In the following description, for the purposes of explanation, numerous specific details are set forth in order to provide a thorough understanding of the present invention. It will be apparent, however, to one skilled in the art that the present invention may be practiced without these specific details. In other instances, well-known structures and devices are shown in block diagram form in order to avoid unnecessarily obscuring the present invention.

FUNCTIONAL OVERVIEW

In one embodiment of the invention, the computation of OLAP ranking functions is optimized by filtering data based on the predicate of a given ranking function during the window sort procedure associated with the particular ranking function. To illustrate, a typical OLAP query has the following general structure:

SELECT deptno, ename, salary, rnk

FROM (select deptno, ename, salary,

RANK OVER (Partition By deptno Order By salary DESC) as rnk

FROM EmpTable)

WHERE rnk<=5

ORDER BY rnk;

The syntax used in the preceding statements is merely illustrative. The actual syntax of statements involving OLAP queries may vary from implementation to implementation. The present invention is not limited to any particular syntax.

The embodiment is described, in part, with reference to the structure of the query. The above query retrieves a result set that displays the identities and salaries of the top 5 highest salaried employees in each department in a company. In the context of structure, the above query is generally referred to as a query block. The query block comprises an inner query block and an outer query block. The inner query block may comprise one or more window functions.

In the above sample query, the inner query block is the indented portion of the query block. The inner query block contains the ranking function, “RANK OVER (Partition By deptname Order By salary DESC) as rnk”, which is a window function from the ranking family of window functions. “Rnk<=5” is a predicate on the ranking function and appears in the immediate outer query block. Window functions allow for the division of a query result set into groups of rows called “Partitions”. Thus, references herein to partitions in the context of window functions are unrelated to the partitioning models for managing very large tables and indexes. Examples of partitioning models for managing very large tables and indexes are hash partitioning and composite partitioning etc. In the above sample query, the clause “Partition By deptname” causes a result set of rows of data that are grouped by department name. The clause, “Order By salary DESC” causes the rows of data in each department group to be ordered in descending order of salary. The predicate in the outer query block, “rnk<=5”, filters all but the top 5 rows of data in each department group before presenting the result set in response to the query.

Ordinarily, filtering occurs after the data has been sorted. Before filtering of the data occurs, the data is first sorted during the window sort of the ranking function corresponding to the predicate. In contrast, techniques described herein filter the data much earlier by pushing the filtering operation down into a lower level of rank computation, which is sorting of the data. The technique of pushing the filtering operation down into a lower level of computation is hereafter referred to as “push-down”.

TABLE 3 represents a possible result set in response to the above sample query.

TABLE 3

deptname	Ename	Salary	Rnk

engineering	Adams	100K		1
engineering	Baker	99K	2
engineering	Edwards	74K	3
engineering	Fitzhugh	66K	4
engineering	Garibaldi	60K	5
marketing	Smith	85K		1
marketing	Goodman	80K	2
marketing	Peterman	79K	3
marketing	Botticelli	60K	4
marketing	Maxmillian	55K	5

For the purpose of explanation, assume that a query block has N window functions, F1, F2, . . . , Fn. Assume that F is one of the ranking functions in the query block, and that P, in the immediate outer query block, is the predicate associated with F. The predicate associated with a ranking function is hereafter referred to as a “filtering predicate”. FIG. 1A, FIG. 1B, and FIG. 1C are flowcharts that illustrates an overview of the steps involved in a query processing technique that implements one embodiment of the invention. Atblock102 in FIG. 1, it is determined whether there is at least one filtering predicate, in the immediate outer query block, that is associated with a ranking function that is in the current query block. If it is determined that there is at least one filtering predicate in the outer query block associated with a ranking function, then atblock106 of FIG. 1B, the first filtering predicate in the outer query block is chosen as a potential candidate for push-down, and the associated ranking function is designated as the corresponding target ranking function. The target ranking function is herein defined to be the ranking function for which the window sort computation involves a filtering predicate push-down. In one embodiment, if there are more than one filtering predicate in the outer query block and each filtering predicate is associated with a ranking function in the query block, then the filtering predicate that can filter out the most rows of data is chosen as the potential candidate for push-down. Otherwise, atblock104 of FIG. 1A, the process is at an end because no predicate qualifies for push-down.

Atblock108 of FIG. 1B, it is determined whether all the window functions in the query block are in the same ordering group. An ordering group is a set of window functions that have ordering requirements that can be satisfied by a single sort operation. The concept of Ordering Groups may be illustrated by the following example.

Assume that a query contains the following multiple window functions A1, A2, A3:

A1) SUM (sales) OVER (PARTITION BY region) sum_region,

A2) SUM (sales) OVER (PARTITION BY region, state) sum_region_state,

A3) RANK ( ) OVER (PARTITION BY region ORDER BY sales DESC) rank.

Each of the above window functions requires a sort operation. Window function A1 requires a sort on “region”. Window function A2 requires a sort on “region, state”. Window function A3 requires a sort on “region, sales DESC”. However, by simply sorting the data once on “region, state” only, both window functions A1 and A2 would be satisfied in one sorting opeation. Thus, window functions A1 and A2 may be grouped together as an Ordering Group because they can be satisfied by a single sort operation by sorting on “region, state”. The remaining Window function A3 would then be classified as another Ordering Group by default. However, if, for example, the above query contains an additional window function A4 that requires a sort on “sales DESC”, then window functions A3 and A4 may be grouped as an Ordering Group because they can be satisfied by a single sort operation by sorting on “region, sales DESC”.

If it is determined that all the window functions in the query block belong to the same ordering group, then atblock110 of FIG. 1B, it is determined whether the window functions satisfy the push-down conditions. The set of push-down conditions are herein described in greater detail with reference to FIG.2 through FIG.6. If, atblock110, it is determined that the window functions satisfy the push-down conditions, then the filtering predicate qualifies for push-down as indicated byblock114 of FIG.1B. Otherwise, atblock112 of FIG. 1B, it is determined whether there is another filtering predicate in the immediate outer query block that is associated with a ranking function in the query block. If it is determined that there is another filtering predicate in the immediate outer query block that is associated with a ranking function in the query block, then control returns to block106. Otherwise, control returns to block104 of FIG. 1A because no filtering predicate qualifies for push-down.

Atblock108, if it is determined that not all the window functions in the query block are in the same ordering group as that of the target ranking function, then atblock116 of FIG. 1C, it is determined whether there are any window functions in the query block that are in the same ordering group as that of the target ranking function. If it is determined that there are no other window functions in the query block that are in the same ordering group as that of the target ranking function, then the filtering predicate qualifies for push-down into the window sort of the target ranking function. However, the window sort of the target window is computed after computing the window sorts in the query block of all window functions that are in a different ordering group than that of the target ranking function as indicated byblock120.

Atblock116, if it is determined that there are some window functions in the query block that are in the same ordering group as that of the target ranking function, then atblock118 of FIG. 1C, it is determined whether those window functions that are in the same ordering group as that of the target ranking function satisfy the push-down conditions. If the window functions satisfy the push-down conditions, then control passes to block120 of FIG.1C. Otherwise, control passes to block112 of FIG.1B.

PUSH-DOWN CONDITIONS

A set of push-down conditions must be met before the push-down technique may be employed. The set of push-down conditions is explained with reference to FIG.2 through FIG.6. All the conditions in the set of push-down conditions need to be satisfied before a filtering predicate can be pushed down into the window sort operation of the target ranking function.

FIG. 2 is a flowchart that illustrates the condition to be satisfied by the filtering predicate associated with the target ranking function. At block202, it is determined whether the filtering predicate is of the form:

“P<relational operator><constant>”

where P can be Rank, Dense_Rank and Row_Number

If, at block202, it is determined that the filtering predicate is of the form “P<relational operator><constant>”, then at block204, it is determined whether the relational operator is from the set {<,<=, =}. If the relational operator is from the set {<,<=, =}, then the condition is satisfied by the filtering predicate, as indicated atblock206. If the relational operator is not from the set {<,<=, =}, then the condition is not satisfied by the filtering predicate, and the predicate may not be pushed down into the window sort computation of the target ranking function, as indicated atblock208.

If, at block202, it is determined that the filtering predicate is not of the form “P<relational operator><constant>”, then atblock210, it is determined whether the filtering predicate is of the form:

“<constant><relational operator>P”

where P is the rank

If, atblock210, it is determined that the filtering predicate is not of the form “<constant><relational operator>P”, then the condition is not satisfied and control passes to block208. Otherwise, if it is determined that the filtering predicate is of the form “<constant><relational operator>P”, then atblock212, it is determined whether the relational operator is from the set {>, >=, =}. If the relational operator is not from the set {>,>=, }, then the condition is not satisfied and control passes to block208. If the relational operator is from the set {>, >=, =}, then atblock214, the filtering predicate, P, is converted to the form “P<relational operator><constant>”. Control then passes to block204. For example, 10>P is converted to P<10 and 10>=P is converted to P<=10.

When the filtering predicate is of the form “P =<constant>”, the relational operator, “=” is converted to “<=” before the predicate is pushed down into the window sort operation. The filtering predicate is reset to “=” in the final filtering run.

The condition that the filtering predicate be of the form “P<relational operator><constant>” where the relational operator is from the set {<,<=} ensures that data is inadvertently filtered out in individual runs during a push-down window sort computation of the target ranking function because ranking functions return integer values in increasing order. The use of individual runs and the execution of push-down window sort computations are described herein in greater detail in the subsection entitled “SERIAL EXECUTION WITH PUSH-DOWN OPTIMIZATION”.

FIG. 3 is a flowchart that illustrates the condition that is to be satisfied by unordered window functions in the query block, and which unordered window functions are in the same ordering group as that of the target ranking function. Atblock302, all unordered window functions that are in the same ordering group as that of the target ranking function are identified in the query block. Atblock304, it is determined whether the granularity of the “Partition By” clause of each identified unordered window function is of equal or finer granularity than the granularity of the concatenation of the “Partition By” and “Order By” clauses of the target ranking function. If it is determined that the granularity of the “Partition By” clause of each identified unordered window function is of equal or finer granularity than the granularity of the concatenation of the “Partition By” and “Order By” clauses of the target ranking function, then the condition is satisfied as indicated byblock306. Otherwise, the condition is not satisfied, and the filtering predicate may not be pushed down into the window sort of target ranking function, as indicated byblock308.

For example, if the target ranking function and an unordered window function in the query block are respectively,

Sum(sal) Over (Partition By x, y)

The “Partition By” clause of the target ranking function is, P( )={x}

The “Order By” clause of the target ranking function is, O( )={y}

If the concatenation of the “Partition By” and “Order By” clauses of the target ranking function is denoted by G( ), then

G( )=P( )∥O( )

Thus, G( )={x, y}

The above sample unordered window function “Sum(sal) Over (Partition By x, y)” may be satisfied by a sort on x, y. Similarly, the target ranking function “Rank( ) Over (Partition By x Order By y” may be satisfied by a sort on x, y. Thus, the above sample target ranking function and unordered window function comprise an ordering group. The “Partition By” clause of the unordered window function “Sum(sal) Over (Partition By x, y)” is

P( ) of unordered window function={x, y}

Thus, P( ) of unordered window function=G( ) of the target ranking function. If, for example, the unordered window function is “Sum(sal) Over (Partition By x, y, z)”, it would still satisfy the condition as expressed atblock304 of FIG. 3 because.

P( ) of unordered window function={x, y, z}

Thus, P( ) of unordered window function is of finer granularity than G( ) of the target ranking function.

However, if the unordered window function is “Sum(sal) Over (Partition By x)”, it would not satisfy the condition as expressed atblock304 of FIG. 3 because

P( ) of unordered window function={x}, which is of coarser granularity than G( ) of the target ranking function.

FIG. 4 is a flowchart that illustrates the condition that is to be satisfied by all other ranking functions in the query block, and which ranking functions are in the same ordering group as that of the target ranking function. At block402, all ranking functions that are in the same ordering group as that of the target ranking function are identified in the query block. Atblock404, it is determined whether the granularity of the “Partition By” clause of each identified ranking function is of equal or finer granularity than the granularity of the “Partition By” clause of the target ranking function. If it is determined that the granularity of the “Partition By” clause of each identified ranking function is not of equal or finer granularity than the granularity of the “Partition By” clause of the target ranking function, then the condition is not satisfied, and the filtering predicate may not be pushed down into the window sort computation of the target ranking function, as indicated atblock410.

If, atblock404, it is determined that the granularity of the “Partition By” clause of each identified ranking function is of equal or finer granularity than the granularity of the “Partition By” clause of the target ranking function, then atblock406, it is determined whether, for each identified ranking function whose “Partition By” clause has a granularity equal to the granularity of the “Partition By” clause of the target ranking function, the granularity of the “Order By” clause is of equal or finer granularity than the granularity of the “Order By” clause of the target ranking function. If it is determined that the granularity of the “Order By” clause is of equal or finer granularity than the granularity of the “Order By” clause of the target ranking function, then the condition is satisfied, as indicated atblock408. Otherwise, control passes to block410.

For example, if the target ranking function and other ranking functions in the query block are respectively,

F: Rank( ) Over (Partition By x Order By y)

F1: Rank( ) Over (Partition By x, y Order By z)

F2: Rank( ) Over (Partition By x Order By y, z)

The “Partition By” clause of the ranking function is P( ) of F={x}

The “Order By” clause of the ranking function is O( ) of F={y}

In the above example, ranking functions, F1 and F2, may be satisfied by a sort operation on x, y, z. The same sort operation on x, y, z may be used to satisfy the target ranking function, F=Rank( ) Over (Partition By x Order By y). Thus, F, F1, F2 comprise an ordering group.

The “Partition By” clause of F1 is P( ) of F1 {x, y}. Thus, F1 satisfies the condition ofblock404 in FIG. 4 because the granularity of P( ) of F1 is of finer granularity than the granularity of P( ) of F. Similarly, the “Partition By” clause of F2 is P( ) of F2={x}. Thus, F2 satisfies the condition as indicated byblock404 because the granularity of P( ) of F2 is of equal granularity as the granularity of P( ) of F. Further, F2 satisfies the condition ofblock406 because the “Order By” clause of F2 is O( ) of F2={y, z}. Thus, the granularity of O( ) of F2 is finer than the granularity of O( ) of F.

However, assume there exists in the query block another ranking function such as,

F3: Rank( ) Over (Order By x)

The “Partition By” clause of F3 is the null set. Thus, F3 would not satisfy the condition as expressed atblock404 because.

P( ) of F3={ }, which is of coarser granularity than P( ) of F={x}, where F is the target ranking function.

FIG. 5 is a flowchart that illustrates the condition that is to be satisfied by all ordered window functions with ROWS option in the query block, and which window functions are in the same ordering group as that of the target ranking function. At block502, all window functions with ROWS option that are in the same ordering group as that of the target ranking function are identified in the query block. Atblock504, it is determined whether the granularity of the “Partition By” clause of each identified ordered window function with ROWS option is of equal or finer granularity than the granularity of the “Partition By” clause of the target ranking function. If it is determined that the granularity of the “Partition By” clause of each identified ordered window function is not of equal or finer granularity than the granularity of the “Partition By” clause of the target ranking function, then the condition is not satisfied, and the filtering predicate may not be pushed down into the window sort computation of the target ranking function, as indicated atblock506. Otherwise, if the granularity of the “Partition By” clause of each identified ordered window function is of equal or finer granularity than the granularity of the “Partition By” clause of the target ranking function, then atblock508 it is determined if the window size of each identified ordered window function only extends to N rows preceding the current row on which the ordered window function is operating, and where N is any positive integer number. If it is determined that the window size of each identified ordered window function only extends to N rows preceding the current row on which the ordered window function is operating, then the condition is satisfied, as indicated atblock510. Otherwise, control passes to block506.

For example, if the target ranking function and the ordered window functions with ROWS option in the query block are respectively,

F: Rank( ) Over (Order By x)

F1: Sum(sal) Over (Order By xROWS 1 preceding)

F2: Sum(sal) Over (Partition By x OrderBy y ROWS 1 preceding)

The “Partition By” clause of the ranking function is P( ) of F={ }

The “Order By” clause of the ranking function is O( ) of F={y}

In the above example, ordered window functions with ROWS option, F1 and F2, may be satisfied by a sort operation on x, y. The same sort operation on x, y may be used to satisfy the target ranking function, F=Rank( ) Over (Order By x). Thus, F, F1, F2 comprise an ordering group.

The “Partition By” clause of F1 is P( ) of F1={ }. Thus, F1 satisfies the condition ofblock504 in FIG. 5 because the granularity of P( ) of F1 is equal to the granularity of P( ) of F. Similarly, the “Partition By” clause of F2 is P( ) of F2={x}. Thus, F2 satisfies the condition as indicated byblock504 because the granularity of P( ) of F2 is finer than the granularity of P( ) of F.

Recall that the filtering predicate of the target ranking function is from the set {<,<=}. Thus, only ordered window functions with “ROWS PRECEDING” the current row of operation will operate on a correct set of data because the pushed down filtering predicate of the target ranking function will have ordered and filtered out rows of data “FOLLOWING” the current row of operation. In the example, F1, F2, each have a window size that extends to N ROWS preceding. In the example, N=1. The window size extends to one row preceding the current row of operation and thus satisfies the condition as expressed atblock508 of FIG.5. However, assume there exists in the query block another ordered window function with ROWS option such as,

FF: Sum(sal) Over (Order By x ROWS 20 following)

The window size of FF extends to 20 rows following the current row of operation. Thus, FF would not satisfy the condition as expressed atblock508.

In another embodiment of the invention, the condition of N ROWS preceding may be relaxed as illustrated by the following example. Assume that F is the target ranking function and F1 . . . F6 are window functions that are ordered with ROWS option.

F: P(X,Y,Z)O(A,B,C)

F1: P(X,Y,Z)O(A,B,C)

F2: P(X,Y,Z)O(A,B,C,D)

F3: P(X,Y,Z)O(A,B)

F4: P(X,Y,Z,A)O(B)

F5: P(X,Y,Z.A)O(B,C)

F6: P(X,Y,Z,A)O(B,C,D)

The window size corresponding to each of the above functions is described in TABLE WS below.

TABLE WS

Window Function	Window can extend up to (or window size)

F1	Current row
F2	Any row preceding or following the current
	row, i.e., any window size
F3	At least one row preceding current row
F4	Any row preceding or following the current
	row, i.e., any window size
F5	Any row preceding or following the current
	row, i.e., any window size
F6	Any row preceding or following the current
	row, i.e., any window size

For F1, the window size may extend up to N rows preceding the current row or to the current row itself. For F2, the window size may extend to rows preceding or following the current row, i.e., there are no restrictions to the window size. For F3, the window size may extend to at least one row preceding the current row. For F4, F5, F6, the window size may extend to rows preceding or following the current row, i.e., there are no restrictions to the window size.

FIG. 6 is a flowchart that illustrates the condition that is to be satisfied by all ordered window functions with RANGE option in the query block, and which window functions are in the same ordering group as that of the target ranking function. Atblock602, all window functions with RANGE option that are in the same ordering group as that of the target ranking function are identified in the query block. Atblock604, it is determined whether the granularity of the “Partition By” clause of each identified ordered window function with RANGE option is of equal or finer granularity than the granularity of the concatenation of the “Partition By” and “Order By” clauses of the target ranking function. If it is determined that the granularity of the “Partition By” clause of each identified ordered window function is not of equal or finer granularity than the granularity of the concatenation of the “Partition By” and “Order By” clauses of the target ranking function, then the condition is not satisfied, and the filtering predicate may not be pushed down into the window sort computation of the target ranking function, as indicated at block606. Otherwise, if the granularity of the “Partition By” clause of each identified ordered window function is of equal or finer granularity than the granularity of the concatenation of the “Partition By” and “Order By” clauses of the target ranking function, then atblock608 it is determined if the window size of each identified ordered window function only extends to N rows preceding the current row on which the ordered window function is operating, and where N is any positive integer number. If it is determined that the window size of each identified ordered window function only extends to N rows preceding the current row on which the ordered window function is operating, then the condition is satisfied, as indicated atblock610. Otherwise, control passes to block606. However, in another embodiment of the invention, the N rows preceding condition may be relaxed as explained herein with respect to the ROWS option above.

If the target ranking function and the ordered window functions with RANGE option in the query block are respectively,

F: Rank( ) Over (Order By x, y)

F1: Sum(sal) Over (Partition By x, y Order By aRANGE 1 preceding)

The “Partition By” clause of the ranking function is P( ) of F={ }

The “Order By” clause of the ranking function is O( ) of F={x, y}

G( )=P( )∥O( )

Thus, G( )={x, y}

In the above example, ordered window function with RANGE option, F1, may be satisfied by a sort operation on x, y, a. The same sort operation on x, y, a may be used to satisfy the target ranking function, F=Rank( ) Over (Order By x, y). Thus, F, F1 comprise an ordering group.

The “Partition By” clause of F1 is P( ) of F1={x, y}. The granularity of P( ) of F1 is equal to the granularity of G( ) of F. Thus, F1 satisfies the condition as indicated byblock604.

In the example, F1 has a window size that extends to RANGE N preceding. In the example, N=1. The window size extends to one row preceding the current row of operation and thus satisfies the condition as expressed atblock608 of FIG.6. However, assume there exists in the query block another ordered window function with RANGE option such as,

F2: Sum(sal) Over (Order By x, RANGE between current row and 20 following)

The window size of F2 extends to a RANGE of 20 following the current row of operation. Thus, F2 would not satisfy the condition as expressed atblock608. For example:

F1: Rank( ) Over( Order By x)

F2: Sum(sal) Over (Order By x, RANGE between current row and 20 following)

Let P<=3

Assume that the data values for x, sal, Rank( ) Over( Order By x) and Sum(sal) Over (Order By x, RANGE between current row and 20 following) are as indicated in Table EMPDATA below.

EMPDATA

	X	Sal	Rank() Over	Sum(sal) Over

1	10	1	40
2	20	2	50
3	10	3	60
4	20	4	90
5	30	5	120
6	40	6	100
7	50	7	60
8	10	8	10

Assume x=3 is the current row of operation. For the current row x=3, the window extends from x=3 to x=5. Thus, if the filtering predicate P<=3 is applied during the sort operation then the rows where x>3 will be filtered out, and F1 for the current row will be incorrectly computed as 10 instead of 60.

SERIAL EXECUTION WITH PUSH-DOWN OPTIMIZATION

For the purpose of illustrating the push-down technique during a serial execution of a query block, a comparison is made between the serial execution of a window sort operation without a filtering predicate push-down and the serial execution window sort operation with a filtering predicate push-down. The following query block and data set are used as examples in the illustration of the push-down technique. Assume that the target ranking function in the query block and the corresponding filtering predicate in the outer query block are respectively:

Rank( ) over (Order By x) RK

SELECT

From (Select Rank( ) Over (Order By x) Rk, F1, . . . Fn)

Where Rk<=3

Further assume that the window functions F1, . . . FN in the query block are in the same ordering group as the target ranking function and that they satisfy all the push-down conditions as described herein. Assume that the data set upon which the window sort operates is,

column x={5,1,2,3,4,6,1,2,3,5,5,5,7,4,6}

During serial execution of a window sort operation without a filtering predicate push-down, data items from the data set upon which the sort operation is performed are read into memory for performing the sort operation until the memory is exhausted. When the memory is exhausted, the sorted data items in memory is written to disk in order to reuse the memory for reading in more data items from the data set and performing the sort operation. Thus, at any given time, only one subset of the data set is read into memory for performing the sort operation. Each subset of sorted data items that is written to disk is herein referred to as a “sort run”. Thus, the number of sort runs depends on the size of the data set and the amount of memory available for the sort operation. Each data item within each sort run is sorted with respect to the other data items in the sort run, according to the sort criterion specified by the target ranking function. However, the data items in each sort run may not be sorted with respect to data items in other sort runs. The sort operation is not complete until the data items in each sort run are sorted with respect to data items in other sort runs. Thus, the sort runs are merged in order to complete the sort operation. Depending on the size of the data set and the amount of memory available to the sort operation, several levels of merging sort runs may be required to complete the sort operation. Each level of merging sort runs is herein referred to as a “merge pass”. The sort run resulting from the final merge pass is herein referred to as a “final sort run”.

Using the above example query block and data set, sort runs may appear as follows. For purposes of simplicity, assume the memory is exhausted after reading and sorting a subset of the data set comprising 5 data items at a time and that only one merge pass is required to complete the sort operation.

SortRun1={1,2,3,4,5} corresponding to reading and sorting the subset {5,1,2,3,4}

Sort Run2={1,2,3,5,6} corresponding to reading and sorting the subset {6,1,2,3,5}

Sort Run3={4,5,5,6,7} corresponding to reading and sorting the subset {5,5,7,4,6}

The final sort run after the merge pass={1,1,2,2,3,3,4,4,5,5,5,5,5,6,6,7}

Thus, the serial execution of a window sort operation of the target ranking function, “Rank( ) over (Order By x) RK”, without a filtering predicate push-down produces the result set {1,1,2,2,3,3,4,4,5,5,5,5,5,6,6,7}. The filtering predicate RK<=3 is applied only to the final sort run when there is no push-down. In order to apply the filtering predicate to the final sort run, the data items in the final sort run are ranked. Once the data items are ranked, only the data items satisfying the filtering conditions are retained. For example,


Final Sort Run before applying	1,1,2,2,3,3,4,4,5,5,5,5,5,6, 6, 7
filtering predicate:
Rank:	1,1,3,3,5,5,7,7,9,9,9,9,9,14,14,16
Then,
Final Sort Run after applyingfiltering	1, 1, 2, 2
predicate RK <= 3 is:

In contrast, the sort runs resulting from the serial execution of a window sort operation with a filtering predicate push-down contain data items that are ordered, ranked and filtered with respect to every other data item within the sort run.

As before, for purposes of simplicity, assume the memory is exhausted after reading and sorting a subset of the data set comprising 5 data items at a time and that only one merge pass is required to complete the sort operation. The filtering predicate RK<=3 is pushed down into the individual sort runs. Thus, each sort run contains data items that are ordered with respect to every other data item within the sort run, and each sort run contains only data items that have a rank of less than or equal to 3. In order to apply the filtering predicate to a sort run, the sorted data in the sort run is ranked. Once the data is ranked, only the data items above the rank specified by the filtering predicate (top-N ranks) is retained before the sort run is written to disk. The filtering predicate is pushed down into sort runs at every merger pass including the final sort run.

Thus, the sort runs resulting from the serial execution of a window sort operation with a filtering predicate push-down using the above example query block and data set may appear as follows:


Sort Run 1 before applying filtering predicate:	1,2,3,4,5
Rank:	1,2,3,4,5
Sort Run 1 after applying filtering predicate:	1,2,3
Sort Run 2 after applying filtering predicate:	1,2,3,5,6
Rank:	1,2,3,4,5
Sort Run 2 after applying filtering predicate:	1,2,3
Sort Run 3 after applying filtering predicate:	4,5,5,6,7
Rank:	1,2,2,4,5
Sort Run 3 after applying filtering predicate:	4,5,5
The final sort run before applying filtering predicate:	1,1,2,2,3,3,4,5,5
Rank:	1,1,3,3,5,5,7,8,8
The final sort run after applying filtering predicate:	1,1,2,2

As can be seen from the above example, less data needs to be processed at each merge pass because the filtering predicate that has been pushed down to the sort filters out rows that have ranks greater than the rank specified by the filtering predicate. The cost savings thus realized by pushing filtering predicates down into the window sort computation may be substantial in typical scenarios where window functions operate on massive datasets.

PARALLEL EXECUTION WITH PUSH-DOWN OPTIMIZATION

Push-down optimization may implemented when queries are executed in parallel. For the purpose of explanation, push-down optimization is described using the following TOP-N query:

SELECT x, y, RK

FROM (SELECT x, y

RANK (Partition By x Order By y DESC) as RK

FROM EmpTable)

Where RK<=3

The query is decomposed into its constituent parts, called row sources. Each row source corresponds to an operation that produces rows. Row sources may be connected to form a tree-like structure, which describes the execution plan of the above query.

FIG. 7 illustrates therow source tree 700 associated with the parallel execution of the above TOP-N query. For parallel execution of queries, row source tree is decomposed into a data-flow operator (DFO) tree. A DFO is a logical piece of query execution assigned to slave processes. A DFO can contain one or more row sources. Data transmission across DFOs (i.e., across slave processes) is done through Table Queues (TQ). TQs manage data flow for load distribution amongst slave processes. In FIG. 7, row sources grouped in ovals, representDFOs702,706, which are associated with the parallel execution of the given Top-N query. In one embodiment, the pushdown optimization is implemented by pushing the filtering predicate into the window sort of the rank computation.DFO702 scans rows of data (data items) from Emp table. Assuming the degree of parallelism to be 2,DFO702 is assigned to slave processes S1 and S2, which perform the table scan while DFO706 is assigned to slave processes S3 and S4, which perform the window sort computation. Assume that the data set upon which the above mentioned ranking function operates is shown below:

EmpTable

X

Y



	1	1
	2	2
	3	3
	1	4
	2	5
	3	6
	1	1
	2	2
	3	3
	3	4
	2	5
	1	6
	3	7
	2	8
	1	9

Slaves S1 and S2 each read subset of data items from the Emp Table and transmit them to slaves S3 and S4 via the table queue,TQ704.TQ704 partitions the data such that work load is evenly distributed across slaves S3 and S4. Assume that TQ affects hash partitioning on x and that x={1,3 } are assigned to slave process S3 while x={2} is assigned to slave process S4. Slave processes S3 and S4 perform the window sort operation on their respective partitions of data by pushing the filtering predicate on RANK into sort. The sorted and ranked data items associated with S3 and S4 may appear as follows:


	S3	S4

X	Y	rank	x	y	rank

1	1	1	2	2	1
1	1	1	2	2	1
1	4	3	2	5	3
1	6	4	2	5	3
1	9	5	2	8	5
3	3	1
3	3	1
3	4	3
3	6	4
3	7	5

After the data items in each partition are ranked, the filtering predicate RK<=3 is applied to the sorted data items to filter out data items with rank that is greater than 3. The filtered subsets of data items associated S3 and S4 may appear as follows:


	S3	S4

x	Y	rank	x	y	rank

1	1	1	2	2	1
1	1	1	2	2	1
1	4	3	2	5	3
3	3	1	2	5	3
3	3	1
3	4	3

Thus, the result set corresponding to the above Top-N query is obtained by combining the result sets from slaves S3 and S4, and may appear as follows:


x	y	Rank

1	1	1
1	1	1
1	4	3
2	2	1
2	2	1
2	5	3
2	5	3
3	3	1
3	3	1
3	4	3

Note that in the above scheme, the entire data set needs to be transmitted through the table queue,TQ704. In another embodiment, this communication cost between slaves {S1, S2 } and {S3, S4} is reduced drastically by pushing window sort computation to slaves S1 and S2. Slaves S1 and S2 not only scan their respective data set, but also rank them and filter unnecessary (rows not satisfying filtering predicate) rows. In this way, less data needs to be transmitted through the table queue thus reducing the time taken to evaluate the query.

To illustrate, the push-down optimization is described using the following TOP-N query and data set of EmpTable:

SELECT x, y, RK

FROM(SELECT x, y

RANK (Partition By x Order By y DESC) as RK



	1	1
	2	2
	3	3
	1	4
	2	5
	3	6
	1	1
	2	2
	3	3
	3	4
	2	5
	1	6
	3	7
	2	8
	1	9

FIG. 8 illustrates the row source and DFO tree associated with the parallel execution of the above Top-N query. FIG. 8 comprisesDFO802, DFO806 andTable Queue TQ804. Unlike the DFO tree of FIG. 7,DFO802 contains a window sort row source with filtering predicate pushed in. This row source is referred to as window child to differentiate it from the window sort row source of DFO806. Assuming the degree of parallelism to be 2, slaves S1 and S2 are assigned toDFO802 while slaves S3 and S4 are assigned to DFO806. The slave processes S1 and S2 perform table scan on Emp Table. In addition, they perform window child sort operation with the pushed down filtering predicate associated with “RANK (Partition By x Order By y DESC)”. Assume that S1 is assigned to work on the first 8 data items of EmpTable, and that S2 is assigned the remaining data items of EmpTable. Thus, the sorted and ranked data items associated with S1, and S2 may appear as:


	S1	S2

x	y	rank	x	y	Rank

1	1	1	1	6	1
1	1	1	1	9	2
1	4	3	2	5	1
2	2	1	2	8	2
2	2	1	3	3	1
2	5	3	3	4	2
3	3	1	3	7	3
3	6	2

By applying the filtering predicate RK<=2, which is associated with “RANK (Partition By x Order By y DESC)”, only data item with rank greater than 2 are transferred up the DFO tree to the window sort with push-down rank DFO806. Thus, the subsets of filtered data items associated with S1 and S2 that are to be transferred to DFO806 may appear as follows:


	S1	S2

x	y	rank	x	y	Rank

1	1	1	1	6	1
1	1	1	1	9	2
2	2	1	2	5	1
2	2	1	2	8	2
3	3	1	3	3	1
3	6	2	3	4	2

Before the sorted and filtered data is transferred to the window sort with push-down rank DFO806,Table Queue804 partitions the respective subset of data items of S1 and S2 in order to distribute the workload among slave processes S3, S4 at the window sort with push-down rank DFO 806. Assume that a hash partitioning is performed on x. Assume that x={1,3} is assigned to slave process S3 and that x={2} is assigned to slave process S4. In the push-down optimization, slave processes S3 and S4 perform the window sort operation on their respective partitions of data by pushing the filtering predicate into “RANK (Partition By x Order By y DESC)”. The sorted and ranked data items associated with S3 and S4 may appear as follows:


	S3	S4

x	y	rank	x	y	Rank

1	1	1	2	2	1
1	1	1	2	2	1
1	6	3	2	5	3
1	9	4	2	8	4
3	3	1
3	3	1
3	4	3
3	6	4

After the data items in each partition are ranked, the filtering predicate RK<=2 is applied to the sorted data to filter out rows of data with rank that is greater than 2. The filtered data of S3 and S4 appear as:


	S3	S4

x	y	rank	x	y	Rank

1	1	1	2	2	1
1	1	1	2	2	1
3	3	1
3	3	1

Thus, the result set corresponding to the above example TOP-N query is obtained by merging the filtered subsets of data items of S3 and S4 as follows:


x	y	Rank

1	1	1
2	2	1
2	2	1
3	3	1
3	3

HARDWARE OVERVIEW

FIG. 9 is a block diagram that illustrates acomputer system900 upon which an embodiment of the invention may be implemented.Computer system900 includes abus902 or other communication mechanism for communicating information, and aprocessor904 coupled withbus902 for processing information.Computer system900 also includes amain memory906, such as a random access memory (RAM) or other dynamic storage device, coupled tobus902 for storing information and instructions to be executed byprocessor904.Main memory906 also may be used for storing temporary variables or other intermediate information during execution of instructions to be executed byprocessor904.Computer system900 further includes a read only memory (ROM)908 or other static storage device coupled tobus902 for storing static information and instructions forprocessor904. Astorage device910, such as a magnetic disk or optical disk, is provided and coupled tobus902 for storing information and instructions.

Computer system

900 may be coupled viabus902 to adisplay912, such as a cathode ray tube (CRT), for displaying information to a computer user. Aninput device914, including alphanumeric and other keys, is coupled tobus902 for communicating information and command selections toprocessor904. Another type of user input device iscursor control916, such as a mouse, a trackball, or cursor direction keys for communicating direction information and command selections toprocessor904 and for controlling cursor movement ondisplay912. This input device typically has two degrees of freedom in two axes, a first axis (e.g., x) and a second axis (e.g., y), that allows the device to specify positions in a plane.

The invention is related to the use ofcomputer system900 for implementing the techniques described herein. According to one embodiment of the invention, those techniques are implemented bycomputer system900 in response toprocessor904 executing one or more sequences of one or more instructions contained inmain memory906. Such instructions may be read intomain memory906 from another computer-readable medium, such asstorage device910. Execution of the sequences of instructions contained inmain memory906 causesprocessor904 to perform the process steps described herein. In alternative embodiments, hard-wired circuitry may be used in place of or in combination with software instructions to implement the invention. Thus, embodiments of the invention are not limited to any specific combination of hardware circuitry and software.

The term “computer-readable medium” as used herein refers to any medium that participates in providing instructions toprocessor904 for execution. Such a medium may take many forms, including but not limited to, non-volatile media, volatile media, and transmission media. Non-volatile media includes, for example, optical or magnetic disks, such asstorage device910. Volatile media includes dynamic memory, such asmain memory906. Transmission media includes coaxial cables, copper wire and fiber optics, including the wires that comprisebus902. Transmission media can also take the form of acoustic or light waves, such as those generated during radio-wave and infra-red data communications.

Common forms of computer-readable media include, for example, a floppy disk, a flexible disk, hard disk, magnetic tape, or any other magnetic medium, a CD-ROM, any other optical medium, punchcards, papertape, any other physical medium with patterns of holes, a RAM, a PROM, and EPROM, a FLASH-EPROM, any other memory chip or cartridge, a carrier wave as described hereinafter, or any other medium from which a computer can read.

Various forms of computer readable media may be involved in carrying one or more sequences of one or more instructions toprocessor904 for execution. For example, the instructions may initially be carried on a magnetic disk of a remote computer. The remote computer can load the instructions into its dynamic memory and send the instructions over a telephone line using a modem. A modem local tocomputer system900 can receive the data on the telephone line and use an infra-red transmitter to convert the data to an infra-red signal. An infra-red detector can receive the data carried in the infra-red signal and appropriate circuitry can place the data onbus902.Bus902 carries the data tomain memory906, from whichprocessor904 retrieves and executes the instructions. The instructions received bymain memory906 may optionally be stored onstorage device910 either before or after execution byprocessor904.

Computer system

900 also includes acommunication interface918 coupled tobus902.Communication interface918 provides a two-way data communication coupling to anetwork link920 that is connected to alocal network922. For example,communication interface918 may be an integrated services digital network (ISDN) card or a modem to provide a data communication connection to a corresponding type of telephone line. As another example,communication interface918 may be a local area network (LAN) card to provide a data communication connection to a compatible LAN. Wireless links may also be implemented. In any such implementation,communication interface918 sends and receives electrical, electromagnetic or optical signals that carry digital data streams representing various types of information.

Network link920 typically provides data communication through one or more networks to other data devices. For example,network link920 may provide a connection throughlocal network922 to ahost computer924 or to data equipment operated by an Internet Service Provider (ISP)926.ISP926 in turn provides data communication services through the world wide packet data communication network now commonly referred to as the “Internet”928.Local network922 andInternet928 both use electrical, electromagnetic or optical signals that carry digital data streams. The signals through the various networks and the signals onnetwork link920 and throughcommunication interface918, which carry the digital data to and fromcomputer system900, are exemplary forms of carrier waves transporting the information.

Computer system

900 can send messages and receive data, including program code, through the network(s),network link920 andcommunication interface918. In the Internet example, aserver930 might transmit a requested code for an application program throughInternet928,ISP926,local network922 andcommunication interface918. In accordance with the invention, one such downloaded application implements the techniques described herein.

The received code may be executed byprocessor904 as it is received, and/or stored instorage device910, or other non-volatile storage for later execution. In this manner,computer system900 may obtain application code in the form of a carrier wave.

SCOPE

In the foregoing specification, the invention has been described with reference to specific embodiments thereof. It will, however, be evident that various modifications and changes may be made thereto without departing from the broader spirit and scope of the invention. The specification and drawings are, accordingly, to be regarded in an illustrative rather than a restrictive sense.