# 0008: Group sorted input by hash, and sort again when unsure

Status: accepted.

GNU datamash sorts every record for `-s`, with a stable `sort -s`, so each of
its groups is exactly the records with one key, in input order. Typical inputs
have far fewer groups than records. When standard input is a regular file,
Fastmash therefore collects each key's records into that group's own
operation state as they arrive and sorts only the keys, reusing the sort's key
order and the group writer, so the output is the sort's. In a language
locale, it does the same for piped input, holding what it reads in memory so
that the input can be read again: the language-locale sort keeps whole
records, so the held input takes about as much memory as the sort would.

Where that could give a different result, Fastmash does not try to reproduce
the sort's behaviour: before writing anything, it reads the input again from
its start and sorts it, in process or through the system sort, as the job
would have been sorted without hash grouping. That happens on a missing or
NUL key, a key the collation refuses, any operation error (so error messages
and line numbers are exactly the sort's), too few records per group, or too
little memory. With `-W`, GNU's sort keys keep the blanks before each field,
which groups ignore, so a group is keyed by its fields with those blanks, and
two keys that differ only in them may be one group or two: Fastmash gives up
there, and on a newline in a `-z` record, which the sort takes for a blank.
In a language locale, glibc ties some keys spelled differently at every
level (`й`, and `и` with a combining breve), which the stable sort keeps in
input order, a group per run of each spelling: Fastmash gives up when a new
key ties so with one already collected.
`--vnlog` and `rand`, whose results depend on more than each group's own
records, always sort.

**Considered:** turning the collected groups into pre-aggregated sort records
when hashing stops paying, which reads the input once and also covers pipes,
but needs a serialized form of every operation's state and must reproduce the
sort's first error from stored state; its surface for mistakes is much
larger. Holding piped input in every locale: in the `C` locales the held
input takes several times the memory of a sort that keeps only the selected
fields, and some jobs are slower (`FASTMASH_PIPE_GROUPING=hash` still does
it). Writing held input beyond a budget to a temporary file: no gain where
the temporary directory is in memory.

**Consequences:** sorted jobs on files are usually several times faster and
use memory for the groups only, and piped jobs in a language locale three to
four times faster with the sort's memory; piped input in the `C` locales
keeps the sort, so `< file` and `cat file |` can differ in time and memory,
not in output. A piped job that gives up late takes about a third longer
than the sort alone. A job that restarts
reads its input twice, and its output is that of the second reading, so a file
that changes while it is read gives the result of reading it later than a
program that reads once would. `FASTMASH_GROUPING=sort` always sorts.