Data processing: database and file management or data structures – Database design – Data structure types
Reexamination Certificate
2005-09-20
2005-09-20
Kindred, Alford (Department: 2161)
Data processing: database and file management or data structures
Database design
Data structure types
C707S793000, C707S793000, C707S793000, C707S793000
Reexamination Certificate
active
06947927
ABSTRACT:
A method for evaluating a user query on a relational database having records stored therein, a workload made up of a set of queries that have been executed on the database, and a query optimizer that generates a query execution plan for the user query. Each query plan includes a plurality of intermediate query plan components that verify a subset of records from the database meeting query criteria. The method accesses the query plan and a set of stored intermediate statistics for records verified by query components, such as histograms that summarize the cardinality of the records that verify the query component. The method forms a transformed query plan based on the selected intermediate statistics (possibly by rewriting the query plan) and estimates the cardinality of the transformed query plan to arrive at a more accurate cardinality estimate for the query. If additional intermediate statistics are necessary, a pool of intermediate statistics may be generated based on the queries in the workload by evaluating the benefit of a given statistic over the workload and adding intermediate statistics to the pool that provide relatively great benefit.
REFERENCES:
patent: 6393419 (2002-05-01), Novak et al.
patent: 6529901 (2003-03-01), Chaudhuri et al.
patent: 6618719 (2003-09-01), Andrei
patent: 6732110 (2004-05-01), Rjaibi et al.
patent: 6754652 (2004-06-01), Bestgen et al.
patent: 2003/0208484 (2003-11-01), Chang et al.
A. Aboulnaga and S. Chaudhuri, “Self-tuning Histograms: Building Histograms without Looking at Data”, In Proceedings of the 1999 ACM International Conference on Management of Data (SIGMOD '99), Jun. 1999, pp. 181-192.
S. Acharya, P.B. Gibbons, V. Poosala and S. Ramaswamy, “Join Synopses for Approximate Query Answering”, In Proceedings of the 1999 ACM International Conference on Management of Data (SIGMOD '99), 1999, pp. 275-286.
N. Bruno, S. Chaudhuri and L. Gravano, “STHoles: A Multidimensional Workload-Aware Histogram”, In Proceedings of the 2001 ACM International Conference on Management of Data (SIGMOD '01), 2001, pp. 211-222.
S. Chaudhuri, “An Overview of Query Optimization in Relational Systems”, In Proceedings of the Seventeenth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, ACM Press, 1998, pp. 34-43.
S. Chaudhuri, R. Krishnamurthy, S. Potamianos and K. Shim, “Optimizing Queries with Materialized Views”, In Proceedings of the Eleventh International Conference on Data Engineering, 1995, pp. 190-200.
S. Chaudhuri and V. Narasayya, “Automating Statistics Management for Query Optimizers”, In Proceedings of the Sixteenth International Conference on Data Engineering, 2000, 10 pages.
S. Chaudhuri and V. Narasayya, “An Efficient Cost-Driven Index Selection Tool for Microsoft SQL Server”, In Proceedings of the Twenty-third International Conference on Very Large Databases (VLDB'97), Aug. 1997, pp. 146-155.
S. Chaudhuri and V. Narasayya, “AutoAdmin “What-If” Index Analysis Utility”, In SIGMOD 1998, Proceedings ACM SIGMOD International Conference on Management of Data, 1998, 12 pages.
J. Goldstein and P.-A. Larson, “Optimizing Queries Using Materialized Views: A Practical, Scalable Solution”, In Proceedings of the 2001 ACM International Conference on Management of Data (SIGMOD '01), 2001, pp. 331-342.
G. Graefe, “The Cascades Framework for Query Optimization”, Data Engineering Bulletin, 18(3), 1995, pp. 19-28.
G. Graefe and D.J. DeWitt, “The Exodus Optimizer Generator”, In Proceedings of the 1987 ACM International Conference on Management of Data (SIGMOD '87), 1987, pp. 160-172.
G. Graefe and W.J. McKenna, “The Volcano Optimizer Generator: Extensibility and Efficient Search”, In Proceedings of the Ninth International Conference on Data Engineering, 1993, pp. 209-218.
D. Gunopulos, G. Kollios, V.J. Tsotras and C. Domeniconi, “Approximating Multi-Dimensional Aggregate Range Queries Over Real Attributes”, In Proceedings of the 2000 ACM International Conference on Management of Data (SIGMOD '00), 2000, 12 pages.
L.M. Haas, J.C. Freytag, G.M. Lohman and H. Pirahesh, “Extensible Query Processing in Starbust,” In Proceedings of the 1989 ACM International Conference on Management of Data (SIGMOD '89), 1989, pp. 377-388.
M. Muralikrishna and D.J. DeWitt, “Equi-Depth Histograms for Estimating Selectivity Factors for Multidimensional Queries”, In Proceedings of the 1988 ACM International Conference on Management of Data (SIGMOD '88), 1988, 9 pages.
G. Pietetsky-Shapiro and C. Conneli, “Accurate Estimation of the Number of Tuples Satisfying a Condition”, In Proceedings of the 1984 ACM International Conference on Management of Data, (SIGMOD '84), 1984, pp. 256-276.
V. Poosala and Y.E. Ioannidis, “Selectivity Estimation Without the Attribute Value Independence Assumption”, In Proceedings of the Twenty-Third International Conference on Very Large Databases, (VLDB '97), Aug. 1997, pp. 486-495.
V. Poosala, Y.E. Ioannidis, P.J. Haas and E.J. Shekita, “Improved Histograms for Selectivity Estimation of Range Predicates”, In Proceedings of the 1996 ACM International Conference on Management of Data, (SIGMOD '96), 1996, pp. 294-305.
R. Pottinger and A.Y. Levy, “A Scalable Algorithm for Answering Queries Using Views”, In VLDB 2000, Proceedings of 26thInternational Conference on Very Large Data Bases, 2000, pp. 484-495.
P.G. Sellinger, M.M. Astrahan, D.D. Chamberlin, R.A. Lorie and T.G. Price, “Access Path Selection in a Relational Database System”, In Proceedings of the 1979 ACM International Conference on Management of Data (SIGMOD '79), 1979, pp. 23-34.
M. Stillger, G.M. Lohman, V. Markl and M. Kandil, “LEO-DB2's Learning Optimizer”, In Proceedings of the Twenty-seventh International Conference on Very Large Databases, 2001, 10 pages.
Bruno Nicolas
Chaudhuri Surajit
Al-Hashemi Sana
Kindred Alford
Microsoft Corp.
Microsoft Corporation
LandOfFree
Method and apparatus for exploiting statistics on query... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method and apparatus for exploiting statistics on query..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for exploiting statistics on query... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3379785