Queries with soft time constraints

• US 7,953,728 B2
• Filed: 05/18/2007
• Issued: 05/31/2011
• Est. Priority Date: 05/18/2007
• Status: Active Grant

• Current Assignee: Oracle International Corporation (Oracle Corporation)
• Original Assignee: Oracle International Corporation (Oracle Corporation)
• Inventors: Hu, Ying, Sundara, Seema, Srinivasan, Jagannathan
• Primary Examiner(s): Kim; Charles
• Assistant Examiner(s): GIRMA, ANTENEH B
• Application Number:
  US11/804,502
• Publication Number:
  US 20080288446A1
• Time in Patent Office: 1,474 Days
• Field of Search: None
• US Class Current: 707/719
• CPC Class Codes: G06F 16/2462 Approximate or statistical queries

Abstract

Systems, methodologies, media, and other embodiments associated with supporting queries with soft time constraints are described. One exemplary system embodiment includes logic for accepting a query having a soft time constraint. The example system may also include logic for rewriting the query having the soft time constraint into a query having a row limitation or a sample percentage limitation. In one example, the row limitation or sample percentage limitation are computed by repetitively comparing an estimated query execution time to the soft time constraint.

Claims

1. A system, comprising:

a non-transitory computer-readable medium storing instructions configured as receive logic to receive a first query having a soft time constraint and an acceptable nature of results constraint that specifies one of, whether a partial result is to be returned, and whether an approximate result is to be returned;

an analytics logic to provide a predicted execution time for a query based, at least in part, on the acceptable nature of results constraint; and

a constraint rewrite logic to selectively produce a rewritten query based on the first query, the rewritten query having a restricted result clause, where the restricted result clause depends, at least in part, on the predicted execution time and specifies one of, a number of rows to which row selection is to be limited by the rewritten query, and a sample percentage to which row selection is to be limited by the rewritten query.

2. The system of claim 1,

where the constraint rewrite logic is configured to use the soft time constraint as an upper bound for constraining an execution time of the rewritten query.

3. The system of claim 1,

where the receive logic is configured to identify the soft time constraint from the first query;

where the analytics logic is configured to generate the predicted execution time based, at least in part, on the soft time constraint; and

where the restricted result clause depends, at least in part, on the soft time constraint and replaces the soft time constraint in the rewritten query.

4. The system of claim 1, where the constraint rewrite logic is to iteratively:

choose different candidate numbers of rows to be selected;

determine a set of predicted execution times associated with queries limited to the candidate numbers of rows; and

manipulate the rewritten query to include a row number clause to cause a limited number of rows to be selected, where the row number clause is based on a relation between a member of the set of predicted execution times and the soft time constraint.

5. The system of claim 4, where the constraint rewrite logic is to choose the different candidate numbers of rows by root finding.

6. The system of claim 5, where the root finding solves for a root of F_Q(R)−

T=0, where;

F_Q(R) represents the execution time for the rewritten query using the specified result set size;

R represents the result set size; and

T represents the amount of time specified in the soft time constraint.

7. The system of claim 1 where the receive logic, the analytics logic, and the constraint rewrite logic comprise instructions stored in a non-transitory computer-readable medium.

8. The system of claim 1, where the first query concerns two or more tables and where the constraint rewrite logic is to generate the rewritten query to divide a time available to execute the rewritten query substantially equally between the two or more tables.

9. The system of claim 1, where the constraint rewrite logic is to iteratively:

choose different candidate sample percentages to control a number of rows to select by the rewritten query;

determine a set of predicted execution times associated with queries limited by the candidate sample percentages; and

generate the rewritten query to include a sample clause to cause a limited number of rows to be provided in a sample, where the sample percentage is based on a relation between a member of the predicted execution times and the soft time constraint.

10. The system of claim 9, where the constraint rewrite logic is to choose the different candidate sample percentages for a single table query using root finding.

11. The system of claim 10, where the root finding solves for a root of F_Q(S)−

T=0, where;

F_Q(S) represents the execution time for the rewritten query using the specified sample percentage;

S represents the sample percentage; and

T represents the amount of time specified in the soft time constraint.

12. The system of claim 1, where the first query involves a join on a foreign key of two tables, where the constraint rewrite logic is to identify a fact table and a non-fact table in the two tables, and where the constraint rewrite logic is to manipulate the rewritten query to first limit row selection in the fact table and then to join the results of the limited row selection to the non-fact table.

13. The system of claim 1, where the first query involves a join of two tables not on a foreign key, and where the constraint rewrite logic is to manipulate the rewritten query to first limit row selection and then to join results of the limited row selection.

14. The system of claim 13, where the constraint rewrite logic is to maximize f₁*f₂, where f₁ represents the sample size of one of the two tables and f₂ represents the sample size of the other of the two tables.

15. The system of claim 1, where the first query includes one of, a hash join, and a sort-merge join, of a first table R1 and a second table R2, where f1 represents a sample size for R1 and f2 represents a sample size for R2, where T1 represents a time to process R1 and T2 represents a time to process R2, where S1 represents a sample of R1 and S2 represents a sample of R2, where t1 represents a time to process S1 and t2 represents a time to process S2;

and

where the constraint rewrite logic is to produce the rewritten query so that t1=t2 and t1+t2<

the time specified by the soft time constraint.

16. The system of claim 14, where the first query includes a nested loop join and the constraint rewrite logic is to identify one of the two tables to join as an outer table and to identify one of the two tables to join as an inner table, the constraint rewrite to acquire a sample from the outer table, and then to join the sample from the outer table to the inner table.

