Patent
1996-04-16
1998-09-01
Black, Thomas G.
395607, G06F 1730, G06F 722
Patent
active
058023577
ABSTRACT:
A technique for efficiently joining multiple large tables in a database system with a processor using a small main memory. The technique utilizes a join index and minimizes the number of Input/Output operations while maximizing the use of the small main memory through a buffer allocation process. Three embodiments of the technique are described all of which use the parallel-merge operation. The first technique, slam-join, is for joining two tables and does not require any pre-allocation of buffers to perform the join operation. The second technique, multi-slam-join, is for joining three or more tables and adds the parallel-merge technique to a join technique which partitions memory to be used for an efficient join operation. The third technique, called parallel-join, processes each input table completely independently using the parallel-merge technique. The parallel-merge technique identifies the lowest value from multiple files and orders all the values from lowest to highest. This enables sequential reading of input files saving I/O operations.
REFERENCES:
patent: 5121494 (1992-06-01), Dias et al.
patent: 5241648 (1993-08-01), Cheng et al.
patent: 5345585 (1994-09-01), Iyer et al.
patent: 5408654 (1995-04-01), Barry
patent: 5557791 (1996-09-01), Cheng et al.
Kitsuregawa, M., Harada, L., Takagi, M., "Join Stratagies on KD-tree indexed relations", Proceedings Fifth International Conference on Data Engineering, pp. 85-93, Feb. 1989.
Shapiro, "Join Processing in Database Systems with Large Main Memories", ACM Transactions on Database Systems, vol. 11, No. 3, Sep. 1986, pp. 239-264.
Valduriez, "Join Indices", ACM Transactions on Database Systems, vol. 12, No. 2, Jun. 1987, pp. 218-246.
Desai, "Performance of a Composite Attribute and Join Index", IEEE Transactions on Software Engineering, vol. 14, No. 2, Feb. 1989, pp. 142-152.
Blakeley et al., "Join Index, Materialized View, and Hybrid-Hash Join: a Performance Anaylsis", Sixth International Conference on Data Engineering, 1990 pp. 256-263.
Mishra et al., "Join Processing in Relational Databases", ACM Computing Surveys, vol. 24, No. 1, Mar. 1992, pp. 63-113.
Perrizo et al., "Distributed Join Processing Performance Evaluation", Proceedings of the Twenty-Seventh Annual Hawaii International Conference on System Sciences, 1994, pp. 236-245.
D. Knuth, The Art of Computer Programming, vol. 3, "Sorting and Searching"; 1973, pp. 247-250.
Li Zhe
Ross Kenneth A.
Black Thomas G.
Choules Jack M.
The Trustees of Columbia University in the City of New York
LandOfFree
System and method for performing an efficient join operation does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with System and method for performing an efficient join operation, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and System and method for performing an efficient join operation will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-281789