Techniques for estimating progress of database queries

Details Techniques for estimating progress of database queries Techniques for estimating progress of database queries

2005-06-10

2008-11-18

Rones, Charles (Department: 2164)

Data processing: database and file management or data structures

Database design

Data structure types

C707S793000, C707S793000, C707S793000

Reexamination Certificate

active

07454407

ABSTRACT:
Techniques for estimating the progress of database queries are described herein. In a first implementation, a respective lower-bound parameter is associated with each node in an operator tree that representing a given database query, and the progress of the database query at a given point is estimated based upon the lower-bound parameters. In a second implementation, the progress of the query is estimated by associating respective lower-bound and upper-bound parameters with each node in the operator tree. The progress of the query at the given point is then estimated based on the lower-bound and upper-bound parameters.

REFERENCES:
patent: 2005/0222965 (2005-10-01), Chaudhuri et al.
patent: 2006/0190430 (2006-08-01), Luo et al.
patent: 2006/0218125 (2006-09-01), Kandil et al.
Chaudhuri et al., “Estimating Progess of Execution for SQL Queries”, SIGMOD 2004, Jun. 13-18, pp. 1-12. (Provided by Applicant).
Markl et al., “Robust Query Processing through Progressive Optimization”, SIGMOD 2004, Jun. 13-18, pp. 1-12. (Provided by Applicant).
Chaudhuri et al; “On Random Sampling over Joins”; ACM SIGMOD '99 Philadelphia PA; pp. 263-274.
Ioannidis; “Query Optimization”; ACM Computing Surveys, vol. 28, No. 1, Mar. 1996; pp. 121-123.
Bruno et al; “Exploiting St6atistics on Query Expressions for Optimization”; ACM SIGMOD 'Jun. 4-6, 2002, Madison, Wisconsin; pp. 263-274.
Haas et al; “Selectivity and Cost Estimation for Joins BAsed on Random Sampling”; Journal of Computer and Systems Sciences, vol. 52, No. 3; Jun. 1996, pp. 550-569.
Kabra et al; “Efficient Mid-Query Re-Optimization of Sub-Optimal Query Execution Plans”; 1998 ACM SIGMOD Seattle WA; pp. 106-117.
Haas et al.; “Ripple Joins for Online Aggregation”; SIGMOD '99 Philadelphia PA; pp. 287-298.
Hellerstein et al; “Online Aggregation”; 1997 ACM SIGMOD AZ; pp. 171-182.
Ioannidis et al.; “On the Propagation of Errors in the Size of Join Results”; 1991 SIGMOD ACM; pp. 268-277.
Luo et al.; “Toward a Progress Indicator for DAtabase Queries”; ACM SIGMOD 2004, Jun. 13-18, 2004, Paris France; 12 pages.
Ioannidis et al.; “Balancing Histogram Optimality and Practicality for Query Result Size Estimation”; ACM SIGMOD '95 San Jose, CA; pp. 233-244.
Haas; “Large-Sample and Deterministic Confidence Intervals for Online Aggregation”; 9th International Conference on Scientific and Statistical Database Management, 1997; pp. 51-62.
Acharya et al.; “Join Synopses for Approximate Query Answering”; ACM SIGMOD '99 Philadelphia PA; pp. 275-286.
Chaudhuri; “An Overview of Query Optimization in Relational Systems”; 10 pages, no date.
Luo et al.; “Increasing the Accuracy and Coverage of SQL Progress Indicators”; 12 pages, no date.
When Can We Trust Progress Estimators for SQL Queries?; Paper ID: 448; 12 pages, no date.

Affiliated with

Also associated with

Rating

Techniques for estimating progress of database queries does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Techniques for estimating progress of database queries, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Techniques for estimating progress of database queries will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-4033437