Boots – shoes – and leggings
Patent
1992-10-27
1998-12-01
Black, Thomas G.
Boots, shoes, and leggings
395800, 39520015, 3642299, 3642283, 364DIG1, G06F 1730, G06F 700, G06F 1516
Patent
active
058451137
ABSTRACT:
A system and method is provided for distributed relational databases for parallel sorting of a relation wherein the relation is a set of tuples to be sorted on multiple sort sites which completely decouples the return phase from the sort phase in order to eliminate the merge phase. The method involves selecting one coordinator site from any of the available logical sites, then generating and sorting a local sample on each of the available storage sites before sending the local random sample from each storage site to the designated coordinator site wherein the local random samples are merged to provide a single global sample. The coordinator site determines the global interval key values based on the global sample. The interval key values being determined such that each interval fits in a single sort site's main memory, wherein the tuples between two interval key values define the interval. The interval key values are sent to the various storage sites wherein each storage site scans its portion of the relation in order to determine for each tuple the assigned interval and its corresponding sort site before sending each tuple to the assigned sort site. At each sort site the tuples are stored in temporary files using a single temporary file for each interval whereafter repeating, for each interval on each sort site, the steps of reading an interval and performing an in-memory sort in any fashion of the interval read before sending the tuples of the sorted interval to the sink site.
REFERENCES:
patent: 4210961 (1980-07-01), Whitlow et al.
patent: 4520456 (1985-05-01), Miranker et al.
patent: 4559612 (1985-12-01), Vrielink
patent: 4567572 (1986-01-01), Morris et al.
patent: 4575798 (1986-03-01), Lindstrom et al.
patent: 4595995 (1986-06-01), Alles
patent: 4766534 (1988-08-01), DeBenedictis
patent: 4799152 (1989-01-01), Chuang et al.
patent: 4809214 (1989-02-01), Shimakura
patent: 5086408 (1992-02-01), Sakata
patent: 5146590 (1992-09-01), Lorie et al.
patent: 5179699 (1993-01-01), Iyer et al.
Iyer et al, "System Issues in Parallel Sorting for Database Systems" 1990 6th Int'l Conf. Data Engineering, IEEE, pp. 246-255, 1990.
A. C. McKellar, Sort Process, Defense Publication T913,007, Published Aug. 14, 1973.
B. T. Bennett et al., Sort Process, Defense Publication T921,028, Apr. 23, 1974.
W. M. Conner II, Sorting Method, Defense Publication T920,010, Published Mar. 5, 1974.
R. A. Lorie and H. C. Young, A Low Communication Sort Algorithm for a Parallel Database Machine, Proceedings of the Fifteenth International Conf. on Very Large Data Bases, Amsterdam, Aug. 22-25, 1989, pp. 125-134.
D. J. DeWitt, J. F. Naughton, and D. A. Schneider, Parallel Sorting on a Shared-Nothing-Architectures Using Probabilistic Splitting, 1st International Conf. on Parallel & Dist. Infor. Sys., Dec. 4-6, 1992, Florida, pp. 280-291.
J. L. Wolf, D. M. Dias and P. S. Yu, Using a Surrogate Median to Speed the Execution of a Parallel Sort Merge Join Algorithm, IBM-Tech. Disclosure Bulletin, vol. 33, No. 9, pp. 215-217, Feb. 1991.
D. M. Dias, B. R. Iyer, J. L. Wolf and P. S. Yu, Methods for Improving the Efficiency of Parallel Sort Merge Joins in the Presence of Data Skew, IBM-Technical Disclosure Bulletin, vol. 33, No. 10A, pp. 166-170, Mar. 1991.
C. C. Douglas and W. L. Miranker, Aggregation Sorting, IBM Technical Disclosure Bulletin, vol. 32, No. 12, pp. 230-237, May 1990.
Salzberg et al., FastSort: A Distributed Single-Input Single-Output External Sort, Proceedings of the 16th International Conference on VLDB, pp. 94-101, Aug. 1990. (SIGMOD Record, vol. 19, Issue 2, Jun. 1990).
Beck et al., Sorting Large Files on a Backend Multiprocessor, IEEE Transactions on Computers, 37(7):769-778, Jul. 1990.
Swami Arun N.
Young Honesty C.
Black Thomas G.
Blair Philip E.
Choules Jack M.
International Business Machines - Corporation
Pintner James C.
LandOfFree
Method for external sorting in shared-nothing parallel architect 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 for external sorting in shared-nothing parallel architect, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method for external sorting in shared-nothing parallel architect will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2402351