Method and apparatus for optimizing computation of OLAP ranking functions

Claim 3

The method of claim 1 , further comprising the step of selecting the target ranking function from a plurality of ranking functions in the set of one or more window functions.

Claim 4

The method of claim 2 , wherein the step of selecting the target ranking function comprises the steps of: determining that there is at least one predicate appearing in an outer query block associated with a ranking function in the set of window functions; selecting as the filtering predicate a first-to-appear predicate appearing in the outer query block; and selecting as the target ranking function the ranking function corresponding to the filtering predicate.

Claim 5

The method of claim 2 , wherein the step of selecting the target ranking function comprises the steps of: determining that there is at least one predicate appearing in an outer query block associated with a ranking function in the set of window functions; selecting as the filtering predicate a most restrictive predicate appearing in the outer query block, wherein the most restrictive predicate filters out the most amount of data items in response to a window sort operation corresponding to the target ranking function; and selecting as the target ranking function the ranking function corresponding to the filtering predicate.

Claim 6

The method of claim 1 , further comprising the steps of: determining whether all the window functions in the set of one or more window functions belong to a same ordering group; determining whether the set of one or more window functions satisfy a predetermined set of push-down criteria when all the window functions in the set of one or more window functions belong to the same ordering group; and computing a window sort operation corresponding to the target ranking function after computing all other window functions in the set of one or more window functions when not all the window functions in the set of one or more window functions belong to the same ordering group.

Claim 7

The method of claim 5 , further comprising the steps of: determining whether any subset of one or more window functions in the set of one or more window functions belong to the same ordering group as that of the target ranking function when not all the window functions in the set of one or more window functions belong to the same ordering group; and determining whether the subset of one or more window functions satisfy the predetermined set of push-down criteria when there is a subset of one or more window functions in the set of one or more window functions that belong to the same ordering group as that of the target ranking function.

Claim 8

The method of claim 6 , wherein the predetermined set of push-down criteria comprises: the filtering predicate is of a form “P<relational operator><constant>”, wherein the relational operator is from the set {<,<=,=}, and wherein P is rank; a granularity of a Partition By clause of each unordered window function in the set of one or more window functions, and which is the same ordering group as the target ranking function is at least of equal granularity as a granularity of a concatenation of a Partition By clause and an Order By clause of the target ranking function; a granularity of a Partition By clause of each ranking function in the set of one or more window functions, and which is in the same ordering group as the target ranking function is at least of equal granularity as the granularity of the Partition By clause of the target ranking function, and for each ranking function Partition By clause of equal granularity as the granularity of the Partition By clause of the target ranking function, a granularity of an Order By clause of the ranking function is at least of equal granularity as the granularity of the Order By clause of the target ranking function; a granularity of a Partition By clause of each ordered window function with ROWS option in the set of one or more window functions, and which is in the same ordering group as the target ranking function is at least of equal granularity as the granularity of the Partition By clause of the target ranking function; and a granularity of a Partition By clause of each ordered window function with RANGE option in the set of one or more window functions, and which is in the same ordering group as the target ranking function is at least of equal granularity as the granularity of the concatenation of the Partition By clause and the Order By clause of the target ranking function.

Claim 9

The method of claim 7 , wherein the ROWS option includes N rows preceding a current row of operation.

Claim 10

The method of claim 7 , wherein the RANGE option includes N rows preceding a current row of operation.

Claim 11

The method of claim 1 , wherein the step of ranking data items within the subset includes: assigning the subset to a parallel process of a plurality of parallel processes; and causing the parallel process to rank the data items within the assigned subset.

Claim 12

The method of claim 1 , wherein the step of filtering data items is performed by the parallel process on data items within the assigned subset.

Claim 13

The method of claim 1 , wherein the steps of ranking and filtering the data items are performed by a single process and include: reading, sorting, ranking, and filtering data items that are within the subset; and storing data items that are within the subset after filtering, is performed.

Claim 14

The method of claim 7 , further comprising the steps of: converting the filtering predicate to the form “P<=<constant>” before computing the window sort operation corresponding to the target ranking function when the relational operator is {=}; and converting the filtering predicate back to the form “P=<constant>” in a final step in the window sort operation.

Claim 15

A computer-readable medium bearing instructions for execution of a query containing a set of one or more window functions, the computer-readable medium comprising instructions for performing the steps: for each subset of a plurality of subsets of data items: ranking, based on a target ranking functions, data items within the subset relative to other data items within the subset; and filtering, based on a filtering predicate that is associated with the target ranking function, data items from the subset; wherein the target ranking function is in the set of one or more window functions.

Claim 16

