Data processing: database and file management or data structures – Database design – Data structure types
Reexamination Certificate
2005-12-27
2005-12-27
Corrielus, Jean M. (Department: 2162)
Data processing: database and file management or data structures
Database design
Data structure types
C707S793000, C707S793000, C707S793000, C707S793000, C707S793000
Reexamination Certificate
active
06980981
ABSTRACT:
Provided are a method, system, and program for selecting a join order for tables subject to a join operation. An estimation is made of a join cost to perform joins on permutations of at least two of the tables, wherein each join permutation indicates an order of joining the tables. A determination is made as to whether sufficient computational resources are available to perform a join cost analysis of further join permutations of the tables. If sufficient computational resources are not available, then a determination is made of a restricted subset of remaining join permutations of at least two of the tables for which join costs have not been estimated that is less than all the remaining join permutations. The join costs of permutations of tables in the restricted subset is estimated and the estimated join costs are used to select one join permutation of all the tables having a lowest estimated join cost.
REFERENCES:
patent: 5301317 (1994-04-01), Lohman et al.
patent: 5335345 (1994-08-01), Frieder et al.
patent: 5600829 (1997-02-01), Tsatalos et al.
patent: 5870747 (1999-02-01), Sundaresan
patent: 6009265 (1999-12-01), Huang et al.
patent: 6240427 (2001-05-01), Szalwinski et al.
patent: 6330552 (2001-12-01), Farrar et al.
patent: 6353818 (2002-03-01), Carino, Jr.
U.S. Appl. No. 09/340,084, filed Jun. 25, 1999, entitled “Method, System, and Program for Determining the Join Order of Tables in a Join Query”, inventors L-C.H. Liu, et al., now patented P.N. 06,397,204.
A. Swami, “Optimization of Large Join Queries”, ACM 0-89791-268-3/88/0066/0008, 1988, pp. 8-18.
A. Swami, “Optimization of Large Join Queries: Combining Heuristics and Combinatorial Techniques”, ACM0-89791-317-5/89/0005/0367, 1989, pp. 367-376.
S. Gangley, et al., “Query Optimization for Parallel Execution”, Rpt. No. HPL-92-93, Mar. 1992, pp22 (abstract).
M. Matysiak, “Efficient Optimization of Large Join Queries Using Tabu Search”, Information Sciences, vol. 83, No. 1-2, Mar. 1995, pp. 77-88 (abstract).
U.J. Langer, et al., “Join Sequence Optimization in Parallel Query Plans”, Proceedings 7thIntl. workshop on Database and Expert Systems Application, 1996, pp. 506-513 (abstract).
B. Vance, et al., “Rapid Bushy Join-Order Optimization with Cartesian Products”, SIGMOD Record, vol. 25, No. 2, Jun. 1996, pp. 35-46 (abstract).
K. Aberer, et al., “Rule-Based Generation of Logical Query Plans with Controlled Complexity”, Proceedings 5thIntl. Conference on Deductive and Object-Oriented Databases, 1997, pp. 399-416, (abstract).
L.M. Haas, et al., “Seeking the Truth About Ad Hoc Join Costs”, VLDB Journal, vol. 6, No. 3, Aug. 1997, pp. 241-256 (abstract).
S. Morishita, “Avoiding Cartesian Products for Multiple Joins”, Journal of the ACM, vol. 44, No. 1, Jan. 1997, pp. 57-85 (abstract).
W. Scheufele, et al., “Efficient Dynamic Programming Algorithms for Ordering Expensive Joins and Selections”, Proceedings 6thIntl. Conference on Extending Database technology, 1998, pp. 201-215 (abstract).
F. Carino, et al., “Plan-Per-Tuple Optimization Solution-Parallel Execution of Expensive User-Defined Functions”, Proceedings of the 24thIntl. Conference on Very-Large Databases, 1998, pp. 690-695 (abstract).
T. Lahiri, “Genetic Optimization Techniques for Large Join Queries”, Proceedings of 3rdAnnual Conference on Genetic Programming, 1998, pp. 535-542 (abstract).
K. Ono, et al., “Measuring the Complexity of Join Enumeration in Query Optimization”, 16thIntl. Conference on Very Large Data Bases, 1990, pp. 314-325 (abstract).
L. Popa, et al., “A Chase Too Far? Query Optimzation”, SIGMOD Record, vol. 29, No. 2, Jun. 2000, pp. 273-284 (abstract).
I.T. Bowman, et al., “Join Enumeration in a Memory-Constrained Environment”, Proceedings of 16thIntl. Conference on Data Engineering, 2000, pp. 645-654 (abstract).
Sousa, J.M., M. Setnes, and U. Kaymak, “Adaptive Decision Alternatives in Fuzzy Predictive Control”,Fuzzy Systems Proceedings, 1998. IEEE World Congress on Computational Intelligence., The 1998 IEEE International Conference on. May 4-9, 1998, vol. 1, pp. 698-703.
Beavin Thomas Abel
Fuh You-Chin
Sinnott, Jr. Joseph F.
Corrielus Jean M.
Konrad Raynes & Victor LLP
Victor David W.
Woo Isaac M.
LandOfFree
Method, system, and program for selecting a join order for... 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, system, and program for selecting a join order for..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method, system, and program for selecting a join order for... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3500667