System and methodology for cost-based subquery optimization...

Details System and methodology for cost-based subquery optimization... System and methodology for cost-based subquery optimization...

2004-04-28

2009-11-10

Jalil, Neveen Abel (Department: 2165)

Data processing: database and file management or data structures

Database design

Data structure types

Reexamination Certificate

active

07617179

ABSTRACT:
A system providing methodology for cost-based enumeration of subqueries using a left-deep tree join enumeration algorithm is described. In one embodiment, for example, in a database system, a method of the present invention is described for optimizing a database query, the method comprises steps of: receiving a database query including at least one subquery; building a query optimization graph for each query block of the database query, the query optimization graph including plan nodes representing subqueries of each query block; generating a set of access methods and join methods for each plan node, including generating at least one access method for a subquery quantifier based on subquery type and semantic properties of the database query; determining an optimal access plan for each query block based upon selecting access methods, join methods, and join order for plan nodes of the query optimization graph having favorable execution costs; and constructing a detailed access plan for execution of the database query based upon the optimal access plan determined for each query block.

REFERENCES:
patent: 5694591 (1997-12-01), Du et al.
patent: 2004/0006561 (2004-01-01), Nica
patent: 2004/0030677 (2004-02-01), Young-Lai
patent: 2004/0220923 (2004-11-01), Nuac
Bowman et al., “Join Enumeration in a Memory-Constrained Environment”, Proceedings, 16th IEEE Data Engineering Conference, San Diego, California; Mar. 2000.
Ramakrishnan et al. “Database Management Systems Third Edition” McGraw Hill Press, 2003 pp. 107-109, 151-153, 479-483, 488, 492, 496-497, 502, 504, and 506-507.
Chu et al., “Least Expected Cost Query Optimization: An Exercise in Utility”, SIGMOD; 1999.
Kabra et al., “Opt++: An object-oriented implementation for extensible database query optimization”, The VLDB Journal 1999, vol. 8, pp. 55-78.
Ramakrishnan et al., “Database Management Statems Thrid Edition” McGraw-Hill Press, 2003, pp. 107-109, 151-153, Sections 14 (pp. 441-472), 15 (pp. 479-507).
Steinebrunn, M. et al, Heuristic and Randomized Optimization for the Join Ordering Problem, VLDB Journal, vol. 6; 191-208, 1997.
Vance, B. et al, Rapid Bushy Join-Order Optimization with Cartesian Products, Proceedings of ACM SIGMOD Conference of Management of Data, pp. 35-46, Jun. 1996.
Cluet, S. et al, On the Complexity of Generating Optimal Left-Deep Processing Trees with Cross Products, Proceedings of the Fifth International Conference on Database Theory, pp. 54-67, Jan. 1995.
Galindo-Legaria, C., Uniformly-Distributed Random Generation of Join Orders, Proceedings of the International Conference on Database Theory, pp. 280-293, Jan. 1995.
Galindo-Legaria, C. et al, Fast, Randomized Join-order Selection—Why Use Transformations?, Proceedings of the International Conference on Very Large Data Bases, pp. 85-95, Sep. 1994.
Swami, A. et al, A Polynomial Time Algorithm for Optimizing Join Queries, Proceedings of the IEEE Conference of Data Engineering, pp. 345-354, Apr. 1993.
Ono, K. et al, Measuring the Complexity of Join Enumeration in Query Optimization, Proceedings of the 16th International Conference on Very Large Data Bases, pp. 314-325, Aug. 1990.
Ioannidis, Y.E. et al, Randomized Algorithms for Optimizing Large Join Queries, Proceedings of ACM SIGMOD Conference of Management of Data, pp. 312-321, Apr. 1990.
Swami, A., Optimization of Large Join Queries: Combining Heuristics and Combinatorial Techniques, Proceedings of ACM SIGMOD Conference of Management of Data, pp. 367-376, May 1989.
Swami, A. et al, Optimization of Large Join Queries, Proceedings of ACM SIGMOD Conference of Management of Data, pp. 8-17, May 1988.
Krishnamurthy, R. et al, Optimization of Non-recursive Queries, Proceedings of the 12th International Conference on Very Large Data Bases, pp. 128-137, Aug. 1986.
Ibaraki, T. et al, On the Optimal Nesting Order for Computing N-Relational Joins, ACM Transaction on Database Systems, vol. 9: pp. 482-502, Sep. 1984.
Selinger, P.G. et al, Access Path Selection in a Relational Database Management System, Proceedings of ACM SIGMOD Conference of Management of Data, pp. 23-34, May 1979.
Wong, E. et al, Decomposition—a Strategy for Query Processing, ACM Transaction on Database Systems, 1(3): pp. 223-241, Sep. 1976.

Affiliated with

Also associated with

Rating

System and methodology for cost-based subquery optimization... does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with System and methodology for cost-based subquery optimization..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and System and methodology for cost-based subquery optimization... will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-4118967