A computer-readable medium bearing instructions for execution of a query containing a set of one or more window functions, the computer-readable medium comprising instructions for performing the steps: for each subset of a plurality of subsets of data items: ranking, based on a target ranking functions, data items within the subset relative to other data items within the subset; and filtering, based on a filtering predicate that is associated with the target ranking function, data items from the subset; wherein the target ranking function is in the set of one or more window functions.

Claim 17

The computer-readable medium of claim 14 , further comprising the step of selecting the target ranking function from a plurality of ranking functions in the set of one or more window functions.

Claim 18

The computer-readable medium of claim 15 , wherein the step of selecting the target ranking function comprises the steps of: determining that there is at least one predicate appearing in an outer query block associated with a ranking function in the set of window functions; selecting as the filtering predicate a first-to-appear predicate appearing in the outer query block; and selecting as the target ranking function the ranking function corresponding to the filtering predicate.

Claim 19

The computer-readable medium of claim 15 , wherein the step of selecting the target ranking function comprises the steps of: determining that there is at least one predicate appearing in an outer query block associated with a ranking function in the set of window functions; selecting as the filtering predicate a most restrictive predicate appearing in the outer query block, wherein the most restrictive predicate filters out the most amount of data items in response to a window sort operation corresponding to the target ranking function; and selecting as the target ranking function the ranking function corresponding to the filtering predicate.

Claim 20

The computer-readable medium of claim 14 , further comprising the steps of: determining whether all the window functions in the set of one or more window functions belong to a same ordering group; determining whether the set of one or more window functions satisfy a predetermined set of push-down criteria when all the window functions in the set of one or more window functions belong to the same ordering group; and computing a window sort operation corresponding to the target ranking function after computing all other window functions in the set of one or more window functions when not all the window functions in the set of one or more window functions belong to the same ordering group.

Claim 21

The computer-readable medium of claim 18 , further comprising the steps of: determining whether any subset of one or more window functions in the set of one or more window functions belong to the same ordering group as that of the target ranking function when not all the window functions in the set of one or more window functions belong to the same ordering group; and determining whether the subset of one or more window functions satisfy the predetermined set of push-down criteria when there is a subset of one or more window functions in the set of one or more window functions that belong to the same ordering group as that of the target ranking function.

Claim 22

The computer-readable medium of claim 19 , wherein the predetermined set of push-down criteria comprises: the filtering predicate is of a form “P<relational operator><constant>”, wherein the relational operator is from the set {<,<=,=}, and wherein P is rank; a granularity of a Partition By clause of each unordered window function in the set of one or more window functions, and which is the same ordering group as the target ranking function is at least of equal granularity as a granularity of a concatenation of a Partition By clause and an Order By clause of the target ranking function; a granularity of a Partition By clause of each ranking function in the set of one or more window functions, and which is in the same ordering group as the target ranking function is at least of equal granularity as the granularity of the Partition By clause of the target ranking function, and for each ranking function Partition By clause of equal granularity as the granularity of the Partition By clause of the target ranking function, a granularity of an Order By clause of the ranking function is at least of equal granularity as the granularity of the Order By clause of the target ranking function; a granularity of a Partition By clause of each ordered window function with ROWS option in the set of one or more window functions, and which is in the same ordering group as the target ranking function is at least of equal granularity as the granularity of the Partition By clause of the target ranking function; and a granularity of a Partition By clause of each ordered window function with RANGE option in the set of one or more window functions, and which is in the same ordering group as the target ranking function is at least of equal granularity as the granularity of the concatenation of the Partition By clause and the Order By clause of the target ranking function.

Claim 23

The computer-readable medium of claim 20 , wherein the ROWS option includes N rows preceding a current row of operation.

Claim 24

The computer-readable medium of claim 20 , wherein the RANGE option includes N rows preceding a current row of operation.

Claim 25

The computer-readable medium of claim 14 , wherein the step of ranking data items within the subset includes: assigning the subset to a parallel process of a plurality of parallel processes; and causing the parallel process to rank the data items within the assigned subset.

Claim 26

The computer-readable medium of claim 14 , wherein the step of filtering data items is performed by the parallel process on data items within the assigned subset.

Claim 27

The computer-readable medium of claim 14 , wherein the steps of ranking and filtering the data items are performed by a single process and include: reading, sorting, ranking and filtering data items that are within the subset; storing data items that are within the subset after filtering is performed.

Claim 28

The computer-readable medium of claim 20 , further comprising the steps of: converting the filtering predicate to the form “P<=<constant>” before computing the window sort operation corresponding to the target ranking function when the relational operator is {=}; and converting the filtering predicate back to the form “P=<constant>” in a final step in the window sort operation.