Group-By Size Result Estimation

• US 20130042085A1
• Filed: 10/12/2012
• Published: 02/14/2013
• Est. Priority Date: 03/30/2004
• Status: Active Grant

• Current Assignee: SAP SE
• Original Assignee: SAP AG (SAP SE)
• Inventors: Miao, Bingjie, Mottupalli, Srinivasan R.
• Granted Patent: US 9,747,337 B2
• Time in Patent Office: Days
• US Class Current: 711/171
• CPC Class Codes: G06F 16/244 Grouping and aggregation
• CPC Class Codes: G06F 16/24537 of operators
• CPC Class Codes: G06F 16/24545 Selectivity estimation or determination
• CPC Class Codes: Y10S 707/954 Relational
• CPC Class Codes: Y10S 707/99932 Access augmentation or optimizing
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching

Abstract

A method and system for accurately estimating a result size of a Group-By operation in a relational database. The estimate utilizes the probability of union of the columns involved in the operation, as well as the relative cardinality of each column with respect to the other columns in the operation. In addition, the estimate incorporates the use of table filters when indicated such that table filters are applied prior to determining the size of the tables in the operation, as well as including equivalent columns into the list of columns that are a part of the Group-By operation. Accordingly, the estimate of the result size of the operation includes influencing factors that provide an accurate estimation of system memory requirements.

Claims

1-15. -15. (canceled)

16. A method for estimating a result size of a Group-By operation comprising:

organizing a database stored on a computer readable medium with data records maintained in multiple tables;

calculating a cumulative selectivity in a Group-By operation; and

allocating memory for the Group-By operation based upon a memory requirement responsive to the cumulative selectivity.

17. The method of claim 16, wherein the cumulative selectivity is based upon a maximum size of the multiple tables.

18. The method of claim 16, wherein the cumulative selectivity is based upon a relative uniqueness of a column based upon a size of a table in which the column resides.

19. The method of claim 16, wherein the cumulative selectivity is based upon an equivalency of columns based on equal join predicates.

20. The method of claim 16, wherein the cumulative selectivity is based upon a probability of union of two or more columns from two or more tables.

21. The method of claim 16, wherein the cumulative selectivity is based upon two or more of a maximum size of the multiple tables, a relative uniqueness of a column based upon a size of a table in which the column resides, an equivalency of columns based on equal join predicates and a probability of union of two or more columns from two or more tables.

22. A system for estimating a result size of a Group-By operation comprising:

a memory configured to store modules comprising;

a first module configured to organize a database stored on a computer readable medium with data records maintained in multiple tables;

a second module configured to calculate a cumulative selectivity in a Group-By operation;

a third module configured to allocate memory for the Group-By operation based upon a memory requirement responsive to the cumulative selectivity; and

one or more processors configured to process the modules.

23. The system of claim 22, wherein the cumulative selectivity is based upon a maximum size of the multiple tables.

24. The system of claim 22, wherein the cumulative selectivity is based upon a relative uniqueness of a column based upon a size of a table in which the column resides.

25. The system of claim 22, wherein the cumulative selectivity is based upon an equivalency of columns based on equal join predicates.

26. The system of claim 22, wherein the cumulative selectivity is based upon a probability of union of two or more columns from two or more tables.

27. The system of claim 22, wherein the cumulative selectivity is based upon two or more of a maximum size of the multiple tables, a relative uniqueness of a column based upon a size of a table in which the column resides, an equivalency of columns based on equal join predicates and a probability of union of two or more columns from two or more tables.

28. A non-transitory computer-readable storage medium having computer-executable instructions stored thereon that, in response to being executed by a computing device, cause the computing device to perform operations comprising:

organizing a database stored on a computer readable medium with data records maintained in multiple tables;

calculating a cumulative selectivity in a Group-By operation; and

allocating memory for the Group-By operation based upon a memory requirement responsive to the cumulative selectivity.

29. The non-transitory computer-readable storage medium of claim 28, wherein the cumulative selectivity is based upon a maximum size of the multiple tables.

30. The non-transitory computer-readable storage medium of claim 28, wherein the cumulative selectivity is based upon a relative uniqueness of a column based upon a size of a table in which the column resides.

31. The non-transitory computer-readable storage medium of claim 28, wherein the cumulative selectivity is based upon an equivalency of columns based on equal join predicates.

32. The non-transitory computer-readable storage medium of claim 28, wherein the cumulative selectivity is based upon a probability of union of two or more columns from two or more tables.

33. The non-transitory computer-readable storage medium of claim 28, wherein the cumulative selectivity is based upon two or more of a maximum size of the multiple tables, a relative uniqueness of a column based upon a size of a table in which the column resides, an equivalency of columns based on equal join predicates and a probability of union of two or more columns from two or more tables.