Data processing: database and file management or data structures – File or database maintenance – Synchronization
Reissue Patent
2011-08-30
2011-08-30
Mahmoudi, Tony (Department: 2169)
Data processing: database and file management or data structures
File or database maintenance
Synchronization
C707S999003, C707S999008, C707S999100, C709S200000, C718S100000
Reissue Patent
active
RE042664
ABSTRACT:
The present invention implements parallel processing in a Database Management System. The present invention provides the ability to locate transaction and recovery information at one location and eliminates the need for read locks and two-phased commits. The present invention provides the ability to dynamically partition row sources for parallel processing. Parallelism is based on the ability to parallelize a row source, the partitioning requirements of consecutive row sources and the entire row source tree, and any specification in the SQL statement. A Query Coordinator assumes control of the processing of a entire query and can execute serial row sources. Additional threads of control, Query Server, execute a parallel operators. Parallel operators are called data flow operators (DFOs). A DFO is represented as structured query language (SQL) statements and can be executed concurrently by multiple processes, or query slaves. A central scheduling mechanism, a data flow scheduler, controls a parallelized portion of an execution plan, and can become invisible for serial execution. Table queues are used to partition and transport rows between sets of processes. Node linkages provide the ability to divide the plan into independent lists that can each be executed by a set of query slaves. The present invention maintains a bit vector that is used by a subsequent producer to determine whether any rows need to be produced to its consumers. The present uses states and a count of the slaves that have reached these states to perform its scheduling tasks.
REFERENCES:
patent: 4414624 (1983-11-01), Summer et al.
patent: 4769772 (1988-09-01), Dwyer
patent: 4829427 (1989-05-01), Green
patent: 4937777 (1990-06-01), Flood et al.
patent: 5091852 (1992-02-01), Tsuchida et al.
patent: 5193189 (1993-03-01), Flood et al.
patent: 5253171 (1993-10-01), Hsiao et al.
patent: 5257372 (1993-10-01), Furtney et al.
patent: 5307485 (1994-04-01), Bordonaro et al.
patent: 5325525 (1994-06-01), Shan et al.
patent: 5339429 (1994-08-01), Tanaka et al.
patent: 5402350 (1995-03-01), Kline
patent: 5442569 (1995-08-01), Osano
patent: 5448732 (1995-09-01), Matsumoto
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: 5551027 (1996-08-01), Choy et al.
patent: 5574900 (1996-11-01), Huang et al.
patent: 5590319 (1996-12-01), Cohen et al.
patent: 5602754 (1997-02-01), Beatty 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: 5857180 (1999-01-01), Hallmark et al.
patent: 5918225 (1999-06-01), White et al.
patent: 6009265 (1999-12-01), Huang et al.
patent: 6289334 (2001-09-01), Reiner et al.
patent: 6311265 (2001-10-01), Beckerle et al.
patent: 6427154 (2002-07-01), Kolodner et al.
patent: 6430550 (2002-08-01), Leo et al.
patent: 6430580 (2002-08-01), Azagury et al.
patent: 6438558 (2002-08-01), Stegelmann
patent: 6438562 (2002-08-01), Gupta et al.
patent: 6684203 (2004-01-01), Waddington et al.
patent: 6687798 (2004-02-01), Thusoo et al.
patent: 6711560 (2004-03-01), Levy et al.
patent: 6901405 (2005-05-01), McCrady et al.
patent: 6941360 (2005-09-01), Srivastava 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: 2002/0038313 (2002-03-01), Klein et al.
patent: 2002/0138376 (2002-09-01), Hinkle
patent: 2002/0143746 (2002-10-01), Levy et al.
patent: 2005/0283471 (2005-12-01), Ahmed
patent: 2006/0041537 (2006-02-01), Ahmed
Hongjun Lu, Kian-Lee Tan, “Dynamic and Load-balanced Task-Oriented Database Query Processing in Parallel Systems”,1992, Springer Berlin / Heidelberg, “Advances in Database Technology—EDBT '92”; pp. 357-372.
Goetz Graefe, “Encapsulation of Parallelism in the Volcano Query Processing System,” Mar. 1990, pp. 102-111.
Bergsten, et al., Prototyping DBS3 a Shared-Memory Parallel Database System, IEEE, 226-234, 1991.
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.
“An Analysis of Three Transaction Processing Architectures” Anupam Bhide, Computer Science Division, UC Berkeley, 1988, pp. 339-350.
“A Benchmark of NonStop SQL Release 2 Demonstrating Near-Linear Speedup and Scaleup on Large Databases”, Susan Englert, et al, Technical Report 89.4, May 1989, pp. 1-23.
“A Benchmark of NonStop SQL on the Debit Credit Transaction”, The Tandem Performance Group, 1988, pp. 337-341.
“Data Placement in Bubba”, George Copeland, et al., MCC, 1988, pp. 99-108.
“The Design of XPRS”, Michael Stonebraker, et al., EECS Department UC Berkeley, 1988, pp. 318-330.
“A Performance Analysis of the Gamma Database Machine”, DeWitt, et al., Computer Sciences Department, University of Wisconsin, 1988, pp. 350-360.
German Patent and Trademark Office, “Attorney/Client Communication Privileged and Confidential”, translation attached, Appliciation No. P4497320.9, dated Apr. 25, 2007, 18 pages.
Claims, App. No. PCT/US94/10092, 4 pages.
Rahm, Erhard, et al., “Analysis of Dynamic Load Balancing Strategies for Parallel Shared Nothing Database Systems”, Proceedings of the 19thVLDB Conference, 1993, printed Apr. 25, 2007, pp. 182-193.
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.
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.
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.
Hong et al, Optimization of Parallel Query Execution Plans in XPRS, IEEE, pp. 218-225, 1991.
“Encapsulation of Parallelism In the Volcano Query Processing System”, Goetz Graefe, Computer Science, University of Colorado, Mar. 1990, pp. 102-111.
Hallmark Gary
Leary Daniel
Hickman Palermo & Truong & Becker LLP
Mahmoudi Tony
Oracle International Corporation
Truong Dennis
LandOfFree
Method and apparatus for implementing parallel operations in... 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 and apparatus for implementing parallel operations in..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for implementing parallel operations in... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2667920