sgrep (sorted grep)
Sgrep (sorted grep) searches sorted input files for lines that match a search key and outputs the matching lines. When searching large files sgrep is much faster than traditional Unix grep, but with significant restrictions.
- All input files must be sorted regular files.
- The sort key must start at the beginning of the line.
- The search key matches only at the beginning of the line.
- No regular expression support.
Sgrep uses a binary search algorithm, which is very fast, but requires sorted input. Each iteration of the search eliminates half of the remaining input. In other words, doubling the size of the file adds just one iteration.
sgrep [ -i | -n ] [ -c ] [ -b ] [ -r ] [ -- ] key [ sorted_file ... ]
If no input files are specified, then sgrep uses stdin which must be a sorted regular file. You cannot pipe into sgrep.
Sgrep compares bytes using the native hardware byte order, so the file must be sorted accordingly. You should set the environment variable LC_ALL to C before running sort or sgrep. For example,
export LC_ALL=C sort -o sorted unsorted sgrep key sorted
Sgrep offers negligible speed improvement over traditional grep on files smaller than 100 KBytes, is measurably faster on files larger than a few MBytes, and is dramatically faster on files larger than 1 GByte.
Sgrep searches large sorted files very efficiently. But the overhead of sorting a very large file is considerable, so sgrep is most useful in situations where many searches are performed on the same file.
Some files, such as system logs, are naturally output in chronological order. If the date is output at the beginning of the line in a format such as YYYY/MM/DD:hh:mm:ss, then the file is already sorted and suitable for quick search by date using sgrep.
Stephen C. Losen, University of Virginia