Data processing: database and file management or data structures – Database design – Data structure types
Reexamination Certificate
2005-09-27
2009-11-10
Fleurantin, Jean B. (Department: 2162)
Data processing: database and file management or data structures
Database design
Data structure types
C707S793000, C707S793000, C707S793000, C707S793000, C707S793000
Reexamination Certificate
active
07617189
ABSTRACT:
Various techniques are described for processing database commands that include MINUS and/or INTERSECT operators. According to one technique, the database server executes the MINUS/INTERSECT in a specialized rowsource in parallel. In one approach, the specialized rowsource implements a sort merge-join like solution, where: a DISTINCT SORT is performed on each input, a left and right pointer is maintained on the respective input streams of tuples, the left or right pointer is incremented based on whether there is a match between the tuples pointed-to by the pointers, and the tuple of the left side is returned (or not returned) based on whether there is a match. Techniques are described for generating multiple query plans for executing a query, where each of the query plans includes a plan portion for executing, in parallel, the operation associated with a MINUS/INTERSECT operator. Cost estimates are generated for the query plans. The database server selects from the query plans a particular query plan to execute based, at least in part, on the cost estimates.
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: 5437032 (1995-07-01), Wolf 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: 5675791 (1997-10-01), Bhide et al.
patent: 5710915 (1998-01-01), McElhiney
patent: 5822748 (1998-10-01), Cohen et al.
patent: 5832477 (1998-11-01), Bhargava et al.
patent: 5848408 (1998-12-01), Jakobsson 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: 5974408 (1999-10-01), Cohen et al.
patent: 6067542 (2000-05-01), Carino, Jr.
patent: 6289334 (2001-09-01), Reiner et al.
patent: 6370524 (2002-04-01), Witkowski
patent: 6438558 (2002-08-01), Stegelmann
patent: 6438562 (2002-08-01), Gupta et al.
patent: 6510422 (2003-01-01), Galindo-Legaria et al.
patent: 6535874 (2003-03-01), Purcell
patent: 6615203 (2003-09-01), Lin et al.
patent: 6618719 (2003-09-01), Andrei
patent: 6622138 (2003-09-01), Bellamkonda et al.
patent: 6665664 (2003-12-01), Paulley et al.
patent: 6684203 (2004-01-01), Waddington et al.
patent: 6792420 (2004-09-01), Stephen Chen et al.
patent: 6801905 (2004-10-01), Andrei
patent: 6941360 (2005-09-01), Srivastava et al.
patent: 7146360 (2006-12-01), Allen et al.
patent: 7467128 (2008-12-01), Larson et al.
patent: 2002/0038313 (2002-03-01), Klein et al.
patent: 2003/0055814 (2003-03-01), Chen et al.
patent: 2003/0120825 (2003-06-01), Avvari et al.
patent: 2004/0220923 (2004-11-01), Nica
patent: 2005/0033730 (2005-02-01), Chaudhuri 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/0198013 (2005-09-01), Cunningham 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/0073643 (2007-03-01), Ghosh et al.
patent: 2007/0192283 (2007-08-01), Larson et al.
Xumin et al., “Using parallel semi-join reduction to minimize distributed query response time”, Algorithms and Architectures for Parallel Processing, 1995. Apr. 19-21, 1995. vol. 2;p. 517-526. Download: http://ieeexplore.ieee.org/stamp/stamp.jsp?arnumber=00472236.
Srivastava et al., “Optimizing multi-joint queries in parallel relational databases”, Parallel and Distributed Information Systems, 1993., Jan. 20-22, 1993. p. 84-92. Download: http://ieeexplore.ieee.org/stamp/stamp.jsp?arnumber=00253067.
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.
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.
Bride, 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.
Chen, et al., “View merging in the context of view selection changing”, Database Engineering and Applications Symposium 2002, Proceedings, Jul. 2002, 10 pages.
Ahmed Rafi
Baer Hermann
Ghosh Bhaskar
Fleurantin Jean B.
Hickman Palermo & Truong & Becker LLP
Jami Hares
Oracle International Corporation
LandOfFree
Parallel query processing techniques for minus and intersect... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Parallel query processing techniques for minus and intersect..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Parallel query processing techniques for minus and intersect... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-4069894