Dynamic selection of optimal grouping sequence at runtime for grouping sets, rollup and cube operations in SQL query processing

Patent metadata

Field	Value
Publication number	US-9535952-B2
Application number	US-201213443997-A
Country	US
Kind code	B2
Filing date	Apr 11, 2012
Priority date	Jul 29, 2003
Publication date	Jan 3, 2017
Grant date	Jan 3, 2017

Abstract

A method, apparatus, and article of manufacture for optimizing a query in a computer system. Grouping operations are optimized during execution of the query in the computer system by: (1) translating the grouping operations into a plurality of levels, wherein each of the levels is comprised of one or more grouping sets with the same number of grouping expressions; (2) deriving the grouping sets on a level-by-level basis, wherein the grouping sets in a base level are obtained from the database and the grouping sets in a next one of the levels are derived by selecting as an input a smallest one of the grouping sets in a previous one of the levels with which it has a derivation relationship; and (3) combining the derived grouping sets into an output for the query.

First claim

What is claimed is:

1. A method of performing a query in a computer system, the query being performed to retrieve data from a database stored on the computer system, the method comprising:
(a) optimizing grouping operations during execution of the query in the computer system by:
(1) constructing a Super Group Block when a GROUPBY operation with one or more super group operations is encountered in the query, wherein the super group operations comprise GROUPING SETS, ROLLUP and CUBE operations;
(2) translating the GROUPBY operation with the super group operations into grouping sets arranged in a plurality of levels using the Super Group Block, wherein each of the grouping sets specifies one or more grouping expressions that are aggregated, each of the levels is comprised of one or more of the grouping sets, and all of the grouping sets in each of the levels have the same number of the grouping expressions, such that:
(i) the Super Group Block has an array of pointers to a plurality of linked lists of Super Group Elements representing the grouping sets arranged in the plurality of levels, wherein the number of pointers in the array corresponds to the number of grouping expressions in the grouping sets in a base level, each pointer points to a particular one of the linked lists of Super Group Elements representing the grouping sets for a particular one of the levels, and at least one of the Super Group Elements is allocated for each of the grouping sets;
(ii) each of the Super Group Elements includes one or more pointers to one or more of the Super Group Elements on a previous one of the levels, to indicate that one or more of the grouping sets on the previous one of the levels can be used to derive the grouping set of the Super Group Element; and
(iii) each of the Super Group Elements includes one or more pointers to one or more workfiles created during processing of the Super Group Element;

(3) deriving the grouping sets on a level-by-level basis using the Super Group Elements of the Super Group Block and storing output from each of the Super GroupElements in the workfiles of the Super Group Elements, wherein the grouping sets in the base level are obtained from the database and the grouping sets in a next one of the levels are derived by selecting as an input a smallest one of the grouping sets in the previous one of the levels with which the grouping sets in the next one of the levels has a derivation relationship; and
(4) combining the derived grouping sets into an output for the query.

2. The method of claim 1 , wherein the grouping expressions comprise grouping columns, and the grouping sets in the base level include all of the grouping columns in the grouping sets.

3. The method of claim 1 , wherein the grouping sets in the next one of the levels are derived by performing grouping operations on the smallest one of the grouping sets in the previous one of the levels with which the grouping sets in the next one of the levels has a derivation relationship.

4. The method of claim 1 , wherein the grouping sets in the next one of the levels can be derived from more than one of the grouping sets in the previous one of the levels.

5. The method of claim 1 , wherein each of the grouping sets in the next one of the levels is derived from different ones of the grouping sets in the previous one of the levels.

6. The method of claim 1 , wherein each pointer in the array is an anchor for a series of the Super Group Elements representing the grouping sets with the same number of grouping expressions.

7. The method of claim 6 , wherein each of the Super Group Elements contains a pointer to a next one of the Super Group Elements in the series.

8. A computer-implemented apparatus for performing a query to retrieve data from a database, the apparatus comprising:
(a) a computer configured for optimizing grouping operations during execution of the query in the computer by:
(1) constructing a Super Group Block when a GROUPBY operation with one or more super group operations is encountered in the query, wherein the super group operations comprise GROUPING SETS, ROLLUP and CUBE operations;
(2) translating the GROUPBY operation with the super group operations into grouping sets arranged in a plurality of levels using the Super Group Block, wherein each of the grouping sets specifies one or more grouping expressions that are aggregated, each of the levels is comprised of one or more of the grouping sets, and all of the grouping sets in each of the levels have the same number of the grouping expressions, such that:
(i) the Super Group Block has an array of pointers to a plurality of linked lists of Super Group Elements representing the grouping sets arranged in the plurality of levels, wherein the number of pointers in the array corresponds to the number of grouping expressions in the grouping sets in a base level, each pointer points to a particular one of the linked lists of Super Group Elements representing the grouping sets for a particular one of the levels, and at least one of the Super Group Elements is allocated for each of the grouping sets; and
(ii) each of the Super Group Elements includes one or more pointers to one or more of the Super Group Elements on a previous one of the levels, to indicate that one or more of the grouping sets on the previous one of the levels can be used to derive the grouping set of the Super Group Element;
(iii) each of the Super Group Elements includes one or more pointers to one or more workfiles created during processing of the Super Group Element;

(3) deriving the grouping sets on a level-by-level basis using the Super Group Elements of the Super Group Block and storing output from each of the Super Group Elements in the workfiles of the Super Group Elements, wherein the grouping sets in the base level are obtained from the database and the grouping sets in a next one of the levels are derived by selecting as an input a smallest one of the grouping sets in the previous one of the levels with which the grouping sets in the next one of the levels has a derivation relationship; and
(4) combining the derived grouping sets into an output for the query.

9. The apparatus of claim 8 , wherein the grouping expressions comprise grouping columns, and the grouping sets in the base level include all of the grouping columns in the grouping sets.

10. The apparatus of claim 8 , wherein the grouping sets in the next one of the levels are derived by performing grouping operations on the smallest one of the grouping sets in the previous one of the levels with which the grouping sets in the next one of the levels has a derivation relationship.

11. The apparatus of claim 8 , wherein the grouping sets in the next one of the levels can be derived from more than one of the grouping sets in the previous one of the levels.

12. The apparatus of claim 8 , wherein each of the grouping sets in the next one of the levels is derived from different ones of the grouping sets in the previous one of the levels.

13. The apparatus of claim 8 , wherein each pointer in the array is an anchor for a series of the Super Group Elements representing the grouping sets with the same number of grouping expressions.

14. The apparatus of claim 13 , wherein each of the Super Group Elements contains a pointer to a next one of the Super Group Elements in the series.

15. A computer program product for performing a query in a computer system, the query being performed to retrieve data from a database stored on the computer system, the computer program product comprising:
(a) a non-transitory computer readable storage device having computer read

Assignees

• Zhang Guogen
• Lin Fen-Ling
• Hu Jung-Hsin
• Chen Yao-Ching S
• Wang Yun
• Yuki Glenn M
• IBM

Inventors

• Zhang Guogen
• Lin Fen-Ling
• Hu Jung-Hsin
• Chen Yao-Ching S
• Wang Yun
• Yuki Glenn M

Classifications

• G06F16/24537 Primary

  of operators · CPC title

• G06F17/30454 Primary

  Physics · mapped topic