Browse Prior Art Database

Memory-Adaptive Sort in Database Systems

IP.com Disclosure Number: IPCOM000118345D
Original Publication Date: 1996-Dec-01
Included in the Prior Art Database: 2005-Apr-01
Document File: 4 page(s) / 165K

Publishing Venue

IBM

Related People

Zhang, W: AUTHOR

Abstract

Sorting is one of the most time consuming and frequently used operations in database systems. It is both memory-intensive and CPU-intensive (and Input/Output (I/O) intensive as well for external sort). When the data to be sorted cannot fit into memory, usually the more memory is allocated to the sort, the less time is required to finish the job.

This text was extracted from an ASCII text file.
This is the abbreviated version, containing approximately 27% of the total text.

Memory-Adaptive Sort in Database Systems

      Sorting is one of the most time consuming and frequently used
operations in database systems.  It is both memory-intensive and
CPU-intensive (and Input/Output (I/O) intensive as well for external
sort).  When the data to be sorted cannot fit into memory, usually
the more memory is allocated to the sort, the less time is required
to finish the job.

      The objective of the memory-adaptive sort of this invention is
to adjust the memory usage (increase or decrease) during sorting
according to data size, changes of available memory space, and memory
requirements of other sorts in the system.  By dynamically changing
memory usage, the memory of a system can be used more efficiently,
and the performance (such as sort speed, system throughput, and
average response time) can be improved.  When the data size is
unknown or is improperly estimated, this new sort can also improve
the system performance even if there is no memory fluctuations.
  1.  The basic algorithm of memory-adaptive sort
      - in-memory sort phase:
         collect data into buffers;
         sort each buffer (using a general in-memory sort
          algorithm)
         < check/adjust memory >;
      - in-memory merge phase:
         if no more input
             merge buffers to produce sorted output;
         if no memory left
             merge buffers and store the sorted data into a
              tmp table;
             if there is more input
                 < check/adjust memory >;
                 go to in-memory sort phase;
      - external merge phase:
         < check/adjust memory >;
         if there are multiple runs in tmp table
             read the runs and merge them to generate
              final results; for multi-pass merge,
              < check/adjust memory > after each merge;
  2.  The mechanism of memory adjustment during sorting
      a.  During in-memory sort, the sort process collects data
           into buffers and sorts each buffer using an in-memory
           sort algorithm.  When there is no free buffer left,
           it asks for more memory from the system.  If the system
           can provide more space, the sort will continue the
           in-memory sort.  The memory usage of the sort increases
           naturally in this way.

              After each buffer is sorted, the sort process checks
        the memory status in the system.  When there is memory
        shortage, the sort can release some of its free buffers (if
        there are) or merge the sorted buffers, write the sorted data
        into a temporary table (as a run), then release part of its
      ...