Method and apparatus for performing hash join

Details Method and apparatus for performing hash join Method and apparatus for performing hash join

2006-08-01

2006-08-01

Wong, Leslie (Department: 2164)

Data processing: database and file management or data structures

Database design

Data structure types

C707S793000

Reexamination Certificate

active

07085769

ABSTRACT:
A parallel hash ripple join algorithm partitions tuples of two relations for localized processing. The algorithm is non-blocking and may be performed in a parallel, multi-processor environment. At each processing node, the tuples are further partitioned such that join operations may be performed as tuples are redistributed to each node during the partitioning.

REFERENCES:
patent: 4930072 (1990-05-01), Agrawal et al.
patent: 5551031 (1996-08-01), M. Cheng et al.
patent: 5557791 (1996-09-01), Cheng et al.
patent: 5613142 (1997-03-01), Matsumoto
patent: 5745896 (1998-04-01), Vijaykumar
patent: 5802357 (1998-09-01), Li et al.
patent: 5832475 (1998-11-01), Agrawal et al.
patent: 5854938 (1998-12-01), Ogi
patent: 5873074 (1999-02-01), Kashyap et al.
patent: 5884320 (1999-03-01), Agrawal et al.
patent: 5901324 (1999-05-01), Ogi
patent: 5983215 (1999-11-01), Ross et al.
patent: 6032144 (2000-02-01), Srivastava et al.
patent: 6061676 (2000-05-01), Srivastava et al.
patent: 6081801 (2000-06-01), Cochrane et al.
patent: 6112198 (2000-08-01), Lohman et al.
patent: 6205441 (2001-03-01), Al-omari et al.
patent: 6226639 (2001-05-01), Lindsay et al.
patent: 6263331 (2001-07-01), Liu et al.
patent: 6415297 (2002-07-01), Leymann et al.
patent: 6484159 (2002-11-01), Mumick et al.
patent: 6493701 (2002-12-01), Ponnekanti
patent: 6542886 (2003-04-01), Chaudhuri et al.
patent: 6618719 (2003-09-01), Andrei
patent: 6625593 (2003-09-01), Leung et al.
patent: 6732107 (2004-05-01), Luo et al.
patent: 6804678 (2004-10-01), Luo et al.
patent: 6865567 (2005-03-01), Oommen et al.
patent: 2002/0194157 (2002-12-01), Zait et al.
T. Urhan et al., “XJoin: Getting Fast Answers from slow and Bursty Networks”, Technical Report, CS-TR-3994, UMIACS-TR-99-13, Feb. 1999.
D. DeWitt et al. “Parallel Sorting on a Shared-Nothing Architecture using Probabilistic Splitting”, Proc. Of the Int. Conf. On Parallel and Distributed Information Systems (PDIS) 1991: 280-291.
Urhan, “XJoin: Getting Fast Answers from slow and Bursty Networks”, Technical Report, CS-TR-3994, UMIACS-TR-99-13, Feb. 1999.
DeWitt, “Parallel Sorting on a Shared-Nothing Architecture using Probabilistic Splitting”, Proc. Of the Intl. Conf. On Parallel and Distributed Information Systems (PDIS) 1991: 280-291.
Urhan et al., “Xjoin: Getting Fast Answers From Slow and Bursty Networks”, Technical Report, CS-TR-3994, UMIACS-TR-99-13, Feb. 1999.
R. Avnur et al., “Eddies: Continuously Adaptive Query Processing”, SIGMOD Conf. 2000: 261-272.
D. Bitton et al., “Benchmarking Database Systems a Systematic Approach”, VLDB 1983: 8-19.
J. Chen et al., “NiagaraCQ: A Scalable Continous Query System for Internet Databases”, SIGMOD Conf. 2000: 379-390.
D. DeWitt et al., “A Performance Analysis of the Gamma Database Machine”, SIGMOD Conf. 1988: 350-360.
D. DeWitt et al., “Client-Server Paradise”, VLDB 1994: 558-569.
D. DeWitt et al., “Parallel Sorting on a Shared-Nothing Architecture Using Probabilistic Splitting”, Proc. Of the Intl. Conf. On Parallel and Distributed Information Systems (PDIS) 1991: 280-291.
D. DeWitt et al., “An Evaluation of Non-Equijoin Algorithms”, VLDB 1991: 443-452.
G. Graefe, “Query Evaluation Techniques for Large Databases”, ACM Comput. Surveys, 25(2):73-170, Jun. 1993.
P. Haas, “Hoeffding Inequalities for Join-Selectivity Estimation and Online Aggregation”, IBM Research Report RJ10040, 1996.
P. Haas, “Large-Sample and Deterministic Confidence Intervals for Online Aggregation”, Proc. Ninth Intl. Conf. Scientific and Statistical Database Mangement, 1997, pp. 51-62.
P. Haas et al., “Join Algorithms for Online Aggregation”, IBM Research Report RJ10126, 1998.
P. Haas, “Hoeffding Inequalities for Online Aggregation”, Proc. Interface '99.
P. Haas, “Techniques for Online Exploration of Large Object-Relational Datasets”, Proc. 11thIntl. Conf. Scientific and Statistical Database Management, 1999: 4-12.
J. Hellerstein et al., “Interactive Data Analysis: The Control Project”, IEEE Computer, 32, Aug. 1999: 51-59.
J. Hellerstein et al., “Informix under CONTROL: Online Query Processing”, Data Mining and Knowledge Discovery, 2000.
J. Hellerstein, “Online Processing Redux”, IEEE Data Engineering Bulletin, Sep. 1997.
J. Hellerstein, “Looking Forward to Interactive Queries”, Database Programming and Design, Aug. 1998.
J. Hellerstein et al., “Adaptive Query Processing: Technology in Evolution”, IEEE Data Engineering Bulletin, Jun. 2000.
P. Haas et al., “Ripple Joins for Online Aggregation”, SIGMOD Conf. 1999: 287-298.
J. Hellerstein et al., “Online Aggregation”, SIGMOD Conf. 1997: 171-182.
C. Hidber, “Online Association Rule Mining”, SIGMOD Conf. 1999: 145-156, May 20, 1998.
Z. Ives et al., “An Adaptive Query Execution System for Data Integration”, SIGMOD Conf. 1999: 299-310.
J. Naughton et al., “The Niagara Internet Query System”, submitted for publication, 2000.
F. Olken, “Random Sampling from Databases”, Ph.D. Dissertation, UC Berkeley, Apr. 1993, available as Tech. Report. LBL-32883, Lawrence Berkeley Laboratories.
H. Pang et al., “Partially Preemptible Hash Joins”, SIGMOD Conf. 1993: 59-68.
H. Pang et al., “Memory-Adaptive External Sorting”, VLDB 1993: 618-629.
J. Patel et al., “Clone Join and Shadow Join: Two Parallel Algorithms for Executing Spatial Join Operations”, Technical Report, University of Wisconsin, CS-TR-99-1403, Aug. 1999.
K. Ramasamy et al., “Set Containment Joins: The Good, The Bad and the Ugly”, VLDB 2000.
V. Raman et al., “Online Dynamic Reordering for Interactive Data Processing”, VLDB 1999.
D. Schneider et al., “A Performance Evaluation of Four Parallel Join Algorithms in a Shared-Nothing Multiprocessor Environment”, SIGMOD Conf., Jul. 10, 1992, 110-121.
S. Seshadri et al., “Sampling Issues in Parallel Database Systems”, Proc. Of the Intl. Conf. on Extending Database Technology (EDBT) 1992; 328-343.
A. Shatdal et al., “Adaptive Parallel Aggregation Algorithms”, SIGMOD Conf. 1995: 104-114.
K. Tan et al., “Online Feedback for Nested Aggregate Queries with Multi-Threading”, VLDB 1999, pp. 18-29.
T. Urhan et al., “XJoin: Getting Fast Answers from Slow and Bursty Networks”, Technical Report, CS-TR-3994, UMIACS-TR-99-13, Feb. 1999.

Affiliated with

Also associated with

Rating

Method and apparatus for performing hash join 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 performing hash join, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for performing hash join will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3635479