Query optimization by sub-plan memoization

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

2005-02-01

2005-02-01

Robinson, Greta (Department: 2177)

Data processing: database and file management or data structures

Database design

Data structure types

C707S793000

Reexamination Certificate

active

06850925

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: 5930785 (1999-07-01), Lohman et al.
patent: 6021405 (2000-02-01), Celis et al.
patent: 6275818 (2001-08-01), Subramanian et al.
patent: 6330552 (2001-12-01), Farrar et al.
patent: 6353818 (2002-03-01), Carino, Jr.
patent: 6438741 (2002-08-01), Al-omari et al.
Robert Philip Kooi, Booklet “The Optimization of Queries in Relational Databases”, Case Western Reserve University, 1980.
V. Poosala and Y. Ioannids, “Selectivity Estimation Without the Attribute Value Independence Assumption”, Proceedings of the 23rd VLDB Conference, Athens, Greece, 1997.

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-3450853