A Scan-Driven Sort Facility for a Relational Database System.

Theo Härder: A Scan-Driven Sort Facility for a Relational Database System. VLDB 1977: 236-244
  author    = {Theo H{\"a}rder},
  title     = {A Scan-Driven Sort Facility for a Relational Database System},
  booktitle = {Proceedings of the Third International Conference on Very Large
               Data Bases, October 6-8, 1977, Tokyo, Japan},
  publisher = {IEEE Computer Society},
  year      = {1977},
  pages     = {236-244},
  ee        = {db/conf/vldb/Harder77.html},
  crossref  = {DBLP:conf/vldb/77},
  bibsource = {DBLP,}


In this paper the design and implementation aspects of an integrated sort package are described which was implemented by the author as a part of an experimental relational database system called System R. The sort facility developed for variable length sort keys and tuples is discussed with regard to its anticipated use in relational database systems. It is considered to be a powerful tool to implement complex relational operations like join and projection and to support the dynamic creation of access paths and the loading and reorganizing of data clustered by field values. The input loop of the sort can be driven by various scans which allow the filtering of qualified tuples according to disjunctive normal forms of simple search arguments. Various aspects of the integration with storage and transaction management, locking and logging components are described. A number of design decisions for the sort facility concerning sorting, peerage, and merging techniques are discussed. Finally, some implementation aspects for sorting variable length keys consisting of a number of distributed fields are pointed out.

Copyright © 1977 by The Institute of Electrical and Electronic Engineers, Inc. (IEEE). Abstract used with permission.

ACM SIGMOD Anthology

CDROM Version: Load the CDROM "Volume 1 Issue 4, VLDB '75-'88" and ... DVD Version: Load ACM SIGMOD Anthology DVD 1" and ... BibTeX

Printed Edition

Proceedings of the Third International Conference on Very Large Data Bases, October 6-8, 1977, Tokyo, Japan. IEEE Computer Society 1977
Contents BibTeX


Morton M. Astrahan, Mike W. Blasgen, Donald D. Chamberlin, Kapali P. Eswaran, Jim Gray, Patricia P. Griffiths, W. Frank King III, Raymond A. Lorie, Paul R. McJones, James W. Mehl, Gianfranco R. Putzolu, Irving L. Traiger, Bradford W. Wade, Vera Watson: System R: Relational Approach to Database Management. ACM Trans. Database Syst. 1(2): 97-137(1976) BibTeX
Rudolf Bayer, Edward M. McCreight: Organization and Maintenance of Large Ordered Indices. Acta Inf. 1: 173-189(1972) BibTeX
Mike W. Blasgen, Richard G. Casey, Kapali P. Eswaran: An Encoding Method for Multifield Sorting and Indexing. Commun. ACM 20(11): 874-878(1977) BibTeX
Laurent Hyafil, F. Prusker, Jean Vuillemin: Design of Optimal Merge on Direct Access Devices. IFIP Congress 1974: 979-982 BibTeX
Donald E. Knuth: The Art of Computer Programming, Volume I: Fundamental Algorithms, 2nd Edition. Addison-Wesley 1973
John Miles Smith, Philip Yen-Tang Chang: Optimizing the Performance of a Relational Algebra Database Interface. Commun. ACM 18(10): 568-579(1975) BibTeX
ACM SIGMOD Anthology - DBLP: [Home | Search: Author, Title | Conferences | Journals]
VLDB Proceedings (1977-1981): Copyright © by IEEE,
ACM SIGMOD Anthology: Copyright © by ACM (, Corrections:
DBLP: Copyright © by Michael Ley (, last change: Sat May 16 23:44:57 2009