VX/SOR – OpenVMS SORT MERGE

The sort engine

The engine is a classic external merge sort. Records are accumulated into an in-memory logical block; each full block is sorted and written to a SORTWORK swap file; the swap files are then combined with a fast buffered k-way heap merge (a legacy N-way merge remains as a fallback). This is the same shape as the OpenVMS Sort/Merge engine, so result ordering, duplicate handling and stability all match.

Because both the DCL verbs and direct SOR$ callers reach the same library, a migrated estate can keep its DCL sort scripts and its compiled programs that call the sort API, with no rewrite of either.

Routine table

Name forms and aliasing

Every routine is exposed under several names, so callers from any supported language link against it:

SOR_D_xxx is the canonical internal C++ symbol. SOR$xxx and sor$xxx are the VMS-style upper and lower-case aliases. F4_SOR_D_xxx is a FORTRAN thunk that unpacks trailing string-length arguments, provided for the descriptor-taking routines (PASS_FILES, RELEASE_REC, RETURN_REC and SPEC_FILE).

Record-interface example

The RECORD interface releases records one at a time and pulls sorted records back until end-of-file. This example sorts on a 10-byte text key at 1-based position 1, the account number in a banking record:

#include "sor$routines.h"
#include "ssdef.h"

U32   ctx = 0;                 /* 0 => allocate a context slot        */
U16   lrl = 80;                /* longest record                      */
U32   opt = SOR$M_STABLE;      /* stable sort                         */
U16   keybuf[1 + 4] = {
    1,                         /* one key descriptor                  */
    DSC$K_DTYPE_T,             /* key_type   = text                   */
    0,                         /* key_order  = ascending              */
    1,                         /* key_offset = 1-based (INIT_SORT)    */
    10                         /* key_length = 10-byte account number */
};

/* 1. initialise (INIT_SORT: offsets are 1-based) */
U32 st = SOR$INIT_SORT(keybuf, &lrl, &opt, 0, 0, 0, 0, 0, &ctx);
if (!(st & 1)) return st;

/* 2. release records (RECORD process only) */
struct dsc$descriptor rec_d;
/* ... fill rec_d for each ACCOUNTS record ... */
st = SOR$RELEASE_REC(&rec_d, &ctx);       /* repeat per input record */

/* 3. run the sort/merge */
st = SOR$SORT_MERGE(&ctx);
if (!(st & 1)) { SOR$END_SORT(&ctx); return st; }

/* 4. pull sorted records back until end-of-file */
char  out[80];
U16   olen;
struct dsc$descriptor out_d;   /* points at out[] */
while ((st = SOR$RETURN_REC(&out_d, &olen, &ctx)) == SS$_NORMAL) {
    /* ... consume out[0..olen) ... */
}
/* st == SS$_ENDOFFILE here */

/* 5. always tear down */
SOR$END_SORT(&ctx);

The file-driven alternative is what the DCL verbs use: call SOR$PASS_FILES once per input file, then SOR$BEGIN_SORT, then SOR$SORT_MERGE (which reads the inputs and writes the output file directly), then SOR$END_SORT, with no release or return loop.

Pluggable sort engine

Each entry point first checks for a replacement engine. On the first call it loads a customer-supplied shared library named by the SORLIB logical or environment variable and looks up the matching lower-case sor$xxx symbol. If it is present, the call is forwarded to that engine and the in-tree engine is bypassed, so a site can drop in an alternative sort implementation without relinking the runtime.

Key buffer

Keys are described by a compact unsigned 16-bit array. The first element is the number of key descriptors; each descriptor is then four elements: data type, order, offset and length.

key_buffer[0]           = N, the number of key descriptors
key_buffer[1 + 4*i + 0] = key_type    (a DSC$K_DTYPE_* code)
key_buffer[1 + 4*i + 1] = key_order   (0 = ascending, 1 = descending)
key_buffer[1 + 4*i + 2] = key_offset  (0-based for BEGIN_SORT, 1-based for INIT_SORT)
key_buffer[1 + 4*i + 3] = key_length

