US5822748A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Group by and distinct sort elimination using cost-based optimization
Assignee: Oracle International Corp
•
Filing: 1997-02-28
•
Granted: 1998-10-13
•
Expires: 2017-02-28
Abstract
Abstract Sort plus operations such as "group by" and "distinct" generally require sorting of the retrieved data before performing the sort plus operation. A method and apparatus is disclosed for executing a query specifying a sort plus operation without performing the sorting operation. A cost-based optimizer determines at least one execution path where the data is retrieved from a sorted source and the data is processed to satisfy the query without sorting. Execution costs are determined for the respective execution paths, and the execution path having the lowest overall execution cost is selected to process the query.
Inventors
- 👤 Jeffrey Ira Cohen
- 👤 Cetin Ozbutun
- 👤 Michael Depledge
- 👤 Hakan Jakobsson
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-27 10:16
CPC Classifications
G; G06; G06F; G06F16/00; G06F16/20; G06F16/24; G06F16/245; G06F16/2453; G06F16/24534; G06F16/24537; Y; Y10; Y10S; Y10S707/00; Y10S707/99931; Y10S707/99932; Y10S707/99933; Y10S707/99934; Y10S707/99935; Y10S707/99936; Y10S707/99937; Y10S707/99951; Y10S707/99952; Y10S707/99953
Claims Analysis
Total Claims: 17
Claim 1
Independent Claim
172 words
A method of executing a query that specifies a sort plus operation, the method comprising: A. determining a first execution path, where execution of the first execution path would require performing the steps of: (1) obtaining data specified in the query from a sorted source, and (2) executing a first version of the sort plus operation that does not perform sorting; B. determining a second execution path, where execution of the second execution path would require performing the steps of: (1) obtaining data specified in the query from an unsorted source, and (2) executing a second version of the sort plus operation that does perform sorting; C. determining a first execution cost for the first execution path and a second execution cost for the second execution path; D. selecting a selected execution path from among a set of execution paths that includes said first execution path and said second execution path based on a comparison of said first execution cost and said second execution cost; and E. executing said selected execution path.
Claim 2
Independent Claim
172 words
A method of executing a query that specifies a sort plus operation, the method comprising: A. determining a first execution path, where execution of the first execution path would require performing the steps of: (1) obtaining data specified in the query from a sorted source, and (2) executing a first version of the sort plus operation that does not perform sorting; B. determining a second execution path, where execution of the second execution path would require performing the steps of: (1) obtaining data specified in the query from an unsorted source, and (2) executing a second version of the sort plus operation that does perform sorting; C. determining a first execution cost for the first execution path and a second execution cost for the second execution path; D. selecting a selected execution path from among a set of execution paths that includes said first execution path and said second execution path based on a comparison of said first execution cost and said second execution cost; and E. executing said selected execution path.
Claim 3
Dependent Claim
33 words
The method of claim 1, wherein the step of obtaining data specified in the query from a sorted source includes the step of obtaining data specified in the query from a first index.
Claim 4
Dependent Claim
32 words
The method of claim 2, wherein the step of obtaining data specified in the query from an unsorted source includes the step of obtaining data specified in the query from a table.
Claim 5
Dependent Claim
80 words
The method of claim 2, wherein the step of determining a first execution cost for the first execution path comprises the steps of: determining a first access cost corresponding to accessing the first index to obtain the data specified in the query; determining a cost of executing the first version of the sort plus operation; and determining the first execution cost based on the first access cost and the cost of executing the first version of the sort plus operation.
Claim 6
Dependent Claim
78 words
The method of claim 4, wherein the step of determining a second execution cost for the second execution path comprises the steps of: determining a second access cost corresponding to accessing a table to obtain data specified in the query; determining a cost of executing the second version of the sort plus operation; and determining the second execution cost based on the second access cost and the cost of executing the second version of the sort plus operation.
Claim 7
Dependent Claim
55 words
The method of claim 1 wherein the step of determining a first execution cost for the first execution path and a second execution cost for the second execution path includes causing a cost-based optimizer to determine the first execution cost for the first execution path and the second execution cost for the second execution path.
Claim 8
Dependent Claim
46 words
The method of claim 2, further comprising determining a third execution path for the query, wherein execution of the third execution path includes the steps of: obtaining data specified in the query from a second index, and executing the first version of the sort plus operation.
Claim 9
Dependent Claim
64 words
The method of claim 1, wherein: the sort plus operation is a "group by" operation; and the step of executing the second version of the sort plus operation includes the steps of sorting data based on a key specified in the query; and grouping data with adjacent data if the adjacent data has a same key value for the key specified in the query.
Claim 10
Dependent Claim
65 words
The method of claim 1, wherein: the sort plus operation is a "distinct" operation; and the step of executing the second version of the sort plus operation includes the steps of sorting data based on a key specified in the query; and returning one key value for every series of consecutive data that has the same key value for the key specified in the query.
Claim 11
Dependent Claim
192 words
A computer readable medium having stored thereon sequences of instructions for a sort plus operation, said sequences of instructions including instructions which, when executed by a processor, cause the processor to perform the steps of: A. determining a first execution path, where execution of the first execution path would require performing the steps of: (1) obtaining data specified in the query from a sorted source, and (2) executing a first version of the sort plus operation that does not perform sorting; B. determining a second execution path, where execution of the second execution path would require performing the steps of: (1) obtaining data specified in the query from an unsorted source, and (2) executing a second version of the sort plus operation that does perform sorting; C. determining a first execution cost for the first execution path and a second execution cost for the second execution path; D. selecting a selected execution path from among a set of execution paths that includes said first execution path and said second execution path based on a comparison of said first execution cost and said second execution cost; and E. executing said selected execution path.
Claim 12
Dependent Claim
192 words
A computer readable medium having stored thereon sequences of instructions for a sort plus operation, said sequences of instructions including instructions which, when executed by a processor, cause the processor to perform the steps of: A. determining a first execution path, where execution of the first execution path would require performing the steps of: (1) obtaining data specified in the query from a sorted source, and (2) executing a first version of the sort plus operation that does not perform sorting; B. determining a second execution path, where execution of the second execution path would require performing the steps of: (1) obtaining data specified in the query from an unsorted source, and (2) executing a second version of the sort plus operation that does perform sorting; C. determining a first execution cost for the first execution path and a second execution cost for the second execution path; D. selecting a selected execution path from among a set of execution paths that includes said first execution path and said second execution path based on a comparison of said first execution cost and said second execution cost; and E. executing said selected execution path.
Claim 13
Dependent Claim
34 words
The computer-readable medium of claim 10, wherein the step of obtaining data specified in the query from a sorted source includes the step of obtaining data specified in the query from a first index.
Claim 14
Dependent Claim
81 words
The computer-readable medium of claim 11, wherein the step of determining a first execution cost for the first execution path comprises the steps of: determining a first access cost corresponding to accessing the first index to obtain the data specified in the query; determining a cost of executing the first version of the sort plus operation; and determining the first execution cost based on the first access cost and the cost of executing the first version of the sort plus operation.
Claim 15
Dependent Claim
197 words
A database system comprising: a database storing a table of a data set, and a sorted version of the data set; a database server for processing a query based on a selected execution path, the database server including a cost-based optimizer for: A. determining a first execution path, where execution of the first execution path would require performing the steps of: (1) obtaining data specified in the query from the sorted version of the data set, and (2) executing a first version of the sort plus operation that does not perform sorting; B. determining a second execution path, where execution of the second execution path would require performing the steps of: (1) obtaining data specified in the query from the data set, and (2) executing a second version of the sort plus operation that does perform sorting; C. determining a first execution cost for the first execution path and a second execution cost for the second execution path; and D. selecting said selected execution path from among a set of execution paths that includes said first execution path and said second execution path based on a comparison of said first execution cost and said second execution cost.
Claim 16
Dependent Claim
197 words
A database system comprising: a database storing a table of a data set, and a sorted version of the data set; a database server for processing a query based on a selected execution path, the database server including a cost-based optimizer for: A. determining a first execution path, where execution of the first execution path would require performing the steps of: (1) obtaining data specified in the query from the sorted version of the data set, and (2) executing a first version of the sort plus operation that does not perform sorting; B. determining a second execution path, where execution of the second execution path would require performing the steps of: (1) obtaining data specified in the query from the data set, and (2) executing a second version of the sort plus operation that does perform sorting; C. determining a first execution cost for the first execution path and a second execution cost for the second execution path; and D. selecting said selected execution path from among a set of execution paths that includes said first execution path and said second execution path based on a comparison of said first execution cost and said second execution cost.
Claim 17
Dependent Claim
16 words
The system of claim 13, wherein the sorted version stored in the database is an index.
References Cited (Backward Citations)
US5301317A
Cited
US5666526A
Cited
US5734884A
Cited
US5671403A
Cited
US5680602A
Cited
US5668987A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2001-10-12 | 2002-04-13 | 2002-10-13 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2005-10-12 | 2006-04-13 | 2006-10-13 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2009-10-12 | 2010-04-13 | 2010-10-13 | $7700.00 | Window Closed / Lapsed |