Patent US5956706A successfully refreshed from Google Patents.
US5956706A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Method and system for limiting the cardinality of an SQL query result
Assignee: International Business Machines Corp
•
Filing: 1997-05-09
•
Granted: 1999-09-21
•
Expires: 2017-05-09
Abstract
Abstract A STOP AFTER clause for a relational database management system (RDBMS) structured query language (SQL) causes the RDBMS, in response to a query, to return a query result having at most a predetermined cardinality specified in the query. A query with a STOP AFTER clause is processed by the RDBMS by provision of one or more STOP operators that are inserted into a query execution plan generated by the RDBMS to execute the query. In a conservative policy, STOP operators are inserted in the query execution plan such that no tuples that might be required in the query result are discarded. In contrast, an aggressive policy inserts a STOP operator in the query execution plan wherever it is able to provide a beneficial cardinality reduction. A RESTART operator is inserted into aggressive policy query execution plans to ensure that at least the predetermined number of tuples are returned in the query result, and a final STOP operator is added at or near the root of the plan to ensure that at most the specified number of tuples are produced.
Inventors
- 👤 Michael James Carey
- 👤 Donald Alan Kossmann
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-08 22:17
CPC Classifications
G; G06; G06F; G06F16/00; G06F16/20; G06F16/24; G06F16/242; G06F16/2433; G06F16/2438; G06F16/2445; Y; Y10; Y10S; Y10S707/00; Y10S707/99931; Y10S707/99932
Claims Analysis
Total Claims: 29
Claim 1
Independent Claim
67 words
A method of generating a query execution plan in a computer with a memory responsive to a query including a specified size for a result of the query, comprising: generating a query execution plan in the memory of the computer; and inserting at least one STOP operator in the query execution plan for limiting the size of the query result to no more than a specified cardinality.
Claim 2
Independent Claim
67 words
A method of generating a query execution plan in a computer with a memory responsive to a query including a specified size for a result of the query, comprising: generating a query execution plan in the memory of the computer; and inserting at least one STOP operator in the query execution plan for limiting the size of the query result to no more than a specified cardinality.
Claim 3
Dependent Claim
44 words
The method of claim 1, wherein the STOP operator is inserted in a conservative location of the query execution plan, the conservative location being characterized such that no tuples are discarded during execution of the query that may be required in the query result.
Claim 4
Dependent Claim
25 words
The method of claim 2, wherein the conservative location is characterized such that predicates in the query execution plan above the conservative location are non-reductive.
Claim 5
Dependent Claim
46 words
The method of claim 1, wherein the query includes an ORDER BY clause and the STOP operator is inserted in an aggressive location of the query execution plan, the aggressive location being characterized such that a first column of the ORDER BY clause may be computed.
Claim 6
Dependent Claim
28 words
The method of claim 4, wherein the aggressive location is a location in the query execution plan below at least one non-reductive predicate in the query execution plan.
Claim 7
Dependent Claim
20 words
The method of claim 5, flier comprising determining a stopping cardinality for the STOP operator, based on the specified cardinality.
Claim 8
Dependent Claim
49 words
The method of claim 4, further comprising inserting a RESTART operator into the query execution plan at a restart location above the aggressive location, the RESTART operator for restarting execution of the query when an input stream to the RESTART operator contains fewer than a preselected number of tuples.
Claim 9
Dependent Claim
25 words
The method of claim 7, wherein the restart location is characterized such that predicates in the query execution plan above the restart location are non-reductive.
Claim 10
Independent Claim
99 words
A method executable by a computer for limiting the size of a query result in a database management system in response to a query, comprising: receiving a query in the memory of the computer; examining the query to determine whether the query includes a requirement for a size of a result of the query; generating at least one query execution plan in response to the query; and; inserting at least one STOP operator in the query execution plan for limiting a number of tuples in the result to a cardinality number corresponding to a required size of the result.
Claim 11
Independent Claim
99 words
A method executable by a computer for limiting the size of a query result in a database management system in response to a query, comprising: receiving a query in the memory of the computer; examining the query to determine whether the query includes a requirement for a size of a result of the query; generating at least one query execution plan in response to the query; and; inserting at least one STOP operator in the query execution plan for limiting a number of tuples in the result to a cardinality number corresponding to a required size of the result.
Claim 12
Dependent Claim
17 words
The method of claim 9, further comprising generating a query execution plan with a plurality of predicates.
Claim 13
Dependent Claim
42 words
The method of claim 10, further comprising the step of: inserting the STOP operator in a conservative location of the query execution plan, the conservative location being characterized such that predicates in the query execution plan above the conservative location are non-reductive.
Claim 14
Dependent Claim
42 words
The method of claim 10, further comprising: inserting the STOP operator in an aggressive location of the query execution plan, the aggressive location being characterized such that the aggressive location is below at least one non-reductive predicate in the query execution plan.
Claim 15
Dependent Claim
24 words
The method of claim 12, further comprising determining a stopping cardinality for the STOP operator, based on the requirement for size of the result.
Claim 16
Dependent Claim
52 words
The method of claim 13, further comprising inserting a RESTART operator into the query execution plan at a restart location above the aggressive location, the RESTART operator for causing execution of the query execution plan to restart when an input stream to the RESTART operator contains fewer tuples than the stopping cardinality.
Claim 17
Dependent Claim
25 words
The method of claim 14, wherein the restart location is characterized such that predicates in the query execution plan above the restart location are non-reductive.
Claim 18
Dependent Claim
107 words
A computer program device comprising: a computer program storage device readable by a digital processing apparatus; and a program means on the program storage device and including instructions for causing the digital processing apparatus to limit the number of tuples returned by a database management system in a query result, by: receiving a query including specification of a result cardinality; generating a query execution plan in response to the query, the query execution plan having predicates for executing the query; and placing an operator in the query execution plan to limit a number of tuples returned in the query result to no more than the result cardinality.
Claim 19
Dependent Claim
107 words
A computer program device comprising: a computer program storage device readable by a digital processing apparatus; and a program means on the program storage device and including instructions for causing the digital processing apparatus to limit the number of tuples returned by a database management system in a query result, by: receiving a query including specification of a result cardinality; generating a query execution plan in response to the query, the query execution plan having predicates for executing the query; and placing an operator in the query execution plan to limit a number of tuples returned in the query result to no more than the result cardinality.
Claim 20
Dependent Claim
39 words
The computer program device of claim 16, wherein limiting is accomplished by inserting at least one STOP operator in the query execution plan, the STOP operator for limiting the size of an output stream in the query execution plan.
Claim 21
Dependent Claim
45 words
The computer program device of claim 17, the program means is further for: inserting the STOP operator in a conservative location of the query execution plan, the conservative location being characterized such that predicates in the query execution plan above the conservative location are non-reductive.
Claim 22
Dependent Claim
48 words
The computer program device of claim 17, the program means is farther for: inserting the STOP operator in an aggressive location of the query execution plan, the aggressive location being characterized such that the aggressive location is below at least one nonreductive predicate in the query execution plan.
Claim 23
Dependent Claim
26 words
The computer program device of claim 19, the program means is further for determining a stopping cardinality for the STOP operator, based on the result cardinality.
Claim 24
Dependent Claim
59 words
The computer program device of claim 20, the program means is further for inserting a RESTART operator into the query execution plan at a restart location above the aggressive location, the RESTART operator for causing execution of the query execution plan to restart when an input stream to the RESTART operator contains fewer than a predetermined number of tuples.
Claim 25
Dependent Claim
27 words
The computer program device of claim 21, wherein the restart location is characterized such that predicates in the query execution plan above the restart location are non-reductive.
Claim 26
Independent Claim
85 words
A method for querying a database using a database management system, the method executable on a computer with a memory and including: receiving in the memory of the computer a query that includes a clause limiting the size of a query result to N; executing the query to produce a result set of tuples that satisfy the query; during execution of the query, limiting the number of tuples in the result set to no more than N; and returning the result set to a user.
Claim 27
Independent Claim
85 words
A method for querying a database using a database management system, the method executable on a computer with a memory and including: receiving in the memory of the computer a query that includes a clause limiting the size of a query result to N; executing the query to produce a result set of tuples that satisfy the query; during execution of the query, limiting the number of tuples in the result set to no more than N; and returning the result set to a user.
Claim 28
Dependent Claim
13 words
The method of claim 23, wherein the clause is a STOP AFTER clause.
Claim 29
Dependent Claim
14 words
The method of claim 24, wherein the query further includes an ORDER BY clause.
References Cited (Backward Citations)
US4769772A
Cited
US5367675A
Cited
US5412804A
Cited
US5412806A
Cited
US5794228A
Cited
US5794229A
Cited
US5598559A
Cited
US5530939A
Cited
US5548754A
Cited
US5548758A
Cited
US5546570A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2002-09-20 | 2003-03-22 | 2003-09-21 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2006-09-20 | 2007-03-22 | 2007-09-21 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2010-09-20 | 2011-03-22 | 2011-09-21 | $7700.00 | Window Closed / Lapsed |