Delaying evaluation of expensive expressions in a query

Details Delaying evaluation of expensive expressions in a query Delaying evaluation of expensive expressions in a query

2011-01-25

2011-01-25

Le, Miranda (Department: 2159)

Data processing: database and file management or data structures

Database and file access

Query optimization

C707S719000, C707S999002

Reexamination Certificate

active

07877379

ABSTRACT:
Techniques are provided for delaying evaluation of expensive expressions in a query. Expensive expressions in the query are established by cost information or by looking up a list of known expensive expressions for a match. After an execution plan is determined by using the early evaluation technique, one or more equivalent execution plans is established. The one or more equivalent execution plans may include both a type of execution plans that delay evaluation of expensive expressions and a type of execution plans that do not. In addition, the one or more equivalent execution plans may include both parallelized and non-parallelized alternatives to the execution plan identified by the early evaluation technique. Finally, based on a set of criteria, which may include comparing cost information among all the equivalent execution plans generated thus far, the best execution plan is chosen for the query.

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: 5452468 (1995-09-01), Peterson
patent: 5495419 (1996-02-01), Rostoker et al.
patent: 5495605 (1996-02-01), Cadot
patent: 5495606 (1996-02-01), Borden et al.
patent: 5537588 (1996-07-01), Engelmann 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: 5590324 (1996-12-01), Leung 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: 5924088 (1999-07-01), Jakobsson et al.
patent: 5960427 (1999-09-01), Goel et al.
patent: 5963932 (1999-10-01), Jackobsson et al.
patent: 5974408 (1999-10-01), Cohen 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: 6061676 (2000-05-01), Srivastava et al.
patent: 6067542 (2000-05-01), Carino, Jr.
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: 6366934 (2002-04-01), Cheng 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: 6510422 (2003-01-01), Galindo-Legaria et al.
patent: 6529896 (2003-03-01), Leung et al.
patent: 6529901 (2003-03-01), Chaudhuri et al.
patent: 6622138 (2003-09-01), Bellamkonda et al.
patent: 6684203 (2004-01-01), Waddington et al.
patent: 6694306 (2004-02-01), Nishizawa et al.
patent: 6792420 (2004-09-01), Chen et al.
patent: 6799184 (2004-09-01), Bhatt et al.
patent: 6801905 (2004-10-01), Andrei
patent: 6832219 (2004-12-01), Lal
patent: 6901405 (2005-05-01), McCrady et al.
patent: 6915304 (2005-07-01), Krupa
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: 7024425 (2006-04-01), Krishnaprasad et al.
patent: 7089225 (2006-08-01), Li et al.
patent: 7146360 (2006-12-01), Allen et al.
patent: 7246108 (2007-07-01), Ahmed
patent: 7363289 (2008-04-01), Chaudhuri et al.
patent: 7440935 (2008-10-01), Day 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/0055814 (2003-03-01), Chen et al.
patent: 2003/0140308 (2003-07-01), Murthy et al.
patent: 2003/0167258 (2003-09-01), Koo et al.
patent: 2004/0220911 (2004-11-01), Zuzarte et al.
patent: 2005/0010896 (2005-01-01), Meliksetian et al.
patent: 2005/0033730 (2005-02-01), Chaudhuri 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-08-01), Cunningham et al.
patent: 2005/0210010 (2005-09-01), Larson et al.
patent: 2005/0283471 (2005-12-01), Ahmed
patent: 2006/0041537 (2006-02-01), Ahmed
patent: 2006/0167865 (2006-07-01), Andrei
patent: 2006/0218123 (2006-09-01), Chowdhuri et al.
patent: 2007/0027880 (2007-02-01), Dettinger et al.
patent: 2007/0038649 (2007-02-01), Agrawal et al.
patent: 2007/0073642 (2007-03-01), Ghosh et al.
patent: 2007/0073643 (2007-03-01), Ghosh et al.
patent: 2008/0189302 (2008-08-01), Evani
patent: 2008/0243916 (2008-10-01), Liu
patent: 2009/0055349 (2009-02-01), Ahmed
German Patent Office, “Office Action,” GR App. No. P4479320.9-53, dated Dec. 22, 2005 (5 pages), with English translation (4 pages).
Current Claims, GR App. No. P4479320.9-53, 9 pages (attached).
Borla-Salamet, Pascale, “Compiling Control into Database Queries for Parallel Execution Management,” IEEE Conference on Parallel Distributed Information Systems, 1991, ISBN 0-8186-2295-4, pp. 271-279.
Bergsten, et al., “Prototyping DBS3 a Shared-Memory Parallel Database System”,IEEE, 226-234, 1991.
Bhide, Anupam “An Analysis of Three Transaction Processing Architectures”, Computer Science Division, UC Berkeley, 1998, pp. 339-350.
Copeland, George et al., “Data Placement in Bubba,” MCC, 1988, pp. 99-108.
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, May 1989, pp. 1-23.
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.
Graefe, Goetz, “Encapsulation of Parallelism in the Volcano Query Processing System,” Mar. 1990, pp. 102-111.
Leverenz et al., “Oracle 8i Concepts Release 8.1.5”, Oracle Corporation, Feb. 1999, located on the internet at <http://www.csee.umbc.edu/help/oracle8/server.815/a67781/toc.htm>, 121 pages.
Stonebraker, Michael, et al. “The Design of XPRS,”, et al., EECS Department UC Berkeley, 1988, pp. 318-330.
Tandem, “A Benchmark of NonStop SQL on the Debit Credit Transaction”, The Tandem Performance Group, 1988, pp. 337-341.
Chaudhuri, Surajit et al., “Including Group-By in Query Optimization,” Proceedings of the 20thVLDB Conference—1994, pp. 354-366.
Galindo-Legaria, Cesar et al., “Outerjoin Simplification and Reordering for Query Optimization,” ACM Transactions on Database Systems, vol. 22, No. 1, Mar. 1997, pp. 43-74.
Erickson, Gail et al., “Improving Performance with SQL Server 2000 Indexed Views,” Microsoft TechNet, Sep. 2000, located on the internet at http://www.microsoft.com/technet/prodtechnol/sql/2000/maintain/indexvw.mspx?pf=true, retrieved on Nov. 11, 2006, 14 pages.
Mishra, Priti et al., “Join Processing in Relational Databases,” ACM Computing Surveys, vol. 24, No. 1, Mar. 1992, pp. 63-113.
Muralikrishna, M., “Improved Unnesting Algorithms for Join Aggregate SQL Queries,” Proceedings of the 18thVLDB Conference—1992, pp. 91-102.
Seshadri, Preveen, “Cost-Based Optimization for Magic: Algebra and Implementation,” Sigmond '96, 1996 ACM 0-89791-794-4, pp. 435-446.
Deu

Affiliated with

Also associated with

Rating

Delaying evaluation of expensive expressions in a query does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Delaying evaluation of expensive expressions in a query, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Delaying evaluation of expensive expressions in a query will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-2727700