Query optimization by sub-plan memoization

Details Query optimization by sub-plan memoization Query optimization by sub-plan memoization

2007-07-03

2007-07-03

Kim, Chong H. (Department: 2167)

Data processing: database and file management or data structures

Database design

Data structure types

C707S793000, C707S793000, C707S793000, C707S793000, C707S793000

Reexamination Certificate

active

10941113

ABSTRACT:
Database system query optimizers use several techniques such as histograms and sampling to estimate the result sizes of operators and sub-plans (operator trees) and the number of distinct values in their outputs. Instead of estimates, the invention uses the exact actual values of the result sizes and the number of distinct values in the outputs of sub-plans encountered by the optimizer. This is achieved by optimizing the query in phases. In each phase, newly encountered sub-plans are recorded for which result size and/or distinct value estimates are required. These sub-plans are executed at the end of the phase to determine their actual result sizes and the actual number of distinct values in their outputs. In subsequent phases, the optimizer uses these actual values when it encounters the same sub-plan again.

REFERENCES:
patent: 5301317 (1994-04-01), Lohman et al.
patent: 5600831 (1997-02-01), Levy et al.
patent: 6021405 (2000-02-01), Celis et al.
patent: 6330552 (2001-12-01), Farrar et al.
patent: 6466931 (2002-10-01), Attaluri et al.
patent: 6581055 (2003-06-01), Ziauddin 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: 6850925 (2005-02-01), Chaudhuri et al.
patent: 6947927 (2005-09-01), Chaudhuri et al.
patent: 7080062 (2006-07-01), Leung et al.
patent: 2003/0208484 (2003-11-01), Chang et al.
patent: 2005/0267877 (2005-12-01), Chaudhuri et al.
A. Aboulnaga and S. Chaudhuri, Self-Tuning Histograms: Building Histograms without Looking at Data. In Proceedings of the ACM SIGMOD Conference, pp. 181-192, 1999.
S. Chaudhuri, R. Motwani and V.R. Narasayya, “Random Sampling for Histogram Construction: How Much is Enough?” In Proceedings of the ACM SIGMOD Conference, pp. 436-447, 1998.
C.M. Chen and N. Roussopoulos, “Adaptive Selectivity Estimation Using Query Feedback.” In Proceedings of the ACM SIGMOD Conference, pp. 161-172, 1994.
Y.E. Ioannidis and S. Christodoulakis, “On the Propagation of Errors in the Size of Join Results.” In Proceedings of the ACM SIGMOD Conference, pp. 268-577,1991.
R.J. Lipton, J.F. Naughton and D.A. Schneider, “Practical Selectivity Estimation Through Adaptive Sampling.” In Proceedings of the ACM SIGMOD Conference, pp. 1-11, 1990.
L.F. Macket and G.M. Lohman, “R* Optimizer Validation and Performance Evaluation for Local Queries.” In Proceedings of the ACM SIGMOD Conference, pp. 84-95, 1986.
Y. Matias, J.S. Vitter, and M. Wang, “Wavelet-Based Histograms for Selectivity Estimation.” In Proceedings of the ACM SIGMOD Conference, pp. 448-459, 1998.
V. Poosala, Y.E. Ioannidis, P.J. Haas and E.J. Shekita, “Improved Histograms for Selectivity Estimation.” In Proceedings of the ACM SIGMOD Conference, pp. 294-305.

Affiliated with

Also associated with

Rating

Query optimization by sub-plan memoization does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Query optimization by sub-plan memoization, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Query optimization by sub-plan memoization will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3729833