SOR$INIT_SORT treats offsets as 1-based and decrements each one before forwarding to BEGIN_SORT, so an offset of 0 there is a fatal bad-key error. If no key is supplied at all, BEGIN_SORT synthesises a single ascending text key spanning the whole record. A context can hold up to 50 keys.

Per-record header

Inside the work buffer each record is prefixed with a packed header. The sequence number is what makes STABLE sorts stable: records that compare equal on all keys break the tie on insertion order.

typedef struct {
  U32   recnum;                 // duplicate flag = recnum |= 0x80000000
  U32   seqnum;                 // preserves insertion order for STABLE
  U16   ctx_num;
  U16   reclen;
  off_t offset_into_swap_file;
  char  data[0];
} sort_header_t;

Context limits

A context is referenced by a 32-bit handle. Passing a context value of 0 on the first call allocates a free slot from the 64 available.

Options and process types

The options bitmask controls sort behaviour. Only three bits are legal; any other bit is rejected. The default when no options are supplied is STABLE.

Setting STABLE and NODUPS together is rejected as an exclusive-option error. The process type can be RECORD (the default), TAG, INDEX or ADDRESS: all four are accepted by BEGIN_SORT, but SOR$RELEASE_REC handles RECORD only, so TAG, INDEX and ADDRESS are reached through the file interface (SOR$PASS_FILES).

Statistics

SOR$STAT returns one statistic selected by a code. The counters below are wired; the remaining OpenVMS codes (nodes, initial runs, merge order, work allocation, merge buffer count) return zero with a success status, so a missing statistic is a zero rather than an error.

Command syntax

$ SORT/KEY=(POSITION:1,SIZE:10) [/DESCENDING] [/STABLE] [/NODUPLICATES]
       [/STATISTICS] [/SPECIFICATION=RULES.SPC] ACCOUNTS.DAT SORTED_ACCOUNTS.DAT

$ MERGE/KEY=(POSITION:1,SIZE:10) BRANCH_EAST.DAT,BRANCH_WEST.DAT ACCOUNTS.DAT

Key sub-keywords

The /KEY clause is where most of the sort is defined. The keywords below change the key descriptor and behave exactly as on OpenVMS:

For source compatibility, VX/SOR also parses and consumes a further set of /KEY sub-keywords that have no effect on the sort, so existing command lines carry across without edits. These accepted-for-compatibility keywords are:

Command-level qualifiers

Specification files

A specification file lets you drive the sort declaratively instead of on the command line. /SPECIFICATION reads FIELD, CONDITION and INCLUDE/OMIT directives (handled by SOR$SPEC_FILE), so you can define fields and record-selection conditions in one place and reuse them across jobs.

Statistics output

The /STATISTICS qualifier prints a banner after the run:

        VX/SOR Sort and Merge Utility v<Version_Id>

Records read:         <n>
Records sorted:       <n>
Records output:       <n>
Elapsed time (Secs)   <n>
Elapsed CPU  (Secs)   <f>

Behaviour notes for a migrating team

• Register a user compare routine through SYR$DTYPE or the lower-case sor$dtype until the upper-case SOR$DTYPE alias is corrected.
• TAG, INDEX and ADDRESS sorts are driven through SOR$PASS_FILES, not through the release/return record loop.
• The NOSIGNAL option and the disk-allocation arguments are accepted but have no observable effect, because the engine reports every condition as a returned status value.
• /PROCESS and /FORMAT at the DCL layer parse cleanly and are ignored, so existing command lines run without edits.

Call lifecycle

DCL syntax

$ SORT/KEY=(POSITION:1,SIZE:10) [/DESCENDING] [/STABLE]
       [/NODUPLICATES] [/STATISTICS] [/SPECIFICATION=RULES.SPC] in.dat out.dat
$ MERGE/KEY=(POSITION:1,SIZE:10) in1.dat,in2.dat out.dat

Callable routines

Key buffer

[N, {type, order, offset, length} x N]
INIT_SORT offsets 1-based; BEGIN_SORT offsets 0-based.

Tuning environment

Limits