17. The system of claim 1, where the first query includes a union operation between a first table R1 and a second table R2, and where the constraint rewrite logic is to configure the rewritten query with a sample(R1, f1) union sample(R2, f2) clause with f1=f2, where f1 represents a sample size for R1 and f2 represents a sample size for R2.

18. The system of claim 1, where the first query includes a difference operation between a first table R1 and a second table R2, and where the constraint rewrite logic is to configure the rewritten query with a sample(R1, f1) difference R2 clause, where f1 represents a sample size for R1.

19. The system of claim 1, where the first query includes an intersection operation between a first table R1 and a second table R2, and where the constraint rewrite logic is to configure the rewritten query with a sample(R1, f1) intersect sample(R2, f2) clause, where f1*f2 is maximized, where f1 represents a sample size for R1 and f2 represents a sample size for R2.

20. The system of claim 1, where the first query includes a sub-query.

21. The system of claim 20, where the constraint rewrite logic is to produce the rewritten query so that a predicate in the sub-query is not sampled.

22. The system of claim 1, including an aggregate function logic to provide an estimated aggregate function and a related confidence function.

23. The system of claim 22, where the estimated aggregate function is one of, an estimated sum function, an estimated count function, and an estimated average function.

24. The system of claim 1, where the system receives the first query from one or more of, a decision support system, a mobile network application, and a radio frequency identification application, and where the system provides results within a time period that satisfies a service level agreement.

25. A non-transitory computer-readable medium storing processor executable instructions that when executed by a computer cause the computer to perform a method, the method comprising:

receiving a first select statement having a soft time constraint clause, the select statement describing a desired selection of one or more rows from a set of tables;

determining an execution time estimate for the first select statement;

selecting from the set of tables a subset of tables from which row selection is to be limited, where the subset of tables is selected based, at least in part, on the soft time constraint clause and the execution time estimate;

selecting a method by which row selection from a member of the subset of tables is to be limited, where the method selected is based, at least in part, on the soft time constraint clause and the execution time estimate;

selecting an amount by which row selection from a member of the subset of tables is to be limited, where the amount selected is based, at least in part, on the soft time constraint clause and the execution time estimate;

providing a second select statement having at least one additional clause to limit selection of rows from a member of the subset of tables by the selected amount according to the selected method, the second select statement being based on the first select statement;

selecting an initial number of rows to which row selection will be limited based on a comparison of the initial estimate and the soft time constraint; and

iteratively selecting and analyzing a subsequent number of rows to which row selection will be limited until a time estimate falls within a threshold amount of the soft time constraint, the subsequent number of rows being based on a previous number of rows, a time estimate associated with a previous number of rows, and the soft time constraint.

26. The computer-readable medium of claim 25, where the first select statement includes a clause that specifies the method by which row selection is to be limited;

where the a soft time constraint clause includes a soft time constraint; and

the second select statement is provided in response to receiving the first select statement.

27. A non-transitory computer-readable medium storing processor executable instructions that when executed by a processor cause the processor to perform a method, the method comprising:

receiving a first select statement having a soft time constraint clause, the select statement describing a desired selection of one or more rows from a set of tables;

determining an execution time estimate for the first select statement;

selecting from the set of tables a subset of tables from which row selection is to be limited, where the subset of tables is selected based, at least in part, on the soft time constraint clause and the execution time estimate;

selecting a method by which row selection from a member of the subset of tables is to be limited, where the method selected is based, at least in part, on the soft time constraint clause and the execution time estimate;

selecting an amount by which row selection from a member of the subset of tables is to be limited, where the amount selected is based, at least in part, on the soft time constraint clause and the execution time estimate;

providing a second select statement having at least one additional clause to limit selection of rows from a member of the subset of tables by the selected amount according to the selected method, the second select statement being based on the first select statement;

selecting an initial sample percentage to which row selection will be limited for a member of the subset of tables based on a comparison of the initial estimate and the soft time constraint; and

iteratively selecting and analyzing a subsequent sample percentage to which row selection will be limited for a member of the subset of tables until a time estimate falls within a threshold amount of the soft time constraint, the subsequent sample percentage being based on a previous sample percentage, a time estimate associated with a previous sample percentage, and the soft time constraint.

28. A system, comprising:

means for computing a predicted execution time for a query having a soft time constraint and an acceptable nature of results constraint that specifies one of, whether a partial result is to be returned, and whether an approximate result is to be returned; and

means for rewriting the query based, at least in part, on the predicted execution time and the soft time constraint, where the rewriting includes replacing the soft time constraint with a result set limitation clause that specifies one of, a number of rows to which row selection is to be limited, and a sample percentage to which row selection is to be limited.

29. The system of claim 28, where the means for computing and the means for rewriting include a non-transitory computer-readable medium storing executable instructions that when executed perform at least the computing and the rewriting.

30. A non-transitory computer-readable medium storing computer executable instructions that when executed by a computer cause the computer to perform a method, the method, comprising:

computing a predicted execution time for a query having a soft time constraint and an acceptable nature of results constraint that specifies one of, whether a partial result is to be returned, and whether an approximate result is to be returned; and

rewriting the query based, at least in part, on the predicted execution time and the soft time constraint, where the rewriting includes replacing the soft time constraint with a result set limitation clause that specifies one of, a number of rows to which row selection is to be limited, and a sample percentage to which row selection is to be limited.