Data processing: database and file management or data structures – Database and file access – Query optimization
Reexamination Certificate
2007-03-08
2010-10-05
Le, Debbie (Department: 2168)
Data processing: database and file management or data structures
Database and file access
Query optimization
Reexamination Certificate
active
07809713
ABSTRACT:
Under a type of query transformation referred to herein as join factorization, the branches of an UNION/UNION ALL query that join a common table are combined to reduce accesses to the common table. The transformation can be expressed as (T1join T2) union all (T1join T3)=T1join (T2union all T3), where T1, T2and T3are three tables. A given query may be rewritten in many alternate ways using join factorization. Evaluating each alternative can be expensive. Therefore, the alternatives are generated and evaluated in a way that minimizes the cost of evaluating the alternatives.
REFERENCES:
patent: 4769772 (1988-09-01), Dwyer
patent: 4829427 (1989-05-01), Green
patent: 5091852 (1992-02-01), Tsuchida et al.
patent: 5325525 (1994-06-01), Shan et al.
patent: 5339429 (1994-08-01), Tanaka et al.
patent: 5412804 (1995-05-01), Krishna
patent: 5437032 (1995-07-01), Wolf et al.
patent: 5452468 (1995-09-01), Peterson
patent: 5495419 (1996-02-01), Rostoker et al.
patent: 5495606 (1996-02-01), Borden et al.
patent: 5537588 (1996-07-01), Engelmann et al.
patent: 5548755 (1996-08-01), Leung et al.
patent: 5551027 (1996-08-01), Choy et al.
patent: 5574900 (1996-11-01), Huang et al.
patent: 5590319 (1996-12-01), Cohen et al.
patent: 5642515 (1997-06-01), Jones et al.
patent: 5675791 (1997-10-01), Bhide et al.
patent: 5680547 (1997-10-01), Chang
patent: 5710915 (1998-01-01), McElhiney
patent: 5787251 (1998-07-01), Hamilton et al.
patent: 5797136 (1998-08-01), Boyer et al.
patent: 5822748 (1998-10-01), Cohen et al.
patent: 5832477 (1998-11-01), Bhargava et al.
patent: 5857180 (1999-01-01), Hallmark et al.
patent: 5905981 (1999-05-01), Lawler
patent: 5918225 (1999-06-01), White et al.
patent: 5960427 (1999-09-01), Goel et al.
patent: 5963932 (1999-10-01), Jakobsson et al.
patent: 6009265 (1999-12-01), Huang et al.
patent: 6021405 (2000-02-01), Celis et al.
patent: 6026394 (2000-02-01), Tsuchida et al.
patent: 6044378 (2000-03-01), Gladney
patent: 6061676 (2000-05-01), Srivastava et al.
patent: 6289334 (2001-09-01), Reiner et al.
patent: 6298342 (2001-10-01), Graefe et al.
patent: 6339768 (2002-01-01), Leung et al.
patent: 6370524 (2002-04-01), Witkowski
patent: 6430550 (2002-08-01), Leo et al.
patent: 6438558 (2002-08-01), Stegelmann
patent: 6438562 (2002-08-01), Gupta et al.
patent: 6529896 (2003-03-01), Leung et al.
patent: 6529901 (2003-03-01), Chaudhuri et al.
patent: 6535874 (2003-03-01), Purcell
patent: 6684203 (2004-01-01), Waddington et al.
patent: 6694306 (2004-02-01), Nishizawa et al.
patent: 6708179 (2004-03-01), Arora
patent: 6792420 (2004-09-01), Chen et al.
patent: 6901405 (2005-05-01), McCrady et al.
patent: 6934699 (2005-08-01), Haas et al.
patent: 6941360 (2005-09-01), Srivastava et al.
patent: 6947927 (2005-09-01), Chaudhuri et al.
patent: 6954776 (2005-10-01), Cruanes et al.
patent: 6961729 (2005-11-01), Toohey et al.
patent: 6980988 (2005-12-01), Demers et al.
patent: 6990503 (2006-01-01), Luo et al.
patent: 7031956 (2006-04-01), Lee et al.
patent: 7072896 (2006-07-01), Lee et al.
patent: 7089225 (2006-08-01), Li et al.
patent: 7107255 (2006-09-01), Kiernan et al.
patent: 7167852 (2007-01-01), Ahmed et al.
patent: 7188098 (2007-03-01), Chen et al.
patent: 7246108 (2007-07-01), Ahmed
patent: 7363289 (2008-04-01), Chaudhuri et al.
patent: 7383256 (2008-06-01), Larson et al.
patent: 7440937 (2008-10-01), Kiernan et al.
patent: 7467152 (2008-12-01), Kearsey et al.
patent: 7587383 (2009-09-01), Koo et al.
patent: 2001/0047372 (2001-11-01), Gorelik et al.
patent: 2002/0038313 (2002-03-01), Klein et al.
patent: 2002/0138376 (2002-09-01), Hinkle
patent: 2003/0120825 (2003-06-01), Avvari et al.
patent: 2004/0068509 (2004-04-01), Garden et al.
patent: 2004/0068696 (2004-04-01), Seyrat et al.
patent: 2004/0143791 (2004-07-01), Ito et al.
patent: 2004/0148278 (2004-07-01), Milo et al.
patent: 2004/0153435 (2004-08-01), Gudbjartsson et al.
patent: 2004/0220911 (2004-11-01), Zuzarte et al.
patent: 2004/0220923 (2004-11-01), Nica
patent: 2004/0267760 (2004-12-01), Brundage et al.
patent: 2004/0268305 (2004-12-01), Hogg et al.
patent: 2005/0055382 (2005-03-01), Ferrat et al.
patent: 2005/0076018 (2005-04-01), Neidecker-Lutz
patent: 2005/0149584 (2005-07-01), Bourbonnais et al.
patent: 2005/0187917 (2005-08-01), Lawande et al.
patent: 2005/0198013 (2005-09-01), Cunningham et al.
patent: 2005/0234965 (2005-10-01), Rozenshtein et al.
patent: 2005/0278289 (2005-12-01), Gauweiler et al.
patent: 2005/0278616 (2005-12-01), Eller
patent: 2005/0283471 (2005-12-01), Ahmed
patent: 2005/0289125 (2005-12-01), Liu et al.
patent: 2006/0026115 (2006-02-01), Ahmed
patent: 2006/0026133 (2006-02-01), Ahmed
patent: 2006/0041537 (2006-02-01), Ahmed
patent: 2006/0047638 (2006-03-01), Dettinger et al.
patent: 2006/0167865 (2006-07-01), Andrei
patent: 2006/0168513 (2006-07-01), Coulson et al.
patent: 2007/0043697 (2007-02-01), Driesch et al.
patent: 2007/0044012 (2007-02-01), Suver et al.
patent: 2007/0185833 (2007-08-01), Turkel et al.
patent: 2008/0010240 (2008-01-01), Zait
patent: 2008/0077606 (2008-03-01), Fang et al.
Bergsten, et al., “Prototyping DBS3 a Shared-Memory Parallel Database System”, IEEE 818622954, 226-234, 1991, pp. 226-234.
Bhide, Anupam, “An Analysis of Three Transaction Processing Architectures”, Computer Science Division, UC Berkeley, Proceeding of the 14thVLDB Conference,1998, pp. 339-350.
Copeland, George et al., “Data Placement in Bubba,” ACM 0897912683, 1988, pp. 99-108.
Dayal, Umeshwar, “Of Nests and Trees: A Unified Approach to Processing Queries That Contain Nested Subqueries, Aggregates and Quantifiers”, Proceedings of the 13thVLDB Conference, Brighton 1987, pp. 197-208.
Dewitt, et al., “A Performance Analysis of the Gamma Database Machine,” Computer Sciences Department, University of Wisconsin, 1988, pp. 350-360.
Englert, Susan et al., “A Benchmark of Nonstop SQL Release 2 Demonstrating Near-Linear Speedup and Scaleup on Large Databases”, Technical Report 89.4, Tandem Part No. 27469, May 1989, pp. 1-23.
Graefe, Goetz, “Encapsulation of Parallelism in the Volcano Query Processing System,” Mar. 1990, pp. 102-111.
Hirano, et al., “Load Balancing Algorithm for Parallel Processing on Shared Memory Multiprocessor”, IEEE, pp. 210-217, 1991.
Hong, et al., “Optimization of Parallel Query Execution Plans in XPRS”, Proceedings of the First International Conference on Parallel and Distributed Information Systems, IEEE, 1991, pp. 218-225.
Leverenz et al., “Oracle 8i Concepts Release 8.1.5- A67781-01”, Oracle Corporation, Feb. 1999, located on the internet at <http://www.csee.umbc.edu/help/oracle8/server.815/a67781/toc.htm>, 122 pages.
Lumpkin, George et al., “Query Optimization in Oracle 9/”, Oracle Corporation, Oracle White Paper, Feb. 2002, pp. 1-30.
Pirahesh, Hamid, et al., “Extensible/Rule Base Query Rewrite Optimization in Starburst”, IBM Almaden Research Center, 9 Pages.
Selinger, P. Griffiths, et al., “Access Path Selection in a Relational Database Management System”, Proceedings of the 1979 ACM SIGMOD International Conference on the Management of Data, 1979, pp. 23-34.
Stonebraker, Michael, et al. “The Design of XPRS,” Proceedings of the 14thVLDB Conference, 1988, pp. 318-330.
Tandem, “A Benchmark of NonStop SQL on the Debit Credit Transaction”, The Tandem Performance Group, 1988, pp. 337-341.
Ahmed, Rafi, et al., “Cost-Based Query Transformation in Oracle,” Copyright 2006 VLDB, ACM 1595933859, pp. 1026-1036.
Oracle, “Oracle 9I Database Documentation”, Oracle, Parts A96670-01, A96674-01, A96673-02, 2002, 833 pages.
Fitzgerald et al., “Special Edition Using Crystal Reports IO”, Que, Chapters 23, 24, 27, 35, Appendix A, Jul. 14, 2004, 170 pages.
Rankins et al., “Microsoft SQL Server 2000 Unleashed,” Second Edition, Sams, Chapters 3, 4, 5, 6, 36, Dec. 18, 2002, 109 pages.
Erickson, Gail, “Improving Performance with SQL S
Ahmed Rafi
Lee Allison
Su Hong
Zait Mohamed
Hickman Palermo & Truong & Becker LLP
Le Debbie
Oracle International Corporation
LandOfFree
Efficient search space analysis for join factorization does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Efficient search space analysis for join factorization, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Efficient search space analysis for join factorization will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-4194549