Iterative dynamic programming system for query optimization with

Details Iterative dynamic programming system for query optimization with Iterative dynamic programming system for query optimization with

1994-12-30

1997-09-23

Black, Thomas G.

395602, 395604, 395605, 395611, G06F 1730

Patent

active

056714033

ABSTRACT:
A query optimizer for optimizing join queries in a relational database system by iterative application of dynamic programming (DP) to select optimal subgraph join execution plans. Unlike traditional DP optimization methods, bounds on search space time and space complexity can be established and adjusted by imposing a subgraph threshold. Each bounded subgraph is selected using a greedy heuristic (GH) hill-climbing procedure or other similarly useful technique to build a low-cost execution plan. The low-cost GH subgraph execution plan is then discarded in favor of an optimal DP subgraph execution plan selected by a dynamic programming optimizer for each subgraph identified by the bounded GH optimization process. The complexity bound may be dynamically tuned to improve execution plan quality responsive to changes in query complexity.

REFERENCES:
patent: 4769772 (1988-09-01), Dwyer
patent: 4829427 (1989-05-01), Green
patent: 5043872 (1991-08-01), Cheng et al.
patent: 5067166 (1991-11-01), Ito
patent: 5241648 (1993-08-01), Cheng et al.
patent: 5276870 (1994-01-01), Shan et al.
patent: 5301317 (1994-04-01), Lohman et al.
patent: 5345585 (1994-09-01), Iyer et al.
patent: 5367675 (1994-11-01), Cheng et al.
patent: 5412806 (1995-05-01), Du et al.
patent: 5469568 (1995-11-01), Schiefer et al.
patent: 5495605 (1996-02-01), Cadot
patent: 5542073 (1996-07-01), Schiefer et al.
patent: 5544355 (1996-08-01), Chaudhuri et al.
patent: 5548758 (1996-08-01), Pirahesh et al.
patent: 5574900 (1996-11-01), Huang et al.
patent: 5608904 (1997-03-01), Chaudhuri et al.
patent: 5615361 (1997-03-01), Leung et al.
W. Hong et al., "Optimization of Parallel Query Execution Plans in XPRS", Distributed and Parallel Databases, vol. 1, No. 1, pp. 9-32, Jan. 1993.
K. Ono et al., "Measuring the Complexity of Join Enumeration in Query Optimization", Proceedings of the 16th VLDB Conference, Brisbane, Australia, Aug. 1990, pp. 314-325.
P. Selinger et al., "Access Path Selection in a Relational Database Management System", Proc. of the 1979 Assoc. of Comp. Mach.(ACM) SIGMOD Intl Conf. On Management of Data, Boston, MA, Jun. 1979, pp. 23-24.
A. Swami, "Optimization of Large Join Queries: Combining Heuristics and Combinatorial Techniques", Proc. of 1989 ACM-SIGMOD Intl Conf. of Management of Data, Portland, Oregon, Jun. 1989, pp. 367-376.
Y. Ioannidis et al., "Randomized Algorithms for Optimizing Large Join Queries", Proc. of the 1990 ACM-SIGMOD Intl Conf. on Management of Data, Atlantic City, NJ, May 1990, pp. 312-321.
Y. Ioannidis et al., "Query Optimization by Simulated Annealing", Proc. of the 1987 ACM-SIGMOD Conf. on Management of Data, San Francisco, CA, May 1987, pp. 9-22.
A. Shibamiya et al., "DB2 Cost Formula", IBM Technical Disclosure Bulletin, vol. 34, No. 12, May 1992, pp. 389-394.
D. Cornell et al., "Integrated Buffer Management and Query Optimization Strategy for Relational Databases", IBM Technical Disclosure Bulletin, vol. 32, No. 12, May 1990, pp. 253-257.
E. Omiecinski, "Heuristics for Join Processing Using Nonclustered Indexes", IEEE Trans. on Software Engineering, vol. 15, No. 1, Jan. 1989, pp. 18-25.
S. Lee et al., "Semantic Query Reformulation in Deductive Databases", IEEE Proc. of the 7th Intl Conf. on Data Engr., Koby, Japan, Apr. 1991, pp. 232-239.
M. Shan et al., "Method of Evaluating a Recursive Query of a Database", World Intellectual Property Organization, Publication No. WO92/15066, Sep. 1992.
R. Kabler et al., "Performance Evaluation of Algorithms for Transitive Closure", Information Systems, vol. 17, No. 5, Sep. 1992, pp. 415-441.
S. Chi et al., "Recursive Query Answering with Non-Horn Clauses", Proc. of the 9th Intl. Conf. on Automated Deduction, Argonne, ILL, May 1988, pp. 294-313.
S. Pramanik et al., "Optimizing Join Queries in Distributed Databases", IEEE Trans. On Software Engr., vol. 14, No. 9, pp. 1319-1326, Sep. 1988.
A. Chen et al., "Properties of Optimal Semi-join Programs for Distributed Query Processing", Proc. of the IEEE Comp. Soc., 7th Intl. Comp. Sofware and Appls. Conf., Chicago, Ill. Nov. 1983, pp. 476-483.
M. Chen et al., "Using Join Operations as Reducers in Distributed Query Processing", Proc. 2nd Intl. Sym. on Databases in Parallel and Distributed Systems, Dublin, Ireland, Jul. 1990, abstract only.
D. Cornell et al., "Integrated Site Assignment for Relations and Join Operations in Distributed Transaction Processing", IBM Technical Disclosure Bulletin, vol. 32, No. 4A, Sep. 1989, pp. 306-314.

Affiliated with

Also associated with

Rating

Iterative dynamic programming system for query optimization with does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Iterative dynamic programming system for query optimization with, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Iterative dynamic programming system for query optimization with will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-1942166