Method and apparatus for optimizing computation of OLAP ranking functions

• US 6,622,138 B1
• Filed: 09/06/2000
• Issued: 09/16/2003
• Est. Priority Date: 09/06/2000
• Status: Active Grant

• Current Assignee: Oracle International Corporation (Oracle Corporation)
• Original Assignee: Oracle International Corporation (Oracle Corporation)
• Inventors: Ghosh, Bhaskar, Bellamkonda, Srikanth, Witkowski, Andrew
• Primary Examiner(s): Mizrahi, Diane D.
• Application Number:
  US09/656,304
• Time in Patent Office: 1,105 Days
• Field of Search: 707/2, 707/3-6, 707/203, 707/100, 707/1, 706/47, 709/203
• US Class Current: 1/1
• CPC Class Codes: G06F 16/24537 of operators
• CPC Class Codes: G06F 16/24547 Optimisations to support specific applications; Extensibility of optimisers
• CPC Class Codes: Y10S 707/99932 Access augmentation or optimizing

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.

Claims

1. A method for execution of a query containing a set of one or more window functions, the method comprising the computer implemented steps of:

for each subset of a plurality of subsets of data items;

ranking, based on a target ranking function, 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.

2. 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.

3. 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.

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 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.

5. 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.

6. 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.

7. 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.

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

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

10. 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.

11. 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.

12. 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.

13. 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.

14. 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.

15. 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.

16. 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.

17. 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.

18. 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.

19. 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.

20. 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.

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

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

23. 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.

24. 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.

25. 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.

26. 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.